基于兩級過濾的時間序列近似查詢

蔡青林,陳　嶺,梅寒蕾,孫建伶

(浙江大學 計算機科學與技術學院,浙江 杭州 310027)

?

基于兩級過濾的時間序列近似查詢

蔡青林,陳嶺,梅寒蕾,孫建伶

(浙江大學 計算機科學與技術學院,浙江 杭州 310027)

摘要:針對現有的近似查詢模型對查詢精度的可控性較差,后續處理效率較低的問題,提出基于兩級過濾的查詢模型.通過采用不同粒度的SAX表示方法提取時間序列的字符型特征向量,可以將高維的時間序列映射到低維的特征空間；將不同粒度的特征向量以向量近似文件(VA-File)的結構進行存儲,有效引入了倒排索引.在查詢過程中,設計了啟發式的查詢過濾算法,根據粗粒度特征向量查詢細粒度特征向量,實現第一級過濾；針對VA-File設計了高效的邊界剪枝算法,實現第二級過濾.模型基于多粒度的SAX特征向量進行構建,可以對查詢精度進行有效控制；在第二級過濾中采用的邊界剪枝算法可以有效地提高后續處理的執行效率.實驗結果表明,提出的查詢模型具有較高的性能,對時間序列長度、kNN查詢規模及數據集規模具有穩定的擴展性.

關鍵詞：時間序列；相似性查詢；符號聚集近似；向量近似文件；倒排索引

時間序列相似性查詢是時間序列數據挖掘領域的基本問題,可簡要描述為對于給定的一條時間序列,需要快速完整的從時間序列數據庫中找出與其相似的序列.針對該問題,學術界提出了大量的查詢模型[1],這些模型通常基于特定的數據表示方法,如奇異值分解(singular value decomposition, SVD)[2]、離散傅里葉變換(discrete fourior transformation, DFT)[3]、離散小波變換(discrete wavelet transformation, DWT)[4]、分段聚集近似(piecewise aggregation approximation, PAA)[5]、符號聚集近似(symbolic aggregation approximation, SAX)[6]等,將高維的時間序列映射到低維的特征空間,然后構建索引結構.模型的查詢過程可以簡要描述為：基于時間序列的近似表示查詢索引結構獲取候選集；通過磁盤I/O讀取候選集的原始數據,并與查詢序列進行精確比較,獲得最終結果,該階段稱為后續處理[3].很明顯,模型的查詢效率由磁盤I/O的開銷規模決定.

根據查詢結果的完備性,模型可以分為精確查詢模型與近似查詢模型.對于前者,查詢過程需要滿足“下界定理”[7],即基于數據表示的度量距離須小于基于原始數據的度量距離,由此獲得的候選集包含了所有的真實結果(即對原始數據通過線性掃描的查詢結果).受下界定理的限制,精確查詢模型的數據表示方法對原始數據的近似精度(或稱下界緊湊度)較低,因此可能導致查詢過程生成較大規模的候選集,影響模型的查詢效率.為了滿足實際應用對查詢效率的高度需求,通過適當地犧牲查詢結果的完備性來換取查詢效率顯著提升的近似查詢模型,在近年來得到了廣泛研究,比如最新提出的EBSM模型[8]、iSAX模型[9]、iSAX2.0模型[10]、最長相關子序列查詢模型[11]等.盡管近似查詢模型具有較高的查詢效率,但是它們對查詢精度的可控性較差,并且后續處理階段的時間開銷沒有充分削減.

針對上述問題,基于多分辨率的SAX表示方法,提出基于兩級過濾(two-step filtering)的時間序列近似查詢模型.通過不同粒度的SAX表示提取時間序列的字符型特征向量,將高維的時間序列映射到低維的特征空間；將不同粒度的特征向量以向量近似文件(VA-File)的結構進行存儲,并對其構建倒排索引.在查詢過程中,設計了啟發式的查詢過濾算法,根據粗粒度特征向量查詢細粒度特征向量,實現第一級過濾；針對VA-File設計了高效的邊界剪枝算法,實現第二級過濾.由于模型基于多粒度的SAX特征向量構建倒排索引,查詢過程可以對查詢精度進行有效控制；在第二級過濾中所采用的邊界剪枝算法可有效地提高后續處理的執行效率.

1相關工作

根據查詢結果的完備性不同,時間序列相似性查詢模型可以分為精確查詢模型與近似查詢模型.精確查詢模型是目前研究較多且較成熟的方法,研究者們已經提出大量的時間序列數據表示方法及索引結構用于實現精確查詢.比如,早期的DFT表示[3-7]通過提取時間序列的離散傅里葉系數作為特征,實現數據壓縮,然后構建R*-樹索引實現精確查詢.該方法忽略了時間序列較多的局部特征,容易導致下界緊湊度較低.此后,基于分段表示和基于矩陣分解的方法相繼被提出.常見的有PAA表示方法[5]和適應性分段常數 (adaptive piecewise constant approximation, APCA) 表示方法[12],它們分別將時間序列進行等長分段和適應性分段后,提取各子段的平均值特征來構建空間索引.基于簡單的子段平均值的近似會導致較低的下界緊湊度.另外,還有分段線性表示方法(piecewise linear approximation, PLA)[13],提取子段的線性擬合斜率作為特征以及最新的導數分段近似(derivative segment approximation, DSA)[14],提取導數子序列的平均值作為特征.這兩種方法都對噪聲較敏感,容易受異常值的影響.常見的基于矩陣分解的表示方法有SVD[2]和主成分分析(principal component analysis, PCA)[15],但是這兩類方法需要在內存中實現,使得它們的擴展性較差.

為了提高查詢效率,近似查詢模型正受到越來越多的研究.最新的EBSM模型[8]可以在查詢精度損失較小的情況下,實現基于動態時間彎曲距離(dynamic time warping, DTW)的高效子序列匹配,但是沒有考慮數據規范化問題[16],所以查詢結果無意義.最長相關子序列查詢模型[11]通過利用持續最長的相關子序列來判斷時間序列的相似性,可以支持對任意長子序列的規范化度量,但是需要非常復雜的索引構建過程.此外,最新的iSAX[9]和iSAX2.0[10]模型基于較早提出的SAX表示方法[6]實現.SAX表示在PAA表示的基礎上提取時間序列的數值特征,然后對數值空間離散化,將時間序列變換為符號序列進行處理.與其他表示方法相比,SAX可以結合信息檢索領域較成熟的索引結構[17],如倒排索引、前綴樹索引等,實現時間序列的近似查詢.同時,對數值空間的離散化處理使得SAX具有較好的多分辨率性質,這為構建索引提供了較大的優勢.盡管iSAX模型充分利用了SAX的性能優勢,但它是一棵非平衡樹,索引構建時間將隨著數據集的增大而迅速膨脹.盡管iSAX2.0彌補了這一缺陷,但是在查詢時隨著節點的深入計算,無法保證查詢結果的相似性逐步提高,即基于距離下界的剪枝效果得不到改善.

2時序數據表示和索引構建

首先給出時間序列的定義如下.

定義1時間序列變量X在n個連續時刻的采樣值序列稱為時間序列,表示為T= {t1,t2, …,ti, …,tn},其中ti表示X在第i個時刻的采樣值.

2.1特征抽取

基于當前學術界廣泛研究的SAX表示方法[6]提取時間序列的特征向量,將時間序列從原始數值空間映射到SAX符號空間.

定義2時間序列特征向量已知時間序列T,若存在f:T→ V = [v1,v2,…,vm] ∈Rm,則向量V稱為時間序列T的特征向量.

圖1　時間序列的分段聚集近似Fig.1　Piecewise aggregation approximation of time series

SAX表示方法是基于PAA表示[5]提出的.在PAA表示中,長度為n的時間序列T被平均劃分為w段,通過計算各段元素的平均值得到一個w維的平均值向量,作為T的特征向量：

(1)

圖1給出長度為60的時間序列以6維PAA特征向量的近似表示.

圖2　由PAA表示轉化為SAX表示Fig.2　Transformation from PAA to SAX

由于z-規范化的時間序列服從高斯分布,Keogh等[6]基于高斯概率密度函數對實數域作等概率的區間劃分,并將各區間以特定的字符表示.將PAA特征向量的各元素映射到對應的劃分區間,得到時間序列的SAX特征向量,表示為SAX(T).如圖2所示,若將實數域劃分為3個區間,由下到上分別以字符{a,b,c}表示,則圖2所示的PAA特征向量可以轉化為SAX特征向量SAX(T) = [b,b,a,b,c,c].

SAX特征向量采用向量近似文件(VA-File)[18]的組織形式進行編碼.VA-File是一種基于空間劃分的數據結構,可以在查詢過程中實現高效的邊界剪枝算法.給定向量集合Φ= {v1, v2,…, vi,…, vm},|vi|表示向量vi的維度,以vij表示vi在第j維的元素值.假設ai是vi的特征向量,以n位存儲,則存儲ai各元素所需的位數nj可由下式計算得到：

(2)

式中：%表示求模運算.將vi的第j維劃分為2nj個區間,整個向量空間Φ劃分為2n個元胞.通過將第j維的所有區間依次編號為{0, 1, 2,…, 2nj-1},并以vij所在區間的編號作為其特征aij,得到vi的特征向量ai.VA-File是所有特征向量a1, a2,…, am依次相連構成的二進制字符串.如圖3所示,若|vi|=2,n=3,由式(2)可得n1= 2,n2= 1,于是vi的第1維可以劃分為4個區間,第2維可以劃分為2個區間,整個向量空間被劃分為8個元胞.若圖3中的向量v3=[9, 3],則特征向量為a3= [1, 0]；對圖3中向量集合Φ= {v1, v2, v3, v4, v5}所構建的VA-File為"101110010101111".

圖3　基于VA-File對二維向量空間的劃分(|vi|=2, n=3)Fig.3　Division for two-dimensional space based on VA-File

VA-File的顯著優點在于基于元胞的上下邊界可在高維向量空間中設計高效的剪枝算法,并且有效地克服了“維災問題”[7].如圖3所示,假設查詢向量vq=[3, 6],它到向量v3的上、下邊界距離l和u分別是vq到v3所在元胞的最近點o和最遠點p的距離.

2.2索引構建

針對VA-File引入信息檢索領域的倒排索引結構來實現高效查詢.倒排索引由單詞詞表與索引文件構成,單詞詞表用于維護所有Term,索引文件包含了各Term指向的Postings,各Posting分別包含Term所在的文檔及其在該文檔內的偏移量.

與傳統的倒排索引結構不同,提出基于兩種不同粒度SAX特征向量的倒排索引結構,即多粒度時序倒排索引：基于粗粒度的特征向量構建單詞詞表,基于包含細粒度特征向量的VA-File構建索引文件.目的在于基于粗粒度的SAX特征向量從VA-File中查詢出細粒度的SAX特征向量集合作為初始候選集,實現第一級過濾.

定義3 多粒度時序倒排索引假設時間序列Ti分別表示為不同參數的SAX特征向量SAX(Ti)和SAX(Ti),a1插入向量近似文件VAk中.若以SAX(Ti)作為Termj構建單詞詞表vocabulary,以作為Termj指向的Posting構建索引文件file,其中,σ表示Ti在VAk中的位置偏移量,則由vocabulary與file構成的倒排索引稱為多粒度時序倒排索引,表示為MGTI (multi-granularity time inverted-index).

根據信息檢索領域較成熟的倒排索引構建算法[17],MGTI的構建過程如算法1所示.

算法1MGTI構建算法

輸入：時間序列集合Ф = {T1,T2, …,Ti, …}；SAX參數,.

輸出：多粒度時序倒排索引MGTI．

1)遍歷Ф,分別將Ti表示為σ=SAX(Ti)和θ= SAX(Ti) .

2) 掃描完畢,獲得SAX特征向量對(σ,θ)的集合Λ.

3)遍歷Λ,以σ作為主鍵,以θ作為次鍵,對Λ元素排序.

拋物線y=ax2+bx+c上有一點C(m，n)，直線l與拋物線交于A，B兩點，當∠ACB=90°時，直線l是否經過一定點.

4)將與σi對應的所有θj依次插入鏈表,作為σi指向的Postings,并存儲為VA-File的結構形式VAi;同時,計算θj在VAi中的偏移量σj.

5)將所有σi及對應的Postings指針pi組織為單詞詞表vocabulary(哈希表或樹結構),將所有VAi組織為索引文件file.

6)將作為MGTI并返回.

對于小規模的數據集,MGTI的構建過程可以在內存實現；對于大規模數據集,構建過程需要考慮二級存儲操作.對于后者,信息檢索領域已經提出較成熟的算法[17],如基于塊排序的索引(blocked sort-based indexing)、內存單遍歷索引(single-pass in-memory indexing)、分布式索引(distributed indexing)、動態索引(dynamic indexing)等.

3查詢處理

針對以上模型,提出兩級過濾算法,可以對時間序列實現高效的近似查詢.從查詢時間序列提取粗粒度SAX特征向量作為查詢Term,通過查詢MGTI獲取與該Term對應的Postings,根據Postings的信息從VA-File中獲取查詢Term所對應的細粒度SAX特征向量作為初始候選集；提出一種邊界剪枝算法過濾初始候選集,得到最終候選集；對最終候選集進行后續處理,即訪問原始數據并進行相似性度量,得到查詢結果.

定義4 時間序列相似性度量已知時間序列T1和T2,若存在f: (T1,T2) → R+,可以在數值上反映T1與T2之間的形態相似性,則函數f稱為時間序列相似性度量,表示為f(T1,T2).

定義5時間序列近似查詢已知查詢時間序列Q,時間序列數據集合Φ= {T1,T2, …,Ti, …,Tn}及子集S={Ti|Ti∈Φ,f(Q,Ti)≥ε,ε∈R+},若Q經查詢算法F得到的結果集合V= {Vi|Vi∈Φ,SV,S∩V≠?},則該查詢過程稱為近似查詢.

3.1第一級過濾

定義6初始候選集已知基于參數和,a1的SAX特征向量SAX(T)作為查詢Term,則從MGTI得到的參數為的SAX特征向量集合,稱為初始候選集,表示為C1.

簡單查詢是指從MGTI中直接獲取與查詢序列Q的粗粒度SAX特征向量SAX(Q)對應的Postings作為查詢結果,見算法2.在第2行中,Q被平均切分為w1條子序列；在第3行計算了每條子序列的平均值,得到Q的PAA特征向量；第4行將PAA特征向量映射到基數為a1的SAX區間,得到Q的SAX特征向量；第5行以Q的SAX特征向量作為Term,查詢MGTI獲取對應的Postings作為初始候選集C1.若倒排索引的單詞詞表以哈希表維護,則簡單查詢的時間復雜度是O(1).

算法2簡單查詢算法

輸入：查詢序列Q,SAX參數；

輸出：初始候選集C1．

1)C1← Null;

2)S← segment(Q);

3) PAA ← mean(S);

4) SAX ← symbolize(PAA);

5)C1← MGTI(SAX);

6) ReturnC1．

圖4　3個PAA特征向量的距離關系示意圖Fig.4　Relationship between three PAA feature vectors

雖然簡單查詢算法具有很高的查詢效率,但是在以距離度量作為時間序列相似性評價標準的前提下,簡單查詢可能會產生較多的“誤遺漏”[3].如圖4所示,對于PAA向量P1、P2、P3,SAX特征向量分別為SAX(P1) = [c,d,c,b],SAX(P2) = [b,c,b,a],SAX(P3) = [b,c,b,a].若以SAX(P2)作為簡單查詢算法的輸入Term,則初始候選集將包含SAX(P3),而不包含SAX(P1).雖然P1與P2的對應元素分別落在不同的區間,P2與P3的對應元素都落在相同的區間,但是若以歐氏距離作為相似性度量,則有f(P1, P2)

擴展查詢是指首先將SAX(Q)的各元素從它所在的SAX區間βj擴展到相鄰區間βj-1和βj+1,于是SAX(Q)被擴展到一個SAX特征向量集合Ψ；然后從MGTI中獲取與Ψ中各元素對應的Postings集合作為查詢結果,見算法3.第3～5行表示基于粗粒度參數提取Q的SAX特征向量；在第6～8行依次擴展SAX特征向量的每個符號元素至相鄰的劃分區間；在第9行,以集合Ψ中的所有元素作為查詢Term,對MGTI執行布爾或查詢,獲取所有Postings作為初始候選集C1.

算法3擴展查詢算法

輸入：查詢序列Q,SAX參數；

輸出：初始候選集C1．

1)C1← Null;

2)Ψ← Null;

3)S← segment(Q);

4) PAA ← mean(S);

5) SAX ← symbolize(PAA);

6) fori← 1:w1

7)Ψ← {SAX[i]-1, SAX[i], SAX[i]+1};

8) end

9)C1← MGTI(Ψ)V;

10) ReturnC1．

算法3等同于對邏輯或的布爾查詢,時間開銷與Ψ的元素個數成正比.若將SAX(Q)的各元素擴展到γ個相鄰區間,則Ψ包含γw個元素,考慮到查詢效率,γ不宜過大；在粗粒度的SAX表示中,離散區間較少,因此只需向外擴展一個相鄰區間(γ= 3),便能保證細粒度SAX對象的顯著增加,即C1的規模增加,由此使得查詢精度得到較大提升.

3.2第二級過濾

為了進一步剔除C1的“誤命中”,節省后續處理中磁盤I/O的時間開銷,基于VA-File的組織結構,提出一種高效的邊界剪枝算法對C1進行第二級過濾,以獲取規模更小的最終候選集C2,見算法4.

定義7最終候選集已知初始候選集C1= {SAX(T1), SAX(T2),…, SAX(Tn)},若存在算法F,以C1作為輸入,以集合C2作為輸出,并且C2?C1,則C2稱為最終候選集.

算法4基于VA-File的邊界剪枝算法

輸入：查詢序列Q,初始候選集C1；

SAX參數；

輸出：最終候選集C2．

1.C2← Null;

2. MaxUpper ← zeros[k];

3. MinLower ← Null;

4. query ← SAX(Q);

5. fori← 1:k

6.l← low_boud(query,C1[i]);

7.u← up_boud(query,C1[i]);

8. MaxUpper ←u;

9. MinLower ← (C1[i],l,u);

10. end

11. fori←k+1:n

12.l← low_boud(query,C1[i]);

13. ifl< MaxUpper[1]

14.u← up_boud[query,C1(i)];

15. MaxUpper ←u;

16. MinLower ← (C1[i],l,u);

17. end

18. end

19. forj← 1:m

20. if MinLower[j] > MaxUpper[1]

21. break;

22. else

23.C2← MinLower[j];

24. end

25. end

26. ReturnC2．

在算法4中,第2和第3行分別構建了容量為k的最大優先隊列MaxUpper和最小優先隊列MinLower；第4行基于參數提取Q的SAX特征向量；第6和第7行分別計算query與C1第i個元素的上下邊界距離；在第9行根據下界距離對C1的前k個元素進行排序；在第20行判斷MinLower中第j個元素的下界距離與MaxUpper中當前最大上界距離的關系；在第23行取出MinLower的第j個元素對應的時間序列插入最終候選集C2.算法4是一種基于邊界距離的剪枝算法,滿足下界定理[7]可知,不會導致“誤遺漏”,計算復雜度為O(n+mlog2m),其中n為C1的元素數目,m為C2的元素數目.另外,算法4可以采用多種提前終止技術[16]及內存表技術[6]進行加速計算.

4實驗分析

4.1實驗設置

實驗環境：Intel(R) Core(TM) i5-2400 CPU @ 3.10 GHz,8 GB內存,Windows 7 64位操作系統.模型基于Java語言和開源的Lucene 4.6.0框架實現.原始數據集全部存儲于基于MYISAM存儲引擎的數據庫管理系統MySQL 5.6.17中,并通過JDBC讀取數據.實驗采用以下兩類數據集.

1)真實股票數據集,從Yahoo! Finance[19]獲取的美國NASDAQ證券交易市場的5031個上市公司在1962/1/2至2013/12/03期間的股票日收盤價格序列.對所有股票序列進行z-規范化處理,并切分為不重疊的子序列集合,得到6種不同序列長度L的數據集所包含的序列數目Ω,如表1所示.

表1　不同序列長度的真實股票數據集

2)隨機游走數據集：按照公式o[i+1]=o[i]×[1+N(μ,σ)][20]生成序列長度為256的隨機游走數據集,其中N(μ,σ)為正態分布函數,選擇默認參數為均值μ= 0,標準差σ= 0.2[11].生成了6個不同規模Ω的數據集,分別包含10萬條、50萬條、100萬條、500萬條、1 000萬條、1 600萬條時間序列.

在時間序列相似性查詢研究中,查詢結果的漏報率(false dismissal rate, FDR)是衡量查詢完備性的重要指標[3].本文模型僅在第一級過濾中引入“誤漏報”,而第二級過濾算法滿足下界定理,不會進一步造成“誤漏報”,模型的漏報率只需通過初始候選集進行檢驗.采用P@N(Precision@N)指標[17]對查詢結果的準確率進行檢驗.每次查詢的ground-truth全部基于歐氏距離從原始數據集找出.

時間序列相似性查詢模型的時間開銷主要集中在后續處理的磁盤I/O上,候選集規模越大,磁盤I/O的開銷越大,因此模型的查詢效率實際由候選集規模決定,前者可以通過后者進行檢驗.

在構建模型時,需要對MGTI的SAX特征向量維度w和特征空間基數a選擇兩組不同粒度的參數,即和,其中w1決定詞典的大小以及第一級過濾的候選集大小,為了避免數據空間過于稀疏,對于所用實驗的數據集規模,取值不宜過大；同時,擴展查詢算法的時間開銷需要控制在較低的水平,為此首先確定w1=4,然后通過檢驗模型的召回率來選擇參數a1.的大小決定了VA-File中元胞邊界的緊湊度,進一步決定了第二級過濾的性能,其中,取值越大,性能越好；實驗數據集的最小序列長度為L=32,為了保證SAX表示對數據空間的壓縮作用(即保證較低的索引開銷),選擇w2=16,a2=16.

4.2實驗結果及分析

4.2.1參數影響由于模型的查詢精度由決定,在確定參數w1的情況下,檢驗模型在7個不同序列長度的真實股票數據集上采用擴展查詢算法執行Top-20的kNN查詢,模型的召回率R隨特征空間基數a1的變化情況,如圖5所示.

圖5　模型召回率隨特征空間基數a1的變化情況Fig.5　Recall variation with space cardinality a1

由圖5可知,隨著參數a1的增大,模型召回率逐漸下降.原因在于參數a1越大,SAX對數據空間的劃分越細,空間越稀疏,查詢到的初始候選集越小,所包含的真實結果越少,召回率越低.在參數a1的各取值上,模型在7個不同序列長度數據集上的召回率相差較小,說明模型對時間序列長度具有魯棒性.為了保證模型具有較高的召回率,選擇參數a1=8用于后續實驗.

4.2.2有效性檢驗模型分別基于6個不同序列長度的數據集對簡單查詢與擴展查詢算法執行Top-20、Top-40、Top-60的kNN查詢,以檢驗漏報率RFD.實驗結果如圖6所示.

圖6　模型漏報率檢驗結果Fig.6　Evaluation results for dismissal rate

由圖6可得以下結論.1)模型基于簡單查詢與擴展查詢的漏報率差距較大,因此擴展查詢比簡單查詢算法更加有效；2)在不同序列長度的數據集上,模型執行kNN查詢的漏報率相差較小,說明模型對kNN查詢規模具有魯棒性.原因在于SAX采用等概率的區間劃分,相似時間序列的SAX特征向量在MGTI中會以較高的概率落在同一個或相鄰的Term所對應的Postings中,隨著k的增大,被查詢出的相似時間序列的概率保持了較高的穩定性.

基于P@N指標對模型(基于擴展查詢算法)的有效性檢驗結果如圖7所示.圖中，P為查準率.由圖7可得以下結論.1)模型在不同規模的kNN查詢中,都能保持較高的查準率(>0.8)；2)每條曲線都比較平緩,說明模型對kNN查詢規模具有魯棒性；3)在不同序列長度的數據集上,執行同樣kNN查詢的查準率相差較小,說明模型對時間序列長度具有魯棒性.在實驗中,模型對不同長度的時間序列采用了統一的SAX特征向量維度參數w1和w2,而模型的查準率是由SAX特征向量對原始時間序列的近似精度決定的,因此模型的查準率對時間序列長度的穩定性來源于SAX表示方法的近似精度對時間序列長度的穩定性.

圖7　模型查準率檢驗結果Fig.7　Evaluation results for precision rate

4.2.3查詢性能檢驗實驗基于6個不同序列長度的真實股票數據集開展Top-20的kNN查詢,以分別基于DFT[7]、PAA[5]、SAX[6]的精確查詢模型以及iSAX[9]近似查詢模型作為對比方法.表2呈現了5種方法查詢生成的候選集大小(時間序列數目).

由表2可得如下結論.1)對于本文模型,初始候選集的數目C1較大,但是最終候選集的數目C2遠小于所有對比方法生成的候選集數目C′；2)隨著時間序列長度的增加,C2始終維持在較低的水平,說明模型的查詢性能對時間序列長度具有魯棒性.由于兩級過濾方法在MGTI中采用了兩種粒度的SAX特征向量,逐漸細化的參數使得SAX下界緊湊度越來越高,由此保證了模型對不相似時間序列具有較強的濾除能力.

基于6個不同規模的隨機游走數據集對5種模型分別執行Top-20的kNN查詢,以檢驗它們的實際查詢時間開銷T,結果如圖8所示.

由圖8可得如下結論.1)本文模型的查詢性能比4種對比方法的性能最多高出2個數量級,很明顯導致這一差距的主要因素是查詢過程中的候選集規模差別較大； 2)本文模型在不同規模數據集上的查詢時間始終維持在較低的水平,因此模型的查詢性能對數據集規模具有較強的魯棒性.

表2　各種查詢模型在不同數據集上的候選集大小

圖8　5種方法的實際查詢時間開銷比較Fig.8　Runtime comparison between five models

5結語

本文基于多粒度的SAX表示,提出基于兩級過濾的時間序列相似性查詢模型,構建多粒度倒排索引結構,并設計啟發式的查詢過濾算法,用于實現高效高精度的近似查詢.

下一步的研究工作將圍繞范圍查詢深入展開,并且如何將模型有效地應用于超大規模時間序列數據集的問題,有待進一步的深入研究.

參考文獻(References)：

[1] ESLING P, AGON C. Time-series data mining [J]. ACM Computing Surveys, 2012, 45(1): 1-34．

[2] CONG F, CHEN J, DONG G, et al. Short-time matrix series based singular value decomposition for rolling bearing fault diagnosis [J]. Mechanical Systems and Signal Processing, 2013, 34(1): 218-230．

[3] AGRAWAL R, FALOUTSOS C, SWAMI A. Efficient similarity search in sequence databases [J]. Foundations of Data Organization and Algorithms, 1993, 730(1): 69-84．

[4] CHAOVALIT P, GANGOPADHYAY A, KARABATIS G, et al. Discrete wavelet transform-based time series analysis and mining [J]. ACM Computing Surveys, 2011, 43(2): 1-37．

[5] KEOGH E, CHAKRABARTI K, PAZZANI M, et al. Dimensionality reduction for fast similarity search in large time series databases [J]. Knowledge and Information Systems, 2001, 3(3): 263-286．

[6] LIN J, KEOGH E, WEI L, et al. Experiencing SAX: a novel symbolic representation of time series [J]. Data Mining and Knowledge Discovery, 2007, 15(2): 107-144．

[7] FALOUTSOS C, RANGANATHAN M, MANOLOPOULOS Y. Fast subsequence matching in time-series databases [C]∥Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1994: 419-429．

[8] ATHITSOS V, PAPAPETROU P, POTAMIAS M, et al. Approximate embedding-based subsequence matching of time series [C]∥ Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 365-378．

[9] SHIEH J, KEOGH E.iSAX: disk-aware mining and indexing of massive time series datasets [J]. Data Mining and Knowledge Discovery, 2009, 19(1): 24-57．

[10] CAMERRA A, SHIEH J, PALPANAS T, et al. Beyond one billion time series: indexing and mining very large time series collections with iSAX2+ [J]. Knowledge and Information Systems, 2013, 39(1): 1-29．

[11] LI Y, YIU M L, GONG Z. Discovering longest-lasting correlation in sequence databases [J]. Proceedings of the VLDB Endowment, 2013, 6(14): 1666-1677．

[12] KEOGH E, CHAKRABARTI K, PAZZANI M, et al. Locally adaptive dimensionality reduction for indexing large time series databases [J]. ACM SIGMOD Record, 2001, 30(2): 151-162．

[13] KEOGH E, CHU S, HART D, et al. Segmenting time series: a survey and novel approach [J]. Data Mining in Time Series Databases, 2004, 57(1): 1-22．

[14]GULLOF,PONTIG,TAGARELLIA,etal.Atimeseriesrepresentationmodelforaccurateandfastsimilaritydetection[J].PatternRecognition, 2009, 42(11): 2998-3014．

[15]PAPADIMITRIOUS,SUNJ,FALOUTSOSC.Streamingpatterndiscoveryinmultipletime-series[C]∥Proceedingsofthe31stInternationalConferenceonVeryLargeDataBases.NewYork:ACM, 2005: 697-708．

[16]RAKTHANMANONT,CAMPANAB,MUEENA,etal.Searchingandminingtrillionsoftimeseriessubsequencesunderdynamictimewarping[C]∥Proceedingsofthe18thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDatamining.NewYork:ACM, 2012: 262-270．

[17]MANNING,CHRISTOPHERD,PRABHAKARR,etal.Introductiontoinformationretrieval[M].Cambridge:CambridgeUniversityPress, 2008．

[18]BLOTTS,WEBERR.Asimplevector-approximationfileforsimilaritysearchinhigh-dimensionalvectorspaces[R].Zurich:ETHZentrum, 1997．

[19]YAHOO!Finance. [2015-05-01].http:∥finance.yahoo.com/.

[20]MonteCarlosimulatedstockpricegenerator. [2015-05-01].http:∥25yearsofprogramm-ing.com/．

收稿日期：2015-05-13.浙江大學學報(工學版)網址： www.journals.zju.edu.cn/eng

基金項目：中國工業和信息化部“核高基”重大專項基金資助項目(2010ZX01042-002-003-001)；中國工程科技知識中心基金資助項目(CKCEST-2014-1-5)；國家自然科學基金資助項目(61332017).

作者簡介：蔡青林(1987-)，男，博士生，從事數據挖掘、信息檢索、模式識別的研究. ORCID：0000-0001-5219-7771. E-mail: qlcai@zju.edu.cn 通信聯系人：陳嶺，男，副教授. ORCID：0000-0003-1934-5992. E-mail: lingchen@zju.edu.cn

DOI:10.3785/j.issn.1008-973X.2016.07.010

中圖分類號：TP 39

文獻標志碼：A

文章編號：1008-973X(2016)07-1290-08

Two-step filtering based time series similarity search

CAI Qing-lin, CHEN Ling, MEI Han-lei, SUN Jian-ling

(CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027,China)

Abstract:A two-step filtering based search model was proposed in order to solve the problms that existing approximated search models have the poor controllability on the accuracy and have the low efficiency at the post-processing step. The symbolic aggregate approximation (SAX) method was employed to extract the symbolic feature vectors from time series. The high-dimensional time series was projected into the low-dimensional feature space. The symbolic feature vectors were saved as the form of vector approximation file (VA-File), and the efficient inverted index was introduced. A heuristic query and filtering algorithm was proposed at the procedure of searching in order to perform the first filtering, and an efficient boundary pruning method was proposed over the VA-File to reach the second filtering. The model can effectively control the search accuracy by the SAX feature vectors with multiple precision. Experimental results show that the proposed model has the efficient performance and the robust scalability on the series length, the kNN query scale and the dataset size．

Key words:time series; similarity search; symbolic aggregation approximation; vector approximation file; inverted index