改進(jìn)DTW下界函數(shù)的距離度量方法研究

王 超，龍英文，殷煒宏，黃 勃

上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620

時(shí)間序列數(shù)據(jù)通常出現(xiàn)在許多應(yīng)用領(lǐng)域，例如醫(yī)學(xué)的腦電波和心電數(shù)據(jù)[1]、氣象天文數(shù)據(jù)[2]、股票證券交易數(shù)據(jù)[3]和工業(yè)用電數(shù)據(jù)[4]等。盡管如今的數(shù)據(jù)庫隨著相關(guān)應(yīng)用的增加而持續(xù)增長，但一個(gè)普遍的需求是去找到時(shí)間序列之間的相似性[5]。作為一種度量?jī)蓚€(gè)序列相似程度的方法，時(shí)間序列相似性度量是時(shí)間序列異常檢測(cè)、聚類、分類、相關(guān)規(guī)則提取和模式識(shí)別等工作的重要子進(jìn)程[6]。因此，尋找一種合適的度量方法將會(huì)對(duì)后續(xù)的時(shí)間序列挖掘任務(wù)的效率和性能產(chǎn)生深遠(yuǎn)影響[7]。

在相似性度量方法中，動(dòng)態(tài)時(shí)間彎曲（dynamic time warping，DTW）定義了序列之間最優(yōu)對(duì)齊匹配關(guān)系，并支持兩個(gè)不等長時(shí)間序列之間的相似性度量和時(shí)間軸的伸縮與彎曲。不同于歐氏距離（ED）“點(diǎn)對(duì)點(diǎn)”的線性映射匹配策略，且要求兩條時(shí)間序列的長度必須相等。DTW允許將向量分量與從完全對(duì)應(yīng)的位置“漂移”進(jìn)行比較，即非線性映射[8]，用于尋求兩個(gè)序列間的最優(yōu)對(duì)齊方式，是一種常規(guī)的距離度量方法。

DTW的距離度量效果影響著挖掘工作結(jié)果，許多研究者都將動(dòng)態(tài)時(shí)間彎曲的改進(jìn)工作作為主要研究任務(wù)。其改進(jìn)任務(wù)主要分為兩類[9]：（1）設(shè)計(jì)出滿足動(dòng)態(tài)時(shí)間彎曲下界要求的下界函數(shù)；（2）針對(duì)動(dòng)態(tài)時(shí)間彎曲算法過程的改進(jìn)。

相似性度量工作較多用到下界函數(shù)，原始DTW距離度量的時(shí)間復(fù)雜度高，因此研究者提出利用DTW的下界，過濾掉不滿足相似性要求的序列，有效提高了時(shí)間序列相似性搜索的性能。為保證準(zhǔn)確高效的相似性度量，DTW下界距離應(yīng)滿足以下三個(gè)條件[10-11]：

（1）有效性：下界距離度量的時(shí)間計(jì)算成本應(yīng)保持在低位值；

（2）緊湊性：下界距離的度量結(jié)果應(yīng)盡可能接近DTW距離，即保證候選集在規(guī)定量級(jí)的情況下，從而減少后期再處理的工作量；

（3）正確性：經(jīng)過下界距離函數(shù)篩選得到候選序列，必須包含所有滿足條件的序列，即不準(zhǔn)出現(xiàn)誤報(bào)、漏報(bào)現(xiàn)象。

Yi[12]、Kim[13]、Keogh[14]等人分別提出支持DTW距離度量的邊界距離函數(shù)。LB_Yi是由Yi等人提出的首個(gè)針對(duì)DTW的低邊界函數(shù)。為了構(gòu)建DTW下界距離，該函數(shù)以一條時(shí)間序列作為基本度量序列，將另一條序列中小于基本度量序列的最小值點(diǎn)集和大于該基本序列最大值的點(diǎn)集作為特征，從而完成構(gòu)建。Kim等人提出了LB_Kim函數(shù)，它比LB_Yi更接近真實(shí)DTW下界距離，其核心思想是：選出兩個(gè)序列的第一個(gè)序列特征值、最后一個(gè)序列特征值、最大值及最小值這4個(gè)特征值，然后計(jì)算對(duì)應(yīng)特征值的絕對(duì)差值，以最值作為邊界距離，構(gòu)建DTW下界距離函數(shù)。Keogh等人利用全局時(shí)間彎曲約束，構(gòu)造約束動(dòng)態(tài)彎曲路徑的上下邊界，并提出了下界距離函數(shù)LB_Keogh，它比LB_Kim和LB_Yi更接近真實(shí)DTW下界距離。

Jeong、Sakurai分別針對(duì)算法過程進(jìn)行改進(jìn)。文獻(xiàn)[15]Jeong等人為了優(yōu)化動(dòng)態(tài)時(shí)間彎曲度量效果，提出了WDTW方法，通過賦予在距離矩陣中時(shí)間序列數(shù)據(jù)點(diǎn)的相位差高的元素更高的懲罰權(quán)重，避免了時(shí)間序列過度彎曲和不合理匹配的問題。而文獻(xiàn)[16]Sakurai等人利用early stopping，即提前終止思想，在計(jì)算累計(jì)矩陣時(shí)，當(dāng)出現(xiàn)比當(dāng)前累積值大的單元格時(shí)，終止該單元格后的行（或列）之后的所有單元格的計(jì)算，從對(duì)角線的新單元格開始計(jì)算，減少計(jì)算成本。

文獻(xiàn)[17]Górecki等人將DTW和時(shí)間序列的一階導(dǎo)數(shù)相融合，即根據(jù)時(shí)間序列的一般形狀特征，提出一種新的距離度量方式DDDTW，該距離度量經(jīng)過實(shí)驗(yàn)證明取得了不錯(cuò)的效果。文獻(xiàn)[18]Górecki等人對(duì)上述方法做出進(jìn)一步改進(jìn)，在上述研究成果的前提下結(jié)合時(shí)間序列特征的二階導(dǎo)數(shù)，又進(jìn)而提出一種新的距離度量2DDDTW。該相似性度量方法與文獻(xiàn)[17]相比，分類效果有了更進(jìn)一步。

文獻(xiàn)[19]晏臻等人提出一種改進(jìn)的基于下界函數(shù)的DTW相似性搜索方法——NLB-FDTW。該方法從下界函數(shù)入手，首先經(jīng)過序列標(biāo)準(zhǔn)化后，再采用LB_Kim對(duì)序列進(jìn)行首次下界函數(shù)過濾，篩選掉那些不相似的序列，然后再采用所提出的LB_Lweng方法進(jìn)行二次過濾，即采用LB_Lweng下界距離度量序列之間的相似距離，并初始化閾值ε，若LB_Lweng距離大于ε，則將該候選序列剔除相似候選序列集合，否則就將該序列加入到相似候選集中。最后，再從相似候選集中找出k個(gè)最為相似的序列進(jìn)行相似匹配。

但到目前為止，已有的基于下界函數(shù)的DTW距離度量方法仍缺少良好的均衡性，即上述的現(xiàn)存研究方法雖然保證了算法的準(zhǔn)確性卻難以提高算法的時(shí)間效率，而有些方法降低了計(jì)算成本，卻無法保證度量的準(zhǔn)確性與穩(wěn)定性。

針對(duì)上述問題，本文綜合考慮了度量的準(zhǔn)確性和時(shí)間效率，采用提前終止思想，找到一種基于DTW的下界距離函數(shù)。即在下界距離函數(shù)的基礎(chǔ)上，提出一種基于early stopping的DTW下界距離函數(shù)方法。進(jìn)而，通過實(shí)驗(yàn)對(duì)所提方法進(jìn)行計(jì)算效率、緊湊性和分類準(zhǔn)確性分析。

1 相關(guān)定義

定義1（時(shí)間序列）時(shí)間序列是一組由連續(xù)時(shí)間變量和對(duì)應(yīng)的特征值組成的有序集合[20]，從時(shí)間序列的角度來看，每個(gè)數(shù)據(jù)單元可以被抽象成一個(gè)二元組(t,v)，其中t為時(shí)間變量，v為特征值變量。定義時(shí)間序列X={x1=(t1,v1),x2=(t2,v2),…,xn=(tn,vn)}，并滿足ti＜ti+1(i=1,2,…,n-1)，并且保證時(shí)間間隔固定，一般取Δt=ti+1-ti=1。此時(shí)，將時(shí)間序列簡(jiǎn)記為：

定義2（DTW距離）設(shè)時(shí)間序列S={s1,s2,…,sn}，Q={q1,q2,…,qm}，DTW距離實(shí)際上就是找到序列S與Q上每個(gè)點(diǎn)之間的對(duì)齊匹配關(guān)系[21]，如圖1（a）所示，這種匹配關(guān)系可能有很多種，每一種匹配關(guān)系可以用一條彎曲路徑表示，如圖1（b）所示。也就是說，序列間的匹配關(guān)系與彎曲路徑是一一對(duì)應(yīng)的關(guān)系。

圖1 彎曲路徑與點(diǎn)對(duì)點(diǎn)匹配結(jié)果Fig.1 Matching result of warping path and point-to-point

為計(jì)算S和Q的DTW距離，需要構(gòu)造一個(gè)m×n的矩陣，其中：

為向量點(diǎn)si和qj間的基距離，其中i=1,2,…,n，j=1,2,…,m，可根據(jù)不同情況選擇不同距離度量。本文將采用歐氏距離作為基距離，即l=2。為計(jì)算DTW(S,Q)，需找到一條最優(yōu)的彎曲路徑，其中彎曲路徑W中的第k個(gè)元素定義為wk=()i,j k，由此可得：

彎曲路徑長度滿足max(m,n)≤K≤m+n-1。

彎曲路徑W必須滿足3個(gè)特性[22]：

（1）邊界性：路徑起始于(s1,q1)、終止于(sm,qm)，它表示兩個(gè)序列的起始點(diǎn)和終止點(diǎn)的對(duì)應(yīng)匹配；

（2）連續(xù)性：彎曲路徑上的任意兩個(gè)相鄰元素wk(i,j),wk-1(i",j")需滿足0≤|i-i"|≤1,0≤|j-j"|≤1；

（3）單調(diào)性：若(i,j)和(i",j")為路徑上前后相鄰的兩個(gè)點(diǎn)，則要滿足i-i"≥0，j-j"≥0。

在眾多彎曲路徑中找到唯一最優(yōu)的路徑，使得累積距離達(dá)到最小：

為求式（4），則需要利用動(dòng)態(tài)規(guī)劃方法構(gòu)造一個(gè)代價(jià)矩陣γ。

其中，i=1,2,…,n，j=1,2,…,m，γ(0,0)=∞，γ(i,0)=γ(0,j)=∞。那么，γ(i,j)可以看成是當(dāng)前元素的基距離值與3個(gè)元素累積距離值的最小值之和。最終得到的γ(n,m)就是DTW距離度量S和Q的最小累積代價(jià)，即DTW(S,Q)=γ(n,m)。以此，便可找到最優(yōu)的彎曲路徑。

定義3（下界函數(shù)）對(duì)于時(shí)間序列的相似性度量[23]，若單純使用DTW度量，時(shí)間復(fù)雜度會(huì)很高。出于計(jì)算成本的角度考慮，可以根據(jù)設(shè)定條件利用快速下界算法篩選出較為匹配的候選序列，之后再進(jìn)行下一步的精確度量，從而加快時(shí)間序列度量精度。因此，任意兩條時(shí)間序列距離值的特點(diǎn)是，一定小于等于這兩者之間的DTW距離，即LB(S,Q)≤DTW(S,Q)，下一章在改進(jìn)DTW距離的同時(shí)也將證明該下界函數(shù)定理的合理性。

2 基于DTW下界函數(shù)的提前終止算法

2.1 彎曲路徑的全局約束

為了提高相似性度量效率，采用全局約束來提高度量算法的效率成為了關(guān)鍵，也就是規(guī)定了某個(gè)待查詢序列的某個(gè)點(diǎn)與候選序列的約束范圍內(nèi)的幾個(gè)點(diǎn)進(jìn)行動(dòng)態(tài)匹配。設(shè)時(shí)間序列S、Q的彎曲路徑上的元素為wk=(i,j)k，那么彎曲路徑的全局約束可以理解為對(duì)wk中k的限制，即其邊界為j-r≤i≤j+r。r表示了序列上某點(diǎn)的彎曲路徑局限性。對(duì)帶狀約束Sakeo-Chiba來說，r的取值與i不相關(guān)聯(lián)，如圖2（a）；而對(duì)于平行四邊形約束Itakura-Parallelogram來說，r是關(guān)于i的函數(shù)，如圖2（b）所示。本文將采用全局約束Sakeo-Chiba進(jìn)行相似性度量工作。

圖2 兩種彎曲窗口Fig.2 Two warping windows

2.2 基于early stopping的DTW距離度量

提前終止（early stopping）算法原理較為簡(jiǎn)單易懂。其核心思想為：在本次的距離計(jì)算中，若累積距離值達(dá)到預(yù)期設(shè)定的閾值，則立即終止本次計(jì)算，并開始下一輪的距離計(jì)算，根據(jù)此原理來達(dá)到節(jié)約計(jì)算成本的效果。如在計(jì)算DTW累積矩陣的某行列單元格，可以不必計(jì)算整行或者整列單元格的累積距離，通過這種算法思想來減少計(jì)算成本。這種計(jì)算方式尤其應(yīng)用于高維距離計(jì)算效果更好[24]。

性質(zhì)1假設(shè)時(shí)間序列S={s1,s2,…,sn}，Q={q1,q2,…,qm}，在累積距離矩陣M中，若能夠找到唯一的最佳彎曲路徑，并且這個(gè)最佳路徑上的累積距離之和為γ，那么有DTW(S,Q)≤γ。

證明上一章提到過，在累積矩陣中，能夠找到一條最優(yōu)的彎曲路徑W=(w1,w2,…,wk,…,wK)，彎曲路徑W中的第k個(gè)元素定義為wk=(i,j)k，使得由路徑W組最小，其中成的累積距離值即為兩個(gè)序列的點(diǎn)對(duì)基距離。由上一節(jié)DTW定義可得，DTW距離等于該最小累積距離之和，即DTW(S,Q=)

接下來，將結(jié)合early stopping思想對(duì)DTW距離度量進(jìn)行改進(jìn)。

基于early stopping的DTW改進(jìn)具體過程如算法1所示。首先給定兩個(gè)時(shí)間序列S、Q；然后，根據(jù)這兩個(gè)序列構(gòu)成的距離矩陣，計(jì)算出代價(jià)矩陣對(duì)應(yīng)元素單元格的累積距離γ(i,j)，并與預(yù)設(shè)閾值ε作比較，若大于該閾值，則停止當(dāng)前元素之后的所有代價(jià)矩陣所在單元格行（或列）的累積距離計(jì)算，進(jìn)而根據(jù)其對(duì)角線的新的單元格繼續(xù)開始計(jì)算累積距離，直到最后一列停止，并輸出最優(yōu)累積距離值ES_DTW(S,Q)。通過該算法來減小搜索范圍，降低了距離度量的計(jì)算成本，同時(shí)也確保了原本DTW距離度量的精度。

算法1基于early stopping的DTW算法（ESDTW）

接下來，先參考一個(gè)例子來進(jìn)一步了解early stopping在DTW中發(fā)揮的作用。圖3是S、Q根據(jù)DTW距離度量計(jì)算構(gòu)成的代價(jià)矩陣，每個(gè)單元格表示對(duì)應(yīng)元素的累積距離大小。假設(shè)提前終止的閾值ε為26，由于γ(1,2)＞ε，則第一列單元格中γ(1,3)，γ(1,4)都將被排除在外，即不參與距離計(jì)算。同理，γ(2,2)=γ(3,2)=32＞ε，則與之所在列的后續(xù)單元格代價(jià)距離都無需計(jì)算。最終，得到該代價(jià)矩陣的最優(yōu)解為γ(6,4)=28，即ESDTW(S,Q)=γ(6,4)=28。

圖3 基于DTW距離度量的代價(jià)矩陣Fig.3 Cost matrix based on DTW distance measurement

性質(zhì)2假設(shè)時(shí)間序列S={s1,s2,…,sn}，Q={q1,q2,…,qm}，在累積距離矩陣M中，該彎曲路徑上的累積距離之和為γ，若存在一條最優(yōu)路徑，那么有ESDTW(S,Q)≤γ。

證明參考性質(zhì)1，由于ESDTW算法進(jìn)行距離度量的方法與DTW保持一致，那么，在累積矩陣中，同樣能夠形成一條最佳路徑W=(w1,w2,…,wk,…,wK)，使得由路徑W組成的累積距離值最小，同理可得

因此，同理可證ESDTW(S,Q)≤γ，即說明了ESDTW距離度量方法的有效性。

Early stopping算法不僅能應(yīng)用于精確的DTW距離計(jì)算，也能在粗略的DTW距離計(jì)算中發(fā)揮作用，大大降低了計(jì)算成本，提高算法性能。

2.3 下界函數(shù)方法分析

文中之所以引入下界函數(shù)，正因?yàn)閯?dòng)態(tài)時(shí)間規(guī)整算法原始時(shí)間復(fù)雜度過高，如果直接進(jìn)行兩序列之間的DTW距離度量，勢(shì)必會(huì)使得算法的整體的度量效率下降，使得后續(xù)的數(shù)據(jù)挖掘任務(wù)變得難以進(jìn)行下去[25]。下面將對(duì)下界函數(shù)進(jìn)行展開分析，并舉出代表性的下界函數(shù)方法。

首先給出下界函數(shù)的定義為，假設(shè)存在一個(gè)對(duì)象O，且它的距離度量函數(shù)為M，若某個(gè)定義在對(duì)象域O上的函數(shù)為M"，那么對(duì)于所有存在于對(duì)象域的參數(shù)值oi,oj，總有下列不等式：

如果不等式恒成立，那么將上述M"函數(shù)稱之為M的下界函數(shù)。

如果在度量?jī)蓚€(gè)時(shí)間序列時(shí)，采用度量函數(shù)度量其相似度，在沒有下界函數(shù)參與的情況下，單單依靠距離度量函數(shù)只是機(jī)械化地將整個(gè)樣本序列的相似性度量執(zhí)行完，這種度量的效率較低，時(shí)間耗費(fèi)過大，若加入了下界函數(shù)，則能夠在度量期間對(duì)超過某個(gè)預(yù)先設(shè)定的相似性度量閾值進(jìn)行比對(duì)判斷，若實(shí)際得到距離值比預(yù)設(shè)閾值大，那么認(rèn)定這兩條序列是不相似的，相應(yīng)地也就將其摒棄，也為后續(xù)度量節(jié)省了時(shí)間開銷。

那么為了保證下界函數(shù)在距離度量函數(shù)運(yùn)行過程中能夠有效進(jìn)行，需滿足兩個(gè)必要條件：

（1）盡量與真實(shí)距離度量函數(shù)得到的距離接近。因?yàn)橄陆缇嚯x函數(shù)只是真實(shí)距離度量函數(shù)的一個(gè)先行者，它需要盡可能幫助實(shí)際距離度量函數(shù)去篩選和過濾掉一些不相似序列，所以下界函數(shù)需要更加貼近真實(shí)的距離度量函數(shù)的邊界值，保證度量誤差在一個(gè)合理范圍內(nèi)。

（2）滿足時(shí)間復(fù)雜度要求，盡可能在O(n)內(nèi)完成。即下界函數(shù)需要在線性時(shí)間內(nèi)完成度量，如果下界函數(shù)的時(shí)間復(fù)雜度超過了實(shí)際距離度量函數(shù)的計(jì)算耗時(shí)，那么可以說此下界函數(shù)是無效的。

如今的下界函數(shù)方法已有很多，典型的主要有：LB_Kim、LB_Yi和LB_Keogh。下面將重點(diǎn)介紹一下LB_Keogh下界函數(shù)。

LB_Keogh的提出是為了針對(duì)DTW的耗時(shí)問題。該方法通過計(jì)算候選序列的邊界序列來組成動(dòng)態(tài)時(shí)間規(guī)整距離的下界。設(shè)候選序列Q={q1,q2,…,qn}，將全局約束引入到彎曲路徑中，邊界約束為r，利用參數(shù)r定義兩個(gè)邊界序列U={u1,u2,…,un}，L={l1,l2,…,ln}，其中：

U、L分別代表上邊界序列和下邊界序列，如圖4組成了上下包絡(luò)線與Q的位置關(guān)系，而被U、L包裹其中的區(qū)域，則稱之為封袋。

圖4 查詢序列與其上線邊界序列Fig.4 Query sequence and its on-line boundary sequence

其中，包絡(luò)線上界與下界的一個(gè)重要性質(zhì)為：

進(jìn)而，得到動(dòng)態(tài)時(shí)間規(guī)整的下界函數(shù)LB_Keogh為：

該下界函數(shù)可理解為候選序列C中沒有落入封袋的點(diǎn)與邊界線的距離之和，如圖5。

圖5 下界距離LB_ESDTW的示意圖Fig.5 Schematic diagram of LB_ESDTW with lower bound distance

2.4 基于ESDTW下界距離（LB_ESDTW）

上文提出了一種改進(jìn)的DTW距離度量方法，即ESDTW，下面將給出該方法的下界距離。

設(shè)長度為n的兩條時(shí)間序列Q、C，其邊界約束為j-r≤i≤j+r，則ESDTW的下界函數(shù)為：

下面首先證明LB_ESDTW(Q,C)≤DTW(Q,C)，即該下界函數(shù)滿足下界距離引理。

證明在ESDTW度量中，假設(shè)Q,C的最佳彎曲路徑為W=(w1,w2,…,wk,…,wK)，由上一節(jié)對(duì)ESDTW的證明可知，其中n≤K≤2n-1，則原命題可轉(zhuǎn)換為：

不等式兩邊平方，得：

對(duì)于式（11），不等式左側(cè)分為3種情況：

當(dāng)ci＞ui時(shí)，不等式左側(cè)第i項(xiàng)為(ci-ui)2，不等式右側(cè)第i項(xiàng)基距離為D(wi)=(ci-qi)2。由于ui=max(qi-r:qi+r)且i-r≤j≤i+r，所以qj≤max(qi-r:qi+r)，即qj≤ui；那么，不等式兩邊變形后為ci-ui≤ci-qj，又因?yàn)樽筮吅愦笥?，則不等式兩邊平方可得因此

當(dāng)ci＜li，同理可證(ci-li)2≤D(wi)。

當(dāng)li≤ci≤ui時(shí)，顯然有0≤(ci-qi)2=D(wi)。

綜上所述，不等式（8）成立，即證明了LB_ESDTW(Q,C)≤DTW(Q,C)，該下界距離是有效的。

對(duì)于上述下界函數(shù)，其計(jì)算方法與歐式距離類似，都是通過計(jì)算點(diǎn)對(duì)點(diǎn)距離的累積和，因此，在計(jì)算過程中達(dá)到下界函數(shù)的最優(yōu)解ε時(shí)，往往會(huì)把序列點(diǎn)全部計(jì)算完畢才去判斷是否滿足最優(yōu)條件，這種計(jì)算方式會(huì)大大增加時(shí)間成本，往往是不必要的。在這里，同樣可以將early stopping算法用于下界函數(shù)來提高算法的時(shí)間效率，采用從左往右依次計(jì)算序列點(diǎn)之間的距離，若到達(dá)某序列點(diǎn)的距離之和超過了最優(yōu)解，則終止當(dāng)前序列計(jì)算，因?yàn)槌^該序列點(diǎn)的計(jì)算都將會(huì)比ε大，完成整個(gè)序列的下界函數(shù)計(jì)算變得沒有意義。

如圖6，假設(shè)采用下界函數(shù)計(jì)算到第8個(gè)序列點(diǎn)時(shí)，該點(diǎn)距離和已經(jīng)大于最優(yōu)解了，那么序列點(diǎn)8往后的序列點(diǎn)的計(jì)算都將失去意義，由此得出該測(cè)試序列與原始序列之間的相似度較低，可將其剔除。通過該方式能進(jìn)一步提高算法的運(yùn)行效率，從而降低時(shí)間成本。

圖6 基于下界函數(shù)的提前終止方法Fig.6 Early termination method based on lower bound function

2.5 算法分析

下面給出基于DTW下界函數(shù)的提前終止算法（LB_ESDTW）。將改進(jìn)的ESDTW算法1與下界函數(shù)相結(jié)合，進(jìn)一步提高了算法的運(yùn)算效率，大大節(jié)省時(shí)間成本，同時(shí)也保證了后續(xù)算法相似性度量的準(zhǔn)確性。

算法2基于DTW下界函數(shù)的提前終止算法（LB_ESDTW）

算法LB_ESDTW在相似性距離度量方法DTW的基礎(chǔ)上采用了提前終止算法，同時(shí)在下界距離度量上也在局部增加了提前終止算法，這兩次的提前終止算法與下界距離相結(jié)合能夠提升算法效率。根據(jù)算法2的描述和式（11）的計(jì)算公式可以得出，長度為n的兩條時(shí)間序列Q、C進(jìn)行下界距離度量時(shí)，其復(fù)雜度為O(n)，內(nèi)部嵌套提前終止距離度量算法ESDTW，時(shí)間復(fù)雜度為O(m)，其中m≤n，因而整體算法LB_ESDTW的時(shí)間復(fù)雜度大小為O(n×m)。而傳統(tǒng)的動(dòng)態(tài)時(shí)間規(guī)整算法（DTW）的時(shí)間復(fù)雜度則是O(n2)，所以，本文算法的時(shí)間復(fù)雜度與DTW算法相比，則有不等式O(n×m)≤O(n2)恒成立。當(dāng)測(cè)試數(shù)據(jù)量較大時(shí)，本文的度量算法在時(shí)間計(jì)算效率上與DTW算法相比將有明顯的優(yōu)勢(shì)，即大大提高了算法的運(yùn)行效率，節(jié)約了時(shí)間成本。該方法對(duì)于分類數(shù)據(jù)維數(shù)的大小都能有良好的適應(yīng)性，不會(huì)因?yàn)闃颖緮?shù)據(jù)量大而限制算法的性能。

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

為了驗(yàn)證LB_ESDTW的有效性，本文將在特定的時(shí)間序列分類數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。對(duì)比實(shí)驗(yàn)的內(nèi)容主要針對(duì)算法的運(yùn)行時(shí)間測(cè)試、下界距離的緊湊性和算法的相似性度量準(zhǔn)確率這三部分進(jìn)行分析。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文實(shí)驗(yàn)的實(shí)驗(yàn)數(shù)據(jù)集全部來源于Keogh等人提供的來自不同領(lǐng)域的用于時(shí)間序列分類、聚類UCR數(shù)據(jù)集。該數(shù)據(jù)集中包含了各個(gè)領(lǐng)域的不同數(shù)據(jù)集，里面包含預(yù)先處理好的訓(xùn)練集和測(cè)試集。本實(shí)驗(yàn)共選擇了15個(gè)數(shù)據(jù)集進(jìn)行算法性能測(cè)試，這15個(gè)數(shù)據(jù)集的具體特征如表1所示。

表1 UCR數(shù)據(jù)集描述Table 1 Description of UCR data set

3.2 實(shí)驗(yàn)設(shè)置

在實(shí)驗(yàn)中，為了驗(yàn)證本文LB_ESDTW算法的性能，分別選取了DTW、LB_Keogh和WDTW三種不同的度量算法進(jìn)行對(duì)比實(shí)驗(yàn)。

由于時(shí)間序列數(shù)據(jù)集來自不同領(lǐng)域，彼此的特征值取值范圍有一定差距，為了便于對(duì)比實(shí)驗(yàn)，在采用線性分段算法之前首先對(duì)時(shí)間序列做規(guī)范化處理，將序列特征值規(guī)范化到[0，1]之間，其規(guī)范化公式如下：

3.3 實(shí)驗(yàn)結(jié)果

算法運(yùn)行在2.5 GHz CPU，8 GB內(nèi)存Windows系統(tǒng)的Python 3.5.1環(huán)境下。本文選取了UCR中的10個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，每個(gè)算法均進(jìn)行100次實(shí)驗(yàn)，結(jié)果取100次實(shí)驗(yàn)的平均值。

由于本文采用Sakeo-Chiba全局約束進(jìn)行時(shí)間序列相似性度量實(shí)驗(yàn)。首先，為確定實(shí)驗(yàn)的具體全局約束參數(shù)，將采用LB_ESDTW算法準(zhǔn)確率實(shí)驗(yàn)來選定具體的全局約束參數(shù)R。表2是在時(shí)間序列都為原始序列長度的情況下，且保證全局約束在10%≤R≤50%范圍內(nèi)進(jìn)行準(zhǔn)確率實(shí)驗(yàn)。目的是探究全局約束R取何值，時(shí)序的度量準(zhǔn)確率達(dá)到最高。其中，標(biāo)粗?jǐn)?shù)據(jù)是當(dāng)前數(shù)據(jù)集下得到的最高準(zhǔn)確率所對(duì)應(yīng)的全局約束。從表2列出的準(zhǔn)確率數(shù)據(jù)可以看出，在測(cè)試的15個(gè)數(shù)據(jù)集中，有4條數(shù)據(jù)集在R=10%時(shí)算法準(zhǔn)確率達(dá)到最優(yōu)；有5條數(shù)據(jù)集在R=15%時(shí)算法準(zhǔn)確率達(dá)到最優(yōu)；有4條數(shù)據(jù)集在R=20%時(shí)算法度量準(zhǔn)確率達(dá)到最優(yōu)；有2條數(shù)據(jù)集在R=25%時(shí)算法準(zhǔn)確率達(dá)到最優(yōu)。綜合這15個(gè)數(shù)據(jù)集的算法準(zhǔn)確率來看，整體趨勢(shì)都是先逐漸上升到某個(gè)峰值（算法準(zhǔn)確率達(dá)到最高）再逐漸下降，且當(dāng)全局約束R越大，準(zhǔn)確率下降幅度也隨之變高。因此，根據(jù)這一參數(shù)特性，可以得出算法的全局約束參數(shù)值在10%≤R≤25%這一范圍內(nèi)能得到最優(yōu)準(zhǔn)確率。而在實(shí)驗(yàn)中，只需在算法中加一個(gè)記錄判斷環(huán)節(jié)，即加一個(gè)for循環(huán)和if判斷得到當(dāng)前數(shù)據(jù)集下的全局約束最優(yōu)解。

表2 全局約束下的LB_ESDTW算法準(zhǔn)確率Table 2 Accuracy of LB ESDTW algorithm under global constraints

實(shí)驗(yàn)1算法的運(yùn)行時(shí)間分析

在本實(shí)驗(yàn)中，選取UCR訓(xùn)練數(shù)據(jù)集中的CBF、ECGFiveDays、ECG200，Coffee這四個(gè)數(shù)據(jù)樣本的第一條樣本序列與測(cè)試序列進(jìn)行相似序列搜索的運(yùn)行時(shí)間的對(duì)比分析。通過分析上述四種算法在邊界約束r取不同值時(shí)，即取序列長度壓縮率為10%～100%時(shí)的彎曲范圍，得到不同的運(yùn)行時(shí)間，從而得出各個(gè)算法的運(yùn)行效率。那么，邊界約束與彎曲范圍的關(guān)系為r=N×w×100%。其中，r為邊界約束，N是時(shí)間序列長度，w為彎曲范圍。由于r和w成正比，所以在本實(shí)驗(yàn)中，將采用彎曲范圍w與運(yùn)行時(shí)間t進(jìn)行實(shí)驗(yàn)分析。

如圖7，分別在上述的三個(gè)數(shù)據(jù)樣本下進(jìn)行四種算法的彎曲范圍w和運(yùn)行時(shí)間t的對(duì)比實(shí)驗(yàn)。

從圖7對(duì)比可以看出本文算法都有最低的時(shí)間消耗，即本文的LB_ESDTW算法在四種數(shù)據(jù)集下的運(yùn)行時(shí)間都為最短，從側(cè)面反映了該算法的運(yùn)行效率較高。

圖7 不同彎曲范圍下的運(yùn)行時(shí)間Fig.7 Running time under different warping ranges

實(shí)驗(yàn)2下界距離LB_ESDTW的緊致性分析

算法的緊致性越好，說明下界距離更接近實(shí)際距離，使得在使用下界距離進(jìn)行相似性度量時(shí)，得到的誤報(bào)序列更少，更精確地匹配到相似序列，同時(shí)保證了準(zhǔn)確率。本實(shí)驗(yàn)采用緊縮率和修剪率這兩個(gè)性能指標(biāo)來度量下界距離LB_ESDTW的緊致性。下界距離LB_ESDTW的緊縮率SESDTW定義為：

修剪率P定義為：

其中，N0為在下界距離LB_ESDTW的過濾篩選下得到的不需要與訓(xùn)練集樣本進(jìn)行相似性度量的序列數(shù)量，N為該數(shù)據(jù)集的總樣本序列數(shù)。

本實(shí)驗(yàn)選取了上述15個(gè)UCR數(shù)據(jù)集進(jìn)行緊縮率分析。對(duì)同一數(shù)據(jù)集進(jìn)行多次緊縮率實(shí)驗(yàn)記錄并最終選取緊縮率SESDTW的平均值，具體實(shí)驗(yàn)結(jié)果如表3所示。

表3 下界距離LB_ESDTW的緊縮率Table 3 Contraction rate of LB_ESDTW with lower bound distance

本實(shí)驗(yàn)選取了其中的六個(gè)數(shù)據(jù)集對(duì)修剪率在邊界約束r取不同值時(shí)進(jìn)行分析，實(shí)驗(yàn)結(jié)果如圖8。

圖8 下界距離LB_ESDTW的修剪率Fig.8 Pruning rate of LB_ESDTW with lower bound distance

在第一個(gè)緊縮率實(shí)驗(yàn)中，下界算法LB_ESDTW在五個(gè)不同數(shù)據(jù)集下的緊縮率都在50%以上，也就證明了該下界距離算法的緊致性較好；在第二個(gè)修剪率實(shí)驗(yàn)上，該算法在距離閾值較小時(shí)的修剪率都能達(dá)到70%以上，而當(dāng)距離閾值逐漸增加，相應(yīng)的修剪率則隨之減小，由此得知下界距離LB_ESDTW的修剪率和距離閾值存在一定的關(guān)系，即當(dāng)距離閾值過大，超出了ESDTW距離時(shí)，意味著該下界距離失去了原有的過濾篩選作用。綜上兩個(gè)對(duì)于緊湊性判斷標(biāo)準(zhǔn)的實(shí)驗(yàn)結(jié)果，能夠明顯看出該算法的緊湊性較好。

實(shí)驗(yàn)3算法準(zhǔn)確率對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)中，將本文下界算法LB_ESDTW分別與其他相似性度量方法進(jìn)行算法的分類準(zhǔn)確率對(duì)比實(shí)驗(yàn)，目的在于分析各算法之間的相似性度量準(zhǔn)確率，從而判斷本文所提算法的相似性度量性能。

本實(shí)驗(yàn)采用上述15個(gè)不同領(lǐng)域的數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)。進(jìn)行對(duì)比的相似性度量算法分別有ED、DTW、LB_Keogh、WDTW以及本文算法LB_ESDTW。同時(shí)保證這五個(gè)算法在不同數(shù)據(jù)集下的邊界約束r都是壓縮率在100%的彎曲路徑。

表4給出了在上述描述的15個(gè)不同數(shù)據(jù)集下的各算法的相似性度量的分類準(zhǔn)確率。

表4 算法度量的分類準(zhǔn)確率Table 4 Classification accuracy of similarity measure

表4中用粗體表示的數(shù)據(jù)為算法在當(dāng)前數(shù)據(jù)集下獲得的最高分類準(zhǔn)確率。從表4的分類結(jié)果不難發(fā)現(xiàn)，對(duì)于所選的15個(gè)數(shù)據(jù)集來說，其中LB_ESDTW算法在11個(gè)數(shù)據(jù)集的分類結(jié)果都優(yōu)于其他四種算法的分類結(jié)果，也表明了LB_ESDTW下界距離度量的分類性能較好。

4 結(jié)束語

本文給出了一種基于early stopping思想的DTW距離度量，即在計(jì)算兩個(gè)序列的距離時(shí)，發(fā)現(xiàn)本次計(jì)算所積累的距離信息已經(jīng)足以判斷結(jié)果，則終止本次計(jì)算，大大降低了計(jì)算成本；并在下界距離函數(shù)LB_Keogh方法基礎(chǔ)之上，提出了一種基于DTW下界距離函數(shù)的提前終止算法，實(shí)現(xiàn)了算法在DTW距離度量和下界函數(shù)距離度量相融合的相似性度量，同時(shí)也提高了算法的適應(yīng)性。通過在UCR數(shù)據(jù)集上的三種對(duì)比實(shí)驗(yàn)，表明其在時(shí)間計(jì)算成本低、算法的緊致性良好且算法的分類準(zhǔn)確率高的特點(diǎn)。本文已在大多數(shù)時(shí)間序列數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)論證，由于數(shù)據(jù)集的時(shí)效性和局限性，后續(xù)將通過更多不同領(lǐng)域的時(shí)序數(shù)據(jù)集來驗(yàn)證本文所提算法的有效性。同時(shí)，為了能夠更好地平衡算法的度量準(zhǔn)確率和時(shí)間效率，接下來的工作主要是將時(shí)間序列的表示方法與相似性度量方法結(jié)合起來，并根據(jù)數(shù)據(jù)挖掘的任務(wù)需求，設(shè)計(jì)出針對(duì)不同場(chǎng)景的具有普適性的融合度量查詢系統(tǒng)，如針對(duì)病人的心電數(shù)據(jù)，設(shè)計(jì)一種實(shí)時(shí)在線的度量系統(tǒng)；而針對(duì)股票趨勢(shì)的分析，則設(shè)計(jì)出一種預(yù)測(cè)度量系統(tǒng)模型，以此將本文度量方法在數(shù)據(jù)挖掘中的優(yōu)勢(shì)發(fā)揮到最大化。