動態時間規整算法優化

葉科淮，陳 志，王仁杰，史佳成，胡 宸

（1.南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，江蘇南京 210023；2.南京郵電大學 通信與信息工程學院，江蘇 南京 210003）

0 引言

時間序列數據在生活中隨處可見，時間序列數據本質上反映的是某個或某些隨機變量隨時間不斷變化的趨勢。目前時間序列相似性度量常用方法是動態時間歸整（Dy?namic Time Warping，DTW）算法，文獻［1］證明出DTW 算法比歐幾里得距離搜索算法更有效率，但該算法時間序列長度較長，兩段時間序列長度相當時計算效率較低。本文通過分析現有DTW 算法優化方法，對算法進行擴展和改進。

DTW 基于動態規劃（Dynamic Programming，DP）的思想，具有較高的時間復雜度且對噪聲敏感，傳統DTW 時間復雜度為O（mn），其中m、n 為時間序列長度。DTW 算法有很多變種，如多變量動態時間規整MDTW［2］、測量索引距離的IDTW［3］、可以解決傳統DTW 奇異問題的DDTW［4］及WDTW 算法［5］等。

為提高DTW 度量效果，眾多學者進行了相關研究。Salvador 等［6］提出的FastDTW 算法在粗粒度空間內執行DTW 算法，將復雜度優化至O（n），該算法在數據量極大的情況下十分有效，但是在求取DTW 距離時會產生較大誤差；分塊算法可優化效率，如對時間序列進行分塊［7］、對動態規劃產生的矩陣進行分塊［8］等，但是也會帶來一定誤差；褚蓉等［9］提出一種基于形狀與升降性提取序列數據重要特征點的DTW 相似性搜索算法，解決了分塊帶來的特征丟失問題；文獻［10］展示了通過全局變量約束，限制搜索區域可行性；針對全局約束以減少計算時間的方法主要有Sakoe-Chiba 約束［11］與Itakura-Parallelogram 約束［12］；文獻［13］根據后者應用情景，將全局約束范圍由平行四邊形轉變為動態平行四邊形；文獻［14］證明Sakoe-Chiba 約束在彎曲限制為r 時只適用于n-r≤m≤n+r的情形。本文對Sakoe-Chiba 約束進行拓展，擴充其應用范圍。

本文對DTW 算法進行擴展和改進，將該優化方法應用于較長的時間序列進行試驗。結果表明，該方法在兩個時間序列相差不大時能將時間復雜度降低至線性，并可以準確判斷時間序列是否相同。

1 傳統DTW 算法

設參考模板為R={R1,R2,R3,…,Rn}，測試 模板為T={T1,T2,T3,…,Tm}，其中參考模板共包含n幀，測試模板共包含m幀，Ri、Tj分別表示參考模板的第i幀和測試模板的第j幀特征矢量。

參考模板與特征模板的失真度決定了兩個序列相似度，失真度越小，則相似度越高。測試模板第i幀Ti與參考模板第j幀Rj的失真度為d(i,j)，設D(i,j)為測試模板匹配了i幀、參考模板匹配了j幀失真度。為了求取最終答案D(m,n)，可以定義1 個矩陣，矩陣的(i,j)位置包含d(i,j)和D(i,j)。

對于規整路徑W={w1,w2,w3,…,wk}，有：

其中W的約束條件有：

（1）規整路徑滿足w1=(1,1)，且wk=(m,n)。

（2）對于任意的1≤i＜k，當wi=(ai,bi)，wi+1=(ai+1,bi+1)時，有ai+1≤ai+1 且bi+1≤bi+1。

（3）對于任意的1≤i＜k，當wi=(ai,bi)，wi+1=(ai+1,bi+1)時，有ai+1≥ai，bi+1≥bi，且ai+bi≠ai+1+bi+1。

基于以上約束條件，通過動態規劃的方法，得出狀態轉移方程為：

在矩陣中通過該轉移方程得到的是一條從(1,1)走到(m,n)的路徑，約束條件限定了每一步只能從(i,j)走到(i+1,j)，(i,j+1)或(i+1,j+1)，規整路徑是所有路徑中滿足經過格點的∑d(i,j)最小的一條。

2 優化方法

傳統DTW 算法需在對任意1≤i≤m，1≤j≤n都求出D(i,j)值后，才能得到最終答案D(m,n)。設DTW 算法計算次數為NM，實際上，該算法對每一對可能比對的幀均進行比較。

2.1 時間序列壓縮

應用傳統DTW 算法對兩個時間序列進行比較，最終得到的匹配結果是通過對模板T 和R 進行伸縮和拉伸后的時間序列。在實際應用中，如語音序列相似度計算，對參考模板的改變并沒有實際意義，所以可令參考模板不變，只將測試模板向參考模板的方向進行變化即可。

在參考模板和測試模板的界限比較模糊時，易知參考模板與測試模板可互換，求得的結果相等，所以可令序列長度較短的模板為參考模板T，較長的模板為測試模板R，因為有m≤n，所以應對R 進行收縮。

2.2 全局約束條件添加

在傳統約束條件之外，有時候關鍵路徑還需要滿足全局約束條件，即任意一條關鍵路徑中的每一個點（i，j）需要滿足全局路徑中的要求。這樣，對于不滿足約束條件中的所有點，在計算D（i，j）時可在不影響后續點的情況下忽略。

在Sakoe-Chiba 約束［11］中，關鍵路徑的可能點是一條主對角線方向上的帶形。根據DTW 算法的狀態轉移方程，在帶形之外所有狀態失真度均不會作為格點之內的狀態失真度計算的前提，所以僅計算帶形之內的狀態失真度即可，約束范圍如圖1 所示。

Fig.1 Sakoe-Chinba restriction圖1 Sakoe-Chiba 約束

設這種全局約數限制為r，則對于所有1≤j≤n，陰影部分所有狀態(i,j)均需滿足j-r≤i≤j+r［14］，所以使用Sakoe-Chiba 約束必須有m-n≥r，即對不等長序列長度差具有一定限制。

為了盡可能地克服這種限制，本文將陰影區域劃分為狀態(1,r)邊界中點與狀態(m-r+1,n)右邊界中點的連線、狀態(r,1)左邊界中點與狀態(m,n-r+1)右邊界中點狀態連線與全局邊界圍成的部分，如圖2 所示。

Fig.2 Improved restriction when r=2圖2 改進后r=2 時的約束

改進后Sakoe-Chiba 約束可普遍應用于求DTW 距離的場景，即使是兩個時間序列相差比較大的情況。設置全局約束可優化DTW 計算時間，基于該思想，本文對規整路徑W 的約束條件進行改進，使改進后的DTW 算法在一些特殊的應用環境中可達到更高效率。

2.3 特殊情況下的改進

上述優化雖然一定程度上減少了算法計算時間，但是在比較兩段包含相同內容的時間序列時，仍有改進空間。針對兩段內容相同的時間序列，如果一段時間序列是另一段時間序列部分壓縮的結果，使用這種改進方法可以得到很好的反饋。

在2.1 章節的前提下，假設新的約束條件：

（1）規整路徑滿足w1=(1,1)，且wk=(m,n)。由于R不變，反映到圖像上，規整路徑方向只有從(i,j)到(i,j+1)與(ι+1,j+1)，所以可得出k=max(n,m)=n。

（2）對于任意1≤i＜k，當wi=(ai,bi)，wi+1=(ai+1,bi+1)時，有ai≤ai+1≤ai+1 且bi+1=bi+1。在原約束條件的基礎上整合單調性與連續性，并由性質給出更加精確的條件bi+1=bi+1。

基于以上約束條件，每個點(i,j)能轉移到的地方為(i,j+1)或(i+1,j+1)，可以看出無論(i,j)向哪個方向轉移，縱坐標j都增加了1，所以規整路徑的長度一定為n。并且由于規整路徑是從(1,1)到(m,n)的路徑，所以轉移到(i+1,j+1)的次數恒為m-1。

為了求出最終答案D(m,n)并盡可能多地減少不必要運算，在[1,m]×[1,n]的矩陣中，所有不可能通過前文所述的兩條約束條件走到(m,n)的點均無需計算。

矩陣中的任意點(i,j)，根據縱坐標的約束條件，走到(m,n)需要n-j步，在每一步中同時需要橫坐標增加m-i次，所以有：

同時，這個點還要滿足可以從起點（1，1）轉移過來，即：

所有滿足上述兩式的點，都不需要在動態規劃的過程中計算出來，因此可以省去大部分計算時間。通過線性規劃的方法，可以得到規整路徑可能經過的地方，也就是需要計算D(i,j)的點，如圖3 所示。當n=m時，計算次數僅有n次，此時關鍵路徑W={(i,i)|i=1,2,3,…n}。

Fig.3 Points to be calculated for warping path圖3 規整路徑需要計算的點

經過這種在特殊情況下的優化，需要計算的D(i,j)狀態有n(m-n+1)個，而原算法計算的數量為nm個，即改進算法可以比傳統算法少計算n(n+1)次。因此可以得出結論，改進算法的復雜度為O(n(m-n))，當n越大，改進算法的優勢越大，又因為n≤m，所以當n與m越接近時，算法效率越高。

3 實驗數據分析

3.1 隨機數據下的實驗

將改進的時間序列相似度計算算法與傳統DTW 算法進行比較，為了使任意兩幀的失真度d(i,j)可由O(1)求出，隨機生成兩個正整數數組T、R，并令d(i,j)=(Ti-Rj)2。在相同的實驗環境與數據集中，分別運行兩個算法，同時記錄兩個程序運行中消耗的CPU 時間。對每組實驗結果進行對比，并且分析在不同模板長度下對時間序列進行計算的改進效果。得出的數據如表1 所示。

Table 1 Test results of random data表1 隨機數據實驗結果

通過表1 的數據可以看出，兩種算法在數據量比較少的情況下運行時間均較短，看不出明顯差異。為了對比參考模板長度與測試模板長度關系對算法改進效率的影響，假設測試模板長度不變，實驗效果如圖4 所示。

Fig.4 Efficiency comparison when m=20 000圖4 當m=20 000 時的效率對比

橫軸代表n 的長度，縱軸是算法運行時間，單位為秒。如圖4 可知，在數據量比較大的情況下，當測試模板與參考模板長度差異較大時，如表1 的第4 組實驗，提高了39.5% 的效率；而參考模板長度約接近測試模板，如表1 第3 組實驗，提高了約99% 的效率。

3.2 時間序列內容判斷

就視頻來說，兩段內容相同的視頻只可能是播放速率不同，在時間序列上的體現是某些幀重復了多次，如果使用2.3 章節中的改進方法，相同視頻得到的失真度應該為無窮小。隨機產生一些參考模板，并且選取若干幀進行左右重復擴展，將處理好的時間序列作為測試模板進行實驗，結果如表2 所示。

Table 2 Test results表2 實驗結果

經過觀察可以發現，表2 得出的實驗結果與2.3 章節得出的結論一致：當參考模板長度n越大，算法運行時間越短。實驗數據中算法運行時間符合改進算法O(n(m-n))的復雜度，并且當兩段時間序列相同時，得到的DTW 失真度為無窮小，符合實驗前的預測。

4 結語

本文在現有約束前提下，增加及改變了一些約束，提出了一種在時間序列規整過程中壓縮時間序列的思想。針對現有他人研究，擴展了Sakoe-Chiba 約束，解決了該約束不能應用于兩個模板長度差距過大的問題。根據擴展Sakoe-Chiba 約束設置全局變量的思想，改進了DTW 的前提約束，改進后DTW 算法在識別時間序列時，能在保證高準確度的情況下高效應用。因此該算法可為依賴于實時性的識別匹配系統提供一定幫助，減少硬件開銷。

改進后的DTW 算法雖然高效但對應用環境有嚴格的要求，對除了識別時間序列內容之外的問題不能保證準確性，還待進一步優化與研究。