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

上海工程技術大學 電子電氣工程學院，上海 201620

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

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

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

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

（1）有效性：下界距離度量的時間計算成本應保持在低位值；

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

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

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

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

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

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

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

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

1 相關定義

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

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

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

為計算S和Q的DTW距離，需要構造一個m×n的矩陣，其中：

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

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

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

（1）邊界性：路徑起始于(s1,q1)、終止于(sm,qm)，它表示兩個序列的起始點和終止點的對應匹配；

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

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

在眾多彎曲路徑中找到唯一最優(yōu)的路徑，使得累積距離達到最?。?/p>

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

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

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

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

2.1 彎曲路徑的全局約束

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

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

2.2 基于early stopping的DTW距離度量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 基于ESDTW下界距離（LB_ESDTW）

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

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

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

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

不等式兩邊平方，得：

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

當ci＞ui時，不等式左側(cè)第i項為(ci-ui)2，不等式右側(cè)第i項基距離為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，又因為左邊恒大于0，則不等式兩邊平方可得因此

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

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

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

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

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

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

2.5 算法分析

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

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

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

3 實驗與結(jié)果分析

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

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

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

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

3.2 實驗設置

在實驗中，為了驗證本文LB_ESDTW算法的性能，分別選取了DTW、LB_Keogh和WDTW三種不同的度量算法進行對比實驗。

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

3.3 實驗結(jié)果

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

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

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

實驗1算法的運行時間分析

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

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

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

圖7 不同彎曲范圍下的運行時間Fig.7 Running time under different warping ranges

實驗2下界距離LB_ESDTW的緊致性分析

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

修剪率P定義為：

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

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

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

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

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

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

實驗3算法準確率對比實驗

本實驗中，將本文下界算法LB_ESDTW分別與其他相似性度量方法進行算法的分類準確率對比實驗，目的在于分析各算法之間的相似性度量準確率，從而判斷本文所提算法的相似性度量性能。

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

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

表4 算法度量的分類準確率Table 4 Classification accuracy of similarity measure

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

4 結(jié)束語

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