王 見(jiàn)，毛黎明，尹愛(ài)軍

重慶大學(xué) 機(jī)械工程學(xué)院，重慶400044

1 引言

時(shí)間序列數(shù)據(jù)廣泛存在于眾多應(yīng)用領(lǐng)域，其相似性分析已受到越來(lái)越多的關(guān)注。歐式距離和動(dòng)態(tài)時(shí)間規(guī)整算法（Dynamic Time Warping，DTW）距離是廣泛使用的兩種相似性度量方法[1]。DTW 能夠較好地處理時(shí)間序列的偏移、伸縮問(wèn)題，具有較高的靈活性，在語(yǔ)音識(shí)別[2-3]、姿勢(shì)識(shí)別[4-6]、數(shù)據(jù)挖掘[7-8]、故障識(shí)別[9-10]等領(lǐng)域得到廣泛研究。DTW 相關(guān)的算法主要分為兩類：一類以單維時(shí)間序列為研究對(duì)象；另一類以多維時(shí)間序列為研究對(duì)象。

對(duì)于單維時(shí)間序列，Keogh等[11]研究了DDTW（Derivative Dynamic Time Warping）算法，將一階梯度信息與單維DTW結(jié)合，一定程度緩解了傳統(tǒng)單維DTW對(duì)單維時(shí)間序列過(guò)度壓縮的問(wèn)題；Górecki 等[12]將一階梯度信息、二階梯度信息與單維DTW 結(jié)合，進(jìn)一步提升了單維DTW 的準(zhǔn)確性；Zhang 等[13]研究了SC-DTW（Shape Context Dynamic Time Warping）算法，利用上下文信息提高了DTW對(duì)單維時(shí)間序列相似性分析的準(zhǔn)確性。

對(duì)于多維時(shí)間序列，單維DTW 一般針對(duì)其中某一維序列，獲取匹配路徑，然后將該路徑直接作用于其他維序列。然而由單個(gè)維度上獲得的最優(yōu)匹配路徑不一定是所有維度的最優(yōu)匹配，一般不使用單維DTW處理多維時(shí)間序列。Ten 等[14]研究了多維DTW（Multi-Dimensional DTW，MD-DTW）算法，利用向量記錄每個(gè)時(shí)間點(diǎn)的信息，從而使用所有維度的信息匹配路徑，該算法過(guò)于簡(jiǎn)單，忽略了多維時(shí)間序列的其他信息。Orsenigo等[15]提出了TDVM（Temporal Discrete SVM）算法，該算法首先利用MD-DTW 將多維時(shí)間序列轉(zhuǎn)換成相同的長(zhǎng)度，然后使用離散支持向量機(jī)對(duì)相似性進(jìn)行度量，計(jì)算繁瑣，算法復(fù)雜度較高。Shen 等[16]將度量學(xué)習(xí)算法LMNN（Large Margin Nearest Neighbor）與DTW 相結(jié)合，使用特定的損失函數(shù)來(lái)學(xué)習(xí)馬氏矩陣，提高了多維時(shí)間序列相似性度量的準(zhǔn)確性，但該算法原理復(fù)雜，求解困難。Mei 等[17]研究了一種基于馬氏矩陣的LDMLDTW，它使用度量學(xué)習(xí)算法，利用三元約束學(xué)習(xí)馬氏矩陣，取得了較好的度量效果，該算法同樣原理復(fù)雜，求解困難。

本文借鑒單維DTW的研究成果，將MD-DTW與梯度信息、上下文信息結(jié)合，提出了一種綜合多維時(shí)間序列形狀信息及其上下文信息的相似性度量算法（Multi-Dimensional Contextual Dynamic Time Warping，MDCDTW）。該算法首先計(jì)算多維時(shí)間序列的一階梯度，然后對(duì)其進(jìn)行采樣處理，利用多維時(shí)間序列一階梯度形狀信息及其上下文信息來(lái)查找最優(yōu)匹配路徑。MDCDTW的原理簡(jiǎn)單，易于理解和實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，相較于其他高效算法，MDC-DTW 具有較高的準(zhǔn)確率和時(shí)間效率。

2 MDC-DTW算法

2.1 DTW算法

DTW是一種通過(guò)動(dòng)態(tài)規(guī)劃尋找時(shí)間序列之間最佳匹配路徑的算法，能夠處理在時(shí)間維度上的偏移和伸縮問(wèn)題。設(shè)單維時(shí)間序列X 的長(zhǎng)度為m,Y 的長(zhǎng)度為n，其中X={ x1,x2,…,xm} ，Y={ y1,y2,…,yn} 。構(gòu)建一個(gè)m×n 的距離矩陣D，其中的元素d(i,j)表示xi與yj之間的距離，常用的是歐式距離，d(i,j)=(xi-yj)2。設(shè)X與Y 之間的匹配路徑為W ，W=w1,w2,…,wk,…,wK,max(m,n)≤K ＜m+n-1，wk=(i,j)表示路徑W 中的第k 個(gè)元素為xi映射到y(tǒng)j。為了保證匹配的有效性，W需滿足下面三個(gè)約束條件：

（1）邊界條件：w1=(1,1)，wK=(m,n)。

（2）連續(xù)型：設(shè)wk=(p,q) ，wk+1=(p′,q′) ，需滿足p′-p ≤1 和q′-q ≤1。

（3）單調(diào)性：設(shè)wk=(p,q) ，wk+1=(p′,q′) ，需滿足p′-p ≥0 和q′-q ≥0。

可能存在多個(gè)W 滿足以上三個(gè)條件，DTW通過(guò)動(dòng)態(tài)規(guī)劃尋找其中距離最短的路徑。設(shè)s(i,j)表示距離矩陣D 中(1,1)到(i,j)的路徑長(zhǎng)度，最短路徑的求解如式（1）所示：

2.2 結(jié)合形狀特征及其上下文的多維DTW

MDC-DTW 的設(shè)計(jì)借鑒了單維DTW 的研究成果，本文與MDC-DTW 設(shè)計(jì)相關(guān)的幾個(gè)算法之間的關(guān)系如圖1 所示。傳統(tǒng)DTW 進(jìn)行多維時(shí)間序列相似性分析時(shí)，只利用了單個(gè)維度的信息，丟失了其他維度的信息；MD-DTW 同樣存在著缺陷，它雖然考慮了所有維度的坐標(biāo)信息，但是進(jìn)行時(shí)間序列相似性匹配計(jì)算時(shí)，可能形狀的信息更加重要；MDe-DTW（Multidimensional Derivative Dynamic Time Warping）將梯度形狀信息與MD-DTW結(jié)合，然而這種算法仍然存在不足，它只考慮單個(gè)點(diǎn)的形狀信息而忽略了上下文信息；MDC-DTW將梯度形狀信息和上下文信息與MD-DTW 結(jié)合，利用的信息更加全面。

圖1 各算法之間的關(guān)系圖

A 和B 是兩個(gè)K 維的多維時(shí)間序列，它們的長(zhǎng)度分別為M 和N ，利用式（2）計(jì)算多維時(shí)間序列的一階梯度：

對(duì)時(shí)間序列進(jìn)行采樣，獲取上下文描述因子。設(shè)U(i,k)為對(duì)A′(i,k)進(jìn)行采樣后的上下文描述因子，采樣長(zhǎng)度為L(zhǎng)=5，U(i,k)的計(jì)算如式（3）所示：

MDC-DTW的d(i,j)計(jì)算如式（4）所示：

MDC-DTW的原理示意圖如圖2所示。

圖2 MDC-DTW的原理示意圖

3 對(duì)比實(shí)驗(yàn)

3.1 仿真數(shù)據(jù)

隨機(jī)產(chǎn)生二維時(shí)間序列，并通過(guò)縮放、拉伸得到變形之后的時(shí)間序列，如圖3（a）所示。左側(cè)是維度1，右側(cè)是維度2，紅色曲線為原始時(shí)間序列，黑色曲線為經(jīng)過(guò)縮放、伸縮之后的時(shí)間序列，中間藍(lán)色虛線為匹配路徑。傳統(tǒng)DTW 利用維度1 數(shù)據(jù)獲得匹配路徑，并將該匹配路徑應(yīng)用于維度2，結(jié)果如圖3（b）所示；MD-DTW 利用了所有維度的信息，結(jié)果如圖3（c）所示；MDe-DTW 利用所有維度的一階梯度形狀信息，結(jié)果如圖3（d）所示；MDC-DTW 利用了所有維度的一階梯度形狀及其上下文信息，結(jié)果如圖3（e）所示。

圖3 仿真數(shù)據(jù)運(yùn)行結(jié)果

將各個(gè)算法的運(yùn)行結(jié)果與真實(shí)的匹配路徑進(jìn)行對(duì)比，DTW和MD-DTW的運(yùn)行結(jié)果中存在過(guò)多一點(diǎn)映射多點(diǎn)的匹配，對(duì)時(shí)間序列造成過(guò)度壓縮；MDe-DTW 運(yùn)行結(jié)果的前半部分和真實(shí)匹配相距較大，后半部分和真實(shí)匹配較接近；MDC-DTW的運(yùn)行結(jié)果和真實(shí)匹配很接近，相較于另外3個(gè)算法，MDC-DTW的性能更優(yōu)異。

根據(jù)算法原理對(duì)結(jié)果進(jìn)行分析，傳統(tǒng)DTW 丟失了維度2 的信息；MD-DTW 雖然利用了所有維度的信息，但只利用了數(shù)據(jù)點(diǎn)的y 軸坐標(biāo)信息；MDe-DTW利用了所有維度的一階梯度形狀信息，在該仿真數(shù)據(jù)上，使用一階梯度形狀信息相較于使用y 軸坐標(biāo)信息準(zhǔn)確性更高；MDC-DTW利用了一階梯度形狀信息及其上下文信息，考慮更加全面，得到的匹配結(jié)果也更加準(zhǔn)確。

3.2 多維時(shí)間序列分類實(shí)驗(yàn)I

從UEA Time Series Classification Repository中選出9 個(gè)多維時(shí)間序列數(shù)據(jù)集，各個(gè)數(shù)據(jù)集的信息如表1所示。DTW、MD-DTW、MDe-DTW以及MDC-DTW都是度量距離的算法，因此需要結(jié)合1-NN 算法來(lái)進(jìn)行分類實(shí)驗(yàn)，最后通過(guò)比較分類的正確率來(lái)比較各算法的準(zhǔn)確性。實(shí)驗(yàn)中采用了五折交叉驗(yàn)證（Cross-Validation）方法，取平均值作為分類的準(zhǔn)確率。在MDC-DTW 中，比較了3個(gè)不同采樣長(zhǎng)度（5、10、15）下的準(zhǔn)確率。各個(gè)算法的簡(jiǎn)要描述如表2所示，實(shí)驗(yàn)得到的分類正確率如表3所示。

表1 數(shù)據(jù)集信息I

表2 各個(gè)算法的簡(jiǎn)要描述

從表3可以看出，采樣長(zhǎng)度對(duì)MDC-DTW的評(píng)價(jià)效果有不同程度的影響，但是MDC-DTW的準(zhǔn)確率都要比其他3 個(gè)算法的準(zhǔn)確率高。從算法的原理上理解，MDC-DTW在進(jìn)行時(shí)間點(diǎn)匹配時(shí)，使用了時(shí)間點(diǎn)的形狀信息及其上下文信息，使用的信息更加全面，匹配更加準(zhǔn)確。綜合來(lái)看，本文提出的MDC-DTW算法在上述9個(gè)多維時(shí)間序列集上的效果要比DTW、MD-DTW 和MDe-DTW 的效果好。結(jié)合上述實(shí)驗(yàn)結(jié)果可知，MDCDTW算法的設(shè)計(jì)是合理的。

3.3 多維時(shí)間序列分類實(shí)驗(yàn)II

為進(jìn)一步檢測(cè)MDC-DTW 的性能，將MDC-DTW與LDML-DTW[17]、LMNN-DTW[16]、TDVM[15]和LBM[18]等高級(jí)算法進(jìn)行比較。實(shí)驗(yàn)中采用了五折交叉驗(yàn)證方法，取平均值作為分類的準(zhǔn)確率，MDC-DTW 的采樣長(zhǎng)度設(shè)置為5。實(shí)驗(yàn)中選取了5 個(gè)數(shù)據(jù)集，它們的信息如表4所示，實(shí)驗(yàn)結(jié)果如表5所示。

由表5 可知，在JapaneseVowels、PenDigits、LP1 和LP4 這4 個(gè)數(shù)據(jù)集上，MDC-DTW 的分類準(zhǔn)確率略低于LDML-DTW；但在其余數(shù)據(jù)集上，MDC-DTW的表現(xiàn)明顯優(yōu)于LDML-DTW、LMNN-DTW、TDVM、LBM，這表明MDC-DTW有著較高的準(zhǔn)確性。

3.4 算法復(fù)雜度分析

將MDC-DTW算法與當(dāng)前表現(xiàn)較好的LDML-DTW算法進(jìn)行時(shí)間復(fù)雜度的對(duì)比分析，MDC-DTW算法的時(shí)間復(fù)雜度是O(Nldmn)，LDML-DTW 算法的時(shí)間復(fù)雜度是O(Nd2mn)，其中N 為訓(xùn)練樣本的個(gè)數(shù)，l 為采樣長(zhǎng)度，d 為樣本維度，m 和n 為樣本的長(zhǎng)度。設(shè)置MDCDTW的采樣長(zhǎng)度l=5。在5個(gè)數(shù)據(jù)集上，兩種算法的運(yùn)行時(shí)間如圖4 所示。由圖4（a）可知，在JapaneseVowels數(shù)據(jù)集上，MDC-DTW 相較于LDML-DTW 用時(shí)更少；在Libras、PenDigits 和Character Trajectories 數(shù)據(jù)集上，MDC-DTW 相較于LDML-DTW 用時(shí)更多。由圖4（b）可知，在LP數(shù)據(jù)集上，MDC-DTW相較于LDML-DTW普遍用時(shí)更少。這主要是因?yàn)長(zhǎng)ibras、PenDigits和Character Trajectories數(shù)據(jù)集的維度小于MDC-DTW的采樣長(zhǎng)度，而JapaneseVowels 和LP 數(shù)據(jù)集的維度大于MDC-DTW的采樣長(zhǎng)度。

表3 多維時(shí)間序列分類實(shí)驗(yàn)的正確率I

表4 數(shù)據(jù)集信息II

表5 多維時(shí)間序列分類實(shí)驗(yàn)的正確率II

圖4 分類時(shí)間消耗

4 結(jié)束語(yǔ)

本文針對(duì)多維時(shí)間序列的相似性分析提出了一種結(jié)合形狀特征及其上下文的MDC-DTW算法，并對(duì)該算法進(jìn)行了兩方面的研究：一是研究了MDC-DTW算法設(shè)計(jì)的合理性；二是研究了MDC-DTW算法的性能。在算法設(shè)計(jì)合理性方面，對(duì)該算法從定性分析和定量分析的角度分別進(jìn)行了探究。與MDC-DTW 設(shè)計(jì)相關(guān)的有DTW、MD-DTW、MDe-DTW 算法。在定性分析上，本文使用二維的時(shí)間序列數(shù)據(jù)，對(duì)其進(jìn)行縮放、拉伸處理，獲得仿真的二維時(shí)間序列數(shù)據(jù)，然后利用DTW、MDDTW、MDe-DTW、MDC-DTW 獲取仿真時(shí)間序列數(shù)據(jù)和真實(shí)時(shí)間序列數(shù)據(jù)之間的匹配路徑，可視化展示算法的運(yùn)行結(jié)果，并將其和真實(shí)的匹配進(jìn)行對(duì)比，直觀展示出MDC-DTW 算法相比其余3 個(gè)算法準(zhǔn)確性更高。在定量分析上，本文使用了9 個(gè)多維時(shí)間序列數(shù)據(jù)集，將DTW、MD-DTW、MDe-DTW、MDC-DTW 與1-NN 算法結(jié)合進(jìn)行分類實(shí)驗(yàn)，獲取分類正確率，通過(guò)分類正確率來(lái)評(píng)估各算法在多維時(shí)間序列相似性分析上的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明，相比另外3 個(gè)算法，MDC-DTW 具有一定的優(yōu)越性，MDC-DTW的設(shè)計(jì)是合理的。在算法性能方面，本文對(duì)MDC-DTW算法的準(zhǔn)確率和時(shí)間效率進(jìn)行了研究。在準(zhǔn)確率研究上，利用5個(gè)多維時(shí)間序列數(shù)據(jù)集，結(jié)合1-NN 算法，對(duì)MDC-DTW 算法與當(dāng)前表現(xiàn)優(yōu)異的4個(gè)多維DTW算法進(jìn)行了分類實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)結(jié)果表明，相較于這4 個(gè)高效算法，MDC-DTW 有著較高的準(zhǔn)確率。在時(shí)間復(fù)雜度研究上，將MDC-DTW和當(dāng)前表現(xiàn)較好的LDML-DTW算法進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果表明，當(dāng)采樣長(zhǎng)度小于數(shù)據(jù)維度時(shí)，MDC-DTW 的耗時(shí)相對(duì)更少；當(dāng)采樣長(zhǎng)度大于數(shù)據(jù)維度時(shí)，MDCDTW稍慢于LDML-DTW。