一種基于動態時間彎曲距離的快速子序列匹配算法

劉曉影

摘 要： 動態時間彎曲距離在用于計算時間序列間的距離時是極其耗費時間的，尤其是處理較大規模的時間序列數據庫中的子序列匹配問題時，時間消耗更是難以忍受。該文提出一種新的低邊界距離，能夠快速濾掉不滿足結果條件的時間序列，以提高查詢速度，并證明該低邊界距離不會丟棄真實的結果。一種基于水平邊界區域的索引技術被用于進一步提高查詢效率。分別以真實數據集和人造數據集作為實驗數據來測試該文所提出的算法的性能，結果表明該算法在數據庫規模上和序列長度上都有良好的健壯性。

關鍵詞： 時間彎曲距離； 低邊界距離； 范圍查詢； 數據庫

中圖分類號： TN911?34； TP311.13 文獻標識碼： A 文章編號： 1004?373X（2017）06?0025?06

Abstract： It is very time?consuming to calculate the distance between time sequences by using dynamic time warping distance， especially when the subsequence matching in large time?series databases is concerned. A new method of lower bound distance is presented in this paper， which can quickly filter the time sequences which are unable to satisfy the result condition， so as to improve the query speed. It is proven that the true results can not be lost if the method is used. To further increase the query speed， a technique for building an index based on skyline bounding region is also proposed. Some experiments with the data from real data set and synthetic data set were carried out to verify the performance of the methods. The results reveal that the method has robostness in the scale of database and sequence length.

Keywords： time warping distance； lower bounding distance； range query； database

0 引 言

時間序列是由一些在特定時間點上采樣得到的實數組成。在現實世界中，有很多時間序列的例子，如股票的價格、天氣的變化情況、商品的銷售記錄。時間序列間的相似性查詢就是從時間序列數據庫中發現與給定查詢序列有相似的變化模式的序列，該操作在很多新的數據庫應用領域（數據挖掘、數據倉庫）中是很重要的，它能用于預測未來發展趨勢、識別新的模式、發現規則[1?3]。例如，可能需要找出一天的股票價格中的特定模式來預測未來發展趨勢；也可能需要找出歷史上與今天有相似磁暴模式的日子來預測地球磁場的變化。

通常，時間序列相似性查詢可以分為兩類：全序列匹配和子序列匹配。全序列匹配是給定一條查詢序列，在數據庫中找出與其相似的完整數據序列，而子序列匹配是在數據庫中找出與其相似的部分數據序列，即子序列。全序列匹配又可以看成是子序列匹配的一種特殊情況[3?5]，故子序列匹配比全序列匹配有更廣泛的應用。本文重點研究子序列匹配。

子序列匹配就是在給定一變長時間序列數據庫、一長度為N的查詢序列Q和閾值ε的情況下，從數據庫中找出所有與查詢序列相似的子序列（即子序列與Q之間的距離小于ε），并返回這些結果。

1 子序列匹配

在介紹子序列匹配前，先說明本文所用到的符號以及它們的定義，見表1。

1.1 動態時間彎曲距離

動態時間彎曲（Dynamic Time Warping，DTW）距離不要求時間序列中的元素與元素之間進行一一對應匹配，允許序列中的元素自我復制后再進行對齊匹配。當時間序列沿時間軸發生彎曲時，可以在彎曲部分進行自我復制，使兩條時間序列之間的相似波形進行對齊匹配。DTW距離很好地解決了時間序列發生時間軸伸縮和彎曲后的相似性度量問題。例如，給定兩條序列P=<4，5，6，8，9>和Q=<3，4， 7，8，9，7>，可以分別將這兩條序列拉伸為P′=<4，5，6，6，8，9，9>和Q′=<3，3，4，7，8，9，7>，通過計算P′和Q′間的距離來衡量P和Q間的距離。在這種情況下，就稱序列P和Q之間相互“調整”。P和Q之間“調整”的路徑稱為彎曲路徑。在兩條序列間存在多條彎曲路徑，可稱根據最小彎曲代價的路徑計算的距離為動態時間彎曲距離。

表1 符號及其定義

由于存在多條彎曲路徑，找到最小彎曲代價的路徑是極其耗費時間的。為了解決這一問題文獻[6]介紹了一種基于累積距離矩陣的動態規劃方法來計算兩條時間序列之間的DTW距離，時間復雜度為O（MN）。累積距離矩陣實際上是一個遞推關系。給定兩條時間序列P=，Q=，其長度分別為M和N。它們之間的動態時間彎曲距離定義如下：

[DDTW（P，Q）=f（M，N）f（i，j）=d（pi，qj）+minf（i，j-1）f（i-1，j）f（i-1，j-1）f（0，0）=0， f（i，0）=f（0，j）=∞i=1，2，…，M； j=1，2，…，N] （1）

式中，d（pi，qj）表示序列元素pi和qj之間的距離，可以根據應用而選擇不同的距離度量，比如d（pi，qj）=[pi-qj]。

使用動態規劃方法計算數據序列P和查詢序列Q間距離的同時，通過累積距離矩陣也可獲得所有P的前綴P[-，e]與Q之間的距離。例如，給定數據序列P=<7，9，8，5，2，4>和查詢序列Q=<5，6，7，4，8，7>，以及查詢閾值ε為8。在計算P和Q間的距離時，也可得到所有P的前綴中與Q的距離小于8的子序列。圖1給出了P和Q間的累積距離矩陣。圖1中陰影部分表示兩條時間序列之間的具有最小代價的動態時間彎曲路徑，累積距離矩陣的右下角得到的值就是這兩條時間序列之間的距離16。通過累積距離矩陣中的最后一列可以獲得P的前綴與Q之間的距離，即DDTW（P[-，1]，Q）=7；DDTW（P[-，2]，Q）=9；DDTW（P[-，3]，Q）=8；DDTW（P[-，4]，Q）=9；DDTW（P[-，5]，Q）=14；DDTW（P[-，6]，Q）=16。因此，P[-，1]和P[-，3]就是子序列匹配的結果。

子序列匹配時，可以通過檢測數據序列的所有后綴與查詢序列的距離來獲得完整的匹配結果。進行子序列匹配的時間復雜度為O（M2N）。

1.2 相關工作

目前已有很多研究工作是研究如何索引時間序列才能在DTW距離下做高性能的查詢[5，7?9]。

文獻[8]中，作者設計了一種DTW距離的低邊界函數Dtw?lb，該距離滿足三角不等式。一個四元的特征向量用于Dtw?lb的計算，該特征向量是提取序列的第一個元素、最后一個元素、以及序列的最大值、最小值。為了提高查詢速度，可用高維索引來存儲這些四元特征向量，用Dtw?lb作為距離函數。然而，在文獻中的結果表明這種近似是粗糙的，需要花費很高的搜索代價，進行大量的準確計算。

文獻[7]提出了一種基于動態規劃中的全局約束的查詢方法。該方法根據彎曲路徑的范圍得到查詢序列的“封套”（envelope），并計算出“封套”的PAA（Piecewise Aggregate Approximation）。查詢序列與數據序列間的低邊界距離被定義為“封套”的PAA與包含數據序列的最小邊界矩形MBR（Minimum Bounding Rectangle）間的歐氏距離。這種方法當彎曲路徑在狹小范圍內時是有效的，但當彎曲路徑范圍變寬時查詢性能將下降。

文獻[9]中，提出了FTW（Fast search method for dynamic Time Warping）算法。算法使用一種低邊界函數LBS（lower bounding functions）來近似計算DTW距離；使用Early Stopping算法來排除那些不能產生結果的彎曲路徑；并采用Refinement算法來逐漸提高近似計算的準確程度。FTW用很低的計算代價就可排除大量的非結果序列，提高了查詢效率。

由于任意兩序列間的DTW距離與等長的序列前綴間不存在任何關系，故DTW距離下的子序列匹配變得更加復雜。文獻[10]中，提出了一個利用動態規劃求解兩條時間序列DTW中心的方法，即以最小化中心序列到兩條樣本序列的DTW距離平方和為目標，遞歸求解最優解。文獻[11]提出了一種基于前綴的查詢技術，用文獻[8]中提出的邊界函數來進行子序列查詢，然而，在文獻[7]中指出“該低邊界函數是松散的，大量非結果序列將不能被過濾掉”。

文獻[12]擴展了文獻[7]中的全序列匹配算法，該方法主要是基于滑動窗口和彎曲路徑約束的，對于狹小范圍下的彎曲路徑匹配，該查詢是很有效的，但當彎曲路徑的范圍變寬時，也將面臨文獻[7]中的問題，即查詢性下降。

1.3 FTW技術

全序列匹配是子序列匹配的一種特殊情況，故可以通過擴展一些全序列匹配方法來進行子序列匹配。在1.2節中提到的FTW算法是一種全序列匹配的方法，它主要是基于三個思想建立的[9]：LBS距離、Early Stop Ping算法和Refinement算法。

LBS距離用于計算時間序列的近似序列間的距離，可評估時間序列間的DTW距離，但LBS距離的計算量要比DTW距離小很多。近似序列就是用較少的信息來表示時間序列的。近似序列由近似段組成，給定一條長度為M的時間序列P=，P的第i個近似段定義如下：

[pAi={pRi，pTi}， pRi={pLi，pUi}pLi=min{px，…，py}， pUi=max{px，…，py}x=1， i=1j=1i-1pTj+1， 2≤i≤n， y=j=1ipTj] （2）

式中：[pRi]和[pTi]分別是在該段中時間點上的數值范圍和該段所跨的時間數；[pUi]和[pLi]分別代表[pRi]的上下邊界。[pUi]和[pLi]分別是在從px到py的[pRi]個元素中的最大和最小的值。因此，P能近似地表示成PA=，m是P被劃分的段數?？赏ㄟ^計算近似序列間的距離來評估DTW距離。定理1可以保證這種計算方法不會漏掉真正的結果，即不產生假丟棄。

定理1 設PA和QA分別是P和Q的近似序列，將有[DLBS（PA，QA）≤DDTW（P，Q）]，其中[DLBS（PA，QA）]是近似序列間的距離。

EarlyStopping算法用于進行k?近鄰查詢。在得到最后k個結果之前會維護一個候選結果列表。當前第k個近鄰與查詢序列間的準確距離dcb可以用來過濾那些不能產生查詢結果的彎曲路徑。如果一個序列與查詢序列間的距離小于dcb，就認為發現了一條相似序列，此時候選結果列表也將要更新，將會得到更小的dcb。Early Stopping算法通過使用dcb能夠過濾掉那些不能產生結果的彎曲路徑。即使是沒有約束彎曲路徑的范圍（即全局約束沒有被使用），該算法也能通過判斷彎曲路徑是否大于dcb來動態的縮減彎曲路徑的范圍。也就是說，dcb是減少彎曲路徑范圍的閾值。

Refinement算法使用不同粒度下的近似序列來評估DTW距離。這樣做的好處是能夠使DTW距離評估準確程度有一個逐漸增加的過程，當數據序列與查詢序列距離很大時，通過在較粗糙的粒度下進行很少的計算來就可以判斷出該數據序列不是結果序列。

2 低邊界距離

子序列匹配得到的相似子序列的長度以及在數據序列中的開始位置是不定的，見圖2。給定數據序列P=和查詢序列Q=，PA=和QA=分別是P和Q的近似序列。PA和QA間的距離即使大于閾值ε，這也并不表明P和Q的所有子序列間的距離也大于ε。所以，為了能夠保證查詢時不產生假丟棄，必對LBS距離做一下更改。

3 基于水平區域邊界技術的索引

子序列匹配過程中如果對數據序列進行索引可進一步提高查詢性能。在FTW方法中，由于處理的是全序列匹配，即使沒有對數據序列建立索引，也能取得很好的效果。但對于子序列匹配，所涉及的計算量將大大增加，故下面將介紹一種基于水平邊界技術用于索引時間序列的方法。首先獲得數據庫中所有數據序列在一給定粗糙粒度下的近似序列，抽出這些近似序列的所有后綴來構造多維索引。索引的方法采用在水平索引[13]中所用到的水平邊界區域SBR（Skyline Bounding Region）技術，即用一個被上下水平線和兩條垂直線所包圍的二維區域來表示序列所在的范圍。如圖3所示，圖3中曲線為一近似序列的片斷，水平的實線用來表示近似序列在某一時間段內數值的變化范圍，垂直的虛線表示時間段。根據近似序列的后綴得到的SBR可用于構建索引。上水平線TS（Top Skyline）和下水平線BS（Bottom Skyline）分別定義如下：

索引中，內部節點用于記錄SBR以及指向SBR中所包含的后綴的葉子節點的指針，葉子節點中存放著近似序列的后綴。子序列匹配時，先計算查詢序列Q的近似序列QA，然后再計算QA與每個SBR之間的距離。如果距離大于閾值ε，表明該SBR中不包含與查詢序列相似的子序列，將被過濾掉；否則繼續計算QA與該SBR中所包含的所有后綴P[s，-]A之間的距離。對于那些能產生結果的后綴，將通過計算原始數據序列P[s，-]與Q之間的距離來決定哪條子序列屬于結果集。如果子序列P[s，e]與Q之間的距離小于閾值ε，該子序列將被加入結果集，同時記錄該子序列在數據序列P中的起始位置以及子序列的長度，具體算法如下：

Algorithm SubSBRSearch（Q， ε）

Compute QA；

// range query

for each SBR do

dcoarse ：= EarlyStopping（SBR， QA， ε）；

if all d in dcoarse is not above ε then

add SBR to TempList；

endif

endfor

for each SBR in TempList do

for each suffix PA[i， -] in SBR do

dapprox ：= EarlyStopping（PA[i， -]， QA， ε）；

if all d in dapprox is not above ε then

dexact ：= EarlyStopping（P[i， j]， Q， ε）；

if each d in dexact is below ε then

add P[i， j] to ResultSet；

endif

endif

endfor

endfor

return ResultSet；

4 實 驗

4.1 實驗數據

實驗所用的數據集包括人造數據和真實數據。人造數據序列P=是根據如下公式生成的：

[pi=pi-1+zi]

式中，zi是一個取值在[-0.1， 0.1]區間的獨立同分布的隨機變量。序列中第一個元素p1的值在[1，10]區間中隨機選取。真實數據集來源于股票數據USA S&P 500（http：//biz.swcp.com/stocks），數據集中包含545條序列，平均長度為231。查詢序列的選取采用了與文獻[11]相同的方法生成了100條查詢序列，生成方法如下：

（1） 從數據集中隨機選取一條數據序列；

（2） 從選取的數據序列中隨機的抽取一段子序列；

（3） 在[[-std10，std10]]中為子序列中的每個元素選取一個隨機值，std是序列的標準方差；

（4） 分別加隨機值到子序列的相應元素中。100次查詢的平均時間被用來做性能評價。

為了評估提出算法的性能，將在實驗中比較以下三個算法：

（1） 本文提出的算法，記為SubSBR算法，在子序列匹配時，僅使用了一種粒度下的近似序列，近似段的每段有4個元素，t=4，用SBR建索引時每頁大小為256 B；

（2） 改進原有FTW算法用于子序列匹配，記為SubRFM算法，在子序列匹配時，數據序列有三種不同的粒度，分別是t1=2，t2=8，t3=32；

（3） 順序匹配算法，記為Sequential Search，在匹配的過程中沒有建立索引，按順序掃描數據庫查找相似子序列。表2列出了實驗中所用到的詳細參數。

實驗的硬件環境是：Pentinum 4 2.6 GHz的CPU、主存為512 MB；軟件環境是：操作系統為Microsoft Windows xp，算法采用C編寫。

4.2 性能比較

圖4顯示了建立SBR索引時頁面的大小對查詢時間的影響。頁面大小的變化范圍為64～1 024。從圖4可以看出建索引時頁面大小的增加對查詢時間的影響不大。在不同頁面大小下的所需的查詢時間的標準方差僅為0.04。當頁面大小為256時，所需的查詢時間最少。圖5顯示了閾值ε與查詢時間的關系。當閾值ε從30增加到170， SubSBR算法所需的查詢時間要比順序查詢和SubRFM算法小很多。圖6顯示了查詢序列長度與查詢時間的關系。當查詢序列的長度從70增加到130時，SubRFM和SubSBR無論是在查詢時間還是在查詢時間增長幅度上都要比順序查詢小很多。SubRFM和SubSBR這兩個算法在查詢序列長度的變化時，所需的查詢時間相對穩定。

圖7顯示了時間序列長度與查詢時間的關系。數據序列長度的變化范圍是200～800，相應的查詢序列的長度變化范圍為70～280。隨著數據序列的變長，數據序列中所包含的子序列的數量也會增加，這將導致查詢時需要更長的時間。從圖7中可以很明顯地看到這一點。SubRFM和SubSBR這兩種方法都優于順序的查詢方法，而且隨著序列長度的增加，查詢時間的增長幅度也比順序查詢小。SubRFM和SubSBR這兩種算法分別比順序查詢快10.57倍和68.27倍；SubSBR算法平均比SubRFM算法快6.54倍。

圖8顯示了數據集大小對查詢時間的影響。數據集中包含的序列從1 000變化到4 000時，三個算法所需的查詢時間均有所增長。但SubRFM和SubSBR這兩種算法增長幅度的比順序查詢緩慢，其中SubSBR算法所需查詢時間最短，SubRFM和SubSBR這兩種算法分別比順序查詢快6.12倍和43.18倍。SubSBR算法平均比SubRFM算法快7.05倍。

5 結 論

本文提出一種基于DTW距離的子序列匹配算法。該算法的優點有：查詢速度快、可查詢任意長度的子序列、不需要約束彎曲路徑的范圍和保證不產生假丟棄。本文的主要貢獻有兩點：修改了用于全序列匹配的LBS距離，使其能夠處理子序列匹配，并證明該距離不會產生假丟棄；設計一種基于SBR的索引，并提出了相應的查詢算法。實驗顯示本文所提出的算法在當序列的長度、數據集的大小以及閾值變化時也具有很好的性能。當數據序列長度變化時，提出的算法SubSBR平均比順序查詢快68.27倍；比SubRFM快6.54倍。當查詢序列長度變化時，提出的算法SubSBR平均比順序查詢快32.37倍；比SubRFM快1.05倍。當數據集大小變化時，提出的算法SubSBR平均比順序查詢快43.18倍；比SubRFM快7.05倍。SubSBR算法是有很好的健壯性的，可用于大規模數據庫中的子序列查詢。

參考文獻

[1] AGRAWAL R， FALOUTSOS C， SWAMI A. Efficient similarity search in sequence databases [C]// International Conference on Foundations of Data Orgazanation. [S.l.： s.n.]， 1993： 69?84.

[2] 馮鈞，陳煥霖，唐志賢，等.一種基于DTW的新型股市時間序列相似性度量方法[J].數據采集與處理，2015（1）：99?105.

[3] FALOUTSOS C， RANGAUATHAN M， MANOLOPOULOS Y. Fast subsequence matching in time?series databases[J]. ACM sigmod record， 1994， 23（2）： 419?429.

[4] CHU K W， WONG M H. Fast time?series searching with scaling and shifting [C]// Eighteenth ACM Sigact?sigmod?sigart Symposium on Principles of Database Systems. [S.l.]： ACM， 1999： 237?248.

[5] YI B K， JAGADISH H， FALOUTSOS V C. Efficient retrieval of similar time sequences under time warping [C]// International Conference on Data Engineering. [S.l.]： ICDE， 1998： 201?208.

[6] BERNDT J， CLIFFORD D. Using dynamic time warping to find patterns in time series [C]// AAAI Workshop on Knowledge Discovery in Database. USA： AAAI， 1994： 229?248.

[7] KEOGH E J. Exact indexing of dynamic time warping [J]. Knowledge and information systems， 2005， 7（3）： 358?386.

[8] KIM S W， PARK S， CHU W W. Approach for similarity search supporting warping in large sequence databases [C]// International Conference on Data Engineering. [S.l.：s.n.]， 2001： 607?614.

[9] SAKURAI Y， YOSHIKAWA M， FALOUTSOS C. FTW： Fast similarity search under the time warping distance [C] //Symposium on Principles of Database Systems. [S.l.]： ACM， 2005： 326?337.

[10] 孫燾，夏斐，劉洪波.基于動態規劃求解時間序列DTW中心[J].計算機科學，2015（12）：278?282.

[11] PARK S， KIM S W， CHO J S， et al. Prefixquerying： an approach for effective subsequence matching under time warping in sequence databases[C]// Acm Cikm International Conference on Informatio. [S.l.]： ACM， 2001： 255?262.

[12] Wong T S F， Wong M H. Efficient subsequence matching for sequences databases under time warping [C]// Proceedings of Database Engineering and Applications Symposium. [S.l.]： IEEE Computer Society， 2003： 139?148.

[13] LI Quanzhong， LOPEZ Lopez， MOON Bongki. Skyline index for time series data [J]. IEEE transactions on knowledge and data engineering， 2004， 16（6）： 669?684.

[14] 趙慧，候建榮，施伯樂.一種基于分形時變維數的非平穩時間序列相似性匹配方法[J].計算機學報，2005，28（2）：227?231.