王 見，毛黎明，尹愛軍

重慶大學 機械工程學院，重慶400044

1 引言

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

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

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

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

2 MDC-DTW算法

2.1 DTW算法

DTW是一種通過動態(tài)規(guī)劃尋找時間序列之間最佳匹配路徑的算法，能夠處理在時間維度上的偏移和伸縮問題。設(shè)單維時間序列X 的長度為m,Y 的長度為n，其中X={ x1,x2,…,xm} ，Y={ y1,y2,…,yn} 。構(gòu)建一個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 個元素為xi映射到y(tǒng)j。為了保證匹配的有效性，W需滿足下面三個約束條件：

（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。

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

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

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

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

A 和B 是兩個K 維的多維時間序列，它們的長度分別為M 和N ，利用式（2）計算多維時間序列的一階梯度：

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

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

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

圖2 MDC-DTW的原理示意圖

3 對比實驗

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

隨機產(chǎn)生二維時間序列，并通過縮放、拉伸得到變形之后的時間序列，如圖3（a）所示。左側(cè)是維度1，右側(cè)是維度2，紅色曲線為原始時間序列，黑色曲線為經(jīng)過縮放、伸縮之后的時間序列，中間藍色虛線為匹配路徑。傳統(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ù)運行結(jié)果

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

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

3.2 多維時間序列分類實驗I

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

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

表2 各個算法的簡要描述

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

3.3 多維時間序列分類實驗II

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

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

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

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

表3 多維時間序列分類實驗的正確率I

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

表5 多維時間序列分類實驗的正確率II

圖4 分類時間消耗

4 結(jié)束語

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