基于LDTW 的動態時間規整改進算法

夏寒松，張力生，桑春艷

（重慶郵電大學軟件工程學院，重慶 400065）

0 概述

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

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

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

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

1 相關工作

1.1 DTW 算法

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

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

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

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

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

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

圖1 病態對齊現象示意圖Fig.1 Schematic diagram of pathological alignment phenomenon

1.2 LDTW 算法

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

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

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

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

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

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

2 FDTW 算法

2.1 算法原理

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

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

2.2 算法描述

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

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

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

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

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

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

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

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

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

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

因此，根據參數FL和互補子序列之間的原始對齊路徑長度，對子序列間原始的齊路徑長度范圍的上限和下限進行進一步調整。

1）調整范圍上限

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

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

2.2.2 子序列之間距離值計算

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

算法3FDTW 算法

2.3 算法時間復雜度

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

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

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

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

其中：m=maxS?LUB。

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

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

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

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

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

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

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

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

3 實驗

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

3.1 數據集

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

表1 數據集參數信息Table 1 Parameters information of data set

3.2 FDTW-1NN 分類結果

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

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

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

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

與高準確率相比，算法提前在哪些數據集上能取得高的準確率更能體現算法的可靠性［20］。本文采用文獻［20］提出的增益混淆矩陣對FDTW 算法的可靠性進行評估。通過式（14）分別計算FDTW 算法與對比算法（competitor algorithm）之間的預期準確率增益和實際準確率增益：

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

圖8 FDTW 算法與其他4 種算法的預期準確率增益和實際準確率增益對比Fig.8 Expected accuracy gain and actual accuracy gain comparison between FDTW algorithm and the other four algorithms

從圖8（a）～圖8（c）可以看出，絕大多數數據點都落入TP 區域，說明相比ED 距離、DTW、Sakoe-Chiba 窗口DTW3 種算法，FDTW 算法的分類準確率得到提高是可靠的。從圖8（d）可以看出，雖然落入TP 區域的數據點有所減少，但減少的這些數據點并沒有落入其他區域，而是處于橫軸邊緣，說明在測試集上的分類準確率沒有降低。相比其他區域，落在TP 區域的數據點更明顯，因為在部分數據集上有較高的預期準確率增益和實際準確率增益（如BirdChicken 和WordsSynonyms 數據集），說明FDTW 算法與LDTW 算法相比，在分類準確率上有著持平的結果是可靠的。

3.3 時間開銷對比

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

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

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

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

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

3.4 參數對齊路徑長度（FL）的選取

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

在不同數據集上交叉驗證性FL值對比如圖11所示，從圖11 可以看出，部分數據集的最佳準確率所對應的FL值并不唯一，本文選取更小的FL值，因這些FL值通常小于（5R?4）/3，根據2.3 節當FL小于（5R?4）/3 時，FL值越小，算法的計算量越小。

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

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

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

4 結束語

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