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

(浙江大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310027)

?

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

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

(浙江大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310027)

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

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

時間序列相似性查詢是時間序列數(shù)據(jù)挖掘領(lǐng)域的基本問題,可簡要描述為對于給定的一條時間序列,需要快速完整的從時間序列數(shù)據(jù)庫中找出與其相似的序列.針對該問題,學(xué)術(shù)界提出了大量的查詢模型[1],這些模型通?；谔囟ǖ臄?shù)據(jù)表示方法,如奇異值分解(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]等,將高維的時間序列映射到低維的特征空間,然后構(gòu)建索引結(jié)構(gòu).模型的查詢過程可以簡要描述為：基于時間序列的近似表示查詢索引結(jié)構(gòu)獲取候選集；通過磁盤I/O讀取候選集的原始數(shù)據(jù),并與查詢序列進(jìn)行精確比較,獲得最終結(jié)果,該階段稱為后續(xù)處理[3].很明顯,模型的查詢效率由磁盤I/O的開銷規(guī)模決定.

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

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

1相關(guān)工作

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

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

2時序數(shù)據(jù)表示和索引構(gòu)建

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

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

2.1特征抽取

基于當(dāng)前學(xué)術(shù)界廣泛研究的SAX表示方法[6]提取時間序列的特征向量,將時間序列從原始數(shù)值空間映射到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表示轉(zhuǎn)化為SAX表示Fig.2　Transformation from PAA to SAX

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

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

(2)

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

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

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

2.2索引構(gòu)建

針對VA-File引入信息檢索領(lǐng)域的倒排索引結(jié)構(gòu)來實(shí)現(xiàn)高效查詢.倒排索引由單詞詞表與索引文件構(gòu)成,單詞詞表用于維護(hù)所有Term,索引文件包含了各Term指向的Postings,各Posting分別包含Term所在的文檔及其在該文檔內(nèi)的偏移量.

與傳統(tǒng)的倒排索引結(jié)構(gòu)不同,提出基于兩種不同粒度SAX特征向量的倒排索引結(jié)構(gòu),即多粒度時序倒排索引：基于粗粒度的特征向量構(gòu)建單詞詞表,基于包含細(xì)粒度特征向量的VA-File構(gòu)建索引文件.目的在于基于粗粒度的SAX特征向量從VA-File中查詢出細(xì)粒度的SAX特征向量集合作為初始候選集,實(shí)現(xiàn)第一級過濾.

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

根據(jù)信息檢索領(lǐng)域較成熟的倒排索引構(gòu)建算法[17],MGTI的構(gòu)建過程如算法1所示.

算法1MGTI構(gòu)建算法

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

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

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

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

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

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

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

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

6)將作為MGTI并返回.

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

3查詢處理

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

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

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

3.1第一級過濾

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

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

算法2簡單查詢算法

輸入：查詢序列Q,SAX參數(shù)；

輸出：初始候選集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特征向量的距離關(guān)系示意圖Fig.4　Relationship between three PAA feature vectors

雖然簡單查詢算法具有很高的查詢效率,但是在以距離度量作為時間序列相似性評價標(biāo)準(zhǔn)的前提下,簡單查詢可能會產(chǎn)生較多的“誤遺漏”[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的對應(yīng)元素分別落在不同的區(qū)間,P2與P3的對應(yīng)元素都落在相同的區(qū)間,但是若以歐氏距離作為相似性度量,則有f(P1, P2)

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

算法3擴(kuò)展查詢算法

輸入：查詢序列Q,SAX參數(shù)；

輸出：初始候選集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等同于對邏輯或的布爾查詢,時間開銷與Ψ的元素個數(shù)成正比.若將SAX(Q)的各元素擴(kuò)展到γ個相鄰區(qū)間,則Ψ包含γw個元素,考慮到查詢效率,γ不宜過大；在粗粒度的SAX表示中,離散區(qū)間較少,因此只需向外擴(kuò)展一個相鄰區(qū)間(γ= 3),便能保證細(xì)粒度SAX對象的顯著增加,即C1的規(guī)模增加,由此使得查詢精度得到較大提升.

3.2第二級過濾

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

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

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

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

SAX參數(shù)；

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

4實(shí)驗(yàn)分析

4.1實(shí)驗(yàn)設(shè)置

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

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

表1　不同序列長度的真實(shí)股票數(shù)據(jù)集

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

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

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

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

4.2實(shí)驗(yàn)結(jié)果及分析

4.2.1參數(shù)影響由于模型的查詢精度由決定,在確定參數(shù)w1的情況下,檢驗(yàn)?zāi)Ｐ驮?個不同序列長度的真實(shí)股票數(shù)據(jù)集上采用擴(kuò)展查詢算法執(zhí)行Top-20的kNN查詢,模型的召回率R隨特征空間基數(shù)a1的變化情況,如圖5所示.

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

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

4.2.2有效性檢驗(yàn)?zāi)Ｐ头謩e基于6個不同序列長度的數(shù)據(jù)集對簡單查詢與擴(kuò)展查詢算法執(zhí)行Top-20、Top-40、Top-60的kNN查詢,以檢驗(yàn)漏報率RFD.實(shí)驗(yàn)結(jié)果如圖6所示.

圖6　模型漏報率檢驗(yàn)結(jié)果Fig.6　Evaluation results for dismissal rate

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

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

圖7　模型查準(zhǔn)率檢驗(yàn)結(jié)果Fig.7　Evaluation results for precision rate

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

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

基于6個不同規(guī)模的隨機(jī)游走數(shù)據(jù)集對5種模型分別執(zhí)行Top-20的kNN查詢,以檢驗(yàn)它們的實(shí)際查詢時間開銷T,結(jié)果如圖8所示.

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

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

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

5結(jié)語

本文基于多粒度的SAX表示,提出基于兩級過濾的時間序列相似性查詢模型,構(gòu)建多粒度倒排索引結(jié)構(gòu),并設(shè)計啟發(fā)式的查詢過濾算法,用于實(shí)現(xiàn)高效高精度的近似查詢.

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

參考文獻(xiàn)(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.浙江大學(xué)學(xué)報(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

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

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

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

中圖分類號：TP 39

文獻(xiàn)標(biāo)志碼：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