技術(shù)報告基于線性散列索引的時間序列查詢方法

1、計劃類別 項目編號 項目技術(shù)報告課題名稱 項目主持人 承擔(dān)單位 題目：基于線性散列索引的時間序列查詢方法研究隨著信息化的發(fā)展，大量的數(shù)據(jù)被產(chǎn)生。在新產(chǎn)生的數(shù)據(jù)中，時間序列數(shù)據(jù)是一種重要的數(shù)據(jù)類型，而對該類數(shù)據(jù)進行高效的查詢處理成為了當(dāng)前研究的熱點。本文針對線性散列的索引機制，提出了一種新型的時間序列的查詢處理方法，以降低索引創(chuàng)建時間和提高查詢效率。實驗證明，本方法中的線性散列索引，在創(chuàng)建時的時間耗費有所下降。在查詢階段采用K近鄰與下界距離相結(jié)合的方法，能有效地過濾掉多余的結(jié)果，提高了時間序列查詢處理的效率和精確度。關(guān)鍵詞：時間序列；線性散列；K-近鄰；下界距離Abstract：With the

2、 development of information science，more and more data is generated through different applications.Time series is an important data type，and the research on how to query time series data efficiently has drawn more and more attention.This paper proposes a new time series query processing method based

3、 on linear hash，aiming to reduce the index construction time and improve the query efficiency.The experiment results show that the index construction time has been reduced to some extent.Through the combined method of the K-nearest neighbor and the lower bounding distance in the query phase，redundan

4、t results can be effectively filtered，which improves the efficiency and accuracy of the time series query.Keywords：time series；linear hash；K-nearest neighbor；lower bounding distance1 引言（Introduction）時間序列（Time Series）指同一指標(biāo)的數(shù)值按其先后發(fā)生的時間順序排列而成的數(shù)列，它作為時態(tài)數(shù)據(jù)的一種特殊形式出現(xiàn)在許多領(lǐng)域，如金融的股票交易價格、醫(yī)學(xué)的心腦電圖、氣象的溫濕度走勢、企業(yè)的產(chǎn)銷走勢

5、等。時間序列的表示是針對時間序列的結(jié)構(gòu)復(fù)雜而采取的，將時間序列進行變形的技術(shù)；時間序列的索引是針對如何進行高效存儲，以及快速查詢時間序列的技術(shù)。由于時間序列的數(shù)據(jù)量大和復(fù)雜結(jié)構(gòu)，為表示和索引提出了難題?，F(xiàn)有的檢索技術(shù)，處理大數(shù)據(jù)時經(jīng)常會耗費大量的時間。其相似性度量也往往不夠準(zhǔn)確。國內(nèi)外研究學(xué)者提供了許多相似性度量的技術(shù)，但查詢的完整和準(zhǔn)確程度仍有待提高。本文結(jié)合時間序列分段集成近似表示（Piecewise Aggregate Approximation，PAA）方法1，2，提出了基于線性散列作為索引技術(shù)來處理時間序列查詢的新方法。在時間序列的預(yù)處理階段，提出一種新的規(guī)范化方法，很好的保留了時間

6、序列的原始形態(tài)。采用線性散列索引機制，對時間序列進行有效靈活的存取，自然地處理存儲過程中產(chǎn)生的沖突。在時間序列的查詢階段，提出了一種下界距離方法。并與K近鄰方法相結(jié)合，提高了查詢的效果，完成了用戶對于時間序列的查詢需求。2 相關(guān)工作（Related work）時間序列是隨著時間的先后順序而變化的多維的復(fù)雜數(shù)據(jù)類型。形式上時間序列表示為，其中元素是點的序列，其中代表時間，代表時間序列在時刻的值。國內(nèi)外研究學(xué)者關(guān)于查詢處理的研究，大致可分成時間序列的表示方法、索引技術(shù)和相似性度量研究。時間序列表示方法有離散小波變換（Discrete Wavelet Transform，DWT）3，4和離散傅立葉變

7、換（Discrete Fourier Transform，DFT）5、奇異值分解法（Singular Value Decomposition，SVD）6、分段線性表示（Piecewise Linear Representation，PLR）7，8、符號化近似（Symbolic Approximation，SAX）9，10方法等。時間序列索引技術(shù)分基于空間劃分的索引和基于數(shù)據(jù)劃分的索引，基于空間的劃分有K-D樹11，12、四叉樹13、網(wǎng)格文件14等，基于數(shù)據(jù)的劃分有R-tree15、iSAX-tree16和ADS-tree17。時間序列的相似性度量是衡量時間序列相互之間聯(lián)系的方法。相似性度量是數(shù)

8、據(jù)挖掘中的一項重要的任務(wù)。一般情況下，時間序列的每一種相似性度量方法都能夠?qū)?yīng)一種或多種時間序列特征表示。例如，經(jīng)典的時間序列PAA特征表示方法用到了歐式距離的度量方法，離散傅立葉變換通常會用到動態(tài)時間彎曲距離的度量方法。不同的特征表示選擇不同的度量方法，這要與設(shè)計的算法相結(jié)合。選擇一個適合的度量方法，可以提高算法的性能，提高時間序列查詢的查全率與查準(zhǔn)率。經(jīng)典的相似性度量方法主要有編輯距離、歐氏距離、動態(tài)時間彎曲距離等。為了進一步提高查詢效率，國外學(xué)者提出了下界距離的概念，下屆距離有LB-Yi距離和LB-Kim距離18，19等。 3 時間序列預(yù)處理（Preprocessing the time

9、 series）3.1 時間序列規(guī)范化給定某企業(yè)近幾年的原始交易值數(shù)據(jù)如圖1所示。圖1中，橫坐標(biāo)表示時間（天），縱坐標(biāo)表示交易值（元）。從圖中可以看出，交易值數(shù)據(jù)分布相對不均勻，這就給后期建立索引，近似性匹配帶來了困難。所謂時間序列的規(guī)范化，就是在保留原來的總體趨勢的情況下，將原始的時間序列轉(zhuǎn)換至區(qū)間內(nèi)。這樣原始的時間序列就經(jīng)過了規(guī)范化，與之前相比，規(guī)范后的時間序列，完美地保留了原始序列的趨勢，數(shù)據(jù)分布相對比較均勻。3.2 時間序列分段通常單條的時間序列規(guī)模也較大。如我國某地連續(xù)一年的氣溫數(shù)據(jù)。假設(shè)每小時檢測一次，那么連續(xù)一年有8760個數(shù)據(jù)點，索引全部點在時間和空間上代價都比較大。觀察天氣預(yù)

10、報的規(guī)律可知，常常會報道某一天的平均氣溫，通常一天中溫度變化不大（個別地區(qū)除外）。就可以用平均氣溫來代表一天的氣溫，以24小時對時間序列分段，全年的氣溫時間序列就分成365段，直接索引這365段要比原始時間序列代價小很多。定義一個時間序列，時間序列的集合組成了數(shù)據(jù)庫，假定Y的時間序列長度為n，將n單位的元素劃分成N段數(shù)。為了簡便，假定N是n的一個因數(shù)。一條長度為n的時間序列X，通過向量表示為，要素通過以下公式計算得到。假定只取一天當(dāng)中的1點到16點的氣溫數(shù)據(jù)，組成了一條有16個元素的時間序列。選定分段數(shù)為4，這條時間序列被分成4個規(guī)整框。分別計算出每個規(guī)整框中數(shù)據(jù)的平均值。向量就成為時間序列分

11、段之后的表示。這種轉(zhuǎn)換將原始時間序列轉(zhuǎn)換成了一個分段的常數(shù)近似。當(dāng)N=n和N=1時轉(zhuǎn)換后的表示與原序列相同，分段如圖3所示。3.3 時間序列離散化大多數(shù)的時間序列都符合高斯分布，因而可采用離散化處理。高斯分布如表1所示。給定一條標(biāo)準(zhǔn)的符合正態(tài)分布的時間序列，決定“斷點”使時間序列的目標(biāo)變量分成若干個區(qū)域。表中a表示字母集的大小，即基。選擇字母集的大小，并且確定分裂點。將分段累計近似得到的序列的表示確定到所屬區(qū)間之后，用十進制進行編碼。選定字母集的大小a為4，對應(yīng)斷點數(shù)為。從高斯分布表里可以看出，這三個斷點分別為（-0.67，0.00，0.67）。從圖4中可以看出，斷點數(shù)為3的區(qū)域劃分情況。劃分

12、的區(qū)域分別用0、1、2、3表示。原始的時間序列X就會被離散化編碼為“0023”。4 線性散列索引（Linear hash index）4.1 線性散列索引概述線性散列是一種動態(tài)的散列技術(shù)，基本思想是利用散列函數(shù)，將檢索的時間序列的值映射到固定的散列桶號，然后就可以找到待查的時間序列。通過時間序列的規(guī)范化，使時間序列絕大部分都分布在標(biāo)準(zhǔn)正態(tài)分布的區(qū)間中，能解決數(shù)據(jù)分布的不均勻性。線性散列輪轉(zhuǎn)分裂機制：定義一個循環(huán)級，在一個循環(huán)級內(nèi)使用和這兩個散列函數(shù)。開始循環(huán)后，文件中的桶逐個分裂，一次循環(huán)分裂結(jié)束以后就開始下一輪的分裂，直至循環(huán)結(jié)束。有三種類型桶，已被分裂的桶、將要分裂的桶和分裂創(chuàng)建的映像桶。

13、線性散列索引在執(zhí)行插入操作時，在相應(yīng)的桶編號對應(yīng)的桶存滿的情況下就要觸發(fā)桶的分裂，在這之前增加一個溢出頁來存儲要插入的時間序列離散化后的表示。此時，要確定哪個編號的桶分裂，根據(jù)上文中的輪轉(zhuǎn)分裂機制確定，分裂的方式是依次分裂。即將要發(fā)生分裂的桶，也就是在第一個循環(huán)級，的桶。要分裂的桶是以循環(huán)分裂的方式進行選擇，全部的桶都要進行分裂。4.2 創(chuàng)建線性散列索引假定散列表初始桶為，則值為時間序列的二進制離散化表示。時間序列二進制離散化表示時的最小位數(shù)用表示。用表示當(dāng)前循環(huán)級數(shù)，則每輪的桶數(shù)。第1輪，初始桶為。hash桶依次按編號分裂，用Next指示。每次發(fā)生分裂的桶總由Next決定，為處理溢出情況，可

14、以引入溢出頁來解決。線性散列索引文件初始創(chuàng)建的形態(tài)如圖5所示。4.3 插入與刪除線性散列索引線性散列索引在插入時，首先判斷時間序列符號化表示所對應(yīng)的桶能否觸發(fā)分裂，如果條件成立，則發(fā)生分裂，產(chǎn)生映像桶和溢出頁。插入h（r）=2321=100100010001，對應(yīng)01編號，該桶未滿，不發(fā)生分裂，直接插入。插入h（r）=1330=10100110010，對應(yīng)10編號，該桶已存滿，在插入“1330”時Next指向的00桶發(fā)生分裂，產(chǎn)生映像桶，映像桶的編號為Next+N0=4=100，同時，10桶產(chǎn)生溢出頁暫存“1330”，00桶里的數(shù)據(jù)在00桶和它的映像桶100桶之間進行重新分布。插入h（r）=0

15、211=11010011，取二進制的最后兩位11，對應(yīng)11編號的桶，該桶未滿，不發(fā)生分裂，直接插入。插入h（r）=2031=11111101111，取二進制的最后兩位11，對應(yīng)11編號的桶，該桶在繼插入“0211”之后已經(jīng)存滿，所以在插入“2031”時Next指向的01桶就需要進行分裂，產(chǎn)生映像桶，映像桶的編號為Next+N0=5=101，同時，11桶產(chǎn)生溢出頁暫存“2031”，11桶和它的映像桶101桶之間進行數(shù)據(jù)重新分布，操作完成之后的數(shù)據(jù)分布如圖6所示。Next下移一位，Next=2。5 時間序列的查詢 （Querying the time series）5.1 近似查詢數(shù)據(jù)挖掘應(yīng)用需要

16、近似查詢，線性散列索引能夠支持快速近似查詢，由于兩個相似的時間序列的符號化表示往往會相同，一次訪問就可實現(xiàn)。從線性散列索引文件中查詢所要結(jié)果的時間序列表示，順序掃描相應(yīng)的時間序列作為近似查詢結(jié)果。 如給定時間序列，經(jīng)過序列轉(zhuǎn)換后表示為“3102”，h（r）=3102=110000011110，取后兩位“10”位于Next=4和N=4之間，所以對應(yīng)的桶已經(jīng)發(fā)生分裂，此時取后三位“110”，定位相應(yīng)110桶，查找到“3102”。返回查詢的結(jié)果BSF（Best-So-Far），它是一個粗略的結(jié)果集，叫做輸入實例時間序列的近似查詢。采用一種近似查詢和KNN（K-Nearest Neighbor）查詢組

17、合的方式來縮小查詢空間，以提高查詢效率和查詢精度。基于線性散列索引的精確查詢算法，將近似查詢得到的結(jié)果（BSF）作為輸入。因為BSF結(jié)果里的時間序列之間的距離相對較小，給最近鄰查詢創(chuàng)造條件，在近似查詢階段將大部分的搜索空間進行修剪，既提高了查詢精度，也降低了查詢時間。K近鄰的核心在于找到實例時間序列的鄰居，也就是找到與目標(biāo)序列相鄰的時間序列。衡量兩條時間序列是不是鄰居的判定標(biāo)準(zhǔn)，可直觀地理解為兩條時間序列之間的距離，如果距離在可接受的范圍，就可判定這兩條時間序列是鄰居。因為特征空間中兩條時間序列的距離能反映出兩條時間序列之間的相似程度。K近鄰查詢將近似查詢得到的結(jié)果作為K近鄰中的數(shù)據(jù)集，當(dāng)輸入

18、新的時間序列時，在時間序列數(shù)據(jù)集中找到與目標(biāo)時間序列最近鄰的K條鄰居，可認(rèn)為這K條時間序列與目標(biāo)時間序列最為相似。當(dāng)K取1時，查詢到達(dá)了精確查詢。輸入：BSF結(jié)果集，大小為，其中，為時間序列的特征向量，目標(biāo)時間序列特征向量。輸出：目標(biāo)時間序列特征向量的鄰居。根據(jù)距離度量方法，在時間序列數(shù)據(jù)集（BSF結(jié)果集）S中找出與最臨近的K條時間序列，涵蓋這K條時間序列的的鄰域記做。相應(yīng)的K近鄰法的模型對應(yīng)的特征空間劃分如圖7所示。假定特征空間所有的實例點組成了近似查詢結(jié)果集BSF，大小為。給定一個查詢實例時間序列X0，通過近似查詢得到X0粗略的結(jié)果集BSF，再從已有的BSF結(jié)果集中盡可能的剔除與X0不相近

19、的時間序列，得到比較精確的結(jié)果集。兩條時間序列之間的距離表示它們之間的相似程度，有多種距離的計算方法，通常使用歐式距離、距離和Minkowski距離。假設(shè)Xi和Xj是特征空間里的兩條時間序列，它們之間的距離為：5.2 緊密性討論不直接取順序遍歷BSF結(jié)果集是因為時間耗費仍然比較大，用加入界限緊密性TLB（Tightness of Lower Bound）的方式來過濾掉一部分結(jié)果。所謂的TLB是一個對相似性度量非常有意義的方法，它的表達(dá)式如公式（5）所示。其中，T和S是兩條時間序列。TLB的優(yōu)點是B實現(xiàn)了完全的自由測量，可對索引的有效性進行有效的預(yù)測。如果TLB的值為0，則證明這個索引需要從磁盤

20、順序讀出時間序列，索引不具有高效性。如果TLB的值為1，則證明對索引稍微調(diào)整一下就可檢索出需要的一個時間序列，并且能夠保證得到真實的最近鄰。給定時間序列T和S，長度都為n。假定T為查詢實例時間序列，S為待查序列，設(shè)置一個規(guī)整窗口R，恰好能把T分成w（w=1，2，w）塊，如圖11所示，當(dāng)規(guī)整窗口R向指示的方向移動時T被分成了w塊區(qū)域，每個R就是一個區(qū)域，在每個區(qū)域里都會存在一個最大值，將每一塊的最大值，組成一條序列，取這條序列中最大值的均值，記作；最小值組成一條序列，取這條序列中最小值的均值，記作。它們的定義如公式（6）所示。6 實驗評估（Experiments evaluation）實驗環(huán)境：

21、Intel（R） Core（TM） i3-4370 3.8GHz，Windows 7操作系統(tǒng)，實驗程序采用Java語言編寫。在進行離散化表示時選取的基數(shù)分別為2，4，6，8，10。（1）選取不同的基數(shù)對下界緊密度（TLB）的影響。如圖9所示，固定時間序列長度為480時，基數(shù)對TLB的影響是非線性的，當(dāng)基數(shù)變大時，TLB增長，并且增長速度越來越快，造成這種現(xiàn)象的原因是，在進行離散化表示時，選取的基數(shù)越大，相應(yīng)的斷點數(shù)就越大，這樣時間序列離散越細(xì)化，離散化表示之后的時間序列越接近于原始時間序列，下界距離與真實歐式距離的比值就越接近于1。（2）選取不同的時間序列長度對下界緊密度（TLB）的影響。如圖

22、10所示，固定基數(shù)大小為10，之所以選取基數(shù)為10是因為從上圖中可以看出當(dāng)基數(shù)是10的時候，TLB的值相比更接近于1，這樣實驗誤差更小一點，從圖中可以看出，當(dāng)時間序列的長度增大的時候，下界緊密度越來越小。在設(shè)置的規(guī)整窗口大小不變的情況下，隨著時間序列的增大，規(guī)整窗口向右滑動時造成的誤差也是越來越大的，這勢必造成下界距離可靠性越來越差，TLB的值就會越來越小。（3）選取不同的分段大小對時間序列表示耗時的影響。如圖11所示，固定時間序列的長度為480，隨著分段大小的不斷變大，系統(tǒng)耗時越來越小，當(dāng)分段大小在40左右的時候，耗時在770ms處下降開始顯得不明顯，這主要是因為在分段之前有一步對時間序列進

23、行規(guī)范化的過程，也可以理解成規(guī)范化一條長度為480的時間序列用時是770ms左右。（4）選定時間序列長度為480，基數(shù)為10，分段大小選擇40。對系統(tǒng)的完整耗時進行測試，選擇對比實驗，結(jié)果如圖12所示。對比實驗主要分索引創(chuàng)建時間和查詢時間兩部分，其中索引創(chuàng)建時間是前期時間序列規(guī)范化表示，創(chuàng)建索引的時間總和表示。從圖12中可以看出，無論哪種方法，索引創(chuàng)建和預(yù)處理耗時占完整耗時中的大部分，而查詢時間占完整耗時中的小部分。在索引創(chuàng)建方面的性能提升與iSAX相比不明顯；主要是查詢方面的提升，從而驗證了下界距離的有效性。7 結(jié)論（Conclusion）本文基于已有的時間序列表示方法上，提出了關(guān)于時間序列

24、規(guī)范化方法，并嘗試使用了線性散列創(chuàng)建時間序列的索引，在時間序列的相似性查詢方面提出了一種新的下界距離來衡量時間序列之間的相似度。經(jīng)過實驗得出了時間序列規(guī)范化方法的有效性，驗證了線性散列在索引時間序列時，索引創(chuàng)建時間并沒有很大的提升，但是降低了時間序列查詢的時間。對提出的下界距離方法做了討論，效果比較理想。 參考文獻(xiàn)（References）1 Keogh E，et al.Dimensionality Reduction for Fast Similarity Search in Large Time Series DatabasesJ.Knowledge & Information System

25、s，2001，3（3）：263-286.2 劉芬，郭躬德.基于符號化聚合近似的時間序列相似性復(fù)合度量方法J.計算機應(yīng)用， 2013，33（01）：192-198.3 Chan K P，F(xiàn)u W C.Efficient Time Series Matching by WaveletsC.IEEE International Conference on Data Engineering.IEEE，1999：126-133.4 Zhou H A，Wang X M，Mei Y L.Theoretical Analysis of the Sound Absorption Characteristics

26、of Periodically Stiffened Micro-perforated PlatesJ.Acta Mechanica Sinica，2014，30（5）：714-726.5 Agrawal R，F(xiàn)aloutsos C，Swami A.Efficient Similarity Search in Sequence DatabasesC.International Conference on Foundations of Data Organization and Algorithms.Springer-Verlag，1993：69-84.6 Korn F，Jagadish H V，

27、Faloutsos C.Efficiently Supporting Ad Hoc Queries in Large Datasets of Time SequencesJ.Acm Sigmod Record，1999，26（2）：289-300.7 Pavlidis T，Horowitz S L.Segmentation of Plane CurvesJ.IEEE Transactions on Computers，1974，C-23（8）：860-870.8 喻高瞻，等.時間序列數(shù)據(jù)的分段線性表示J.計算機應(yīng)用與軟件，2007，24（12）：17-18.9 Lin J，et al.Expe

28、riencing SAX：A Novel Symbolic Representation of Time SeriesJ.Data Mining & Knowledge Discovery，2007，15（2）：107-144.10 李桂玲，等.基于SAX的時間序列相似性度量方法J.計算機應(yīng)用研究，2012，29（3）：893-896.11 Ooi B C，McDonell K J，Sacks-Davis R.Spatialkd-tree：An Indexing Mechanism for Spatial DatabasesC.IEEE COMPSAC，1987，87：85.12 黃河，史忠植，鄭征.基于形狀特征k-d樹的多維時間序列相似搜索J.軟件學(xué)報，2006，17（10）：2048-2056.13 Tayeb J，Ulusoy ，Wolfson O.A Quadtree-based Dynamic Attribute Indexing MethodJ.The Computer Journal，1998，41（3）：185-200.14 Hinrichs K，Nievergelt J.The Grid File：A Data S