一種提高DTW算法運(yùn)算效率的改進(jìn)算法?

謝揚(yáng)揚(yáng) 婁淵勝 商國中

（河海大學(xué)計算機(jī)與信息學(xué)院 南京 211100）

1 引言

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

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

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

2 DTW算法

2.1 DTW算法描述

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

圖1 動態(tài)時間規(guī)整路徑圖

2.2 規(guī)整窗口約束的DTW算法

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

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

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

圖2 平行四邊形約束

3DTW算法改進(jìn)

3.1 現(xiàn)有算法存在的問題

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

3.2 改進(jìn)算法的原理

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

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

圖3 改進(jìn)的DTW范圍約束1

圖4 改進(jìn)的DTW范圍約束2

3.3 改進(jìn)算法適用范圍

下面根據(jù)Xa、Xb的大小關(guān)系，說明在各種情況下兩種設(shè)計方式中矩形面積和的大小關(guān)系：

1）Xa＞Xb

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

2）Xa=Xb

當(dāng)Xa=Xb時，即A點(diǎn)橫坐標(biāo)的值等于B點(diǎn)橫坐標(biāo)的值，A點(diǎn)和B點(diǎn)在同一垂線上只能采用圖4所示的方式。

3）Xa＜Xb

如圖5、圖6所示。

圖5 Xa＜Xb時適用范圍1

圖6 Xa＜Xb時適用范圍2

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

Sc-Sd=8N2+3M2-10MN得出如下關(guān)系：

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

3.4 改進(jìn)算法實(shí)現(xiàn)

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境：Eclipse+java，JDK1.7；

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

編碼語言：java語言；

實(shí)驗(yàn)數(shù)據(jù)：本文實(shí)驗(yàn)的數(shù)據(jù)選取滁河金牛湖滁紅山窯閘水庫的日平均水位作為數(shù)據(jù)集。

4.2 實(shí)驗(yàn)過程

實(shí)驗(yàn)過程：為了能在不同長度段的時間序列上驗(yàn)證傳統(tǒng)動態(tài)時間規(guī)整算法和改進(jìn)的算法運(yùn)算效率。

數(shù)據(jù)選取：

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的時間序列。

對數(shù)據(jù)預(yù)處理并將其規(guī)范化在［0，1］區(qū)間。每兩個時間序列進(jìn)行5次試驗(yàn)，總共有四組對比數(shù)據(jù)，分別計算這四組兩種算法下運(yùn)算時間的平均值，試驗(yàn)結(jié)果如表1。

表1 兩種算法下的運(yùn)算時間比較

4.3 實(shí)驗(yàn)結(jié)果

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

5 結(jié)語

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

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