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

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

1 引 言

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

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

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

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

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

主要工作如下:

1)將實(shí)數(shù)形式的時間序列轉(zhuǎn)化成整型的ID序列.

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

3)實(shí)現(xiàn)了本文的算法.將局部敏感哈希算法和動態(tài)時間彎曲相結(jié)合,通過實(shí)驗(yàn)證明大大加快了檢索的速度.

2 問題定義

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

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

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

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

(1)

動態(tài)時間彎曲首次被應(yīng)用是在語音識別領(lǐng)域中,是一種準(zhǔn)確性較高的時間序列距離度量方法.該方法區(qū)別于傳統(tǒng)的歐氏距離,可以通過彎曲時間軸,實(shí)現(xiàn)一點(diǎn)對應(yīng)多點(diǎn)的匹配,從而可以度量兩條不等長的時間序列.

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

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

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之間的距離.

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

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

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

令U為對象的集合,d為距離函數(shù).對于哈希家族H,如果任意兩個對象x、y滿足如下兩個條件,則認(rèn)為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.解釋了不相似的兩個對象會以很低的概率哈希到同一個桶中.

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

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

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

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

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

(6)

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

(7)

(8)

ID=(row-1)*COLUMN_NUM+col

(9)

給定參數(shù)COLUMN_NUM即桶的個數(shù),遍歷原始序列數(shù)據(jù)找到其最大值和最小值,根據(jù)給定的COLUMN_NUM,確定每個桶的寬度,然后就可以將原始的序列分配到每一個桶中,并為其分配ID.實(shí)數(shù)值的時間序列則映射為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′;

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

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

2.2 將ID序列投影到局部敏感哈?？臻g

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

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

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

算法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 建立候選集并驗(yàn)證

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

算法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 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

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

表1 數(shù)據(jù)集描述Table 1 DataSet description

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

3.2 TQLD算法分析

TQLD算法第一步需要將原始的實(shí)數(shù)形式的時間序列轉(zhuǎn)變?yōu)檎偷腎D序列,即將每條序列映射到不同的格子中,用每個格子的ID組成的序列來表示原始的序列,每個格子的大小等同.因此TQLD算法的準(zhǔn)確度會受到格子的長度和寬度這兩個參數(shù)的影響,長和寬的取值越小,和原始序列的貼近程度會越強(qiáng).

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

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

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

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

3.3 算法性能比較

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

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

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

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

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

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

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

我們對Symobols數(shù)據(jù)集進(jìn)行了不同DTW閾值下的范圍查詢,Jaccard閾值會根據(jù)DTW閾值的設(shè)定相應(yīng)的改變,實(shí)驗(yàn)運(yùn)行時間比較如圖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

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

4 結(jié) 論

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