一種提高DTW算法運算效率的改進算法?

謝揚揚 婁淵勝 商國中

（河海大學計算機與信息學院 南京 211100）

1 引言

通過對水文時間序列相似性的分析我們可以得到水文數據的特點，理解水文數據變化的規律，并且回答了在防汛指揮中經常被問到的一個問題“在歷史上什么時候出現過同當前情況相似的水文過程？”水文時間序列的相似性度量是水文序列相似性搜索的一個必須的環節，目前在水文時間序列的相似性度量常采用的方法是動態時間規整距離，它可以有效地處理沿時間軸上形變的問題，具有很好的魯棒性，被越來越多的應用到水文領域的相似性度量中。

在實際應用中，傳統動態時間規整算法直接采用動態規劃，計算復雜度為O（mn），其中m，n為時間序列的長度，復雜度過高。目前國內外學者針對DTW復雜度高的問題的進行研究，主要的方法有：1）提前終止技術，當累計的規整距離超過閾值時，停止剩余路徑的搜索；2）采用全局約束設置搜索范圍，將搜索路徑控制在規整窗口內部［3］。

本文通過分析現有的DTW算法，在此基礎上對平行四邊形規整窗口外畫出三個矩形，對路徑進行快速修剪，矩形外的點都不需要再做計算，減少了計算量，在一定程度上提高了算法運算效率。該算法進一步縮小了規整路徑的搜索范圍，在一定程度上減少了原算法的計算量，從而達到運算效率上的提高，尤其是在兩個時間序列的長度較長時，這種運算效率的提高顯得更加的明顯。

2 DTW算法

2.1 DTW算法描述

動態時間規整算法的主要思想是對兩個需要進行相似性比較的時間序列Q（q1，q2，…，qi，…qn）和C（c1，c2，…，cj，…，cm），構造一個在時間上對齊的n*m維矩陣D（其中n為Q的長度，m為C的長度，通常n≠m）。矩陣D中的元素di，j=（qi-cj）2代表Q中點qi和C中點cj之間的歐式距離［1］。在距離矩陣D中運用動態規劃的思想從起點d1，1到dn，m之間找到一條累計距離最小的路徑，這個距離就是動態規整距離，如圖1所示。動態時間規整路徑L需要滿足的條件有：1）有界性：max（m，n）≤ L ≤ m+n。2）規整路徑的起止點為距離矩陣斜對角線的兩端的元素。3）連續性：路徑L中的元素是連續的。4）單調性：規整路徑L經過某一點（i，j）的前一點必須是（i-1，j），（i，j-1），（i-1，j-1）三點中的一點。

圖1 動態時間規整路徑圖

2.2 規整窗口約束的DTW算法

對于距離矩陣D中的元素不需要全部參與計算和決策，運用全局約束不僅可以加速DTW算法的運算時間，而且可以防治時間序列的病態規整［4］。學者Itakura提出一種平行四邊形的規整窗口約束如圖2所示。認為在動態時間規整距離的計算中，平行四邊形外的點不需要參與運算。在實際應用中通常把k1設為1/2，k2設為2。由于E點和斜率已知，容易表示出平行四邊形的四條邊。

有學者提出把動態彎折分成三段：（0，Xa）、（Xa+1，Xb）和（Xb+1，N），其中：取最接近點的整數，可以得出M、N的限制條件：2M-N ≥3、2N-M ≥2。

當M、N的長度不滿足條件時，認為兩個時間序列不適合進行動態時間規整相似性度量。在現有的DTW算法中，需要構建距離矩陣和累計距離矩陣，即使已經通過平行四邊形規整窗口限制了搜索范圍，但搜索的每一步都需要與四條邊進行邊界計算，運算量依然非常大，當兩條時間序列很長時，這種重復的計算嚴重消耗時間和資源［12］。

圖2 平行四邊形約束

3DTW算法改進

3.1 現有算法存在的問題

現有DTW算法中，需要計算兩個時間序列之間的距離矩陣和累積距離矩陣，計算量很大，即使在限定了規整路徑的搜索范圍處于平行四邊形范圍中的情況下，路徑搜索的每個環節都要進行上下邊界的計算，計算量依然很大，尤其是在兩個時間序列很長時，這種重復性的計算就越多，嚴重地降低了算法的效率。因此我們需要對算法做出進一步改進，提高它的運算效率。

3.2 改進算法的原理

在運用規整窗口約束后，需要判斷哪些點在規整窗口范圍內，這時要進行N*M次計算，判斷其是否在范圍內。為了快速地確定平行四邊形的約束范圍，避免大量的邊界運算［8］，如圖3所示設計出三個矩陣S1、S2、S3。Xa在數值上等于A點橫坐標，Xb在數值上等于B點橫坐標。這時只需要在矩形范圍內對點進行邊界值判斷，并且只需計算平行四邊形OAEB中點的距離和累計距，大大減少了計算量。因為E點的坐標E（N，M）和OA，OC直線的斜率已知，點A，B，G，H的坐標都可以求出：

由于平行四邊形的形狀在斜率一定的情況下，由N，M的長度決定，可能會出現Xa=Xb，或者Xa＞Xb的情況。為了更準確地限制范圍，即在各種情況下使三個矩形面積和在包含平行四邊的前提下最小，在此提出另外一種設計方式，如圖4所示。

圖3 改進的DTW范圍約束1

圖4 改進的DTW范圍約束2

3.3 改進算法適用范圍

下面根據Xa、Xb的大小關系，說明在各種情況下兩種設計方式中矩形面積和的大小關系：

1）Xa＞Xb

如圖3、圖4所示三個矩形面積和分別為Sa、Sb，通過計算得：

2）Xa=Xb

當Xa=Xb時，即A點橫坐標的值等于B點橫坐標的值，A點和B點在同一垂線上只能采用圖4所示的方式。

3）Xa＜Xb

如圖5、圖6所示。

圖5 Xa＜Xb時適用范圍1

圖6 Xa＜Xb時適用范圍2

通過計算得：圖5矩形面積之和Sc與圖6面積矩形面積之和Sd的關系：

Sc-Sd=8N2+3M2-10MN得出如下關系：

這兩種設計方式在本質上是相同的，目的是為了在包含平行四邊形的前提下使規整窗口最小，減少計算量，在實際應用中應該根據兩條水文時間序列的長度關系，判斷使用哪一種方式。

3.4 改進算法實現

以兩個時間序列 R=（r1，r2，r3，…，rm），T=（t1，t2，t3，…，tn）為輸入，改進的DTW算法實現如下：

36：if（m＜n）｛

37：method_column（）；

38｝

39：｝

40：if（［（2m-n）/3］=［2（2n-m）/3］）｛

41： method_row（）；

42：｝

43：if（［（2m-n）/3］＞［2（2n-m）/3］）｛

44：if（（m＞2n）||（m＜［（4n）/3］））｛

45： method_row（）；

46：｝

47：if（4n/3≤m≤2n）｛

48：method_column（）；

49：｝

50：｝

51：for i=0；i＜ n；i++

52：for j=0；j＜m；j++

53： if d［i］［j］==0.0

54： continue；

55：if i==0&&j==0

56： D［i］［j］=d［i］［j］；

57： elseif i==0&&j！=0

58： D［i］［0］=d［i］［0］+D［i-1］［0］；

59： elseif j==0&&i！=0

60： D［0］［j］=d［0］［j］+D［0］［j-1］；

61：else

62： warpDistance=min（D［i-1］［j］==0.0 ？：+∞，D

［i-1］［j-1］）==0.0 ？：+∞，D［i］［j-1］）==0.0 ？：+∞）

63： warpDistance+=d［i］［j］；

64：D［i］［j］=warpDistance；

65：return warpDistance

上述改進的算法中，d［n］［m］為距離矩陣，D［n］［m］為累積距離矩陣，可以看到，三個矩形區域外的格點對應到兩個二維矩陣中元素值沒有被計算，算法最終返回的warpDistance為規整路徑的距離，也就是DTW算法所要求出的最短扭曲距離。

4 實驗結果與分析

4.1 實驗環境

實驗環境：Eclipse+java，JDK1.7；

系統參數：P320 AMD Athlon（tm）ⅡP320 Dual-Core Processor，CPU 2.10GHz，RAM 4GB，32 位Windows7旗艦版操作系統；

編碼語言：java語言；

實驗數據：本文實驗的數據選取滁河金牛湖滁紅山窯閘水庫的日平均水位作為數據集。

4.2 實驗過程

實驗過程：為了能在不同長度段的時間序列上驗證傳統動態時間規整算法和改進的算法運算效率。

數據選?。?/p>

1）1972年1月1日至1974年3月31日長度為90和1971年1月1日至1971年4月30日長度為120的時間序列；

2）2000年1月1日至2000年12月31日長度為366和1998年4月1日至1998年12月31日長度為275的時間序列；

3）2001年1月1日至2005年12月31日長度為1826和2006年1月1日至2010年12月31日長度為1826的時間序列；

4）1990年1月1日至1998年12月31日長度為3287和2000年1月1日至2009年12月31日長度為3653的時間序列。

對數據預處理并將其規范化在［0，1］區間。每兩個時間序列進行5次試驗，總共有四組對比數據，分別計算這四組兩種算法下運算時間的平均值，試驗結果如表1。

表1 兩種算法下的運算時間比較

4.3 實驗結果

通過表1可知：當時間序列對長度為90×120時，改進后的算法提高的時間百分比為3.7%；當時間序列對長度為366×275時，改進后的算法提高的時間百分比為5.0%；當時間序列對長度為1826×1826時，改進后的算法提高的時間百分比為5.9%；當時間序列對長度為3287×3653時，改進后的算法提高的時間百分比為6.3%；因而可以證明本文提出的改進算法，在一定程度上減少了計算量，提高了算法的運算效率，尤其是當兩個時間序列較長時，這種運算效率上的提高更為明顯。

5 結語

DTW算法思想是采用動態規劃技術來求解最優化問題的過程，將一個復雜的全局最優化問題分解為許多局部最優化問題，并一步一步地進行決策［14］，最終得到全局問題的一個最優解，在時間序列相似性匹配過程中體現為利用局部最佳化尋找一條路徑，沿著這條路徑，兩個時間序列之間的累計規整距離最小。但是在進行DTW距離度量兩個時間序列時，由于DTW算法采用逐點匹配的方式，所以很容易受到時間序列中的“噪音”和“孤立點”的干擾［13］，并且當匹配的時間序列的長度過長時，計算量非常大。因此，尋找一個合適的約束條件，有效地控制兩個時間序列的匹配范圍，成為提高DTW匹配結果精確度和縮短匹配時間的關鍵。

本文在分析現有的DTW算法基礎上，在平行四邊形路徑搜索范圍外，規劃出三個矩形區域，矩形區域外的格點不會出現在規整路徑中，因此無須進行格點是否在平行四邊形范圍內的判斷，因此在一定程度上減少了計算量，提高了算法的運算效率。通過上表我們可以看出，改進后的算法不僅減少了運算的時間，在一定程度上還提高了運算效率，尤其是在時間序列很長時效果更加明顯。本文DTW改進算法的本質是縮小規整窗口的范圍，減少沒必要的重復計算，所以算法在準確度上并沒有降低。