一種基于LSH的時(shí)間子序列匹配查詢算法

劉根平，陳葉芳，杜呈透，錢江波

（寧波大學(xué)信息科學(xué)與工程學(xué)院 寧波 315211）

1 引言

時(shí)間序列是按時(shí)間順序排列、隨時(shí)間變化且相互關(guān)聯(lián)的數(shù)據(jù)序列[1,2]。時(shí)間序列數(shù)據(jù)出現(xiàn)在各種各樣的領(lǐng)域中，包括科學(xué)計(jì)量、財(cái)務(wù)數(shù)據(jù)、傳感網(wǎng)絡(luò)、音頻、視頻和人類活動(dòng)等。在這些序列中，典型查詢有找出股票價(jià)格趨勢(shì)相似的公司、找到與某公司有相似銷售模式的公司、找到近幾個(gè)月和某產(chǎn)品銷售模式相似的例子等。

時(shí)間序列的相似性查詢可分為全序列匹配查詢和子序列匹配查詢。全序列匹配查詢是從時(shí)間序列數(shù)據(jù)集中找出所有與查詢序列在整體上相似的時(shí)間序列，即給定N個(gè)數(shù)據(jù)序列 S1,S2,…,SN、一個(gè)查詢序列 Q以及相似性閾值ε，找到所有與Q相似性小于ε的數(shù)據(jù)序列。這里，數(shù)據(jù)序列和查詢序列長(zhǎng)度相等。例如，給定一支股票，已知它在2012-2014年每日的收盤價(jià)，要找出這3年中與它相似的所有股票，這個(gè)問(wèn)題就是全序列匹配問(wèn)題。子序列匹配查詢則是從比查詢序列長(zhǎng)很多的時(shí)間序列中找出所有與查詢序列相似的子序列的位置偏移和長(zhǎng)度，即給定N個(gè)不同長(zhǎng)度的數(shù)據(jù)序列S1,S2,…,SN、一個(gè)查詢序列Q以及相似性閾值ε，找到所有與Q相似性小于ε的子序列。如給定一支股票，已知它在2003-2005年每日的收盤價(jià)，在過(guò)去30年中找出與該股票3年走勢(shì)相似的股票。

子序列匹配是全序列匹配的一般化問(wèn)題。在數(shù)據(jù)庫(kù)序列遠(yuǎn)長(zhǎng)于查詢序列，且最優(yōu)子序列匹配可能出現(xiàn)在數(shù)據(jù)庫(kù)的任何位置時(shí)，實(shí)現(xiàn)高效的子序列匹配是一個(gè)重要的問(wèn)題[3]。對(duì)于現(xiàn)實(shí)世界中的應(yīng)用，如哼唱查詢（query by humming,QbH）、手寫文檔中的字識(shí)別以及大型視頻數(shù)據(jù)庫(kù)和動(dòng)作捕捉數(shù)據(jù)庫(kù)中基于內(nèi)容的檢索等，改進(jìn)子序列匹配算法意義重大。

子序列匹配的算法已有很多，F(xiàn)aloutsos等人[4]提出FRM算法，把數(shù)據(jù)庫(kù)序列劃分成滑動(dòng)窗口，查詢序列劃分成翻轉(zhuǎn)窗口，窗口大小為u，最后把這些窗口用離散傅立葉變換（discrete fourier transform，DFT）轉(zhuǎn)換成 f維的點(diǎn)，它能處理不同長(zhǎng)度的子序列查詢。與查詢序列相似的子序列能在數(shù)據(jù)庫(kù)的任意位置找到。然而，通過(guò)把數(shù)據(jù)序列劃分成滑動(dòng)窗口，F(xiàn)RM產(chǎn)生太多的點(diǎn)需要存儲(chǔ)。DualMatch方法[5]解決了FRM算法的這一問(wèn)題。它把數(shù)據(jù)庫(kù)序列劃分成翻轉(zhuǎn)窗口，查詢序列劃分成滑動(dòng)窗口。數(shù)據(jù)庫(kù)序列劃分成翻轉(zhuǎn)窗口后，DualMatch方法把需要存儲(chǔ)的點(diǎn)降低到FRM算法的 1/u。

雖然通過(guò)DFT后，時(shí)間序列的主要特征被提取出來(lái)，但不能保證提取的特征是完整的，且轉(zhuǎn)換后點(diǎn)的維度f(wàn)的值不能太大，否則建立的索引結(jié)構(gòu)會(huì)遭遇維數(shù)災(zāi)難。為避免這一問(wèn)題，本文不通過(guò)DFT的方法對(duì)時(shí)間序列進(jìn)行處理，而是采用局部敏感散列（locality sensitive hashing，LSH）技術(shù)。

LSH有堅(jiān)實(shí)的理論依據(jù)，在高維數(shù)據(jù)空間中表現(xiàn)優(yōu)異。LSH的基本思想是將距離近的對(duì)象以很高的概率散列到同一個(gè)桶中，而距離遠(yuǎn)的對(duì)象以很低的概率散列到同一個(gè)桶中。通過(guò)這樣的處理，可以過(guò)濾很多不相似的對(duì)象，避免不必要的比較，從而大大提高檢索速度。因此，被廣泛應(yīng)用于許多場(chǎng)景中，包括基于內(nèi)容的圖像檢索[6]、音頻檢索[7]、視頻復(fù)制檢測(cè)[8,9]等。

2 相關(guān)工作

2.1 序列匹配

全序列匹配第一次出現(xiàn)在Agrawal[10]的文章中，它的主要思想如下:首先，把長(zhǎng)度為n的數(shù)據(jù)庫(kù)序列通過(guò)DFT轉(zhuǎn)換到頻域空間，分別提取它們的前f個(gè)特征(f

FRM算法是Faloutsos[4]提出的，用來(lái)解決子序列匹配問(wèn)題。它包括索引建立和子序列匹配兩個(gè)階段。在索引建立階段，首先把數(shù)據(jù)庫(kù)序列劃分成大小為u的滑動(dòng)窗口，對(duì)每個(gè)窗口進(jìn)行DFT，轉(zhuǎn)換為f維的點(diǎn)；然后把這些點(diǎn)組織成最小邊界矩形 （minimum bounding rectangle，MBR）；最后把MBR存儲(chǔ)在R*-tree中。在子序列匹配階段，當(dāng)查詢序列Q到來(lái)時(shí)，把它劃分成大小為u的翻轉(zhuǎn)窗口。對(duì)每個(gè)窗口進(jìn)行DFT，轉(zhuǎn)換為f維的點(diǎn)，然后每個(gè)點(diǎn)在R*-tree中進(jìn)行范圍查詢，找到候選集，最后進(jìn)行驗(yàn)證，得到相似子序列。

由于FRM算法把數(shù)據(jù)庫(kù)序列劃分成滑動(dòng)窗口，存儲(chǔ)這些數(shù)據(jù)需要很大的空間消耗，DualMatch[5]解決了這一問(wèn)題。DualMatch在構(gòu)造窗口時(shí)與FRM算法相反，它把數(shù)據(jù)庫(kù)序列劃分為翻轉(zhuǎn)窗口，查詢序列劃分為滑動(dòng)窗口。通過(guò)把數(shù)據(jù)庫(kù)序列劃分為翻轉(zhuǎn)窗口而不是滑動(dòng)窗口，使R*-tree需要的數(shù)據(jù)存儲(chǔ)空間減小到原來(lái)的1/u，減少了所需的存儲(chǔ)空間，但它允許的窗口大小比FRM算法小。DualMatch可以直接在索引中存儲(chǔ)數(shù)據(jù)點(diǎn)，而不是最小邊界矩形。

以上方法不管如何劃分時(shí)間序列，在劃分完之后，都要通過(guò)特征提取函數(shù)對(duì)窗口進(jìn)行特征提取，形成f維的點(diǎn)，這個(gè)過(guò)程實(shí)質(zhì)是一個(gè)降維的過(guò)程。但提取的特征不能保證信息的完整性，且f的值不能太大。因?yàn)閒太大，索引的性能會(huì)受到影響，導(dǎo)致維度災(zāi)難。基于這個(gè)考慮，本文采用LSH算法對(duì)時(shí)間序列進(jìn)行處理。

2.2 局部敏感散列

局部敏感散列算法[11,12]是一種適合高維數(shù)據(jù)的流行算法。它的主要思想是距離相近的點(diǎn)會(huì)以很高的概率散列到同一個(gè)桶中，距離遠(yuǎn)的點(diǎn)散列到同一個(gè)桶中的概率會(huì)很低。它的定義如下[13]。

定義1 散列函數(shù)族H={h:S→U}是(r1,r2,p1,p2)-敏感的，如果對(duì)于任意的v,q∈S有 （其中S為d維點(diǎn)的數(shù)據(jù)空間，D:S×S→R 為相似性度量）:

·如果 D(v,q)≤r1，則 PrH[h(v)=h(q)]≥p1；

·如果 D(v,q)≥r2，則 PrH[h(v)=h(q)]≤p2。

為使 LSH 的散列函數(shù)族有效，需要保證 r1＜r2，p1＞p2。

不同的距離度量有不同的LSH函數(shù)。歐式距離下的LSH 函 數(shù) 為[14]:

其中，x是d維的向量，a是另一個(gè)d維向量，它的每一維都服從p-穩(wěn)定分布。當(dāng)p=2時(shí)，這個(gè)分布為均值為0、方差為1的高斯分布N(0,1)。a·x是向量a和x的點(diǎn)積。w是一個(gè)常量，變量b服從[0,w]的均勻分布。

通過(guò)使用LSH，可以保證距離近的點(diǎn)沖突的概率大于距離遠(yuǎn)的點(diǎn)。這樣可以過(guò)濾很多不相似的對(duì)象，避免不必要的比較，從而大大提高檢索速度。因此，被廣泛應(yīng)用于許多場(chǎng)景中，包括基于內(nèi)容的圖像檢索、音頻檢索、視頻復(fù)制檢測(cè)等。

[6]使用LSH進(jìn)行衛(wèi)星圖像檢索，參考文獻(xiàn)[15]使用LSH對(duì)局部描述子進(jìn)行索引，參考文獻(xiàn)[16]中使用LSH進(jìn)行3D物體索引，參考文獻(xiàn)[7]中使用兩級(jí)LSH索引機(jī)制對(duì)多變音軌進(jìn)行檢測(cè)，許多視頻復(fù)制檢測(cè)系統(tǒng)也使用LSH創(chuàng)建索引[8,9]。除此外，LSH還被用于處理Web數(shù)據(jù)。參考文獻(xiàn)[17]使用LSH對(duì)Web數(shù)據(jù)進(jìn)行重復(fù)檢測(cè)。Google news使用min-hash對(duì)Web上的新聞進(jìn)行協(xié)同過(guò)濾[18]。在生物數(shù)據(jù)方面，Buhler[19,20]使用LSH對(duì)大規(guī)模的DNA序列進(jìn)行相似性比對(duì)。參考文獻(xiàn)[21,22]利用LSH進(jìn)行離群點(diǎn)的檢測(cè)，參考文獻(xiàn)[23]中利用LSH對(duì)時(shí)間序列產(chǎn)生散列簽名，并把對(duì)象不沖突的概率作為距離，然后利用這個(gè)距離進(jìn)行剪枝操作。

與參考文獻(xiàn)[23]不同，本文把數(shù)據(jù)庫(kù)序列劃分為大小相等的翻轉(zhuǎn)窗口，查詢序列劃分成滑動(dòng)窗口。但不采用DFT對(duì)窗口進(jìn)行轉(zhuǎn)換，而是把劃分好的每個(gè)窗口看成一個(gè)高維的點(diǎn)，直接用LSH對(duì)窗口進(jìn)行散列，既保留了時(shí)間序列信息，又會(huì)避免維度災(zāi)難。通過(guò)散列步驟把數(shù)據(jù)庫(kù)序列的窗口建成索引；待查詢序列到來(lái)時(shí)，用查詢序列的窗口在索引中進(jìn)行查詢，得到候選序列。

3 LSHSM算法及實(shí)現(xiàn)

3.1 基礎(chǔ)知識(shí)

本文所用的符號(hào)及含義見(jiàn)表1。

表1 符號(hào)及含義

定義2 時(shí)間序列S是一個(gè)隨時(shí)間變化的有序序列S=<(t1,s1),(t2,s2),…,(tm,sm),>。其中(ti,si)(i∈[1,m])表示 ti時(shí)刻的值為si，后文為方便把S簡(jiǎn)記為S=s1,s2,…,sm。

時(shí)間序列可以很長(zhǎng)，有時(shí)包含上億個(gè)觀察值。但在本文中，只關(guān)注時(shí)間序列的子部分，即時(shí)間子序列。

定義3 時(shí)間序列S的子序列Si,j是起始于si，終止于sj的短序列，Si,j=si,si+1,…,sj。

定義5 序列 X=x1,…,xN，Y=y1,…,yN是 ε-匹配，當(dāng)且僅當(dāng) D(X,Y)≤ε。

引理1[4]如果長(zhǎng)度相同的兩個(gè)序列Si和Qii是ε-匹配，則任意的序列對(duì)（Sij,Qij）也是ε-匹配。即:

這個(gè)引理保證了用窗口進(jìn)行處理時(shí)不會(huì)有假陰性的序列。

引理2[5]當(dāng)長(zhǎng)度相同的兩個(gè)序列S和Q分別劃分為p個(gè)窗口wsi和 wqi(1≤i≤p)，如果 S和 Q是 ε-匹配，則至少有一對(duì)對(duì)應(yīng)的窗口(wq,ws)是-匹配。即:

3.2 LSHSM算法的思想

要解決的問(wèn)題是:給定一個(gè)查詢序列，在給定的數(shù)據(jù)庫(kù)中找出與查詢序列最相似的幾個(gè)子序列。

首先把數(shù)據(jù)庫(kù)序列分成大小為u的翻轉(zhuǎn)窗口，不采用DFT，而直接把這個(gè)窗口看成u維的點(diǎn)，利用LSH的散列函數(shù)h對(duì)這些窗口進(jìn)行散列。

LSH算法是一個(gè)“過(guò)濾+驗(yàn)證”的框架。從LSH的原理可以看出，散列函數(shù)的過(guò)濾效果越好，需要進(jìn)行的距離計(jì)算次數(shù)會(huì)越少，查詢效率也會(huì)越高。即距離近的窗口沖突的概率越大，距離遠(yuǎn)的窗口沖突的概率越小，LSH的查詢質(zhì)量和查詢效率就會(huì)越高。如果只使用一個(gè)LSH函數(shù)會(huì)產(chǎn)生很多的假陽(yáng)性點(diǎn)，過(guò)濾效果不理想。但如果使用的散列函數(shù)個(gè)數(shù)太多，又會(huì)導(dǎo)致假陰性點(diǎn)增多。所以從H散列函數(shù)族中隨機(jī)均勻獨(dú)立地選擇k個(gè)hi(·)組成函數(shù)g(·)=。通過(guò)散列函數(shù)g(·)將數(shù)據(jù)序列所有窗口映射到一個(gè)散列表中T(·)；但一個(gè)散列表可能會(huì)把真正相似的窗口遺漏，故采用 L 個(gè)這樣的函數(shù) g1(·),g2(·),…,gL(·)，每一次把數(shù)據(jù)庫(kù)中所有的窗口都散列到散列表中，共有L個(gè)散列表。

待給定的查詢序列Q到來(lái)后，先把它劃分成長(zhǎng)度為u的滑動(dòng)窗口wqi，每次滑動(dòng)一格。對(duì)每個(gè)窗口分別計(jì)算g1(wqi)、g2(wqi)、…、gL(wqi)。以落入散列表 Tj(·)的桶 gj(wqi)中的所有窗口作為候選集。

經(jīng)過(guò)上述處理，假設(shè)與查詢窗口wq距離為r的窗口通過(guò)h(·)散列與wq沖突的概率為 p0，那么該窗口與 wq在L張散列表中至少?zèng)_突一次的概率為1-，于是與wq距離不大于r的點(diǎn)被作為查詢結(jié)果而返回的概率就不小于1-。選擇合適的k、L會(huì)得到比較好的結(jié)果。

這樣對(duì)于候選集中的所有窗口，計(jì)算其起始偏移位置，獲取與查詢序列Q長(zhǎng)度相同的子序列作為候選子序列，比較其與Q之間的距離，選出距離最近的K個(gè)子序列。

所以對(duì)數(shù)據(jù)序列的每個(gè)窗口根據(jù)式 （1）進(jìn)行散列計(jì)算，計(jì)算k次，得到一個(gè)g(·)，存儲(chǔ)在散列表中，如此重復(fù)L次，得到L個(gè)散列表，這樣就建立好了索引。待查詢序列Q到來(lái)時(shí)，首先把它劃分成滑動(dòng)窗口，總共有|Q|-u+1個(gè)滑動(dòng)窗口，對(duì)每個(gè)窗口同樣運(yùn)用LSH進(jìn)行散列處理，取出Q的每個(gè)窗口所在的L個(gè)桶g(·)中的數(shù)據(jù)序列窗口，由之前分析可知，這些窗口將以1-(1-pk0)L的概率被返回。

圖1說(shuō)明了LSH處理序列的過(guò)程。數(shù)據(jù)序列S被劃分成翻轉(zhuǎn)窗口，ws是它的一個(gè)窗口。每個(gè)窗口經(jīng)過(guò)兩個(gè)g(·)函數(shù)處理后，映射到散列表T1、T2中。查詢序列Q到來(lái)時(shí)，首先劃分成滑動(dòng)窗口，wq是它的一個(gè)窗口。wq經(jīng)過(guò)兩個(gè)g(·)處理后，映射在T1的2號(hào)桶中、T2的2號(hào)桶中。取出這兩個(gè)桶中的數(shù)據(jù)序列窗口作為候選，進(jìn)行后處理。在后處理中，由于要找的與查詢序列長(zhǎng)度相同的子序列，所以要計(jì)算子序列的起始偏移。圖2描述了計(jì)算子序列起始偏移的過(guò)程。

圖1 LSH處理過(guò)程

圖2 算法后處理

3.3 算法實(shí)現(xiàn)

3.3.1 構(gòu)建索引算法實(shí)現(xiàn)

輸入:數(shù)據(jù)庫(kù)序列S，窗口大小u，LSH參數(shù)k、L。

輸出:LSH索引。

構(gòu)建索引算法的實(shí)現(xiàn)步驟如下:

（1）初始化索引；

（3）對(duì)于每個(gè)窗口，對(duì)L個(gè)散列表中的每個(gè)表，用LSH散列函數(shù)hi進(jìn)行散列值的計(jì)算，重復(fù)k次；

（4）存儲(chǔ)信息到散列表中。

3.3.2 查詢算法實(shí)現(xiàn)

輸入:索引，查詢序列Q。

輸出:與Q相似的子序列。

查詢算法實(shí)現(xiàn)步驟如下。

（1）初始化。把Q劃分為|Q|-u+1個(gè)滑動(dòng)窗口。

（2）查詢索引。對(duì)于每個(gè)滑動(dòng)窗口，對(duì)L個(gè)散列表中的每個(gè)表，用LSH散列函數(shù)hi進(jìn)行散列值的計(jì)算，重復(fù)k次，得到桶信息；取出窗口所在桶的所有數(shù)據(jù)當(dāng)成候選。

（3）后處理。對(duì)候選集中的每個(gè)記錄；在數(shù)據(jù)庫(kù)中找出對(duì)應(yīng)的子序列；計(jì)算與Q的距離；若相似，則輸出。

4 實(shí)驗(yàn)驗(yàn)證

本節(jié)將通過(guò)合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集來(lái)評(píng)估本文所提出算法的性能，并和線性掃描算法進(jìn)行比較。算法用Java語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)在Intel Core i3-3203.3 GHz、4 GB內(nèi)存的機(jī)器上進(jìn)行。

4.1 數(shù)據(jù)集

利用幾個(gè)常用的用于評(píng)估算法的時(shí)間序列數(shù)據(jù)集，包括合成數(shù)據(jù)集Walk1M、真實(shí)數(shù)據(jù)集stock和stock2，它們的數(shù)據(jù)集信息見(jiàn)表2。

表2 數(shù)據(jù)集信息

（1）Walk1M

Walk1M[4,5,25]包含1000000個(gè)數(shù)據(jù)點(diǎn)。它的第一個(gè)點(diǎn)設(shè)置為1.5，而其之后的點(diǎn)是通過(guò)在前一個(gè)點(diǎn)的基礎(chǔ)上加上一個(gè)范圍在[-0.001,0.001]的隨機(jī)值形成的。

（2）stock

stock數(shù)據(jù)集包含紐約證券交易所的408家公司25年中每日的收盤價(jià)。數(shù)據(jù)集是從Yahoo Finance[26]收集的。序列總長(zhǎng)度為1916833個(gè)數(shù)據(jù)點(diǎn)。

（3）stock2

stock2[26]數(shù)據(jù)集包含紐約證券交易所的 500家公司25年中每日的開盤價(jià)。數(shù)據(jù)集是從Yahoo Finance收集的。每個(gè)序列長(zhǎng)度為6480個(gè)數(shù)據(jù)點(diǎn)，把所有序列級(jí)聯(lián)成一個(gè)長(zhǎng)序列，長(zhǎng)度為3240000個(gè)數(shù)據(jù)點(diǎn)。

4.2 實(shí)驗(yàn)對(duì)比

LSHSM算法是一個(gè)近似算法，需要驗(yàn)證它的有效性。因此，采用與線性掃描算法進(jìn)行Top5查詢對(duì)比的方式驗(yàn)證LSHSM算法的有效性。

（1）評(píng)價(jià)標(biāo)準(zhǔn)

3個(gè)評(píng)價(jià)標(biāo)準(zhǔn):運(yùn)行時(shí)間、準(zhǔn)確率、訪問(wèn)率。

運(yùn)行時(shí)間:在相同運(yùn)行環(huán)境下，算法運(yùn)行時(shí)間越少，說(shuō)明算法越有效。

假設(shè)查詢點(diǎn)為Q，用I(Q)表示查詢返回的結(jié)果集合，A(Q)表示數(shù)據(jù)集中所有滿足查詢條件的點(diǎn)的集合。召回率和精度的定義為:

召回率recall表示查詢結(jié)果集中滿足查詢條件的點(diǎn)的數(shù)量與數(shù)據(jù)集中所有滿足查詢條件點(diǎn)的數(shù)量比例，精度precision表示查詢結(jié)果集中滿足查詢條件的點(diǎn)的數(shù)量與查詢結(jié)果集中所有點(diǎn)的數(shù)量的比例[27]。在Topk查詢中，召回率等于精度。用召回率表示準(zhǔn)確率。

訪問(wèn)率是指訪問(wèn)數(shù)據(jù)庫(kù)的比例。用C(Q)表示LSH查詢得到的候選子序列集合，M(Q)表示數(shù)據(jù)庫(kù)中所有長(zhǎng)度為|Q|的子序列集合。訪問(wèn)率可以表示為:

（2）算法的有效性

圖3、圖4、圖5驗(yàn)證了LSHSM算法的有效性。在實(shí)驗(yàn)中，由于各數(shù)據(jù)集的特性各不相同，所以LSHSM算法取的參數(shù)值不盡相同。在Walk1M數(shù)據(jù)集中，窗口大小u為100，散列表個(gè)數(shù)L為1，散列函數(shù)個(gè)數(shù)k為5；stock數(shù)據(jù)集中，窗口大小u為50，散列表個(gè)數(shù)L為2，散列函數(shù)個(gè)數(shù)k為4；stock2數(shù)據(jù)集中，窗口大小u為50，散列表個(gè)數(shù)L為3，散列函數(shù)個(gè)數(shù)k為3。

圖3 與線性掃描算法運(yùn)行時(shí)間的對(duì)比

圖4 與線性掃描算法準(zhǔn)確率的對(duì)比

圖5 與線性掃描算法訪問(wèn)率的對(duì)比

圖3、圖4、圖5分別是LSHSM算法與線性掃描算法在3個(gè)數(shù)據(jù)集中進(jìn)行Top5查詢運(yùn)行10次的運(yùn)行時(shí)間、準(zhǔn)確率、訪問(wèn)量的對(duì)比。可以看出，LSHSM算法的運(yùn)行時(shí)間有很大的提高；LSHSM算法的準(zhǔn)確率接近100%，幾乎和線性掃描相同；相比于線性掃描，LSHSM算法訪問(wèn)的數(shù)據(jù)庫(kù)比率小了3個(gè)數(shù)量級(jí)。

實(shí)驗(yàn)證明LSHSM算法是有效的，且性能比線性掃描算法有極大的提高。

4.3 參數(shù)的影響

LSHSM算法中參數(shù)k、L、u的選擇對(duì)算法性能有很大的影響。k太小，散列到同一個(gè)桶的概率比較大，得到的候選對(duì)象會(huì)很多，其中包括許多假陽(yáng)性對(duì)象，增加計(jì)算開銷；k太大，散列到同一個(gè)桶的概率變小，得到的候選對(duì)象變少，這樣不僅把假陽(yáng)性對(duì)象過(guò)濾掉，同時(shí)也把真正近似的對(duì)象過(guò)濾掉，準(zhǔn)確率不高。L越小，散列到同一個(gè)桶中的概率越小，得到的候選對(duì)象越少，找到真正近似對(duì)象的準(zhǔn)確性越低；L越大，散列到同一個(gè)桶中的概率越大，得到的候選對(duì)象越多，找到真正近似對(duì)象的準(zhǔn)確性越高，但同時(shí)訪問(wèn)數(shù)據(jù)庫(kù)的比率會(huì)越大。所以，需要考慮這兩個(gè)參數(shù)的影響，使算法的性能最好。

實(shí)驗(yàn)中考慮3個(gè)參數(shù)對(duì)算法性能的影響:散列表的個(gè)數(shù)L、散列函數(shù)個(gè)數(shù)k以及劃分窗口大小u。理論上來(lái)說(shuō)，u越大，LSHSM算法計(jì)算越快，u太大可能導(dǎo)致找不到相似子序列。另一方面，u越小，越能精確找到子序列，準(zhǔn)確度越高，但是窗口太小，LSHSM算法所花的時(shí)間會(huì)越多。

在 Walk1M 數(shù)據(jù)集中，k=5，L=1，u=80；stock 數(shù)據(jù)集中，k=4，L=2，u=50；stock2 數(shù)據(jù)集中，k=4，L=3，u=50。實(shí)驗(yàn)中，在改變其中一個(gè)參數(shù)時(shí)，其他兩個(gè)參數(shù)固定不變。

（1）窗口大小u對(duì)算法的影響

圖6顯示了在固定k和L時(shí)，窗口大小u對(duì)算法性能的影響。

圖6 窗口大小u對(duì)算法性能的影響

從圖6中可以看出，u變大時(shí)，算法構(gòu)建的索引會(huì)減小，查詢窗口個(gè)數(shù)也隨著減小，時(shí)間呈整體下降的趨勢(shì)。但隨著u的增大，LSH得到的候選集會(huì)減小，導(dǎo)致假陰性節(jié)點(diǎn)增加，算法的準(zhǔn)確性會(huì)有所下降。

（2）散列表個(gè)數(shù)L對(duì)算法的影響

圖7顯示了在固定k和u時(shí)，散列表個(gè)數(shù)L對(duì)算法性能的影響。L達(dá)到一定數(shù)值，準(zhǔn)確率已達(dá)到很高，再繼續(xù)增大L，得到的效果也已經(jīng)達(dá)到飽和。特別是Walk1M數(shù)據(jù)集中，在L=5時(shí)的效果已經(jīng)非常好，沒(méi)有必要再進(jìn)行更大L的比較。

從圖7中可以得出，其他參數(shù)固定時(shí)，隨著散列表個(gè)數(shù)的增加，算法構(gòu)建的索引增大，需要查詢的散列表增多，候選集增加，因此數(shù)據(jù)訪問(wèn)率呈增長(zhǎng)趨勢(shì)，查詢所用的時(shí)間也呈上升趨勢(shì)。散列表個(gè)數(shù)增大會(huì)增加兩個(gè)對(duì)象沖突的概率，使得算法準(zhǔn)確性增加。

（3）散列函數(shù)個(gè)數(shù)k對(duì)算法的影響

圖8顯示了在固定u和L時(shí)，散列函數(shù)個(gè)數(shù)k對(duì)算法性能的影響。

圖7 散列表個(gè)數(shù)L對(duì)算法性能的影響

圖8 散列函數(shù)個(gè)數(shù)k對(duì)算法性能的影響

從圖8可知，其他參數(shù)固定時(shí)，隨著散列函數(shù)個(gè)數(shù)k的增加，候選集會(huì)減少，數(shù)據(jù)訪問(wèn)率會(huì)降低，所需查詢時(shí)間呈下降趨勢(shì)。但是隨著散列函數(shù)個(gè)數(shù)的增加，會(huì)把真正的近鄰散列到其他桶中，準(zhǔn)確率會(huì)有所下降。

5 結(jié)束語(yǔ)

時(shí)間序列的相似性查詢已有很長(zhǎng)的研究歷史，在子序列匹配問(wèn)題中，傳統(tǒng)基于樹的方法雖然能很好地解決低維空間的問(wèn)題，但當(dāng)數(shù)據(jù)維度增加時(shí)，它們的效果甚至不如線性掃描算法。本文提出了用LSH技術(shù)與時(shí)間序列結(jié)合的方法，既能避免高維數(shù)據(jù)導(dǎo)致的維度災(zāi)難，又能保留時(shí)間序列的主要特征。利用LSH的局部敏感性，把相似的子序列聚集到一起，過(guò)濾掉很多不相似的對(duì)象，減少所需的比較次數(shù)，提高效率。實(shí)驗(yàn)結(jié)果表明，該方法在性能上有很大的提升。

參考文獻(xiàn)

1 肖輝.時(shí)間序列的相似性查詢與異常檢測(cè)（博士學(xué)位論文）.復(fù)旦大學(xué),2005 Xiao H.Similarity search and outlier detection in time series(doctor dissertation).Fudan University,2005

2 曾海泉.時(shí)間序列挖掘與相似性查找技術(shù)研究 （博士學(xué)位論文）.復(fù)旦大學(xué)，2003 Zeng H Q.Research on mining and similarity search in time series database(doctor dissertation).Fudan University,2003

3 Fu T.A review on time series data mining.Engineering Applications of Artificial Intelligence,2011,24(1):164～181

4 Christos F,Ranganathan M,Manolopoulos Y.Fast subsequence matching in time-series databases.Proceedings of ACM SIGMOD Conference,Minneapolis,USA,1994

5 Moon Y S,Whang K Y,Loh W K.Duality-based subsequence matching in time-series databases.Proceedings of the 17th International Conference on Data Engineering,Heidelberg,Germany,2001:263～272

6 Ruben B,Homaifar A,Gebril M,et al.Satellite image retrieval using low memory locality sensitive hashing in Euclidean space.Earth Science Informatics,2011,4(1):17～28

7 Yi Y,Michel C,Vincent O,et al.Local summarization and multi-level LSH for retrieving multi-variantaudio tracks.Proceeding soft he17th ACM International Conference on Multimedia,Beijing,China,2009:341～350

8 Paisitkriangkrai S,Mei T,Zhang J,et al.Scalable clip-based near-duplicate video detection with ordinal measure.Proceedings of the ACM International Conference on Image and Video Retrieval,Xi’an,China,2010:121～128

9 Zhu L,Liu T,Gibbon D,et al.Effective and scalable video copy detection.Proceedings of the 11th ACM International Conference on Multimedia Information Retrieval,Philadelphia,USA,2010:119～128

10 Agrawal R,Faloutsos C,Swami A.Efficient similarity search in sequence databases.Proceedings of the 4th International Conference FODO,Chicago,USA,1993:69～84

11 Indyk P,Motwani R.Approximate nearest neighbors:towards removing the curse of dimensionality.Proceedings of the 30th Annual ACM Symposium on Theory of Computing,Dallas,USA,1998:604～613

12 Gionis A,Indyk P,Motwani R.Similarity search in high dimensions via hashing.Proceedings of the 25th International Conference on Very Large Data Bases (VLDB),Edinburgh,UK,1999:518～529

13 甘駿豪.基于動(dòng)態(tài)碰撞檢測(cè)的位置敏感哈希（碩士學(xué)位論文）.中山大學(xué),2013 Gan J H.Locality-sensitive hashing scheme based on dynamic collision counting(master dissertation).Sun Yat-sen University,2013

14 Datar M,Nicole I,Indyk P,et al.Locality-sensitive hashing scheme based on p-stable distributions.Proceedings of the 20th Annual Symposium on Computational Geometry,New York,USA,2004:253～262

15 Yan K,Sukthankar R,Huston L.Efficient near-duplicate detection and sub-image retrieval.ACM Multimedia,2004,4(1):869～876

16 Bogdan M,Shan Y,Sawhney H S,et al.Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimation.IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(7):1111～1126

17 Manku G S,Jain A,Sarma A D.Detecting near-duplicates for web crawling.Proceedings ofthe 16th International Conference on World Wide Web,Banff,Alberta,Canada,2007:141～150

18 Das A S,Datar M,Garg A,et al.Google news personalization:scalable online collaborative filtering.Proceedings of the 16th International Conference on World Wide Web,Banff,Alberta,Canada,2007:271～280

19 Buhler J. Efficient large-scale sequence comparison by locality-sensitive hashing.Bioinformatics,2001,17(5):419～428

20 Buhler J.Provably sensitive indexing strategies for biosequence similarity search.Journal of Computational Biology,2003,10(3～4):399～417

21 Wang Y,Parthasarathy S,Tatikonda S.Locality sensitive outlier detection:a ranking driven approach.Proceedings of the IEEE 27th International Conference on Data Engineering(ICDE),Hannover,Germany,2011:410～421

22 Pillutla M R,Raval N,Bansal P,et al.LSH based outlier detection and its application in distributed setting.Proceedings ofthe 20th ACM International Conference on Information and Knowledge Management,Glasgow,Scotland,UK,2011:2289～2292

23 湯春蕾,董家麒.基于LSH的時(shí)間子序列查詢算法.計(jì)算機(jī)學(xué)報(bào),2012,35(11):2228～2236 Tang C L,Dong J Q.Similarity query oftime series subsequences based on LSH.Chinese Journal of Computers,2012,35(11):2228～2236

24 李俊奎.時(shí)間序列相似性問(wèn)題研究 （博士學(xué)位論文）.華中科技大學(xué),2008 Li J K.Research on time series sequence similarity(doctor dissertation).Huazhong University of Science and Technology,2008

25 MoonY S,WhangK Y,HanW S.Generalmatch:a subsequence matching method in time-series databases based on generalized windows.Proceedings of the ACM SIGMOD International Conference on Management of Data,Madison,Wisconsin,USA,2002:382～393

26 CaiY,Ng R.Indexing spatio-temporaltrajectories with Chebyshevpolynomials.Proceeding soft he ACM SIGMOD International Conference on Management of Data,Baltimore,Maryland,USA,2004:599～610

27 凌康.基于位置敏感哈希的相似性搜索技術(shù)研究 （碩士學(xué)位論文）.南京大學(xué),2012 Ling K.Research on locality sensitive hashing-based similarity Search(marster dissertation).Nanjing University,2012