基于多維分段和動態權重DTW的多元時間序列相似性度量方法*

魏國強 周從華 張 婷

（1.江蘇大學計算機科學與通信工程學院 鎮江 212013）（2.無錫市婦幼保健院 無錫214002）

1 引言

在我們的生活中，諸如金融、醫療和氣象等領域產生的具有一定時間先后性的數據可稱為時間序列數據［1］。隨著信息時代的到來，現代科學技術水平不斷提高，各個領域產生的時間序列數據也不斷增加，如何從海量的時間序列數據中發掘出隱含的深層知識成為一個熱點問題。時間序列數據挖掘就是利用數據挖掘技術從時間序列數據中發現潛在的有價值的信息和模式，它也已成為目前數據挖掘領域中十個最具挑戰性的問題之一［2］。

時間序列是指在一段時間內，以相同的時間間隔對某個潛在的過程觀測并采樣得到的一系列觀測值，根據同一時間采集的數據指標個數不同可以將時間序列分為一元時間序列可多元時間序列。與一元時間序列相比，多元時間序列在現實生活中更為常見，例如，天氣數據可以用最高溫、最低溫、空氣濕度和降水量等變量來描述［3］，醫學中患者的身體狀況也可以通過一系列生理指標的變化反映出來。

基本的時間序列數據挖掘方法包括聚類、分類和相似性搜索等，而這些方法首先都需要比較時間序列的相似性，即相似性度量。相似性度量也是時間序列數據挖掘的關鍵技術之一，其結果直接影響了時間序列數據挖掘的效果［4］。然而，目前的時間序列相似性度量方法大多面向一元時間序列，對多元時間序列的研究相對較少，還未形成一個系統的體系［5］。多元時間序列的多個變量之間存在某種相關性，共同影響了系統的狀態和發展趨勢，因此并不能視為一元時間序列的簡單疊加［4］，目前的一元時間序列相似性度量方法也不能直接用于多元時間序列。因此，研究多元時間序列相似性度量具有重要的理論和現實意義。

多元時間序列由一系列時間點數據構成，其時間跨度和時間間隔決定了序列的時間維度。若直接在維度高的原始數據上進行相似性度量，不僅計算量大，運行效率低，數據的噪聲和冗余也會對度量精度帶來較大影響。因此，參照普遍的機器學習和數據挖掘方法，首先需要對多元時間序列進行特征提取，保留有價值的信息并降低數據維度。同時，多元時間序列的復雜性也源自其多元性［6］，其變量個數決定了序列的變量維度。由于變量之間存在相關性，在進行模式表示時不僅要降低序列維度，還要考慮變量之間的相關性。

SVD方法［7］是一種基于主成分分析方法的多元時間序列模式表示方法，該方法將原始高維數據映射到低維空間，搜索出若干最能代表數據的k維正交向量，使原始數據被投影到較小的空間中。文獻［8］提出一種基于點分布特征的方法PD，通過三維空間描述多維時間序列，提取極大值、極小值等9個局部重要特征點對原始序列進行模式表示。這兩種方法都是基于統計的模式表示方法，忽略了變量之間的相關性關系，同時都有一定的局限性，例如前者需要有足夠的樣本點，后者對數據規模較小且樣本形狀差異大的數據才比較有效。文獻［9］提出一種趨勢距離TD，對多元時間序列進行多維分段擬合后，選取擬合多項式的一次項系數和擬合段的時間跨度作為序列特征，并基于DTW距離進行時間序列的相似性度量。在多數數據集上，該方法都能取得較高的度量精度，但在一些序列較短，形態變化不突出的數據集上，得不到理想的度量效果。

在對多元時間序列進行模式表示之后，需要設計相應的距離度量函數衡量序列特征之間的相似程度。目前較常用的相似性度量方法有歐式距離［10］和動態時間彎曲（DTW）［11］距離。歐式距離簡潔明了，易于理解和計算，但僅能實現序列之前“一對一”的匹配方式，因此需要滿足序列長度相等的前提條件。與歐式距離相比，DTW距離支持序列在時間軸上的伸縮與彎曲，允許兩條序列擁有不同的長度，但可能存在畸形匹配。對此，文獻［12］提出一種自適應窗口法，通過對數據的學習，自適應地限制最佳彎曲路徑的搜索范圍；文獻［13］提出加權動態時間彎曲距離（WDTW），在求解時引入權重參數，來控制彎曲路徑偏離對角線的程度。但以上兩種方法都在原始DTW的基礎上引入外在的參數，如何設置這些參數成為另一個復雜的問題。

針對現有的特征表示算法存在的問題，本文基于多維分段的序列分段方法，選取擬合線段的斜率、均值和時間跨度作為特征模式。針對動態時間彎曲距離的畸形匹配問題，提出一種動態權重動態時間彎曲距離（Dynamic Weighted Dynamic Time Warp，DWDTW），在搜索最佳彎曲路徑的過程中，為每個擬合段動態地賦予權重，擬合段的匹配次數越多，權重越小，通過限制擬合段匹配次數來解決畸形匹配問題。使用DWDTW距離度量提取到的多元時間序列特征矩陣之間的相似性，提出了一種基于多維分段和DWDTW的多元時間序列相似性度量方法（簡稱MS-DWDTW），并通過實驗證明了該方法的準確性和適用性。

2 多元時間序列模式表示和特征提取

一條多元時間序列可以用X=(X1，X2，…XT)表示，而Xt=(x1(t)，x2(t)，…xm(t))，其m為變量個數，T為時間點數量，xi(t)(1≤t≤T，1≤i≤m)表示第i個變量在第t個時間點的觀察值。

對多元時間序列進行模式表示，較為常用且直觀的方法是分段線性擬合（PLR），即在每個變量維度上將時間序列分段，并采用每一段的均值來表示該分段，構成該多元時間序列在該變量維度上特征。最后將每個變量維度上獲得的特征依次排列構成多元時間序列特征向量，即將多元問題轉化為一元問題［9］。然而，多元時間序列具有時間和變量兩個維度，這種做法只考慮時間維度而忽視了變量維度。多元時間序列各個變量之間往往存在一定的聯系，某個時刻某個變量維度中出現的特征在其他相關的變量維度也會有所體現。

多維分段是指在進行分段擬合時，在所有變量維度上同時進行分段，在降維的同時也保留了變量之間的關聯關系。例如，在人體行走時，左膝高度和右膝高度是兩個相關的變量，圖1（a）和圖1（b）分別是對一個連續的行走動作進行單維分段和多維分段后的結果［9］。可以看出，由于數據誤差的存在，多維分段的意義要遠大于單維分段。

文獻［9］使用多維分段的分段方式，采用每一段的趨勢和時間跨度來進行特征表示。但是，基于趨勢和時間跨度的特征表示只關注分段上的趨勢信息，丟失了分段的值域信息，若兩條序列的趨勢基本相同但值信息差別很大，這種特征表示方法并不能體現出兩條序列之間的差異性。基于此，本文將分段均值信息加入到分段特征中，將多元時間序列的趨勢和均值信息作為序列特征。

在多維分段之后，在所有變量維度上，均選擇對應擬合多項式的一次項系數k，分段均值a和分段時間跨度l作為分段特征。若具有m個維度的多元序列被分成S段時，該序列可用如下m×S的矩陣表示：

針對多元時間序列，考慮到變量之間的差異性，尤其是在量綱上變量之間的差異可能表現得特別突出，需要對提取到得特征矩陣做標準化處理，本文對三個特征分別做如式（2）～（4）所示的處理：

標準化處理之后，得到的轉換后的特征矩陣如下所示。

3 基于動態權重的動態時間彎曲距離

度量多元時間序列之間的相似性，實質上是比較提取到的特征矩陣之間的相似性。由于同一數據集下所有多元時間序列具有相同的變量個數，所以特征矩陣的行數是相同的；但不同序列的分段可能不同，所以矩陣的列數一般差別不一，因此需要能用于不同列數的特征矩陣之間比較的距離度量方法。

特征矩陣可以看作原始多元時間序列在多維分段之后的特征序列，矩陣的列數不同即序列的長短不一。動態時間彎曲距離（DTW）能通過對時間軸的彎曲解決兩個不同長度序列之間相似性度量的問題，因此可以用于特征矩陣之間的比較。而原始的DTW在計算最佳路徑的同時，可能會因為追求累計距離最小化而將某一序列上的一個點對應到另一序列上的多個點上，繼而帶來畸形匹配問題。

畸形匹配會因為時間序列被嚴重壓縮而丟失序列特征，對原始時間序列距離的度量也就變得不再準確，若在得到多元時間序列序列特征矩陣（5）之后直接使用原始DTW進行距離度量，也不可避免地會遇到畸形匹配的問題。基于此，本文提出一種動態權重動態時間彎曲距離，該方法為每個序列點賦予權值，在動態規劃求解最佳彎曲路徑的過程中，動態地調整每個點的權值，一個序列點被匹配的次數越多，其權值也就越小，與其他點的匹配距離就越大，被再次匹配的可能性就越小。

經過標準化處理得到的的特征矩陣（5），可以進一步簡化表示為X=[x1，x2，x3…xS]，其中xi指多維分段后第i個分段區間包含的m個變量的特征值，可以將其當作一條序列上的第i個序列點。兩條序列X和Y中的兩個序列點xi，yj之間的基礎DTW距離可以定義為

它體現了X和Y在第i段擬合和第j段擬合上所有變量維度的累計差異。由于多元時間序列不同維度代表的實際意義不同，對累計差異的貢獻度也存在差異，因此需要為每個變量賦予一定的權重。在式（6）中，使用ωt表示第t個變量所分配的權重值，且ωt的值滿足式（7）：分別表示兩個擬

合段xi和yj在第t個變量上趨勢、均值和時間跨度上的差異性，ε、λ和γ則分別代表三者差異的權重值，同時有下式成立：

在DWDTW距離中，第i個擬合段的權重定義如下：

其中，t表示了擬合段在求解過程中被匹配的次數，擬合段的初始權重為1，被匹配的次數越多，即t越大，擬合段的權重ωi(t)越小。為了防止權重衰減過快，引入權重衰減系數η，η越大，權重衰減越快，其取值在( 0 ，0.1)區間內，通常取0.05。同時，考慮到當兩條序列長度不同，特別是長度差異較為明顯時，勢必會有短序列上一個點對應長序列上多個點的情況，此時不應被判定為畸形匹配，對長序列上的點應給予較大的多次匹配寬容度。因此，引入序列的長度比值k，其定義如下：

S和S'分別代表特征表示之后兩條序列的長度。當兩條序列的長度差異越明顯即k越小時，權重ωi(t)的減小速率也越小，寬容度也越大。

從式（9）可看出，擬合段的權重是在計算過程中自行確定且動態縮小的，其值僅與兩個序列的長度比和擬合段被匹配的次數有關，無需人為設定。引入動態權重信息后，兩條多元時間序列之間的DWDTW距離可以使用動態規劃的方法計算：

其中，DWDTW(i，j)表示第i個擬合段和第j個擬合段之間的DWDTW距離，DWDTW(1，1)=dbase(x1，y1)。ωi(t)表示了第i個擬合段當前的權重，式(i)表示在計算經過(i，j-1)→(i，j)的路徑的彎曲距離時，擬合段i被重復使用，因此需要在原距離基礎上乘以，增大該路徑的距離，以限制算法對其的選擇；同時，若最終算法依然選中該路徑，即式（11）選中式(i)，需要調整第i段的權值，進一步減小其權重。最終，DWDTW算法的描述如下。

4 實驗

4.1 實驗環境

軟件環境：Python3.6.0+Windows10操作系統

硬件環境：處理器Intel Core i5-3337U，內存8Gb，硬盤容量500Gb。

4.2 實驗數據

實驗使用的多元時間序列數據來自UCI數據集。其中，ASL［14］數據集記錄了來自5名手語采集者共95個語意的手語信號信息，每條序列包含22個連續變量，每個語意有27條序列。本文選擇了前10種 語 意（alive，all，answer，boy，building，buy，change（mind），cold，come，computer）共270個序列，序列長度不等且在47～95之間。REF［15］數據集是監控機械故障得到的數據集，包含了5個子數據集，數據分為4類，每個序列包含6個變量，序列長度為15，本文選擇了LP1數據子集共88條序列進行實驗。EEG［16］是由腦電圖像數據構成的數據集，實驗選取了alcoholic和control兩類數據，包含64個變量，序列長度256。本文選取編號為a_co2a0000364和c_co2c0000337的兩人各10次測試作為實驗數據，共20個多元時間序列。JV（Japa?nese Vowel）［17］記錄了日語元音的發音過程，序列長度在7～29之間，屬于多數算法表現都不理想的小規模的多元時間序列。

4.3 實驗結果及分析

在DTW距離度量中，數據點之間的基礎距離對度量結果產生直接的影響。在式（6）中，基礎距離的計算結果同樣會受到ε，λ，γ三者組合的影響，并最終影響到序列直接的距離計算結果。因此，本文首先介紹基于ASL數據集使用KNN分類確定最優參數的過程。文中選取K為10，即從測試集中尋找與測試序列的MS-DWDTW距離最小的10個序列，計算結果的查準率，查準率定義為

針對每種組合，分別使用10條不同的輸入序列，并計算平均查準率。為了不失一般性，這里為每個變量取相同的權重ωt，權重衰減速率η取值0.05。實驗結果如表1所示。注意，由于三者的和為1，表中γ的值并未直接給出。例如當ε=0.0，λ=0.0時，則有γ=1.0。

從表1可知，當ε=0.7，λ=0.2，γ=0.1時，取得最大的平均查準率0.94。可以注意到，在擬合段斜率分配了較小權重即ε取值較低的情況下，隨著均值差異權重λ的增大，平均查準率也在不斷增大，說明當趨勢特征差異不大時，序列的均值差異將主要影響度量結果。同時可以觀察到，表中第一列的數值均小于相應行上的其他列，同樣表明距離度量過程中引入的均值差異能夠提高度量精度，說明了其不可或缺的重要性。

下面基于MS-DWDTW方法在選取的不同特性的數據集上進行相似性比較，以驗證其準確性。本文在選取的數據集上對比了基于MS-DWDTW與MS-DTW、DTW、PD、TD和SVD的KNN算法在進行相似性查找時的查準率。其中，DTW方法直接使用原始數據和動態時間彎曲距離進行相似性度量，MS-DTW表示對原始數據采用本文的方法進行特征提取之后，使用原始DTW計算特征矩陣之間的距離。為了使實驗結果更具比較性和說服力，本文利用得到表1的實驗方法在每個數據集上確定表現最好的參數組合，參數選擇結果見表6。每種方法分別取與測試數據集中數據距離最小的1、5、10條序列，計算最終的平均查準率，實驗結果見表2～表5。

表1 ASL數據集不同的ε，λ，γ選擇下的平均查準率

表2 ASL數據集實驗結果

表5 JV數據集實驗結果

表6 不同數據集下ε，λ，γ選擇情況

表3 EEG數據集實驗結果

由表2～表5可知，基于MS-DWDTW的KNN算法在四個數據集上均能取得較好的平均查準率。在ASL和EEG數據集上，MS-DWDTW的平均查準率均為最高，MS-DTW和TD也能取得不錯的結果。但進一步對比發現，由于MS-DTW加入了均值信息作為序列特征，其結果要優于TD方法。同時，相比于MS-DTW，MS-DWDTW的平均查準率得到一定程度的提高，由此可知，在這兩個數據集上基于DTW算法的相似性度量出現了畸形匹配的情況，且對度量精度產生了一定的影響，而引入動態權重后有效改善了該問題。

此外，在EFG和JV兩個數據集上，MSDWDTW也取得了較好的結果，但從表4和表5可以看出，MS-DWDTW與MS-DTW的結果相差不大，說明序列的畸形匹配并不嚴重。同時，可以觀察到，TD算法在JV數據集上取得了較低的平均查準率，原因在于JV數據集序列較短且趨勢變化不明顯，針對此類數據集，其已經喪失有效性，而MS-DWDTW仍能通過增大均值權重減小趨勢權重的方法取得較為準確的結果。

表4 REF數據集實驗結果

5 結語

本文提出的基于多維分段和動態權重DTW的多元時間序列相似性度量方法，在各個變量維度上統一分段，保證了分段之后變量之間的相關性，選取分段后擬合線段的斜率、均值和時間跨度作為多元時間序列的特征表示，能比較準確描述多元時間序列的趨勢和值特征。本文提出的DWDTW距離度量也能在不增加額外參數的情況下有效避免傳統DTW距離的畸形匹配問題，進一步提高多元時間序列距離度量的準確度。實驗結果表明，MS-DWDTW能在多個數據集上取得較好的度量效果，同時能夠通過調整最優參數來適應多種類型的數據。但是，MS-DWDTW的參數較多，模型參數優化較為復雜。接下來的工作主要是研究如何優化模型參數選擇方法，并將MS-DWDTW方法用在多元時間序列數據挖掘任務如聚類、分類中去。