基于LDTW 的動態(tài)時間規(guī)整改進(jìn)算法

夏寒松，張力生，桑春艷

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

0 概述

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

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

為了抑制病態(tài)對齊現(xiàn)象，提高時間序列之間的相似性度量效果，ZHANG 等［11］提出限制對齊路徑長度的動態(tài)時間規(guī)整（LDTW）算法從時間序列之間的對齊路徑長度開始，通過給定對齊路徑長度上限LUB來限制時間序列之間的對齊路徑長度。相比其他改進(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］等）從局部限制每個數(shù)據(jù)點所能匹配對應(yīng)數(shù)據(jù)點的數(shù)量，LDTW 算法在全局上限制對齊路徑總體長度，保留局部對齊的靈活性，抑制“病態(tài)對齊”現(xiàn)象，在UCR 公共數(shù)據(jù)集上的分類效果有更明顯提升。但LDTW 算法將原DTW算法中的二維累計代價矩陣擴(kuò)張為三維矩陣，增大了時間復(fù)雜度，在多數(shù)數(shù)據(jù)集上進(jìn)行分類實驗的時間開銷遠(yuǎn)大于原DTW 算法以及相關(guān)衍生算法。

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

1 相關(guān)工作

1.1 DTW 算法

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

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

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

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

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

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

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

1.2 LDTW 算法

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

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

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

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

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

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

2 FDTW 算法

2.1 算法原理

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

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

2.2 算法描述

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

其中：表示序列X和Y之間所有長度為FL的對齊路徑的集合。

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

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

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

圖3 不同條件下計算的子問題Fig.3 Sub-problems calculated under different conditions

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

2.2.1 子序列間對齊路徑長度范圍計算

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

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

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

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

算法1計算子序列間對最大對齊路徑長度

算法2計算子序列間對最小齊路徑長度

2.2.2 子序列之間距離值計算

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

算法3FDTW 算法

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

FDTW 算法的時間復(fù)雜度與累計代價矩陣中需要計算的累計代價矩陣元素數(shù)量相關(guān)，本文對LDTW 算法的累計代價矩陣元素數(shù)量N的分析過程中得出FDTW 算法的計算量。

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

圖5 LDTW 算法累計代價矩陣拆分Fig.5 Split the cumulative cost matrix of LDTW algorithm

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

其中：m=maxS?LUB。

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

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

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

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

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

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

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

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

3 實驗

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

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

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

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

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

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

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

FDTW 算法與其他算法的分類準(zhǔn)確率對比如圖7所示。從圖7 可以看出，黑點代表各數(shù)據(jù)集，對角線代表中線，若黑點位于該線上則代表兩種算法準(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個，相比DTW 算法有28 個，相比Sakoe-Chiba窗口DTW 算法有27個），在部分?jǐn)?shù)據(jù)集上持平（相比ED距離有5個，相比DTW 算法有4 個，相比Sakoe-Chiba 窗口DTW 算法有5 個），部分?jǐn)?shù)據(jù)集上呈略微劣勢（相比ED 距離有3個，相比DTW算法有5個，相比Sakoe-Chiba窗口DTW算法有5 個）。從圖7（d）可以看出，相比LDTW 算法，F(xiàn)DTW 算法的分類正確率在22個數(shù)據(jù)集上持平，在8個數(shù)據(jù)集上勝出，7 個數(shù)據(jù)集上呈劣勢。

圖7 FDTW 算法與其他4 種算法的分類準(zhǔn)確率對比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］提出的增益混淆矩陣對FDTW 算法的可靠性進(jìn)行評估。通過式（14）分別計算FDTW 算法與對比算法（competitor algorithm）之間的預(yù)期準(zhǔn)確率增益和實際準(zhǔn)確率增益：

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

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

3.3 時間開銷對比

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

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

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

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

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

3.4 參數(shù)對齊路徑長度（FL）的選取

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

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

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

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

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

4 結(jié)束語

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