動態(tài)時間規(guī)整算法優(yōu)化

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

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

0 引言

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

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

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

本文對DTW 算法進(jìn)行擴展和改進(jìn)，將該優(yōu)化方法應(yīng)用于較長的時間序列進(jìn)行試驗。結(jié)果表明，該方法在兩個時間序列相差不大時能將時間復(fù)雜度降低至線性，并可以準(zhǔn)確判斷時間序列是否相同。

1 傳統(tǒng)DTW 算法

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

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

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

其中W的約束條件有：

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

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

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

基于以上約束條件，通過動態(tài)規(guī)劃的方法，得出狀態(tài)轉(zhuǎn)移方程為：

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

2 優(yōu)化方法

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

2.1 時間序列壓縮

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

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

2.2 全局約束條件添加

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

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

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

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

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

Fig.2 Improved restriction when r=2圖2 改進(jìn)后r=2 時的約束

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

2.3 特殊情況下的改進(jìn)

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

在2.1 章節(jié)的前提下，假設(shè)新的約束條件：

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

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

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

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

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

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

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

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

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

3 實驗數(shù)據(jù)分析

3.1 隨機數(shù)據(jù)下的實驗

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

Table 1 Test results of random data表1 隨機數(shù)據(jù)實驗結(jié)果

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

Fig.4 Efficiency comparison when m=20 000圖4 當(dāng)m=20 000 時的效率對比

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

3.2 時間序列內(nèi)容判斷

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

Table 2 Test results表2 實驗結(jié)果

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

4 結(jié)語

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

改進(jìn)后的DTW 算法雖然高效但對應(yīng)用環(huán)境有嚴(yán)格的要求，對除了識別時間序列內(nèi)容之外的問題不能保證準(zhǔn)確性，還待進(jìn)一步優(yōu)化與研究。