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

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

0 引言

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

DTW 基于動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）的思想，具有較高的時(shí)間復(fù)雜度且對(duì)噪聲敏感，傳統(tǒng)DTW 時(shí)間復(fù)雜度為O（mn），其中m、n 為時(shí)間序列長度。DTW 算法有很多變種，如多變量動(dòng)態(tài)時(shí)間規(guī)整MDTW［2］、測(cè)量索引距離的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 距離時(shí)會(huì)產(chǎn)生較大誤差；分塊算法可優(yōu)化效率，如對(duì)時(shí)間序列進(jìn)行分塊［7］、對(duì)動(dòng)態(tài)規(guī)劃產(chǎn)生的矩陣進(jìn)行分塊［8］等，但是也會(huì)帶來一定誤差；褚蓉等［9］提出一種基于形狀與升降性提取序列數(shù)據(jù)重要特征點(diǎn)的DTW 相似性搜索算法，解決了分塊帶來的特征丟失問題；文獻(xiàn)［10］展示了通過全局變量約束，限制搜索區(qū)域可行性；針對(duì)全局約束以減少計(jì)算時(shí)間的方法主要有Sakoe-Chiba 約束［11］與Itakura-Parallelogram 約束［12］；文獻(xiàn)［13］根據(jù)后者應(yīng)用情景，將全局約束范圍由平行四邊形轉(zhuǎn)變?yōu)閯?dòng)態(tài)平行四邊形；文獻(xiàn)［14］證明Sakoe-Chiba 約束在彎曲限制為r 時(shí)只適用于n-r≤m≤n+r的情形。本文對(duì)Sakoe-Chiba 約束進(jìn)行拓展，擴(kuò)充其應(yīng)用范圍。

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

1 傳統(tǒng)DTW 算法

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

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

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

其中W的約束條件有：

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

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

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

基于以上約束條件，通過動(dòng)態(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)過格點(diǎn)的∑d(i,j)最小的一條。

2 優(yōu)化方法

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

2.1 時(shí)間序列壓縮

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

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

2.2 全局約束條件添加

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

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

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

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

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

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

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

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

上述優(yōu)化雖然一定程度上減少了算法計(jì)算時(shí)間，但是在比較兩段包含相同內(nèi)容的時(shí)間序列時(shí)，仍有改進(jìn)空間。針對(duì)兩段內(nèi)容相同的時(shí)間序列，如果一段時(shí)間序列是另一段時(shí)間序列部分壓縮的結(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）對(duì)于任意1≤i＜k，當(dāng)wi=(ai,bi)，wi+1=(ai+1,bi+1)時(shí)，有ai≤ai+1≤ai+1 且bi+1=bi+1。在原約束條件的基礎(chǔ)上整合單調(diào)性與連續(xù)性，并由性質(zhì)給出更加精確的條件bi+1=bi+1。

基于以上約束條件，每個(gè)點(diǎn)(i,j)能轉(zhuǎn)移到的地方為(i,j+1)或(i+1,j+1)，可以看出無論(i,j)向哪個(gè)方向轉(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)并盡可能多地減少不必要運(yùn)算，在[1,m]×[1,n]的矩陣中，所有不可能通過前文所述的兩條約束條件走到(m,n)的點(diǎn)均無需計(jì)算。

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

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

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

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

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

3 實(shí)驗(yàn)數(shù)據(jù)分析

3.1 隨機(jī)數(shù)據(jù)下的實(shí)驗(yàn)

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

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

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

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

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

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

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

Table 2 Test results表2 實(shí)驗(yàn)結(jié)果

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

4 結(jié)語

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

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