夏寒松，張力生，桑春艷

（重慶郵電大學(xué)軟件工程學(xué)院，重慶 400065）

0 概述

時(shí)間序列是指按照采集時(shí)間先后順序排列的觀測(cè)數(shù)據(jù)，廣泛存在于金融［1-2］、道路交通［3］、社交網(wǎng)絡(luò)［4-5］、工業(yè)電網(wǎng)［6］等領(lǐng)域。隨著信息技術(shù)的發(fā)展，時(shí)間序列數(shù)據(jù)量與日俱增，利用相應(yīng)數(shù)據(jù)挖掘技術(shù)從海量時(shí)間序列中發(fā)現(xiàn)潛在知識(shí)和規(guī)律已成為當(dāng)前數(shù)據(jù)挖掘的研究熱點(diǎn)。時(shí)間序列相似性度量是衡量?jī)蓷l時(shí)間序列相似程度的度量方法，是時(shí)間序列聚類和分類分析中不可缺少的步驟［7］，度量方法性能直接影響時(shí)間序列數(shù)據(jù)挖掘的效果［8］。

BERNDT 等［9］于1994 年提出的動(dòng)態(tài)時(shí) 間規(guī)整（Dynamic Time Warping，DTW）是時(shí)間序列相似性度量中的常用方法。與傳統(tǒng)相似性度量（如歐氏距離）相比，DTW 對(duì)時(shí)間序列的相位偏移、振幅變化等情況具有更強(qiáng)的魯棒性。然而，DTW 算法存在“病態(tài)對(duì)齊”的缺陷，即在并不相似的特征之間進(jìn)行對(duì)齊，使一條時(shí)間序列上的點(diǎn)匹配另一條時(shí)間序列上一大塊區(qū)域的點(diǎn)［10］。在這種不合理匹配的情況下，可能出現(xiàn)同類時(shí)間序列之間的距離值大于不同類時(shí)間序列之間的距離值，進(jìn)而影響最終的度量效果。

為了抑制病態(tài)對(duì)齊現(xiàn)象，提高時(shí)間序列之間的相似性度量效果，ZHANG 等［11］提出限制對(duì)齊路徑長(zhǎng)度的動(dòng)態(tài)時(shí)間規(guī)整（LDTW）算法從時(shí)間序列之間的對(duì)齊路徑長(zhǎng)度開始，通過(guò)給定對(duì)齊路徑長(zhǎng)度上限LUB來(lái)限制時(shí)間序列之間的對(duì)齊路徑長(zhǎng)度。相比其他改進(jìn)算法（如權(quán)重DTW［12-13］、窗口限制Sakoe-Chiba band［14］、Itakura parallelogram［15］、learned window［16］、改進(jìn)進(jìn)步模式step pattern［15，17］等）從局部限制每個(gè)數(shù)據(jù)點(diǎn)所能匹配對(duì)應(yīng)數(shù)據(jù)點(diǎn)的數(shù)量，LDTW 算法在全局上限制對(duì)齊路徑總體長(zhǎng)度，保留局部對(duì)齊的靈活性，抑制“病態(tài)對(duì)齊”現(xiàn)象，在UCR 公共數(shù)據(jù)集上的分類效果有更明顯提升。但LDTW 算法將原DTW算法中的二維累計(jì)代價(jià)矩陣擴(kuò)張為三維矩陣，增大了時(shí)間復(fù)雜度，在多數(shù)數(shù)據(jù)集上進(jìn)行分類實(shí)驗(yàn)的時(shí)間開銷遠(yuǎn)大于原DTW 算法以及相關(guān)衍生算法。

本文對(duì)LDTW 算法進(jìn)行改進(jìn)，提出固定對(duì)齊路徑長(zhǎng)度的動(dòng)態(tài)時(shí)間規(guī)整（FDTW）算法。通過(guò)分析LDTW 算法所需要計(jì)算的累計(jì)代價(jià)矩陣元素?cái)?shù)量、時(shí)間序列長(zhǎng)度和對(duì)齊路徑長(zhǎng)度上限之間的關(guān)系，調(diào)整LDTW 算法中控制對(duì)齊路徑長(zhǎng)度的策略，使得對(duì)齊路徑長(zhǎng)度由限制在某個(gè)范圍內(nèi)改為固定到某個(gè)數(shù)值上，從而降低累計(jì)代價(jià)矩陣元素的計(jì)算量，提高計(jì)算效率。

1 相關(guān)工作

1.1 DTW 算法

DTW 為了適應(yīng)時(shí)間序列間的相位偏移和振幅變化，將時(shí)間序列數(shù)據(jù)點(diǎn)之間對(duì)齊方式由歐氏距離的“一對(duì)一”改為“一對(duì)多”。設(shè)X=｛x1，x2，…，xR｝和Y=｛y1，y2，…，yC｝是兩條長(zhǎng)度分別為R和C的時(shí)間序列。對(duì)齊路徑π用于描述X和Y之間數(shù)據(jù)點(diǎn)的對(duì)齊關(guān)系，它被定義為包含K個(gè)二元組集合，每個(gè)二元組包含兩個(gè)分別來(lái)自時(shí)間序列X和Y的數(shù)據(jù)點(diǎn)下標(biāo)。π的表示如式（1）所示：

在以上條件約束下，X和Y之間所有對(duì)齊路徑的集合記為AXY。DTW 目標(biāo)是最小化兩條時(shí)序數(shù)據(jù)中所有對(duì)應(yīng)數(shù)據(jù)點(diǎn)的局部距離值之和，并以之作為全局距離值，其定義如式（2）所示：

其中：d(xi,yj)=|xi-yj|2。

DTW 算法采用動(dòng)態(tài)規(guī)劃思想利用遞歸公式將以上問(wèn)題轉(zhuǎn)換為對(duì)X和Y子序列問(wèn)題的求解，如式（3）所示：

由于子序列問(wèn)題相互交疊，直接采用遞歸方式會(huì)產(chǎn)生大量的重復(fù)計(jì)算，因此DTW 算法通過(guò)建立一個(gè)R×C累計(jì)代價(jià)矩陣M來(lái)存放子問(wèn)題的解以避免重復(fù)計(jì)算。因此，需計(jì)算R×C個(gè)矩陣元素，DTW 算法的時(shí)間復(fù)雜度為O(R×C)。

DTW 算法為了使序列間的距離值最小，計(jì)算過(guò)程中可能出現(xiàn)“病態(tài)對(duì)齊”現(xiàn)象［18］?！安B(tài)對(duì)齊”示意圖如圖1 所示。時(shí)間序列A 與時(shí)間序列B 為不同類別，而與時(shí)間序列C 為同一類別，但DTW 算法通過(guò)大規(guī)模的“一對(duì)多”對(duì)齊，在序列A 和序列B 并不具有相似性的局部數(shù)據(jù)點(diǎn)之間進(jìn)行匹配，最終使得AB之間距離值大于AC 之間的距離值，違背了同類序列之間度量值應(yīng)更小的事實(shí)。圖1（a）的彎曲路徑長(zhǎng)度為54，圖1（b）的彎曲路徑長(zhǎng)度為51。“病態(tài)對(duì)齊”缺陷限制了DTW 算法的度量效果。

圖1 病態(tài)對(duì)齊現(xiàn)象示意圖Fig.1 Schematic diagram of pathological alignment phenomenon

1.2 LDTW 算法

DTW 算法在出現(xiàn)“病態(tài)對(duì)齊”現(xiàn)象的同時(shí)，對(duì)齊路徑的長(zhǎng)度K也會(huì)增大。因此，LDTW 算法通過(guò)對(duì)對(duì)齊路徑總長(zhǎng)度K進(jìn)行限制來(lái)抑制“病態(tài)對(duì)齊”現(xiàn)象。

給定時(shí)間序列X和Y，令minS、maxS分別表示X和Y之間允許的最小對(duì)齊路徑長(zhǎng)度和最大對(duì)齊路徑長(zhǎng)度，即minS=max(R,C)，maxS=R+C-1。X和Y之間允許長(zhǎng)度相同的對(duì)齊路徑并不唯一，令A(yù)XYl為所有長(zhǎng)度l的對(duì)齊路徑集合；LUB為給定的對(duì)齊路徑長(zhǎng)度上限，則時(shí)間序列X和Y之間的LD距離值如式（4）所示：

LDTW 算法采用動(dòng)態(tài)規(guī)劃方法將問(wèn)題轉(zhuǎn)換為求解X和Y的子序列問(wèn)題，并建立R×C×LUB的三維累計(jì)代價(jià)矩陣M，依次計(jì)算矩陣元素如式（5）所示：

其中：M［r］［c］［l］值為子序列和子序列之間對(duì)齊路徑長(zhǎng)度l的最小距離值。由于不同長(zhǎng)度的子序列之間可能產(chǎn)生的對(duì)齊路徑長(zhǎng)度范圍不同，加上LUB限制，并非所有矩陣M的元素都需要計(jì)算，因此LDTW 算法按第三維優(yōu)先順序計(jì)算矩陣M，且在計(jì)算前先確定所有子序列間對(duì)齊路徑長(zhǎng)度的范圍來(lái)避免不必要計(jì)算。

所有需要計(jì)算的矩陣元素計(jì)算完成后，元素M［R］［C］［minS］為minS長(zhǎng)度的對(duì)齊路徑對(duì)應(yīng)的最小距離值；M［R］［C］［minS+1］為minS+1 長(zhǎng)度的對(duì)齊路徑對(duì)應(yīng)的最小距離值；M［R］［C］［LUB］為L(zhǎng)UB長(zhǎng)度的對(duì)齊路徑所對(duì)應(yīng)的最小距離值。LDTW 算法從候選元素中選取最小值作為最終的度量值。該距離值所對(duì)應(yīng)的對(duì)齊路徑長(zhǎng)度一定小于LUB，達(dá)到了從總體上控制長(zhǎng)度以減少“病態(tài)對(duì)齊”現(xiàn)象的目的。

LDTW 算法引入對(duì)齊路徑長(zhǎng)度概念，將累計(jì)代價(jià)矩陣由原DTW 算法的二維擴(kuò)展到三維，算法的時(shí)間復(fù)雜度也由原DTW 算法的O（R×C）增長(zhǎng)為O（LUB×R×C），使得分 類過(guò)程的時(shí)間開銷大于原DTW 及其衍生算法。

2 FDTW 算法

2.1 算法原理

在LDTW 算法中，當(dāng)時(shí)間序列長(zhǎng)度R為5，LUB為9 時(shí)計(jì)算的矩陣元素如圖2 所示。從圖2 可以看出，矩陣的第一、第二維度分別表示時(shí)間序列數(shù)據(jù)點(diǎn)下標(biāo)，第三維度為對(duì)齊路徑長(zhǎng)度。根據(jù)式（5）可知，當(dāng)前層元素值計(jì)算只與前一層中左方、上方和左上方的相鄰元素值有關(guān)，與正下方的元素值無(wú)關(guān)，即矩陣元素M[r][c][l]的計(jì)算與M[r][c][l-1]無(wú)關(guān)。矩陣元素M[x5][y5][9]的計(jì)算無(wú)需元素M[x5][y5][8]參與，而M[x5][y5][8]的計(jì)算無(wú)需M[x5][y5][7]參與。若只計(jì)算長(zhǎng)度等于LUB對(duì)齊路徑對(duì)應(yīng)的最佳距離值，相比計(jì)算出所有對(duì)齊路徑長(zhǎng)度小于LUB的最佳距離值所需要計(jì)算的累計(jì)代價(jià)矩陣元素?cái)?shù)量更少，且仍保留通過(guò)限制長(zhǎng)度以抑制“病態(tài)對(duì)齊”的原理。由于對(duì)齊路徑長(zhǎng)度被限定為閾值LUB，將這種方法稱為固定對(duì)齊路徑長(zhǎng)度的DTW 算法。

圖2 LDTW 算法的三維累計(jì)代價(jià)矩陣元素Fig.2 The three-dimensional cumulative cost matrix elements of LDTW algorithm

2.2 算法描述

FDTW 算法的目標(biāo)是從所有長(zhǎng)度為給定值的對(duì)齊路徑中找出使得對(duì)應(yīng)距離值最小的對(duì)齊路徑，并將該最小值作為距離值。令X和Y表示待度量的兩條時(shí)間序列，F(xiàn)L表示給定的對(duì)齊路徑長(zhǎng)度，則X和Y之間的FD距離值如式（6）所示：

其中：表示序列X和Y之間所有長(zhǎng)度為FL的對(duì)齊路徑的集合。

利用遞歸公式將式（6）轉(zhuǎn)化為對(duì)子序列間距離值的求解，如式（7）所示：

為避免對(duì)相同子問(wèn)題進(jìn)行重復(fù)求解，F(xiàn)DTW 算法建立三維累計(jì)代價(jià)矩陣M，采用動(dòng)態(tài)規(guī)劃方式從最小子序列開始依次對(duì)所有子序列間被允許的對(duì)齊路徑長(zhǎng)度下的距離值進(jìn)行計(jì)算。使被計(jì)算的子序列在距離數(shù)量最小化的前提下求解出最終序列間距離，計(jì)算過(guò)程應(yīng)當(dāng)滿足以下條件：1）計(jì)算某對(duì)子序列間的距離值時(shí)，其依賴的子序列距離值已經(jīng)被計(jì)算；2）當(dāng)前被計(jì)算的子序列間距離值一定會(huì)被后續(xù)的計(jì)算所依賴。

當(dāng)序列長(zhǎng)度為5 時(shí)，不同條件下計(jì)算的子問(wèn)題如圖3 所示。當(dāng)時(shí)間序列X、Y長(zhǎng)度為5 時(shí)，所有子序列問(wèn)題如圖3（a）所示（矩陣行列坐標(biāo)和矩陣元素值分別對(duì)應(yīng)兩條子序列下標(biāo)以及對(duì)齊路徑長(zhǎng)度）。為滿足計(jì)算過(guò)程的條件1，將圖3（a）中所有子序列問(wèn)題全部求解，但在LDTW 算法中（LUB取為7），由于不需要求取序列X、Y之間對(duì)齊路徑長(zhǎng)度為8、9 對(duì)應(yīng)的距離值。為滿足計(jì)算過(guò)程條件2，將求解的其余子問(wèn)題相應(yīng)縮減為圖3（b）的范圍。在FDTW 算法中（FL為7），只需取序列X、Y之間對(duì)齊路徑長(zhǎng)度為7 對(duì)應(yīng)的距離值，將求解的其余子問(wèn)題進(jìn)一步縮減為圖3（c）的范圍。范圍縮減后某些子序列間不需要計(jì)算任何對(duì)齊路徑長(zhǎng)度下的距離值，其子序列在圖3 中用陰影表示。

圖3 不同條件下計(jì)算的子問(wèn)題Fig.3 Sub-problems calculated under different conditions

為了使計(jì)算過(guò)程滿足以上條件，F(xiàn)DTW 算法首先根據(jù)參數(shù)FL對(duì)所有子序列之間的對(duì)齊路徑長(zhǎng)度范圍進(jìn)行計(jì)算；其次在范圍內(nèi)計(jì)算各子序列距離值。因此，F(xiàn)DTW 算法步驟分為子序列間對(duì)齊路徑長(zhǎng)度范圍計(jì)算和各子序列距離值計(jì)算。

2.2.1 子序列間對(duì)齊路徑長(zhǎng)度范圍計(jì)算

長(zhǎng)度分別為R和C的序列X和Y之間允許產(chǎn)生最小和最大對(duì)齊路徑長(zhǎng)度，其計(jì)算結(jié)果為：minS=max（R，C）、maxS=R+C?1。為方便描述，將minS和maxS組成的對(duì)齊路徑長(zhǎng)度范圍［minS，maxS］稱為原始對(duì)齊路徑長(zhǎng)度范圍。子序列之間調(diào)整后的對(duì)齊路徑長(zhǎng)度范圍如圖4 所示，時(shí)間序列長(zhǎng)度R=C=7，設(shè)FL為11，陰影元素[x6,y4]代表當(dāng)前要計(jì)算子序列之間路徑長(zhǎng)度范圍。從圖4 可以看出，實(shí)線表示之間長(zhǎng)度最大的一條對(duì)齊路徑，其長(zhǎng)度maxS=6+4-1=9；長(zhǎng)虛線表示之間長(zhǎng)度最小的一條對(duì)齊路徑，長(zhǎng)度minS=max（6，4）=6，因此子序列之間的原始長(zhǎng)度范圍為[6,9]。若子序列之間對(duì)齊路徑長(zhǎng)度為6，那么對(duì)齊路徑總長(zhǎng)度為FL，其互補(bǔ)子序列之間對(duì)齊路徑長(zhǎng)度為FL+1-6=6（加1 是對(duì)齊路徑元素(π1(k),π2(k))被計(jì)算了兩次）。子序列之間產(chǎn)生的對(duì)齊路徑長(zhǎng)度小于6；同樣，若對(duì)齊路徑在子序列之間長(zhǎng)度為9，那么子序列之間對(duì)齊路徑長(zhǎng)度為FL+1-9=3，但子序列之間的對(duì)齊路徑長(zhǎng)度總是大于3。

圖4 子序列和之間調(diào)整后的對(duì)齊路徑長(zhǎng)度范圍Fig.4 Alignement path length range betweenand sub-sequence

因此，根據(jù)參數(shù)FL和互補(bǔ)子序列之間的原始對(duì)齊路徑長(zhǎng)度，對(duì)子序列間原始的齊路徑長(zhǎng)度范圍的上限和下限進(jìn)行進(jìn)一步調(diào)整。

1）調(diào)整范圍上限

算法1計(jì)算子序列間對(duì)最大對(duì)齊路徑長(zhǎng)度

算法2計(jì)算子序列間對(duì)最小齊路徑長(zhǎng)度

2.2.2 子序列之間距離值計(jì)算

確定子序列間對(duì)齊路徑長(zhǎng)度范圍后，F(xiàn)DTW 算法根據(jù)式（5）計(jì)算每個(gè)矩陣元素，該過(guò)程和LDTW 算法相同，具體步驟可以用算法3 進(jìn)行描述。算法3第3、第4 行建立累計(jì)代價(jià)矩陣并初始化；第6～14 行對(duì)累計(jì)代價(jià)矩陣進(jìn)行計(jì)算，其中第8、第9 行調(diào)用算法1 和算法2 對(duì)子序列之間的對(duì)齊路徑長(zhǎng)度范圍進(jìn)行計(jì)算。

算法3FDTW 算法

2.3 算法時(shí)間復(fù)雜度

FDTW 算法的時(shí)間復(fù)雜度與累計(jì)代價(jià)矩陣中需要計(jì)算的累計(jì)代價(jià)矩陣元素?cái)?shù)量相關(guān)，本文對(duì)LDTW 算法的累計(jì)代價(jià)矩陣元素?cái)?shù)量N的分析過(guò)程中得出FDTW 算法的計(jì)算量。

LDTW 算法的N值與時(shí)間序列長(zhǎng)度R、C以及對(duì)齊路徑長(zhǎng)度上限LUB相關(guān)（當(dāng)時(shí)間序列長(zhǎng)度不變時(shí)，N值隨LUB變化）。為了找出N值與R、C和LUB之間的關(guān)系，LDTW 算法中累計(jì)代價(jià)矩陣拆分如圖5 所示，用相同的邊緣線條類型來(lái)體現(xiàn)拆分后各分量矩陣在原矩陣的坐標(biāo)位置。將第一個(gè)包含坐標(biāo)為［R，C］元素的分量矩陣及其之前的分量矩陣標(biāo)記為a類分量矩陣，將其余分量矩陣標(biāo)記為b類分量矩陣。從圖5可以看出，根據(jù)先后順序依次計(jì)算分量矩陣將滿足以下規(guī)律：當(dāng)前計(jì)算元素所依賴的元素都已在此之前計(jì)算完畢。從圖5（a）可以看出，箭頭在計(jì)算元素M［x4］［y4］［5］時(shí)，依賴的 三個(gè)元 素M［x3］［y3］［4］、M［x3］［y4］［4］和M［x4］［y3］［4］都已經(jīng)完成計(jì)算。當(dāng)所有a類分量矩陣計(jì)算完成時(shí)，長(zhǎng)度等于LUB的對(duì)齊路徑所對(duì)應(yīng)的最小距離值則計(jì)算完成，該值是FDTW 算法在參數(shù)FL=LUB時(shí)的目標(biāo)值。因此，a類分量矩陣元素?cái)?shù)量是FDTW 算法的累計(jì)代價(jià)矩陣元素的計(jì)算量，而b類分量矩陣元素?cái)?shù)量是FDTW 算法與LDTW 算法之間矩陣元素計(jì)算量的差值。

圖5 LDTW 算法累計(jì)代價(jià)矩陣拆分Fig.5 Split the cumulative cost matrix of LDTW algorithm

根據(jù)確定序列間對(duì)齊路徑長(zhǎng)度范圍的規(guī)則可知，a類分量矩陣個(gè)數(shù)為maxS?LUB+1，每個(gè)a類分量矩陣包含的元素?cái)?shù)量為［R?（maxS?LUB）］［C?（maxS?LUB）］，則所有a類分量矩陣元素總數(shù)量如式（8）所示：

其中：m=maxS?LUB。

b類分量矩陣個(gè)數(shù)為L(zhǎng)UB?minS，所有b類分量矩陣所包含的元素?cái)?shù)量構(gòu)成首項(xiàng)為|R?C|+1，二級(jí)首項(xiàng)為|R?C|+3，二級(jí)公差為2 的二階等差數(shù)列，可推導(dǎo)出所有b類分量矩陣元素的總數(shù)量如式（9）所示：

其中：n=LUB?minS；p=|R?C|。

當(dāng)兩條時(shí)間序列長(zhǎng)度相等，即R=C時(shí)，所有a類分量矩陣元素總數(shù)量簡(jiǎn)化如式（10）所示：

其中：Ma為關(guān)于對(duì)齊路徑長(zhǎng)度上限LUB的三次函數(shù)，當(dāng)LUB為（5R?4）/3 時(shí)Ma的取值范圍如式（11）所示：

當(dāng)兩條時(shí)間序列長(zhǎng)度相等，所有b類分量矩陣元素的總數(shù)量簡(jiǎn)化如式（12）所示：

N值為a類分量矩陣元素?cái)?shù)量和b類矩陣元素?cái)?shù)量之和，N=Ma+Mb。推算出N為關(guān)于對(duì)齊路徑長(zhǎng)度上限LUB的單調(diào)遞增函數(shù)，N的取值范圍如式（13）所示：

在以上推導(dǎo)過(guò)程中，N值代表LDTW 算法中需要計(jì)算累計(jì)代價(jià)矩陣元素的數(shù)量，Ma值代表FDTW 算法中需要計(jì)算的累計(jì)代價(jià)矩陣元素?cái)?shù)量，Mb值為L(zhǎng)DTW算法計(jì)算量和FDTW 算法之間的差值。由于對(duì)累計(jì)代價(jià)矩陣元素的計(jì)算是LDTW 算法和FDTW 算法的基本操作，累計(jì)代價(jià)矩陣元素?cái)?shù)量即為算法基本操作的執(zhí)行頻度。從式（12）和式（13）可以看出，LDTW 算法和FDTW 算法累計(jì)代價(jià)矩陣元素?cái)?shù)量都與時(shí)間序列長(zhǎng)度呈三次方關(guān)系。因此這兩種算法的時(shí)間復(fù)雜度都為O（n3）。當(dāng)R=C=50 時(shí)，N、Ma、Mb隨LUB變化對(duì)比如圖6所示。從圖6 可以看出，LUB取值越大，差值Mb越大。當(dāng)兩種算法的參數(shù)相同時(shí)，F(xiàn)DTW 算法計(jì)算量比LDTW算法更低。

圖6 N、Ma、Mb隨LUB 變化對(duì)比Fig.6 Change comparison of N，Ma and Mb with respect to LUB

3 實(shí)驗(yàn)

為了與DTW 算法及其變體算法的相關(guān)工作保持一致，本文采用1-NN 分類方法，將FDTW 算法作為距離度量，在UCR 公共數(shù)據(jù)集上進(jìn)行分類實(shí)驗(yàn)，以驗(yàn)證FDTW 算法的性能。

3.1 數(shù)據(jù)集

近年來(lái)，UCR 時(shí)間序列數(shù)據(jù)文檔［19］被研究者廣泛引用，本文從該數(shù)據(jù)文檔中選取序列長(zhǎng)度分布在60～637 的37 個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。所選取的數(shù)據(jù)集如表1 所示。

表1 數(shù)據(jù)集參數(shù)信息Table 1 Parameters information of data set

3.2 FDTW-1NN 分類結(jié)果

最近鄰分類方法因無(wú)需設(shè)置參數(shù)，分類結(jié)果僅依賴于度量方式而被廣泛采用，本文采用該方法進(jìn)行分類實(shí)驗(yàn)。ED 距離、DTW 算法、Sakoe-Chiba 窗口DTW算法、LDTW 算法以及FDTW 算法在相同數(shù)據(jù)集上的分類準(zhǔn)確率如表2 所示。其中，w 是Sakoe-Chiba 窗口DTW 算法的參數(shù)，即窗口寬度占序列長(zhǎng)度的百分比。Sakoe-Chiba 窗口DTW 算法、LDTW算法以及FDTW算法設(shè)置的參數(shù)值標(biāo)注在準(zhǔn)確率右側(cè)，該參數(shù)都由交叉驗(yàn)證法在訓(xùn)練集上學(xué)習(xí)得到。從表2 可以看出，LDTW 算法和FDTW 算法在絕大多數(shù)數(shù)據(jù)集上取得最佳分類準(zhǔn)確率。與LDTW 算法相比，在WordSynonyms數(shù)據(jù)集上，F(xiàn)DTW 算法的分類準(zhǔn)確率最多提高了7 個(gè)百分點(diǎn)，在Lightning7 數(shù)據(jù)集上，最多降低了4 個(gè)百分點(diǎn)。

表2 不同算法的分類準(zhǔn)確率對(duì)比Table 2 Classification accuracy comparison between different algorithms

FDTW 算法與其他算法的分類準(zhǔn)確率對(duì)比如圖7所示。從圖7 可以看出，黑點(diǎn)代表各數(shù)據(jù)集，對(duì)角線代表中線，若黑點(diǎn)位于該線上則代表兩種算法準(zhǔn)確率相等。從圖7（a）、圖7（b）、圖7（c）可以看出，相比ED 距離、DTW 算法、Sakoe-Chiba 窗口DTW 算法，F(xiàn)DTW 算法在絕大多數(shù)數(shù)據(jù)集上表現(xiàn)更優(yōu)（相比ED距離有29個(gè)，相比DTW 算法有28 個(gè)，相比Sakoe-Chiba窗口DTW 算法有27個(gè)），在部分?jǐn)?shù)據(jù)集上持平（相比ED距離有5個(gè)，相比DTW 算法有4 個(gè)，相比Sakoe-Chiba 窗口DTW 算法有5 個(gè)），部分?jǐn)?shù)據(jù)集上呈略微劣勢(shì)（相比ED 距離有3個(gè)，相比DTW算法有5個(gè)，相比Sakoe-Chiba窗口DTW算法有5 個(gè)）。從圖7（d）可以看出，相比LDTW 算法，F(xiàn)DTW 算法的分類正確率在22個(gè)數(shù)據(jù)集上持平，在8個(gè)數(shù)據(jù)集上勝出，7 個(gè)數(shù)據(jù)集上呈劣勢(shì)。

圖7 FDTW 算法與其他4 種算法的分類準(zhǔn)確率對(duì)比Fig.7 Classification accuracy comparison between FDTW algorithm and the other four algorithms

與高準(zhǔn)確率相比，算法提前在哪些數(shù)據(jù)集上能取得高的準(zhǔn)確率更能體現(xiàn)算法的可靠性［20］。本文采用文獻(xiàn)［20］提出的增益混淆矩陣對(duì)FDTW 算法的可靠性進(jìn)行評(píng)估。通過(guò)式（14）分別計(jì)算FDTW 算法與對(duì)比算法（competitor algorithm）之間的預(yù)期準(zhǔn)確率增益和實(shí)際準(zhǔn)確率增益：

計(jì)算預(yù)期增益時(shí)，將交叉驗(yàn)證過(guò)程中在訓(xùn)練集上取得的最高準(zhǔn)確率作為預(yù)期準(zhǔn)確率，而計(jì)算實(shí)際增益時(shí)，在測(cè)試集上進(jìn)行分類實(shí)驗(yàn)的結(jié)果作為實(shí)際準(zhǔn)確率。FDTW 算法與其他4 種算法間預(yù)期準(zhǔn)確率增益和實(shí)際準(zhǔn)確率增益對(duì)比如圖8 所示。其中每個(gè)點(diǎn)代表一個(gè)數(shù)據(jù)集，每個(gè)點(diǎn)會(huì)出現(xiàn)在4 個(gè)區(qū)域中的一個(gè)區(qū)域（包括邊緣），這4 個(gè)區(qū)域分別是：1）真陽(yáng)性（TP），數(shù)據(jù)點(diǎn)出現(xiàn)在此區(qū)域是預(yù)計(jì)在該數(shù)據(jù)集上提高準(zhǔn)確率，而實(shí)際上確實(shí)提高了，出現(xiàn)在該區(qū)域的數(shù)據(jù)點(diǎn)越多，證明算法可靠性越強(qiáng)；2）真陰性（TN），數(shù)據(jù)點(diǎn)出現(xiàn)在此區(qū)域是預(yù)計(jì)在該數(shù)據(jù)集上準(zhǔn)確率降低，而實(shí)際上確實(shí)降低了，如果出現(xiàn)在該區(qū)域的數(shù)據(jù)點(diǎn)過(guò)多，應(yīng)避免在此數(shù)據(jù)集上使用被提出的算法；3）假陰性（FN），數(shù)據(jù)點(diǎn)出現(xiàn)在此區(qū)域中是預(yù)計(jì)在該數(shù)據(jù)集上準(zhǔn)確率降低，實(shí)際上準(zhǔn)確率有所提高；4）假陽(yáng)性（FP），數(shù)據(jù)點(diǎn)出現(xiàn)在此區(qū)域中是預(yù)計(jì)在該數(shù)據(jù)集上準(zhǔn)確率會(huì)提高，但實(shí)際上準(zhǔn)確率卻下降了，出現(xiàn)在該區(qū)域的數(shù)據(jù)點(diǎn)越多，說(shuō)明算法的可靠性越差。

圖8 FDTW 算法與其他4 種算法的預(yù)期準(zhǔn)確率增益和實(shí)際準(zhǔn)確率增益對(duì)比Fig.8 Expected accuracy gain and actual accuracy gain comparison between FDTW algorithm and the other four algorithms

從圖8（a）～圖8（c）可以看出，絕大多數(shù)數(shù)據(jù)點(diǎn)都落入TP 區(qū)域，說(shuō)明相比ED 距離、DTW、Sakoe-Chiba 窗口DTW3 種算法，F(xiàn)DTW 算法的分類準(zhǔn)確率得到提高是可靠的。從圖8（d）可以看出，雖然落入TP 區(qū)域的數(shù)據(jù)點(diǎn)有所減少，但減少的這些數(shù)據(jù)點(diǎn)并沒(méi)有落入其他區(qū)域，而是處于橫軸邊緣，說(shuō)明在測(cè)試集上的分類準(zhǔn)確率沒(méi)有降低。相比其他區(qū)域，落在TP 區(qū)域的數(shù)據(jù)點(diǎn)更明顯，因?yàn)樵诓糠謹(jǐn)?shù)據(jù)集上有較高的預(yù)期準(zhǔn)確率增益和實(shí)際準(zhǔn)確率增益（如BirdChicken 和WordsSynonyms 數(shù)據(jù)集），說(shuō)明FDTW 算法與LDTW 算法相比，在分類準(zhǔn)確率上有著持平的結(jié)果是可靠的。

3.3 時(shí)間開銷對(duì)比

由2.3 節(jié)可知FDTW 和LDTW 算法的時(shí)間復(fù)雜度都為O(n3)，但在參數(shù)相同時(shí)，F(xiàn)DTW 算法需要計(jì)算的累計(jì)代價(jià)矩陣元素?cái)?shù)量比LDTW 算法更少。為進(jìn)一步對(duì)比FDTW 和LDTW 算法的計(jì)算量，選取兩種算法所需參數(shù)相同的8 個(gè)數(shù)據(jù)集，分別記錄兩種算法在分類過(guò)程中所花費(fèi)的時(shí)間以及兩者之間的差值。兩種算法在這8 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率是持平的。參數(shù)相同的數(shù)據(jù)集下FDTW 和LDTW 算法的時(shí)間開銷如表3 所示。為了體現(xiàn)兩組時(shí)間數(shù)據(jù)差異，F(xiàn)DTW 和LDTW 算法分類時(shí)間開銷對(duì)比如圖9所示。從圖9 可以看出，F(xiàn)DTW 算法在所有數(shù)據(jù)集上的分類時(shí)間開銷都小于LDTW 算法，時(shí)間開銷最多減少了10%（Ham 數(shù)據(jù)集）。

圖9 FDTW 和LDTW 算法分類時(shí)間開銷對(duì)比Fig.9 Classification time cost comparison between FDTW and LDTW algorithms

表3 在參數(shù)相同的數(shù)據(jù)集下FDTW算法和LDTW算法的時(shí)間開銷對(duì)此Table 3 Time cost comparison between FDTW and LDTW algorithms on the data sets with same parameter

為了更直觀體現(xiàn)FDTW 算法和LDTW 算法計(jì)算量的差異，選取了長(zhǎng)度最短的數(shù)據(jù)集SyntheticControl，將兩種算法在該數(shù)據(jù)集上的三維累計(jì)代價(jià)矩陣元素對(duì)比如圖10 所示。在參數(shù)相同的情況下，與LDTW 算法相比，F(xiàn)DTW 算法的累計(jì)代價(jià)矩陣減少了部分右上角的元素，從而相應(yīng)減少了時(shí)間開銷。

圖10 在SyntheticControl數(shù)據(jù)集上LDTW 與FDTW 算法計(jì)算量對(duì)比Fig.10 Calculation amount comparison between LDTW and FDTW algorithms on the SyntheticControl data set

3.4 參數(shù)對(duì)齊路徑長(zhǎng)度（FL）的選取

參數(shù)FL是FDTW 算法所需的唯一參數(shù)，該參數(shù)的選取將影響數(shù)據(jù)集的分類準(zhǔn)確率。為了選取更合適的FL參數(shù)，本文采用10 折交叉驗(yàn)證法從各數(shù)據(jù)集包含的訓(xùn)練集上對(duì)該參數(shù)進(jìn)行學(xué)習(xí)。將訓(xùn)練集劃分為10 份，每次將其中一份作為訓(xùn)練集，其余作為測(cè)試集，依次計(jì)算出參數(shù)FL在所有可能取值下的準(zhǔn)確率（即FL的步長(zhǎng)為1）。該過(guò)程在不同測(cè)試集上重復(fù)10 次，取均值作為該FL參數(shù)下的最終準(zhǔn)確率，然后選取最高準(zhǔn)確率所對(duì)應(yīng)的FL參數(shù)值作為最終的參數(shù)值。計(jì)算兩條時(shí)間序列在不同F(xiàn)L值下的FDTW 距離值，會(huì)出現(xiàn)累計(jì)代價(jià)矩陣元素被重復(fù)計(jì)算的現(xiàn)象，例如，對(duì)于任何兩條時(shí)間序列，F(xiàn)L無(wú)論如何取值，累計(jì)代價(jià)矩陣的第一個(gè)元素M［1］［1］［1］都將被計(jì)算，說(shuō)明在交叉驗(yàn)證過(guò)程中，F(xiàn)L有多種取值可能，元素M［1］［1］［1］就會(huì)被計(jì)算多次。本文在進(jìn)行交叉驗(yàn)證過(guò)程中，采用LDTW 算法，將參數(shù)LUB設(shè)定為maxS，從而在一次累計(jì)代價(jià)矩陣的計(jì)算過(guò)程中得出兩條時(shí)間序列之間所有對(duì)齊路徑長(zhǎng)度下的彎曲距離值，以此來(lái)避免重復(fù)計(jì)算數(shù)據(jù)集。

在不同數(shù)據(jù)集上交叉驗(yàn)證性FL值對(duì)比如圖11所示，從圖11 可以看出，部分?jǐn)?shù)據(jù)集的最佳準(zhǔn)確率所對(duì)應(yīng)的FL值并不唯一，本文選取更小的FL值，因這些FL值通常小于（5R?4）/3，根據(jù)2.3 節(jié)當(dāng)FL小于（5R?4）/3 時(shí)，F(xiàn)L值越小，算法的計(jì)算量越小。

圖11 交叉驗(yàn)證產(chǎn)生的FL對(duì)比Fig.11 Comparison of FL generated by cross-validation

從數(shù)據(jù)集ArrowHead 和ECG200 中可以看出，它們最佳分類準(zhǔn)確率對(duì)應(yīng)FL值靠近或等于minS，說(shuō)明對(duì)齊路徑長(zhǎng)度與時(shí)間序列長(zhǎng)度相等，此時(shí)的FD距離值與ED 值等價(jià)。同時(shí)從表1 可以看出，這些數(shù)據(jù)集在ED 距離下的分類準(zhǔn)確率和FD距離及FD距離對(duì)應(yīng)的準(zhǔn)確率相似。因?yàn)檫@類時(shí)間序列存在較小的時(shí)滯（相位偏移），在ArrowHead 和BirdChicken 數(shù)據(jù)集上時(shí)滯對(duì)比如圖12 所示。從圖12（a）可以看出，數(shù)據(jù)集ArrowHead 中的序列只在垂直方向上存在一定噪聲（振幅差），橫向上幾乎不存在相位偏移，在這樣的時(shí)間序列之間，歐氏距離更適合作為度量方式。從圖12（b）可以看出，BirdChicken 數(shù)據(jù)集中序列之間相位偏移和振幅差同時(shí)存在，此時(shí)歐氏距離不再有較好的度量效果。經(jīng)過(guò)交叉驗(yàn)證后選取的參數(shù)FL，能夠反應(yīng)序列之間在橫向上相位偏移的大小，即時(shí)滯的嚴(yán)重程度，使得后續(xù)分類更為準(zhǔn)確。

圖12 在ArrowHead 和BirdChicken 數(shù)據(jù)集上的時(shí)滯對(duì)比Fig.12 Time lag comparison between ArrowHead and BirdChicken data sets

4 結(jié)束語(yǔ)

針對(duì)LDTW 算法計(jì)算量較大的問(wèn)題，本文提出FDTW 算法。通過(guò)調(diào)整LDTW 算法中對(duì)齊路徑長(zhǎng)度的控制策略，以減少累計(jì)代價(jià)矩陣中需要計(jì)算的元素?cái)?shù)量。在UCR 時(shí)間序列數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，與其他時(shí)間序列距離度量（ED 歐氏距離、DTW動(dòng)態(tài)彎曲距離和DTWSC窗口動(dòng)態(tài)彎曲距離）相比，F(xiàn)DTW 算法在大多數(shù)數(shù)據(jù)集上具有更高的準(zhǔn)確率，其與FDTW 算法的分類準(zhǔn)確率呈持平狀態(tài)，且時(shí)間開銷更小。后續(xù)將研究如何在保留限制對(duì)齊路徑長(zhǎng)度的同時(shí)降低時(shí)間復(fù)雜度，進(jìn)一步提高FDTW 算法的計(jì)算效率。