基于LSH的時間序列DTW相似性查詢

李 敏,于長永,張 峰,馬海濤,趙宇海

(東北大學 計算機科學與工程學院,沈陽 110819)E-mail:1045317573@qq.com

1 引 言

時間序列挖掘目的是發現時序數據中潛在的有價值的知識,主要包括時間序列預測、聚類、異常檢測、分類、相似性查詢等內容.其中相似性查詢是時間序列挖掘中最根本的一個問題,在時間序列數據的分析中,處理相似性問題是研究其他相關任務的基礎.時間序列相似性查詢就是在時序數據庫中找到與給定序列相似的序列.鑒于時間序列的海量性和高維性,如何快速準確的找到相似的序列是我們亟需解決的問題.

時間序列的相似度通過計算兩條序列間的距離來衡量,所以時間序列的距離度量方式在相似性查詢中扮演了至關重要的作用.最常用的兩種距離度量分別是歐氏距離和動態時間彎曲.鑒于歐氏距離只能處理等長的時間序列,不允許時間軸彎曲等缺點,動態時間彎曲[14]被認為是較準確的一種度量方式,成為人們的首選.然而由于使用動態時間彎曲計算距離的時間復雜度為O(n2),n為時間序列的長度,對于處理海量的高維時間序列來說,計算成本太高.所以在盡可能的保留序列的原始信息的前提下,將高維的時間序列降到低維空間中去處理,從而降低計算的成本,是時間序列相似性查詢的關鍵.

為加快動態時間彎曲的計算速度,Sakoe等人[9]提出通過限制路徑的搜索范圍來提高計算效率,范圍的大小由參數控制.Sakoe-Chiba band[9]是對稱型的彎曲窗口,而Itakura等人[10]提出的是平行四邊形的彎曲窗口,這兩種經典的方法都得到了廣泛的應用,減少了計算時間的消耗.本文我們采用的局部敏感哈希技術可以實現將高維的時間序列降到低維空間中去處理,進而加快計算的速度.

為了減少數據庫中序列的數量,盡可能的避免不相似的序列之間的計算,加快查詢的速度,研究者提出多種計算DTW下界的算法.比如LB_Kim[1],LB_Yi[2],LB_Keogh[3],其中LB_Keogh一經提出,該方法就得到了廣泛應用.LB_Keogh找到每一條查詢序列的上包絡線U和下包絡線L,計算候選序列超出上下包絡線區域的部分之和作為下界,通過證明該方法較LB_Kim,LB_Yi更為緊湊,不會產生漏報.鑒于時間序列的高維性,Keogh等人又提出了低維空間下計算下界的方法LB_PAA[3],在一定程度上降低了動態時間彎曲的計算時間.下界的提出是為了提前篩選掉一些不相似的序列,但是,當處理的時間序列走勢波動程度較大時,現有的下界算法往往效果欠佳.下界作為一種過濾技術是為了提前篩選掉一些不相似的序列,避免過多冗余的計算,進而加快檢索的速度.本文我們使用的局部敏感哈希同樣可以作為一種過濾技術,通過提前過濾掉一些不相似的序列,大大加快了查詢的速度.

時間序列相似性查詢分為全序列查詢和子序列查詢,本文目標旨在解決全序列查詢問題.因為時間序列的高維性特點,利用dtw直接在原始的序列上操作會存在時間復雜度高等問題.所以我們采用一種新穎的技術,即局部敏感哈希.Lsh的第一個優勢是將高維時間序列降到低維空間,加快了計算的速度;第二個優勢就是提前過濾掉一些不相似的序列,減少了冗余的計算,加快了查找的速度.

主要工作如下:

1)將實數形式的時間序列轉化成整型的ID序列.

2)將時間序列映射到局部敏感哈希空間中.為了保證時間序列的相似性在動態時間彎曲空間下比較和在局部敏感哈希空間下比較是等價的.將時間序列隨機抻長為原始序列的w倍.

3)實現了本文的算法.將局部敏感哈希算法和動態時間彎曲相結合,通過實驗證明大大加快了檢索的速度.

2 問題定義

定義1.(時間序列):時間序列T是按相等的時間采樣的數據點構成的序列,T=(t1,t2,t3,…,tn),ti(i∈…n)是任意的實數,n為時間序列的長度.

定義2.(時間序列數據庫):時間序列數據庫TS是N條時間序列的集合,TS=(t1,t2,t3,…,tn),ti(i∈1…N)是一條長度為n的時間序列.

定義3.(時間序列相似性查詢):給定一條查詢序列Q、時間序列數據庫TS、相似性度量函數SIM和閾值τ,時間序列相似性查詢就是要從時間序列數據庫TS中找到和查詢序列Q相似程度大于等于τ的所有時間序列.即

R={C∈TS|SIM(Q,C)≥τ}

(1)

動態時間彎曲首次被應用是在語音識別領域中,是一種準確性較高的時間序列距離度量方法.該方法區別于傳統的歐氏距離,可以通過彎曲時間軸,實現一點對應多點的匹配,從而可以度量兩條不等長的時間序列.

給定兩條時間序列X=(x1,x2,x3,…xm)和Y=(y1,y2,y3,…yn),它們的動態時間彎曲距離定義為:

定義4.(動態時間彎曲):

D(<>,<>)=0

(2)

D(X,<>)=D(<>,Y)=

(3)

(4)

(5)

其中,<>表示空序列,Rest(X)=x2,x3,x4,…xm,Rest(Y)=y2,y3,y4,…yn,d(xi,yj)表示xi與yj之間的距離.

動態時間彎曲距離就是利用動態規劃的思想尋找一條具有最小彎曲代價的彎曲路徑,該算法的時間復雜度為O(mn).

局部敏感哈希是一種應用于高維空間中的近似最近鄰查詢方法.它的基本思想是將原本相近的對象以很大的概率hash到同一個桶中,而原本較遠的對象hash到同一個桶中的概率會很低.形式化描述[14]如下:

定義5.(局部敏感哈希):

令U為對象的集合,d為距離函數.對于哈希家族H,如果任意兩個對象x、y滿足如下兩個條件,則認為H是(d1,d2,p1,p2)敏感的.

如果d(x,y)≤d1,則h(x)=h(y)的概率至少為p1;

如果d(x,y)≥d2,則h(x)=h(y)的概率至多為p2;

其中d(x,y)表示x和y之間的距離,d1p2時H才有意義.

條件1.解釋了相近的兩個對象會以很高的概率哈希到同一個桶中;

條件2.解釋了不相似的兩個對象會以很低的概率哈希到同一個桶中.

本文我們采用的是漢明距離下的哈希函數即:

H={vi:vi(x1,x2,x3,…,xm)=xi|i[m]}.

其是 (d1,d2,1-d1/m,1-d2/m) 敏感的.

2.1 將時間序列映射為ID序列

為了能夠使用漢明距離度量時間序列的相似度,第一步需要將實數形式的時間序列數據轉化成字符串.為了避免平移、縮放等外界因素對衡量時間序列相似度帶來的影響,首先需要對時序數據進行標準化,最常用的標準化公式如下:

(6)

經過標準化之后,平移、縮放的影響就可以消除.然后對每一維度的數據分配ID,實數形式的數據即被整型的ID所代替,減少了存儲代價,同時也達到了降維的目的,并且為利用漢明距離度量提供了方便.具體計算ID的公式如下所述:

(7)

(8)

ID=(row-1)*COLUMN_NUM+col

(9)

給定參數COLUMN_NUM即桶的個數,遍歷原始序列數據找到其最大值和最小值,根據給定的COLUMN_NUM,確定每個桶的寬度,然后就可以將原始的序列分配到每一個桶中,并為其分配ID.實數值的時間序列則映射為ID序列.算法如下所示.

算法1.TimeSeriesTranstoIDSequence

Input:

S:time series

COLUMN_NUM:parameter

ROW_NUM:parameter

Output:

S′:ID sequence presentation of S

1.tempS←TimeSeriesNormalization(S);

2.MaxMin←findMaxMin(tempS);

3.S′←?;

4.length←((xmax-xmin)/ROW_NUM)*1.01;

5.width←((Length(S)-1)/COLUMN_NUM)*1.01;

6.for every pointsiof S do

7.row=?(xi-xmin)/length」+1;

8.col=?(i-1)/width」+1;

9.IDi=(row-1)*COLUMN_NUM+col;

10.S′←S′∪IDi;

11.end

12.returnS′;

桶的寬度決定了所能容納的序列的點的個數,原始維度為n的時間序列經過映射為ID序列之后,維度至多為COLUMN_NUM(小于n),達到了降維的目的.所以在計算ID序列的DTW距離時,會大大加快計算的速度,ID序列的彎曲路徑如圖1所示.

圖1 ID序列彎曲路徑匹配圖Fig.1 ID sequence warping path matching graph

2.2 將ID序列投影到局部敏感哈希空間

我們的目的是為了應用漢明距離下的局部敏感哈希技術,所以第二步就是將ID序列映射到局部敏感哈希空間中.映射的方法就是將不同長度的ID序列抻長為原始最大長度的w倍,每一個ID可能被隨機抻長一次或者多次.這樣做的優勢有如下幾點.第一點考慮到ID序列長短不一,大多數的距離度量不能處理不等長的序列,利用抻長技術將ID序列抻長為長度一致的序列,從而可以更好地度量序列之間的相似程度.第二點DTW在計算的過程中允許時間軸的彎曲,所以為了保證時間序列的相似性在動態時間彎曲空間下比較和在局部敏感哈希空間下比較是等價的,則將ID序列上的每一點隨機抻長,從而滿足了序列間一點對應多點的可能,保證了局部偏移不變性.比如在圖2中,兩條序列整體上非常相似,但在x軸上發生了局部偏移,如果利用歐氏距離度量時,會將實線中的a點和虛線中的b點匹配,但實際應該和c點對應,這就會產生較大的誤差,而我們類比dtw中允許時間軸彎曲的思想,通過抻長技術將每一個點重復一次或多次就可以消除這種誤差.

圖2 局部偏移匹配圖Fig.2 Local offset matching graph

為了盡可能的提高準確度,我們會對序列抻長多次,并且將每次抻長的參數保存,以便對查詢序列采取相同的操作.抻長的具體實現算法如下所示:

算法2.StrecthIDSequence

Input:

S′:IDsequence

Output:

StretchS:stretched representation of S′

1.SeriesLength←findLongestSeries(S′);

2.rand←?;

3.for i←0 to 3*SeriesLength

4.numi←generaterandomnumber(0 or 1);

5.rand←rand∪{numi};

6.end

7.StretchS←?;

8.for every point siofS′ do

9.j←0;k←0;

10.while j<3*SeriesLength

11. if(k < length(S′))

12.StretchS←StretchS∪{sk};

13. k←k+randj;

14. else

15. StretchS←StretchS∪{0};

16. j←j+1;

17. end

18.end

19.return StretchS;

2.3 建立候選集并驗證

在將ID序列映射到局部敏感哈希空間中以后,第三步就是利用局部敏感哈希技術進行過濾.將數據庫中抻長后的ID序列中隨機選取某幾個位置進行哈希,構成哈希家族,同樣的我們會對抻長后的序列進行多次哈希,并將哈希過程中的參數保存,對每次的哈希家族構建前綴索引.判斷查詢序列的哈希族和數據庫序列的哈希族是否相同,數據庫中的序列只要滿足有一次的哈希家族和查詢序列的相匹配,我們就將該序列作為候選序列.然后計算該哈希族對應的原始序列和查詢序列之間的DTW距離,如果二者的DTW距離小于或者等于閾值τ,則認為二者是相似的.每一條候選序列的驗證步驟重復如此.對一條序列的哈希算法如下所示:

算法3.HashIDSequence

Input:

S′:IDsequence

m:hash location number

Output:

HashS:hashed representation ofS′

1.hash←?;

2.fori←0 to m

3.numi←randomnumber(0～Length(S′));4.hash←hash∪{numi};

5.forj←0 toi

6. while hashj==hashi

7.numi←randomnumber(0～Length(S′));

8. end

9.hash←hash∪{numi};

10.end

11.end

12.HashS←?;

13.for i←0 to m

14.HashS←HashS∪{S′hashi};

15.end

16.return HashS;

3 實驗結果

3.1 實驗環境與數據

本文實現了提出的算法TQLD,采用基于下界的DTW算法LB_DTW和基于集合的相似性查詢算法STS3,進行了準確性和有效性的對比.全部算法采用Java語言實現,運行在一臺CPU為Intel(R)Core(TM)i5-4200U 1.60gHz,主存大小為4GB的PC機上,操作系統為win10.

表1 數據集描述Table 1 DataSet description

表1是對數據集的描述,分別為數據集的名稱,查詢序列的數目,數據庫中序列的數目,時間序列的長度,以及設定的DTW的閾值和Jaccard閾值.Jaccard閾值的設定是根據給定DTW閾值下相似性序列的查詢數目所決定的,目的是為了使STS3方法查到的相似性序列的數目和DTW查到的數目盡可能的一致,在數目大體相同的情況下,和其他方法進行準確性和有效性的比較.本實驗所采用的數據集來源于UCR(1)www.cs.ucr.edu/～eamonn/time series data/.公開數據集.

3.2 TQLD算法分析

TQLD算法第一步需要將原始的實數形式的時間序列轉變為整型的ID序列,即將每條序列映射到不同的格子中,用每個格子的ID組成的序列來表示原始的序列,每個格子的大小等同.因此TQLD算法的準確度會受到格子的長度和寬度這兩個參數的影響,長和寬的取值越小,和原始序列的貼近程度會越強.

第二步是我們通過分析DTW距離度量的性質,對Plane數據集中相似的時間序列進行了DTW彎曲路徑比對的計算,結果如圖3所示.我們充分利用DTW距離度量允許時間彎曲這一重要特性,將ID序列抻長,抻長為原始最長序列長度的3倍,在抻長的過程中,每個點可能重復一次或多次.

第三步是將漢明距離下的LSH函數應用到抻長的ID序列中,隨機選取ID序列中的某幾個位置進行哈希,若數據庫中存在序列的哈希值和查詢序列的哈希值相同,則將該序列納入候選集合中.在這個過程中我們通過將高維的時間序列降到低維中去處理,提前對數據庫中的序列的哈希值建立前綴索引,進而加快了候選集合的篩選.哈希位置的選取也會對查詢結果的準確性產生影響.

圖3 DTW彎曲窗口分布Fig.3 Warping windows distribution

最后對候選集中的序列利用DTW驗證,候選集合中無效的序列數量越少,TQLD算法的查詢效率越高.因此當候選集中無效和有效的序列數目都較多時,盡管召回率比較理想,但相應的查詢速度也會減慢.通過在Symbols數據集上測試,當DTW閾值設為23時,暴力算法需要進行89550次DTW計算,而TQLD算法只需要進行13195次計算,并且召回率達到0.8左右.

3.3 算法性能比較

3.3.1 固定閾值的算法性能比較

我們針對表1中提供的數據集在三種不同的算法下進行了準確性和有效性的對比.準確性采用找到給定DTW閾值下(DTW閾值和Jaccard閾值在表1中給出)相似的時間序列的召回率和準確率度量,有效性采用找到給定閾值下相似時間序列的平均查詢時間代價度量.

表2 平均時間代價Table 2 Average time cost

我們的實驗分別在4種不同的數據集上進行測試,表2描述了在進行范圍查詢時不同方法的運行速度,圖4和圖5分別展示了在閾值不變的情況下,不同方法在不同數據集上的召回率和準確率.通過分析可以得出LB_DTW雖然查全率和準確率都較高,但是在查詢速度較DTW并沒有明顯的改善,因此可以判斷對于某些數據集,下界的緊致性并不是很好,沒有起到很好的剪枝作用,甚至執行時間有時會超過暴力算法.而基于集合的算法即STS3雖然在很短的時間內就可以完成相似性序列的查詢,但是通過實驗結果得出,STS3的查全率和查準率沒有達到理想的指標,在某些情況下,不能夠近似于DTW度量完成相似性序列的查詢.而我們的方法雖然召回率略低于Lb_DTW算法,但是查詢速度明顯快于Lb_DTW,證明TQLD算法的過濾能力要優于Lb_DTW.因此我們的算法在保持較好的召回率的情況下,較現有算法有效地提高了DTW相似性查詢速度.

圖4 同一閾值的召回率對比Fig.4 Comparison of recall at the same threshold

圖5 同一閾值的準確率對比Fig.5 Comparison of accuracy at the same threshold

3.3.2 不同閾值的算法性能比較

我們對Symobols數據集進行了不同DTW閾值下的范圍查詢,Jaccard閾值會根據DTW閾值的設定相應的改變,實驗運行時間比較如圖6所示.

510.20.040.0016閾值13閾值18閾值23閾值28時間DTWSTS3TQLDLbDTW_0.00810.08.06.04.02.0召回率DTW閾值STS3TQLDLbDTW_13182328圖6 時間對比圖7 不同閾值的召回率對比Fig.6 TimecomparisonFig.7 Comparisonofrecallfordifferentthresholds

通過實驗結果可以得出,我們的方法的運行時間不會受到閾值大小的影響,由圖7可以得出.并且當給定DTW閾值較小的情況下,TQLD的召回率會達到0.88左右,并且查詢時間較DTW方法顯著提升.對比另外兩種方法, 盡管基于下界的Lb_DTW方法召回率、準確率一直維持完美的指標,但是Lb_DTW的查詢速度會受到閾值變化的影響.由圖7可以看出,隨著閾值增大,Lb_DTW的查詢速度不斷減慢.而基于集合的STS3方法盡管運行時間不會受到閾值的影響,但是當DTW閾值較小時,STS3方法的準確率會受到影響,并且不管閾值如何改變,STS3方法的召回率和準確率都略遜色于TQLD方法.

4 結 論

時間序列的相似性查詢是時間序列挖掘中的關鍵問題之一.本文提出一種基于LSH的時間序列DTW相似性近似查詢算法,較好地解決了DTW相似性查詢速度慢的問題.通過與現有的相似性查詢算法的實驗對比,實驗結果顯示了TQLD方法的準確性和有效性,表明該算法在保持較好的召回率的情況下,較現有算法有效地提高了DTW相似性查詢速度.如何進一步提高算法的準確性和降低算法的時間代價,以處理更大規模的時間序列數據的相似性查詢是論文未來工作方向之一.