劉曉影

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

關(guān)鍵詞： 時間彎曲距離； 低邊界距離； 范圍查詢； 數(shù)據(jù)庫

中圖分類號： TN911?34； TP311.13 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

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

1 子序列匹配

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

1.1 動態(tài)時間彎曲距離

動態(tài)時間彎曲（Dynamic Time Warping，DTW）距離不要求時間序列中的元素與元素之間進(jìn)行一一對應(yīng)匹配，允許序列中的元素自我復(fù)制后再進(jìn)行對齊匹配。當(dāng)時間序列沿時間軸發(fā)生彎曲時，可以在彎曲部分進(jìn)行自我復(fù)制，使兩條時間序列之間的相似波形進(jìn)行對齊匹配。DTW距離很好地解決了時間序列發(fā)生時間軸伸縮和彎曲后的相似性度量問題。例如，給定兩條序列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之間相互“調(diào)整”。P和Q之間“調(diào)整”的路徑稱為彎曲路徑。在兩條序列間存在多條彎曲路徑，可稱根據(jù)最小彎曲代價的路徑計算的距離為動態(tài)時間彎曲距離。

表1 符號及其定義

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

[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之間的距離，可以根據(jù)應(yīng)用而選擇不同的距離度量，比如d（pi，qj）=[pi-qj]。

使用動態(tài)規(guī)劃方法計算數(shù)據(jù)序列P和查詢序列Q間距離的同時，通過累積距離矩陣也可獲得所有P的前綴P[-，e]與Q之間的距離。例如，給定數(shù)據(jù)序列P=<7，9，8，5，2，4>和查詢序列Q=<5，6，7，4，8，7>，以及查詢閾值ε為8。在計算P和Q間的距離時，也可得到所有P的前綴中與Q的距離小于8的子序列。圖1給出了P和Q間的累積距離矩陣。圖1中陰影部分表示兩條時間序列之間的具有最小代價的動態(tài)時間彎曲路徑，累積距離矩陣的右下角得到的值就是這兩條時間序列之間的距離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]就是子序列匹配的結(jié)果。

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

1.2 相關(guān)工作

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

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

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

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

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

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

1.3 FTW技術(shù)

全序列匹配是子序列匹配的一種特殊情況，故可以通過擴(kuò)展一些全序列匹配方法來進(jìn)行子序列匹配。在1.2節(jié)中提到的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]分別是在該段中時間點(diǎn)上的數(shù)值范圍和該段所跨的時間數(shù)；[pUi]和[pLi]分別代表[pRi]的上下邊界。[pUi]和[pLi]分別是在從px到py的[pRi]個元素中的最大和最小的值。因此，P能近似地表示成PA=，m是P被劃分的段數(shù)。可通過計算近似序列間的距離來評估DTW距離。定理1可以保證這種計算方法不會漏掉真正的結(jié)果，即不產(chǎn)生假丟棄。

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

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

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

2 低邊界距離

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

3 基于水平區(qū)域邊界技術(shù)的索引

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

索引中，內(nèi)部節(jié)點(diǎn)用于記錄SBR以及指向SBR中所包含的后綴的葉子節(jié)點(diǎn)的指針，葉子節(jié)點(diǎn)中存放著近似序列的后綴。子序列匹配時，先計算查詢序列Q的近似序列QA，然后再計算QA與每個SBR之間的距離。如果距離大于閾值ε，表明該SBR中不包含與查詢序列相似的子序列，將被過濾掉；否則繼續(xù)計算QA與該SBR中所包含的所有后綴P[s，-]A之間的距離。對于那些能產(chǎn)生結(jié)果的后綴，將通過計算原始數(shù)據(jù)序列P[s，-]與Q之間的距離來決定哪條子序列屬于結(jié)果集。如果子序列P[s，e]與Q之間的距離小于閾值ε，該子序列將被加入結(jié)果集，同時記錄該子序列在數(shù)據(jù)序列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 實驗數(shù)據(jù)

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

[pi=pi-1+zi]

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

（1） 從數(shù)據(jù)集中隨機(jī)選取一條數(shù)據(jù)序列；

（2） 從選取的數(shù)據(jù)序列中隨機(jī)的抽取一段子序列；

（3） 在[[-std10，std10]]中為子序列中的每個元素選取一個隨機(jī)值，std是序列的標(biāo)準(zhǔn)方差；

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

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

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

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

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

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

4.2 性能比較

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

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

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

5 結(jié) 論

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

參考文獻(xiàn)

[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].數(shù)據(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] 孫燾，夏斐，劉洪波.基于動態(tài)規(guī)劃求解時間序列DTW中心[J].計算機(jī)科學(xué)，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] 趙慧，候建榮，施伯樂.一種基于分形時變維數(shù)的非平穩(wěn)時間序列相似性匹配方法[J].計算機(jī)學(xué)報，2005，28（2）：227?231.