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

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

?

基于兩級(jí)過(guò)濾的時(shí)間序列近似查詢

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

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

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

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

時(shí)間序列相似性查詢是時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域的基本問(wèn)題,可簡(jiǎn)要描述為對(duì)于給定的一條時(shí)間序列,需要快速完整的從時(shí)間序列數(shù)據(jù)庫(kù)中找出與其相似的序列.針對(duì)該問(wèn)題,學(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]、符號(hào)聚集近似(symbolic aggregation approximation, SAX)[6]等,將高維的時(shí)間序列映射到低維的特征空間,然后構(gòu)建索引結(jié)構(gòu).模型的查詢過(guò)程可以簡(jiǎn)要描述為：基于時(shí)間序列的近似表示查詢索引結(jié)構(gòu)獲取候選集；通過(guò)磁盤I/O讀取候選集的原始數(shù)據(jù),并與查詢序列進(jìn)行精確比較,獲得最終結(jié)果,該階段稱為后續(xù)處理[3].很明顯,模型的查詢效率由磁盤I/O的開銷規(guī)模決定.

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

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

1相關(guān)工作

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

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

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

首先給出時(shí)間序列的定義如下.

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

2.1特征抽取

基于當(dāng)前學(xué)術(shù)界廣泛研究的SAX表示方法[6]提取時(shí)間序列的特征向量,將時(shí)間序列從原始數(shù)值空間映射到SAX符號(hào)空間.

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

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

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

(1)

圖1給出長(zhǎng)度為60的時(shí)間序列以6維PAA特征向量的近似表示.

圖2　由PAA表示轉(zhuǎn)化為SAX表示Fig.2　Transformation from PAA to SAX

由于z-規(guī)范化的時(shí)間序列服從高斯分布,Keogh等[6]基于高斯概率密度函數(shù)對(duì)實(shí)數(shù)域作等概率的區(qū)間劃分,并將各區(qū)間以特定的字符表示.將PAA特征向量的各元素映射到對(duì)應(yīng)的劃分區(qū)間,得到時(shí)間序列的SAX特征向量,表示為SAX(T).如圖2所示,若將實(shí)數(shù)域劃分為3個(gè)區(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),可以在查詢過(guò)程中實(shí)現(xiàn)高效的邊界剪枝算法.給定向量集合Φ= {v1, v2,…, vi,…, vm},|vi|表示向量vi的維度,以vij表示vi在第j維的元素值.假設(shè)ai是vi的特征向量,以n位存儲(chǔ),則存儲(chǔ)ai各元素所需的位數(shù)nj可由下式計(jì)算得到：

(2)

式中：%表示求模運(yùn)算.將vi的第j維劃分為2nj個(gè)區(qū)間,整個(gè)向量空間Φ劃分為2n個(gè)元胞.通過(guò)將第j維的所有區(qū)間依次編號(hào)為{0, 1, 2,…, 2nj-1},并以vij所在區(qū)間的編號(hào)作為其特征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個(gè)區(qū)間,第2維可以劃分為2個(gè)區(qū)間,整個(gè)向量空間被劃分為8個(gè)元胞.若圖3中的向量v3=[9, 3],則特征向量為a3= [1, 0]；對(duì)圖3中向量集合Φ= {v1, v2, v3, v4, v5}所構(gòu)建的VA-File為"101110010101111".

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

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

2.2索引構(gòu)建

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

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

定義3 多粒度時(shí)序倒排索引假設(shè)時(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)成的倒排索引稱為多粒度時(shí)序倒排索引,表示為MGTI (multi-granularity time inverted-index).

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

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

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

輸出：多粒度時(shí)序倒排索引MGTI．

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

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

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

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

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

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

6)將作為MGTI并返回.

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

3查詢處理

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

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

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

3.1第一級(jí)過(guò)濾

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

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

算法2簡(jiǎn)單查詢算法

輸入：查詢序列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個(gè)PAA特征向量的距離關(guān)系示意圖Fig.4　Relationship between three PAA feature vectors

雖然簡(jiǎn)單查詢算法具有很高的查詢效率,但是在以距離度量作為時(shí)間序列相似性評(píng)價(jià)標(biāo)準(zhǔn)的前提下,簡(jiǎn)單查詢可能會(huì)產(chǎn)生較多的“誤遺漏”[3].如圖4所示,對(duì)于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)作為簡(jiǎn)單查詢算法的輸入Term,則初始候選集將包含SAX(P3),而不包含SAX(P1).雖然P1與P2的對(duì)應(yīng)元素分別落在不同的區(qū)間,P2與P3的對(duì)應(yīng)元素都落在相同的區(qū)間,但是若以歐氏距離作為相似性度量,則有f(P1, P2)

擴(kuò)展查詢是指首先將SAX(Q)的各元素從它所在的SAX區(qū)間βj擴(kuò)展到相鄰區(qū)間βj-1和βj+1,于是SAX(Q)被擴(kuò)展到一個(gè)SAX特征向量集合Ψ；然后從MGTI中獲取與Ψ中各元素對(duì)應(yīng)的Postings集合作為查詢結(jié)果,見算法3.第3～5行表示基于粗粒度參數(shù)提取Q的SAX特征向量；在第6～8行依次擴(kuò)展SAX特征向量的每個(gè)符號(hào)元素至相鄰的劃分區(qū)間；在第9行,以集合Ψ中的所有元素作為查詢Term,對(duì)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等同于對(duì)邏輯或的布爾查詢,時(shí)間開銷與Ψ的元素個(gè)數(shù)成正比.若將SAX(Q)的各元素?cái)U(kuò)展到γ個(gè)相鄰區(qū)間,則Ψ包含γw個(gè)元素,考慮到查詢效率,γ不宜過(guò)大；在粗粒度的SAX表示中,離散區(qū)間較少,因此只需向外擴(kuò)展一個(gè)相鄰區(qū)間(γ= 3),便能保證細(xì)粒度SAX對(duì)象的顯著增加,即C1的規(guī)模增加,由此使得查詢精度得到較大提升.

3.2第二級(jí)過(guò)濾

為了進(jìn)一步剔除C1的“誤命中”,節(jié)省后續(xù)處理中磁盤I/O的時(shí)間開銷,基于VA-File的組織結(jié)構(gòu),提出一種高效的邊界剪枝算法對(duì)C1進(jìn)行第二級(jí)過(guò)濾,以獲取規(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)先隊(duì)列MaxUpper和最小優(yōu)先隊(duì)列MinLower；第4行基于參數(shù)提取Q的SAX特征向量；第6和第7行分別計(jì)算query與C1第i個(gè)元素的上下邊界距離；在第9行根據(jù)下界距離對(duì)C1的前k個(gè)元素進(jìn)行排序；在第20行判斷MinLower中第j個(gè)元素的下界距離與MaxUpper中當(dāng)前最大上界距離的關(guān)系；在第23行取出MinLower的第j個(gè)元素對(duì)應(yīng)的時(shí)間序列插入最終候選集C2.算法4是一種基于邊界距離的剪枝算法,滿足下界定理[7]可知,不會(huì)導(dǎo)致“誤遺漏”,計(jì)算復(fù)雜度為O(n+mlog2m),其中n為C1的元素?cái)?shù)目,m為C2的元素?cái)?shù)目.另外,算法4可以采用多種提前終止技術(shù)[16]及內(nèi)存表技術(shù)[6]進(jìn)行加速計(jì)算.

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語(yǔ)言和開源的Lucene 4.6.0框架實(shí)現(xiàn).原始數(shù)據(jù)集全部存儲(chǔ)于基于MYISAM存儲(chǔ)引擎的數(shù)據(jù)庫(kù)管理系統(tǒng)MySQL 5.6.17中,并通過(guò)JDBC讀取數(shù)據(jù).實(shí)驗(yàn)采用以下兩類數(shù)據(jù)集.

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

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

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

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

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

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

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

4.2.1參數(shù)影響由于模型的查詢精度由決定,在確定參數(shù)w1的情況下,檢驗(yàn)?zāi)Ｐ驮?個(gè)不同序列長(zhǎng)度的真實(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對(duì)數(shù)據(jù)空間的劃分越細(xì),空間越稀疏,查詢到的初始候選集越小,所包含的真實(shí)結(jié)果越少,召回率越低.在參數(shù)a1的各取值上,模型在7個(gè)不同序列長(zhǎng)度數(shù)據(jù)集上的召回率相差較小,說(shuō)明模型對(duì)時(shí)間序列長(zhǎng)度具有魯棒性.為了保證模型具有較高的召回率,選擇參數(shù)a1=8用于后續(xù)實(shí)驗(yàn).

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

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

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

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

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

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

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

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

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

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

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

5結(jié)語(yǔ)

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

下一步的研究工作將圍繞范圍查詢深入展開,并且如何將模型有效地應(yīng)用于超大規(guī)模時(shí)間序列數(shù)據(jù)集的問(wèn)題,有待進(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é)報(bào)(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

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

作者簡(jiǎn)介：蔡青林(1987-)，男，博士生，從事數(shù)據(jù)挖掘、信息檢索、模式識(shí)別的研究. 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

中圖分類號(hào)：TP 39

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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