邱蓮鵬，宋承云

（重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054）

0 引言

時(shí)間序列數(shù)據(jù)在生物系統(tǒng)［1］、遙感［2］、多媒體［3］、手寫［4］和運(yùn)動(dòng)物體軌跡追蹤［5］等領(lǐng)域中廣泛分布。與靜態(tài)數(shù)據(jù)不同，時(shí)間序列數(shù)據(jù)具有完全捕獲觀察對(duì)象的時(shí)間演變的優(yōu)勢(shì)。數(shù)據(jù)挖掘研究人員提出了大量的算法適應(yīng)這種類型的數(shù)據(jù)，這產(chǎn)生了大量的研究任務(wù)，如時(shí)間序列分類［6］、聚類［7］和分割［8］。時(shí)間序列處理中的一項(xiàng)基本任務(wù)是量化兩個(gè)時(shí)間序列之間的相似程度，因此，距離/相似性度量的選擇直接影響時(shí)間序列數(shù)據(jù)分類和聚類的效果［9］。

動(dòng)態(tài)時(shí)間規(guī)整（Dynamic Time Warping，DTW）［10］通過動(dòng)態(tài)規(guī)劃思想尋找兩條時(shí)間序列之間的最佳匹配路徑，從而度量時(shí)間序列相似性。與傳統(tǒng)的相似性度量方法歐氏距離（Euclidean Distance，ED）等相比，DTW 能有效應(yīng)對(duì)時(shí)間序列的振幅變化、相位偏移等問題，已得到更廣泛應(yīng)用。然而，DTW 會(huì)引起彎曲路徑過度拉伸和過度壓縮，導(dǎo)致“病態(tài)路徑”，即一個(gè)時(shí)間序列上的一個(gè)點(diǎn)匹配另一個(gè)時(shí)間序列上的多個(gè)點(diǎn)，如圖1（a）所示。在這種情況下，無法準(zhǔn)確計(jì)算兩個(gè)同類時(shí)間序列之間的距離值，影響相似性度量的準(zhǔn)確性。為了解決該問題，研究者們提出了一些DTW 改進(jìn)算法，這些方法主要分為兩類：一類以提取形狀特征考慮局部信息；另一類以懲罰彎曲路徑減少“病態(tài)路徑”。

圖1 病態(tài)路徑示意圖Fig.1 Schematic diagram of pathological path

在提取形狀特征信息方面，為了在兩個(gè)序列之間獲得直觀正確的“特征到特征”對(duì)齊，Keogh 等［11］引入了導(dǎo)數(shù)DTW（Derivative DTW，DDTW），它計(jì)算時(shí)間序列的一階導(dǎo)數(shù)，然后通過DTW 對(duì)齊兩個(gè)導(dǎo)數(shù)序列。DDTW 只關(guān)注單個(gè)時(shí)間點(diǎn)的信息，沒有考慮到上下文信息，因此王見等［12］提出了一種結(jié)合形狀特征和上下文信息的多維DTW 算法。該算法首先對(duì)多維時(shí)間序列計(jì)算一階梯度，然后利用一階梯度的特征查找最優(yōu)對(duì)齊路徑。盡管以上方法通過重新調(diào)整DTW 度量，在某些數(shù)據(jù)集上取得了較好的結(jié)果，但他們沒有修改原始的DTW 算法。

在懲罰彎曲路徑方面，Jeong 等［13］提出加權(quán)DTW（Weighted DTW，WDTW），這是一種基于懲罰的DTW，WDTW 在計(jì)算兩點(diǎn)之間的距離時(shí)考慮了兩點(diǎn)之間的相位差。Batista 等［14］提出了一種復(fù)雜度不變的距離度量，它本質(zhì)上是通過乘以復(fù)雜度校正因子校正現(xiàn)有的距離度量（ED、DTW）。另外，窗口約束是一種更直觀的解決方案，它限制了每個(gè)點(diǎn)可以對(duì)齊的范圍，約束彎曲路徑的方法主要有全局約束和局部約束兩種：全局約束將彎曲路徑的演化限制到特定區(qū)域，使它盡 可能呈 對(duì)角線，Sakoe-Chiba［15］和Itakura-Parallelogram［16］約束是兩種常見的全局約束。Morel等［17］提出了局部約束方式，利用時(shí)間序列局部結(jié)構(gòu)信息約束彎曲路徑的搜索；然而選擇合適的彎曲約束需要應(yīng)用領(lǐng)域先驗(yàn)知識(shí)，因此很難確定參數(shù)大小。

本文借鑒降噪自動(dòng)編碼器（Denoising AutoEncoder）［18］的算法思想，提出了出一種噪聲魯棒的DTW（Noise robust DTW，NoiseDTW）算法。傳統(tǒng)的DTW 和DTW 的變體總是計(jì)算兩個(gè)時(shí)間序列數(shù)據(jù)之間的最小距離之和，不能提供適當(dāng)?shù)木植科ヅ洌辉谠肼暤挠绊懴?，容易出現(xiàn)兩個(gè)同類型的時(shí)間序列的累積距離值大于兩個(gè)不同類型的時(shí)間序列的累積距離值的情況，從而增加分類誤差。降噪自動(dòng)編碼器為了在處理相似樣本時(shí)模型有更好的泛化能力，將訓(xùn)練數(shù)據(jù)加噪聲后再輸入模型，從而提取到更魯棒性的表征。基于此，在時(shí)間序列中加入少量噪聲后執(zhí)行DTW 算法，以增強(qiáng)算法的噪聲抑制能力。如圖1（b）所示，在原始的信號(hào)中加噪聲后，解決了序列對(duì)齊中存在的一個(gè)點(diǎn)對(duì)齊多個(gè)點(diǎn)的問題。針對(duì)噪聲的隨機(jī)性問題，NoiseDTW 算法通過多次添加噪聲的方式提升了算法的穩(wěn)定性。

1 相關(guān)工作

DTW 是一種利用動(dòng)態(tài)規(guī)劃在兩個(gè)時(shí)間序列之間搜索最佳匹配路徑的算法。為了應(yīng)對(duì)信號(hào)的相位偏移和振幅變化，DTW 將序列進(jìn)行非線性彎曲，以測(cè)量不同長(zhǎng)度序列之間的相似性，DTW 算法的概述如下。

假設(shè)單變量時(shí)間序列P的長(zhǎng)度為M，Q的長(zhǎng)度為N，其中P=(p1，p2，…，pM)，Q=(q1，q2，…，qN)。圖2（a）和圖2（b）分別表示時(shí)間序列P和Q，為了DTW 能夠計(jì)算P和Q之間的相似度，構(gòu)建一個(gè)大小為M×N的距離矩陣D（如圖2（c）所示），其中的元素d(pi，qj)表示pi與qj之間的距離，通過式（1）計(jì)算：

圖2 DTW距離矩陣Fig.2 Distance matrix of DTW

為了保證彎曲路徑匹配的有效性，w通常需要滿足3 個(gè)約束條件，即邊界條件、連續(xù)性條件和單調(diào)性。邊界條件代表路徑必須從w1開始到wk結(jié)束，連續(xù)性條件表示必須一步一步地尋找最優(yōu)路徑，單調(diào)性約束彎曲路徑向前移動(dòng)。DTW 的目標(biāo)是在所有滿足上述約束條件的w中，通過動(dòng)態(tài)規(guī)劃思想確定距離最短的一條路徑w。假設(shè)DTW(P，Q)表示d(pi，qj)的累積距離，為了確定P和Q之間的最佳對(duì)齊路徑，通過式（2）計(jì)算最短的一條路徑的累積距離DTW(P，Q)，根據(jù)這條路徑對(duì)齊兩條時(shí)間序列，可視化結(jié)果如圖1 所示。

其中：M≥i＞1 并且N≥j＞1，D(M，N)為DTW 度量下序列P和Q的最小距離，可知DTW(P，Q)=D(M，N)。當(dāng)i，j=1時(shí)，DTW(P，Q)=D(1，1)=d(p1，q1)。

2 NoiseDTW 算法

2.1 算法原理

針對(duì)DTW 在噪聲的影響下容易出現(xiàn)“病態(tài)路徑”的問題，本文提出了對(duì)噪聲魯棒的NoiseDTW 算法。算法原理示意圖如圖3 所示。

圖3 NoiseDTW 算法的原理示意圖Fig.3 Schematic diagram of principle of NoiseDTW algorithm

對(duì)于給定的兩個(gè)時(shí)間序列P和Q（如圖3（a）所示），加入均值為0、方差為α的高斯噪聲，得到時(shí)間序列nP=(np1，np2，…，npi，…，npM) 和nQ=(nq1，nq2，…，nqj，…，nqN)（如圖3（b）所示）。設(shè)D1是nP和nQ的距離矩陣，大小為M×N，D1的計(jì)算如式（3）所示：

在式（3）計(jì)算加入噪聲之后的兩個(gè)時(shí)間序列的距離矩陣D1中調(diào)用遞歸式（2）搜索累積距離DTW(nP，nQ)最小的彎曲路徑W1。重復(fù)添加隨機(jī)噪聲、計(jì)算距離矩陣和搜索彎曲路徑，在第e次迭代后，得到e個(gè)距離矩陣(D1，D2，…，De)，搜索相應(yīng)的距離矩陣得到e條彎曲路徑(W1，W2，…，We)，每條彎曲路徑代表每次迭代產(chǎn)生的距離矩陣中累積距離最短的路徑（如圖3（c）所示）。

明顯地，越多的彎曲路徑通過位置(i，j)，表明pi和qj具有很強(qiáng)的相似性，應(yīng)該給予較大的匹配可能性。因此，NoiseDTW 統(tǒng)計(jì)每個(gè)點(diǎn)(i，j)的彎曲路徑通過的次數(shù)，以構(gòu)建新的距離矩陣D'（如圖3（d）所示），大小為M×N，計(jì)算公式如式（4）。

進(jìn)一步，調(diào)用遞歸式（2）找到最優(yōu)的彎曲路徑。根據(jù)上一步得到的最優(yōu)路徑，對(duì)齊時(shí)間序列P和Q（如圖3（e）所示）。具體的NoiseDTW 算法偽代碼如算法1 所示。

算法1 NoiseDTW 算法。

算法1 的第7）行和第12）行中的函數(shù)dp代表動(dòng)態(tài)規(guī)劃過程，DTW 算法在動(dòng)態(tài)規(guī)劃過程中有5 種步進(jìn)模式可供選擇［19］。如圖4 所示，DTW 步進(jìn)模式主要包括 “symmetric1”“symmetric2”“asymmetric”“rabinerJuang”和“symmetric5”。步進(jìn)模式定義了匹配點(diǎn)對(duì)之間的轉(zhuǎn)換和相應(yīng)權(quán)重，填充的圓代表點(diǎn)對(duì)匹配的當(dāng)前位置，連接線表示從當(dāng)前位置到下一個(gè)空心圓的權(quán)重，連接線上的數(shù)字表示權(quán)重值?！皊ymmetric1”是被廣泛使用的按對(duì)稱性和邊界分類的步進(jìn)模式。“symmetric2”是基于局部連續(xù)性約束、坡度權(quán)重和平滑度這3 個(gè)特征的步進(jìn)模式，相較于“symmetric1”，“symmetric2”模式賦予對(duì)角線方向更多的權(quán)重?！癮symmetric”“rabinerJuang”和“symmetric5”模式可以跳過特定的元素（實(shí)心圓未與空心圓匹配）。本文采用默認(rèn)的步進(jìn)模式（圖4（a）中的模式），它的遞歸公式如式（2）所示。

圖4 5種步進(jìn)模式Fig.4 Five stepping patterns

2.2 KNN-NoiseDTW 時(shí)間序列分類

Geler 等［20］提出的一種K-近 鄰（K-Nearest Neighbors，KNN）結(jié)合約束DTW 的非常有效的分類器，可以根據(jù)已有標(biāo)簽的時(shí)間序列數(shù)據(jù)預(yù)測(cè)未知的時(shí)間序列數(shù)據(jù)的類別。NoiseDTW 是距離度量算法，需要結(jié)合分類器分類時(shí)間序列數(shù)據(jù)，因此本文結(jié)合KNN 分類器提出了KNN-NoiseDTW 算法。假設(shè)有N對(duì)有標(biāo)簽數(shù)據(jù){(x1，y1)，(x2，y2)，…，(xN，yN)}，其中yi∈{1，2，…，M}代表時(shí)間序列數(shù)據(jù)不同的類別。KNNNoiseDTW 算法的目標(biāo)是對(duì)每一個(gè)沒有標(biāo)簽的數(shù)據(jù)xi′分配一個(gè)對(duì)應(yīng)的標(biāo)簽yi′，KNN-NoiseDTW 的流程如算法2 所示。

算法2KNN-NoiseDTW 算法。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)集

本文使用廣泛用作評(píng)估時(shí)間序列數(shù)據(jù)挖掘算法基準(zhǔn)的公共UCR 時(shí)間序列文檔［21］。這些數(shù)據(jù)集來源于各個(gè)領(lǐng)域，包括醫(yī)學(xué)、氣象學(xué)、計(jì)算機(jī)視覺等。數(shù)據(jù)集在時(shí)間序列長(zhǎng)度方面各不相同，每個(gè)數(shù)據(jù)集由訓(xùn)練集和測(cè)試集兩部分組成。本文在 BeetleFly、BirdChicken、DistalPhalanxTW、Fish、Gun-Point、Symbols、ToeSegmentation1 和ToeSegmentation2 這8個(gè)噪聲影響比較明顯數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，其中時(shí)間序列長(zhǎng)度分布于80～512。數(shù)據(jù)集信息如表1 所示。

表1 數(shù)據(jù)集信息Tab.1 Information of datasets

3.2 參數(shù)分析

NoiseDTW 算法中所涉及的超參數(shù)有高斯噪聲的方差α和迭代次數(shù)e。對(duì)于噪聲方差α，本文選擇α=0.100、α=0.010、α=0.001 這3 種情況下對(duì)8 個(gè)時(shí)間序列數(shù)據(jù)集分類。從圖5 可以看出，總體上，在α=0.010 時(shí)分類準(zhǔn)確較高于其他兩種情況。對(duì)于迭代次數(shù)e，本文選擇5、10、15、20 來實(shí)驗(yàn)，如圖6 中所示，e在4 種情況在8 個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，從圖6 可以看出，總體地，算法在e=10 的時(shí)候分類準(zhǔn)確率最高。因此，在下文的實(shí)驗(yàn)中，本文選擇α=0.010，e=10。

圖6 不同e下的分類準(zhǔn)確率Fig.6 Classification accuracy under different e

3.3 模擬對(duì)齊實(shí)驗(yàn)

在Gun-Point 數(shù)據(jù)訓(xùn)練集中標(biāo)簽為1 的時(shí)間序列中隨機(jī)選擇一條時(shí)間序列，通過縮放、拉伸得到變形之后的時(shí)間序列匹配。如圖7（a）所示，第一條曲線表示原始時(shí)間序列，第二條曲線為經(jīng)過縮放、伸縮之后的時(shí)間序列，中間豎線條為匹配路徑，方框中為對(duì)比的主要區(qū)域。傳統(tǒng)的歐氏距離是點(diǎn)對(duì)點(diǎn)匹配，得到的匹配路徑如圖7（b）中方框區(qū)域所示，可以看出這種一對(duì)一的匹配不適用于不等長(zhǎng)的時(shí)間序列。DTW結(jié)果如圖7（c）所示，出現(xiàn)明顯的一條時(shí)間序列的其中一個(gè)點(diǎn)對(duì)應(yīng)另一條時(shí)間序列的多個(gè)點(diǎn)，即“病態(tài)路徑”。圖7（d）表示W(wǎng)DTW 的實(shí)驗(yàn)結(jié)果，本文在此處將權(quán)重因子設(shè)置為0.2。圖7（e）和圖7（f）分別是NoiseDTW 在α=0.01 下，e=5 和e=10 的實(shí)驗(yàn)結(jié)果，可以看出，在e=10 下更接近真實(shí)匹配路徑。

圖7 四種方法對(duì)齊效果與真實(shí)匹配路徑的對(duì)比Fig.7 Comparison of alignment results between four methods and ground truth

3.4 時(shí)間序列分類實(shí)驗(yàn)

由于ED、DTW、Sakoe-Chiba 窗口DTW［20］、WDTW 和NoiseDTW 都是度量距離的算法，需要結(jié)合分類器進(jìn)行分類實(shí)驗(yàn)。為了方便，本文在KNN-NoiseDTW 中采用1-NN 分類器，優(yōu)點(diǎn)是沒有參數(shù)，分類誤差僅取決于相似性度量算法。本文將以上5 種算法在8 個(gè)時(shí)間序列數(shù)據(jù)集上對(duì)比分類準(zhǔn)確率，如表2 所示。先前的研究人員已經(jīng)發(fā)布了UCR 數(shù)據(jù)集上歐氏距離、DTW 和Sakoe-Chiba 窗口DTW 的1NN 分類準(zhǔn)確率報(bào)告［21］，因此，本文在此基礎(chǔ)上增加了WDTW 和NoiseDTW的分類準(zhǔn)確率。NoiseDTW 較好的對(duì)齊路徑可以提高兩個(gè)時(shí)間序列數(shù)據(jù)相似性度量的準(zhǔn)確性，進(jìn)一步降低分類誤差。從表2 可以看出，分類準(zhǔn)確率在8 個(gè)時(shí)間序列數(shù)據(jù)集上分別比次優(yōu)算法提高了1～15 個(gè)百分點(diǎn)。

表2 8個(gè)時(shí)間序列數(shù)據(jù)集上的分類正確率Tab.2 Classification accuracy on 8 time series datasets

更直觀地，本文用折線圖來展示5 種算法在不同數(shù)據(jù)集上的錯(cuò)誤率（如圖9 所示）。分類錯(cuò)誤率計(jì)算方式為：

從圖8 可以看出，首先，本文算法在整體上有較高的分類準(zhǔn)確率。其次，尤其對(duì)于BirdChicken、ToeSegmentation1 這兩個(gè)數(shù)據(jù)集上分類誤差降低明顯。在Fish、Gun-Point、Symbols 這3 個(gè)數(shù)據(jù)集上有小幅提升。為了分析原因，本文給出了 BirdChicken、DistalPhalanxTW、Fish、Gun-Point、Symbols 和ToeSegmentation1 數(shù)據(jù)集中訓(xùn)練集時(shí)序數(shù)據(jù)的時(shí)滯對(duì)比（如圖9 所示）。從圖9 可以看出，圖9（b）～（d）時(shí)間序列數(shù)據(jù)之間在水平方向位移和扭曲不明顯，所以NoiseDTW提升不顯著。然而，在圖9（a）時(shí)間序列數(shù)據(jù)和圖9（f）時(shí)間序列數(shù)據(jù)之間水平方向存在明顯的扭曲和位移，這說明NoiseDTW 在這類數(shù)據(jù)集上具有更好的性能。

圖8 分類錯(cuò)誤率Fig.8 Classification error rate

圖9 多個(gè)數(shù)據(jù)集上的時(shí)滯對(duì)比Fig.9 Time lag comparison on multiple datasets

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

本文將NoiseDTW 與DTW、Sakoe-Chiba 窗 口DTW 和WDTW 進(jìn)行時(shí)間復(fù)雜度的對(duì)比分析，NoiseDTW 的時(shí)間復(fù)雜度是O(deMN)，DTW 和WDTW的復(fù)雜度分別是O(dMN)、O(dMN2)，其中d為訓(xùn)練集樣本數(shù)，e為迭代次數(shù)（常數(shù)），M和N為樣本的長(zhǎng)度。Sakoe-Chiba 窗口DTW 只是縮小距離矩陣的搜索范圍，在時(shí)間序列分類過程中，復(fù)雜度的量級(jí)和DTW一樣，因此不再贅述。

進(jìn)一步，測(cè)試算法的實(shí)際運(yùn)行時(shí)間。本實(shí)驗(yàn)在Windows 10 專業(yè)版64 位操作系統(tǒng)環(huán)境下運(yùn)行，處理器為Intel Core i5-9400 CPU @2.90 GHz（雙 核），軟件為Matlab R2021a 64 位。實(shí)驗(yàn)設(shè)置NoiseDTW 的迭代次數(shù)e=10，在8 個(gè)數(shù)據(jù)集上，3 種算法的運(yùn)行時(shí)間以及時(shí)間差值如表3 所示。DTW 時(shí)間開銷最小，由于加權(quán)的影響，WDTW時(shí)間消耗更大一些，數(shù)據(jù)集長(zhǎng)度越長(zhǎng)，測(cè)試集數(shù)越大，時(shí)間差越明顯。本文算法是多次加噪聲，雖然比DTW 稍慢一點(diǎn)，但是它的運(yùn)行時(shí)間是隨著加噪聲的次數(shù)變化的，如果只加1 次噪聲，NoiseDTW 的時(shí)間消耗就近似于DTW。

表3 3種算法的時(shí)間開銷對(duì)比 單位：sTab.3 Comparison of time overhead of three algorithms unit：s

4 結(jié)語

針對(duì)DTW 容易出現(xiàn)“病態(tài)對(duì)齊”問題，本文提出對(duì)噪聲魯棒的NoiseDTW 算法。通過添加高斯噪聲，在兩個(gè)時(shí)間序列的多條可能對(duì)齊路徑中，采用動(dòng)態(tài)規(guī)劃思想，找到最優(yōu)的一條對(duì)齊路徑。在UCR 時(shí)間序列數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，與ED 距離、DTW、彎曲窗口的DTW 和WDTW 時(shí)間序列距離度量算法相比，本文算法在大多數(shù)數(shù)據(jù)集上具有更高的準(zhǔn)確率和時(shí)間效率。同時(shí)，NoiseDTW 算法的改善空間也很大，比如超參數(shù)的設(shè)置，將來我們將會(huì)繼續(xù)研究對(duì)不同數(shù)據(jù)采用自適應(yīng)高斯噪聲參數(shù)，以提高時(shí)間序列的相似性度量效果。