基于序變換的時(shí)間序列快速匹配搜索方法

1、基于序變換的時(shí)間序列快速匹配搜索方法    時(shí)間序列作為一種數(shù)據(jù)形式廣泛存在于各種商業(yè)、醫(yī)學(xué)、工程、自然科學(xué)和社會(huì)科學(xué)等數(shù)據(jù)庫(kù)中。時(shí)間序列的搜索是整個(gè)時(shí)間序列數(shù)據(jù)挖掘的基礎(chǔ)，是數(shù)據(jù)挖掘的一個(gè)重要研究方向。該領(lǐng)域的基礎(chǔ)性工作最早是由Agrawal等在1993年提出的。該問(wèn)題可描述為給定某個(gè)的時(shí)間序列，要求從一個(gè)大型時(shí)間序列數(shù)據(jù)庫(kù)中找出與之最相似的序列。近年來(lái)時(shí)間序列的相似性搜索問(wèn)題正得到越來(lái)越多的重視，出現(xiàn)了許多面向相似性搜索的時(shí)間序列近似表示方法，如Agrawai采用的離散傅立葉變換DFTI，chan等人提出的基于小波變換的方法l2，Last等人提出的關(guān)

2、鍵特征(如斜率和信噪比)法，Korn等人31提出的奇異值分解法svD，xeogh等人l4先后提出的分段累積近似法以A、分段線性表示PLR和適應(yīng)性分段常數(shù)近似法APcA15，Pemg等人提出的界標(biāo)模型l6等，這些表示方法各有所長(zhǎng)，針對(duì)了不同的應(yīng)用背景，但仍有許多問(wèn)題有待進(jìn)一步的研究。例如:相似性度量進(jìn)一步認(rèn)識(shí)問(wèn)題，降低對(duì)偏移、噪聲的敏感性問(wèn)題，算法的效率問(wèn)題，用戶與系統(tǒng)的交互性問(wèn)題等。時(shí)間序列的相似性搜索可分為整體匹配和子序列匹配2種。本文針對(duì)子序列匹配問(wèn)題提出的基于序變換的相似匹配搜索方法，以時(shí)間序列特征點(diǎn)的序模式對(duì)相似性進(jìn)行描述，并在此基礎(chǔ)上以分段趨勢(shì)相似進(jìn)行相似度量，從而實(shí)現(xiàn)相似性匹配搜索

3、的準(zhǔn)確性和高效性。1墓于序棋式的時(shí)間序列相似匹妞1.1序棋式與序變換序模式是對(duì)時(shí)間序列中距離均勻分布的時(shí)間序列值排序關(guān)系的描述l7。對(duì)于時(shí)間序列x(O，階次d任N，且延時(shí):任N，則在t時(shí)刻獲得的唯一的排序?yàn)椤?三(。，。，。，一。，幾/r00三可其中，r0，r，rd滿足:(l)x，+r0:x，*。:xr十。_.:x，+。r;.(2)如果x，+。_l:二x，+。:，取介，rl。對(duì)于式(l)中的排序，當(dāng)l=l，2，d時(shí)，其對(duì)應(yīng)的序模式尸的第l個(gè)元素表示如下:i，=i(叮)=#rr。0，l，l一l，可(r)<可(l)(2)其中，二ru(r)表示數(shù)值;對(duì)應(yīng)的序值;運(yùn)算符“#”表示取集合中滿足不等

4、式約束條件的元素:的個(gè)數(shù)。如圖l所示，參數(shù)設(shè)置為r=1，d=4，r=3，得出x(r+3r)<x(t+r)<x(t+4r)<x(t+2:)<x(r+or)，因此有23424、o“(，4·2，0，0氣j廠res月、.、一一一rJ汀心二(3，1，4，2，0)對(duì)應(yīng)的序模式p可通過(guò)如下分析求得:對(duì)于l=l，二認(rèn)0)對(duì)應(yīng)位置為4，而心(l)對(duì)應(yīng)的位置為1，二、(0)=4>礦試1)=l不滿足(2)中的條件，有il二O;對(duì)于1=2，有心(0)二4>心(2)=3，心(l)習(xí)<心(2)=3，。l，一個(gè)元素滿足條件，因此，幾=卜·依次類推，可得出對(duì)于獷J

5、，其序模式為在實(shí)際的序模式計(jì)算中，通常采用由式(l)和式(2)導(dǎo)出的式(4)進(jìn)行計(jì)算:i，=i(可)=#rr。0，l，l一l，xt+，:之xl+rr(4)序變換是在序模式定義的基礎(chǔ)上，將給定的時(shí)間序列變換為處于【0，(d+l)!一l區(qū)間的符號(hào)序列。序模式11，12，i3與nd之間形成的雙射關(guān)系，即0，1!x0，1，2!xx0，1，d取值空間的元素排列與集合0，l，(d+l)!一瑪中的整數(shù)一一對(duì)應(yīng)，且該對(duì)應(yīng)關(guān)系可通過(guò)式(5)描述171:_、若.(d十l)!nJ(I)=么王，二:，二二百氣l+五)!對(duì)于前面的例子中序模式p=O，1，0，2，按照式(5)可得n試P)=22。同時(shí)，通過(guò)分析可知當(dāng)整個(gè)序

6、列為升序時(shí)，勺(P)達(dá)到最大值(d+l)!一l;當(dāng)整個(gè)序列為降序時(shí)，徹(P)達(dá)到最小值0。時(shí)間序列伸縮和平移序模式不變，序變換值不變，這一點(diǎn)可從圖1中觀察到。序模式和序變換的這種平移和伸縮不變性，以及序變換值與序模式的一一對(duì)應(yīng)的特點(diǎn)，不僅為時(shí)間序列相似性提供了更加符合人類思維和視覺(jué)特點(diǎn)的描述方法，還為序模式的快速索引提供了一個(gè)有效途徑。1.2相似性度t序模式能夠比較全面地描述原有序列中的信息，克服以點(diǎn)距離為基礎(chǔ)的時(shí)間序列誤匹配以及物理概念不明確等缺陷。顯然，若直接采用序模式對(duì)原始時(shí)間序列進(jìn)行描述，不但會(huì)引入繁重的計(jì)算量，而且對(duì)相似性匹配搜索沒(méi)有實(shí)際意義。因此，本文采用時(shí)間序列分段線性表示，先將

7、時(shí)間序列數(shù)據(jù)基于時(shí)間表示成多段相鄰的直線，這樣不但可以獲得時(shí)間序列分段拐點(diǎn)作為特征點(diǎn)，而且實(shí)現(xiàn)了對(duì)原始時(shí)間序列的壓縮、降噪和趨勢(shì)特征的提取。子序列相似性度量，通過(guò)子序列的序模式分類和趨勢(shì)分布距離匹配2個(gè)步驟實(shí)現(xiàn)。(1)子序列的序模式分類對(duì)數(shù)據(jù)庫(kù)中的時(shí)間序列進(jìn)行分段，線性表示獲得特征點(diǎn)序列，根據(jù)需要設(shè)定特征點(diǎn)子序列的長(zhǎng)度，并對(duì)各個(gè)子序列按照式(4)進(jìn)行序變換，從而可以實(shí)現(xiàn)對(duì)特征點(diǎn)子序列的劃分，將具有相同序變換數(shù)值的子序列歸為同一類。(2)趨勢(shì)分布距離設(shè)2個(gè)序列51和又對(duì)應(yīng)的分段數(shù)為n，其對(duì)應(yīng)各分段線段的斜率序列分別為k.:，k:2，k13，k，1和IkZ:，走22，無(wú)23，棍小定義2個(gè)序列的趨勢(shì)

8、分布距離為按照式(6)和式(7)的距離定義，當(dāng)51或S:序列在水平方向進(jìn)行縮放時(shí)，二者間的趨勢(shì)分布距離不受影響。趨勢(shì)分布距離是對(duì)2個(gè)序列內(nèi)部相對(duì)趨勢(shì)(或稱趨勢(shì)分布關(guān)系)相似性的度量，這就保證了趨勢(shì)分布距離匹配的合理性。通過(guò)對(duì)上述2點(diǎn)分析可知，如果某特征點(diǎn)子序列P與待查詢特征點(diǎn)序列Q屬于同一個(gè)序模式類，則二者趨勢(shì)分布距離愈短，相似匹配程度愈高。1.3算法雄程基于序模式的時(shí)間序列相似匹配搜索，包括2大部分:(l)索引生成StePI初始化，設(shè)定分段線性化的規(guī)則與相關(guān)參數(shù)，以及子序列的長(zhǎng)度與匹配精度;StePZ分段線性化，對(duì)原始時(shí)間序列分段線性化獲得特征點(diǎn)序列;SteP3基于滑動(dòng)窗的特征子序列序模式提

9、取及序變換;steP4建立索引，根據(jù)序變換值建立索引。(2)匹配搜索StePS對(duì)待匹配子序列進(jìn)行特征點(diǎn)提取、序模式計(jì)算及序變換;SteP6根據(jù)變換的結(jié)果進(jìn)行相似性搜索，得到同一序模式分類的匹配子序列;SteP7在同一序模式分類內(nèi)部，根據(jù)需要按照趨勢(shì)分布距離進(jìn)行二次匹配(或用戶直接瀏覽選取)。2關(guān)健技術(shù)間扭研究2.1簽于柑動(dòng)官和進(jìn)推算法的序棋式提取算扶對(duì)于時(shí)間序列S，取滑動(dòng)窗口的長(zhǎng)度為d+l，設(shè)相鄰2個(gè)滑動(dòng)窗口獲得的時(shí)間子序列為S(t)和S(t+T)，它們對(duì)應(yīng)的序模式分別為P(O和P(t+r)，如下所示:S(t)=xt，xl+:，xt，Zr，xt，3r，xl+J卜r，x，rls(l+:)=xt+

10、r，xlZr，xtl十，xl十4:，一xl十r，xtf，P(t)=毛(t)，12(t)，屯(I)，幾(t)1P(t+T)=!凡(t+r)，12(t+r)，毛(t+r)，幾(t+r)1根據(jù)式(4)，對(duì)于序模式p(r)和p(r+r)，有i。(，)=#r0r<n，x，、。，x，+，:ri。(，+:)=#rlr<n+l，x，+r:x，+。:+:由此，對(duì)于2三n三d，有in(，)=#r0r<n，xr+rrxt+。:=#!r!lr<n，xt+rrxt+。r+#rr=0，xt+rrxt+。r=i卜1(t+T)+e。i。_、(t+r)+l，凡+r:凡+。r+rin_1(t+了)，els

11、eD止“:，“2，=i客會(huì)一甕K。=藝k。.，m=l，2根據(jù)上述推導(dǎo)，可得出下面的基于滑動(dòng)窗和遞推算法的序模式提取算法。對(duì)于T=tl，幾，勺，腸，佃，初始化窗口長(zhǎng)度隊(duì)J+l，窗口序列幾二t，rn，r，+2，t，+3，rn科，+dl。按照定義直接計(jì)算T.對(duì)應(yīng)時(shí)間序列的序模式P(T.)二li，i:131;iu?；诨瑒?dòng)窗和遞推算法的序模式提取算法的偽代碼如下:Forn二2:l:(length(T)一W+l)Fori二n+l:I:n+d一lIfrn_一三t:e、一=l:else:e._一二0;EndEndFork二1:l:d一IIk=Ik+一Ck+I;Elld按照定義直接計(jì)算id;074072叮06

12、8P(T。)=【i:i:131;id;End例如:d二4，Tx二0.66，0.55，0.69，0刀6，0.93的序模式為(0204，幾二0.55，0.69，0.06，0.93，098)時(shí)，根據(jù)上面的算法:cZ，e3，c4二l，0，l，則72的序模式為(2一l)，(0一0)，(4一l)，i4，由定義直接計(jì)算份=4，因此，幾的序模式為1034。2.2序椒式靈飯度生成特征點(diǎn)子序列的序模式的過(guò)程中，可以根據(jù)需要設(shè)定序模式生成過(guò)程的靈敏度，以降低錯(cuò)誤舍棄(falsedismissal)的出現(xiàn)概率。靈敏度的設(shè)置通過(guò)設(shè)定一個(gè)正數(shù)實(shí)現(xiàn)，在序模式生成過(guò)程中，同一子序列中的任意2點(diǎn)瓜十。:和xt+br，如果lx，

13、+。T一，+brl夕，則認(rèn)為x，+。r和xt+b:是相等的，即對(duì)小于的變化不敏感。2.3索引建立長(zhǎng)度為d的序模式，依照序變換值分為(d+l)!類，即序模式與序變換值一一對(duì)應(yīng)。因此，可以以序變換值作為索引，并通過(guò)二分法實(shí)現(xiàn)快速查詢。3實(shí)臉結(jié)果與分析實(shí)驗(yàn)在基于Pentium4主頻ZGHz計(jì)算機(jī)上進(jìn)行，編程環(huán)境為Matlab6.IO11通推葬抉的實(shí)臉實(shí)驗(yàn)?zāi)康氖莻?cè)試序模式計(jì)算的滑動(dòng)窗遞推算法與按照定義直接計(jì)算算法的效率。采用側(cè)試序列的長(zhǎng)度為104點(diǎn)，子序列的長(zhǎng)度變化范圍為5，25，步長(zhǎng)為l。實(shí)驗(yàn)比較見(jiàn)圖2。于0.6，但它們顯著區(qū)別于待查詢子序列，其潛在原因是第4個(gè)關(guān)鍵點(diǎn)的序模式顯著不同于對(duì)應(yīng)待查詢子序

14、列的序模式。因此，這些子序列不能計(jì)入相似查詢的結(jié)果。由此可見(jiàn)，序模式對(duì)相似性的描述更符合人們的思維和觀察模式，而符號(hào)映射法對(duì)子序列的劃分則過(guò)于粗糙，不僅產(chǎn)生了較大的無(wú)用候選集合，還難以構(gòu)建有效的距離度量與之匹配。總:子序乒臨1擬合腳曰1岡尸扁霖么16犯100招50么洲)2閱26從220no0乃8厄子序列53乃擬合線口聲今副油Z一滬.，.“.洲砂r、丫以左仁二子序尹侶月擬合娜巴洲尸呢牙住54少湯ojZ一L呂173公幻.2650062陣簇二_u憑降U5410-二甲34.閣·呷見(jiàn).001匆到刀2閱擬3匆一子序尹卜6L=期時(shí)3叭1刃100150么刀2引)引刀二二尸側(cè)J.0I8t016。竹吩卜

15、195D喇)月科】oo奮502儀】子序尹臨呂.口鷺牡之洲/尹L聲加7【卜刃一5豁054r。耐咧麒社。一一子序列5777”··一一/油油一J湊漏時(shí)5!77750】001父圖3么刃2知州刃刃1田150創(chuàng)刀2知基于序模式的查詢結(jié)果示例叨訓(xùn)詞耐。0661峨直搜計(jì)算遞推算法0.68_二瑞爵溉了.二擬臺(tái)硯L諸L二21了U州-.·，··二奮護(hù)今，硯.巴丁二-·-一:-眾叱0.54卜，、，_二子序列SIV一氣生才_(tái)擬合徽卜1.沙z。呂IJ曰!.口，!引】口刃】夕】2002503嘆協(xié)50100150到1】塑2州一子序列53之理盆架書.卜二峭.悶卜-.一

16、月卜.月卜一二叼心喲心卜.一月卜.卜.一叫，悶卜.。與一言一命一朽州瓦戈槍站一北岌不一成子序列長(zhǎng)度圈2借動(dòng)，班推葬袂與定義宜擠計(jì)葬算按的實(shí)臉比狡由圖2可知遞推算法對(duì)子序列長(zhǎng)度的變化不敏感，算法時(shí)間保持在0.55左右;而直接計(jì)算算法時(shí)間與子序列長(zhǎng)度呈線性關(guān)系，隨著子序列長(zhǎng)度的增大，遞推算法的優(yōu)勢(shì)愈加顯著。由此可見(jiàn)，上述序模式的遞推計(jì)算完全能夠滿足在線匹配搜索的需要。3.2相似匹硯搜索實(shí)臉本實(shí)驗(yàn)?zāi)康氖菧y(cè)試相似匹配搜索質(zhì)量和速度。測(cè)試數(shù)據(jù)通過(guò)Wiener過(guò)程產(chǎn)生，模擬現(xiàn)實(shí)世界中的股票市場(chǎng)價(jià)格波動(dòng)等隨機(jī)現(xiàn)象。測(cè)試數(shù)據(jù)長(zhǎng)度為105個(gè)點(diǎn)，并進(jìn)行規(guī)一化處理。線性分段閱值參數(shù)。0.02，獲得的關(guān)健點(diǎn)個(gè)數(shù)為19

17、27個(gè)。設(shè)里靈敏度參數(shù)。二O。如圖3所示，Sl為216點(diǎn)的待查詢子序列，其分段擬合后得到趨勢(shì)線段Ll，序模式為1么2，4，5，序變換值為689。得到的匹配序列為多個(gè)不同長(zhǎng)度的子序列，其中，趨勢(shì)分布距離小于0.6的子序列為7個(gè)，長(zhǎng)度從173到334不等。因?yàn)檫@里序模式長(zhǎng)度為5，其序變換值的區(qū)間為10，720;查詢時(shí)間只須從上述區(qū)間查詢變換值689對(duì)應(yīng)的子序列即可。將時(shí)間序列數(shù)據(jù)和索引加載在內(nèi)存后，整個(gè)序模式匹配搜索算法的時(shí)間約為70ms。如果采用符號(hào)映射法(將趨勢(shì)的升降用O和l表示)，上述待查詢子序列sl對(duì)應(yīng)的趨勢(shì)符號(hào)表示為1110曰】，將產(chǎn)生無(wú)用候選子序列76個(gè)，其中典型的子序列如圖4所示。雖然子序列Ll，LZ，L3和L4與待查詢子序列的趨勢(shì)分布距離小蒸籌憋江丫匆1001犯