時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)

1、時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)潘定1,2+, 沈鈞毅21（暨南大學(xué)管理學(xué)院1（暨南大學(xué)管理學(xué)院，廣東廣州510632)2（西安交通大學(xué)計算機科學(xué)與技術(shù)系，陜西西安 710049）Similarity Discovery Techniques in Temporal DataMiningPAN Ding1,2+, SHEN Jun-Yi21(Management School, Jinan University, Guangzhou510632, China)gy2(Department of Computer Science and TechnologyXian Jiaotong Univers

2、ity, Xian 710049, China)+ Corresponding author: Phn: +86-20-85220180, E-mail: HYPERLINK mailto:pandingcn pandingcn潘定等:時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)247要集中在實數(shù)或離散數(shù)量的預(yù)測上，時間序列分析方法可用于時態(tài)數(shù)據(jù)的表示、度量和預(yù)測; 機器學(xué)習(xí)研究涉及離散序列的模式發(fā)現(xiàn)和預(yù)測;數(shù)據(jù)庫研究涉及多維數(shù)據(jù)的存儲、索引以及對大數(shù)據(jù)集的相 似性查詢.1993年,Agrawal等人首先發(fā)表了關(guān)于時間序列相似搜索的研究論文1.此后，相關(guān)研究項目和研究者不斷增加.IBM公司的Agrawal和U

3、C Irvine的Pazzani研究小組較早且持續(xù)開展相關(guān)研究,UC Riverside 的 E. Keogh和UI Urbana-Champaign的J. Han研究小組是目前TDM界最活躍的群體.還有美國的UC Santa Barbara、Maryland大學(xué)、Massachusetts大學(xué)、南澳洲的Flinders大學(xué)等，也活躍著相應(yīng)的研究小組.國內(nèi)的相關(guān)研究大約從2000年開始起步，復(fù)旦大學(xué)、浙江大學(xué)、中國科技大學(xué)等2曾有相關(guān)的研究，但比較零散，缺少系統(tǒng)性.傳統(tǒng)數(shù)據(jù)挖掘研究通常按分析目的區(qū)分為:描述性方法、預(yù)測性方法和局部方法.在TDM研 究中，將數(shù)據(jù)演化規(guī)律作為時態(tài)特性進行分析，傳統(tǒng)

4、的區(qū)分已難以適用.文獻3主張將研究分為相似性發(fā)現(xiàn) 和特征值預(yù)測.本文采用這種觀點，集中討論時態(tài)數(shù)據(jù)的相似性發(fā)現(xiàn)技術(shù).時態(tài)數(shù)據(jù)相似性發(fā)現(xiàn)主要有3類任務(wù):相似性搜索，它既是一類獨立的挖掘技術(shù),又是實現(xiàn)其他任務(wù)的基礎(chǔ);時態(tài)關(guān)聯(lián)規(guī)則和序列模式的發(fā)現(xiàn)，涉 及局部特征相似統(tǒng)計顯著性;全局特征綜合分類，涉及全局特征相似性描述的聚類和有監(jiān)督的分類.高維度、高特征相關(guān)性和大量噪音是時態(tài)數(shù)據(jù)的獨特結(jié)構(gòu).這種特征使許多經(jīng)典算法難以發(fā) 揮作用，增加了挖掘算法的研究難度.通常認(rèn)為解決此類問題需要3種成分或技術(shù):比較兩個序列的距 離度量;抽象表示數(shù)據(jù)形態(tài)的技術(shù);實現(xiàn)特定挖掘任務(wù)的搜索或優(yōu)化算法.本文第1節(jié)定義相似性發(fā)現(xiàn)問

5、題.第2節(jié)討論幾種主要的距離度量.第3節(jié)歸納分析序列的 3 類表示和搜索方法.第4節(jié)詳細討論相似性發(fā)現(xiàn)的挖掘任務(wù)及其操作.第5節(jié)總結(jié)并說明未來的研究方向.1 相似性發(fā)現(xiàn)問題在TDM研究中，主要涉及3類時態(tài)數(shù)據(jù):時間序列、事件序列和交易序列.對給定的有限時 間集T、非空狀態(tài)屬性集A=A1A,.,/%m及其對應(yīng)各值域iAD，可分別定義如下：定義1. 一個時間序列S是有序項隊列S1,S2，S，其中,Si項是一個m+1元組(t,a1,am),tT,ai eiiAAD , D取實數(shù)集.定義2.個事件序列E是有序項隊列E1,E2，En，其中,Ei項是一個m+1元組(t,a1,am),teT,ai eiiA

6、AD ,D取標(biāo)稱集，由字母表定義.對于時間序列，每個元組中的屬性值ai取實數(shù)，典型的如每種股票的日收盤價構(gòu)成的序列;而事件序列的屬性值 ai取標(biāo)稱量,如客戶瀏覽某個網(wǎng)站的事件可能是(100,A),(110,B),(115,C),.,(230,Q),其中:每個元組 中的數(shù)字表示一種時序;字母A,B,C等是某種行為的標(biāo)示.以上是對m維序列的定義.當(dāng)m1時，應(yīng) 考慮各ai間的相關(guān)性，增加了研究的難度.現(xiàn)有的多數(shù)研究是先基于一維序列研究后，再向多維情形擴展.定義3. 一個交易序列C是有序項隊列C1,C2,.，Cn，其中,Ci項是一個m+2元組(p,t,a1,am),pP,P 是有限實體集,tT,ai

7、,iAD Ai是交易項目的狀態(tài)，iAD可取實數(shù)(交易量)或二元量(是否成交).交易序列的研究開始于對超市顧客購物行為的分柝即購買商品的關(guān)聯(lián)規(guī)則分析，后來推廣到其他交易類分析，如股票交易、電信服務(wù)等的交叉銷售分析.通常要求時間集T是升序的，為方便處理，常假設(shè)時間是等距的,即ti+1+-ti+=為常數(shù)，這樣 就可以將T映射到自然數(shù)集.以上定義僅涉及一個時間維度，更一般地可定義多個時間維度,如交易時間、有效時間等.對兩實體對象Q1,Q2，其距離(不相似性)記為D(Q1,Q2).距離度量的一個重要性質(zhì)是三角不等式，即對于3個對象A,B,C,存在 D(A,B)WD(A,C)+D(B,C).作為時態(tài)數(shù)據(jù)相

8、似性發(fā)現(xiàn)的基本問題,相似性搜索可簡單地描述為:給定一個序列集合S、一 個序列q、一個距離度量D和容錯閾值，要找出序列集合U=sS|D(q,s)W .進一步地，可定義搜索S 中序列的子序列集合，即不僅比較S中的序列，而且比較序列中所有與q相似的子序列.如果實際搜索的結(jié)果UuU測U-U為漏報(false dismissals);反之，若U河,則U -U為多報(false alarms).保證無漏報的相似性匹配稱為精確的，否則稱為近似的.248 Journal of Software 軟件學(xué)報 Vol.18, No.2, February 2007時態(tài)關(guān)聯(lián)規(guī)則是一對二元組(R,F),其中:R是形如X

9、Y的規(guī)則，且XHY0;F是時態(tài)特征(如 有效時期、周期或特定日歷).非形式地，時態(tài)關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)是對給定的時態(tài)數(shù)據(jù)集S,找出所有滿足指定支 持度和可信度限制的時態(tài)關(guān)聯(lián)規(guī)則的集合;序列模式的發(fā)現(xiàn)是對給定的時態(tài)數(shù)據(jù)集S,找出所有滿足指定支持度 的序列的集合;分類是對給定的未標(biāo)記時態(tài)序列Q,指出Q屬于兩個或若干個預(yù)定義類之一;聚類是對給定的 時態(tài)數(shù)據(jù)集合S,找出滿足某些相似性度量D(q,s)的自然分組.對于時態(tài)關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)，時態(tài)特征F是一個關(guān)鍵性的決定因素，而傳統(tǒng)的關(guān)聯(lián)規(guī)則是忽略 時態(tài)的.序列模式的發(fā)現(xiàn)主要關(guān)注時態(tài)序列中按序出現(xiàn)的頻繁模式時間序列應(yīng)轉(zhuǎn)換成事件序列后再挖掘.2 序列距離度量時態(tài)數(shù)據(jù)序

10、列的相似性是通過距離度量來確定的，而距離度量的選擇與應(yīng)用領(lǐng)域高度相關(guān).有 多種距離度量:對連續(xù)值的時間序列有LP范數(shù)等;對事件序列有編輯距離.由于交易項目的稀疏性，交易序列通常不使用成 對比較的距離度量.對于時間序列，最流行的LP范數(shù)距離定義如下：PliPPiiLXYxy1/1(,)|=-(1)其中,l=|X| = |Y|;p=1,2,8 .在此,l1是 Manhattan 距離,L2就是最常用的Euclidean距離.L2僅適合于兩個等長序列比較，且對時間軸變形很敏感，因而在應(yīng)用中受到許多限制.為了處理局部時間位移,1994年,動態(tài)時間彎曲(dynamic time warping,簡稱DT

11、W)技術(shù)被 引入數(shù)據(jù)挖掘領(lǐng)域，但直接用動態(tài)規(guī)劃計算兩序列距離的算法復(fù)雜性太大(O(mn),因而通常將其應(yīng)用于經(jīng)變 換后的時間序列DTW通過壓縮序列中的非顯著特征，使預(yù)定義的距離最小化，可以比較兩個任意長度序列之 間的相似性，主要用于比較沿時間軸的波動模式.時間序列X,Y的DTW距離可遞歸定義為IIIIIf=-=+=8 =Dab|ab|DXYDxyDXRestYDRestXYDRestXRestYDXDYDbasetwbasetwtwtwtwtwtw(,)(,)(,)min(,(),(),),(),()(,)(,)(,)011(2)這里,X=(x1,x2x，,八m),Y=(y1,y2，yn),R

12、est(X)=(x2x，,八m),Rest(Y)=(y2，yn),Dbase可按需要選擇LP范數(shù).DTW的靈活性使其獲得大量的應(yīng)用，但也伴隨著可伸縮問題.已經(jīng)證明DTW不滿足三角不等式，并有研究表明:任何顯式或隱含地規(guī)定了滿足三角不等式的索引，都將對不符合要求的距離度量產(chǎn)生漏報5.文獻6 介紹并證明了第1個支持時間彎曲且無漏報的索引結(jié)構(gòu),它是由序列的4個特征構(gòu)成距離函數(shù)Dtw-lb和多維索引，但僅僅4個特征顯然無法充分發(fā)揮多維索引的優(yōu)勢，且查詢時若僅使用一個特征將會導(dǎo)致 漏報.文獻7 提出并證明了支持DTW精確索引的新技術(shù)，這種距離度量可看作是將DTW轉(zhuǎn)換成上下限序列的Euclidian 距離

13、.在一些現(xiàn)實的約束下，可為序列Q分別指定上/下限序列U/L,則Q與序列S的距離為=IJ(-niiiiiiiiiLBsLsLsUsUDQS1220,(),(),(,)否則(3)另外,DTW度量距離采用逐點匹配方式,易受噪音、孤立點干擾.LCSS(longest common subsequence)距離度量8能夠有效地克服這些缺陷，在序列比較時忽略噪音或孤立點，取兩序列的最長公共子序列為其 距離度量.ERP (edit distance with real penalty)距 離9則結(jié)合L1與編輯距離的優(yōu)點，既能處理局部時間位移，又滿足三角不等式，因而，可利用下邊界和三角不等式策略修剪空間，并用

14、B+樹索引.對于事件序列的相似性,可以采用編輯距離進行度量9，其基本思想是:兩個序列越相似，則相互變換的代價就越少.可以為一組變換操作(如插入、刪除、移動等)定義相應(yīng)的代價函數(shù)，則事件序列的距 離就是一個序列變ISSN 1000-9825, CODEN RUXUEW E-mail: HYPERLINK mailto:jos josJournal of Software, Vol.18, No.2, February 2007, pp.246-258 HYPERLINK DOI: 10.1360/jos180246 Tel/Fax: +86-10-62562563 2007 by Journal

15、 of Software. All rights reserved.時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)潘定1,2+, 沈鈞毅21(暨南大學(xué)管理學(xué)院，廣東廣州510632)2(西安交通大學(xué)計算機科學(xué)與技術(shù)系，陜西西安710049)Similarity Discovery Techniques in Temporal Data MiningPAN Ding1,2+,SHEN Jun-Yi21(Management School, Jinan University, Guangzhou 510632, China)2(Department of Computer Science and Technolog

16、y, Xian Jiaotong University, Xian 710049, China)+ Corresponding author: Phn: +86-20-85220180, E-mail: HYPERLINK mailto:pandingcn pandingcnPan D, Shen JY. Similarity discovery techniques in temporal data mining.Journal of Software, 2007,18(2):246-258. HYPERLINK /1000-9825/18/246.htm /1000-9825/18/246

17、.htmAbstract: Temporal data mining (TDM) has been attracting more and more interest from a vast range of domains,from engineering to finance. Similarity discovery technique concentrates on the evolution and development of data,attempting to discover the similarity regularity of dynamic data evolutio

18、n. The most significant techniquesdeveloped in recent researches to deal with similarity discovery in TDM are analyzed. Firstly, the definitions ofthree categories of temporal data, time series, event sequence, and transaction sequence are presented, and then thecurrent techniques and methods relate

19、d to various sequences with similarity measures, representations, searching,and various mining tasks getting involved are classified and discussed. Finally, some future research trends on thisarea are discussed.Key words: data mining; temporal data; similarities discovery; temporal rule摘要：現(xiàn)實世界存在著大量的

20、時態(tài)數(shù)據(jù),時態(tài)數(shù)據(jù)挖掘(temporal data mining,簡稱TDM)是 近年來學(xué)術(shù)界關(guān)注的一個重要研究課題.相似性發(fā)現(xiàn)技術(shù)關(guān)注數(shù)據(jù)的發(fā)展變化，試圖從時態(tài)數(shù)據(jù)中發(fā)現(xiàn)事物動態(tài) 演化的相似性規(guī)律.分析和比較了近年來TDM研究中涉及的主要相似性發(fā)現(xiàn)技術(shù).首先區(qū)分定義了 3類時 態(tài)數(shù)據(jù):時間序列、事件序列和交易序列;然后分類并討論了各種與序列相關(guān)的主要方法和技術(shù)涉及相似性度量、 序列抽象表示和搜索,以及各類挖掘任務(wù)及其算法操作;最后展望進一步研究的方向.關(guān)鍵詞：數(shù)據(jù)挖掘;時態(tài)數(shù)據(jù);相似性發(fā)現(xiàn);時態(tài)規(guī)則中圖法分類號:TP311文獻標(biāo)識碼:A傳統(tǒng)上，大多數(shù)數(shù)據(jù)挖掘問題僅涉及靜態(tài)數(shù)據(jù).近幾年來,主要

21、關(guān)注數(shù)據(jù)動態(tài)特性的時態(tài)數(shù)據(jù)挖掘(temporaldata mining,簡稱TDM)成為學(xué)術(shù)界研究的熱點之一.在現(xiàn)實生活中，時態(tài)數(shù)據(jù)隨處可見，如股 市交易指數(shù)、超市銷售、Web訪問、氣象觀測、臨床數(shù)據(jù)等對時態(tài)數(shù)據(jù)的知識發(fā)現(xiàn)已有多方面的研究.統(tǒng)計學(xué) 研究時間序列,主Supported by the National Natural Science Foundation of China under Grant Nos.60173058, 70372024 (國家自然科學(xué)基金)Received 2005-06-19; Accepted 2006-01-11250 Journal of Softwa

22、re 軟件學(xué)報 Vol.18, No.2, February 2007分段常數(shù)逼近方法15,16將序列分成等長的k個段，各段的平均值就構(gòu)成該序列的k維特征向量.這種方法的優(yōu)點是易于理解和實現(xiàn)、轉(zhuǎn)換速度快、無漏報、線性建立索引開銷、存在更靈活的距離度量 等.對這種k維特征向量可建立Lp的多形式距離度量和綜合索引機制，還可加入偏移變換、幅度/時間伸縮15.PAA(piecewiseaggregate approximation)方法16使用更靈活的距離度量,如加權(quán)Euclidian距離、DWT,并支持比索引項更短的查詢,這種能力是 DFT,DWT 和 SVD 所沒有的.APCA(adaptive

23、piecewise constant approximation)方法17是PAA方法的改進,其序列分段是變長的、可索引的，即對波動較大區(qū)間劃分多個短區(qū)段對平穩(wěn)區(qū)間 劃分少量長區(qū)段，優(yōu)化表示性能.為了高效、高質(zhì)量地擬合分段，算法首先利用小波變換，然后還原為變長分段.PAA和APCA都能處理Lp范數(shù),APCA的性能比DFT和DWT提升了 12個數(shù)量級.以上變換方法都是遵循GENMINI框架進行的.DFT, DWT和SVD都是利用多個基本函數(shù)的 線性組合來表示序列的.DFT利用正弦和余弦函數(shù),DWT利用小波基函數(shù),SVD利用特征波函數(shù)(eigenwaves).PAA 和 APCA利用一系列箱型(b

24、ox)基函數(shù)來表示序列，其中PAA的箱型基是定長的，而APCA的箱型基是變 長的.從可使用的距離度量、性能和效果的綜合評價來看，這些方法雖然各有長處,但多數(shù)情況下,PAA是較優(yōu)的. 這些方法的共同不足是:當(dāng)要求匹配的子序列長度超過滑動窗口時,算法性能明顯下降;需要平衡維度約簡與 準(zhǔn)確表示序列的矛盾;大多數(shù)算法不能處理小于滑動窗口的子序列匹配問題.界標(biāo)方法的理論基礎(chǔ)是人類心理和認(rèn)知科學(xué).對于時間序列，界標(biāo)是指序列中“最重要”的點(事件).界標(biāo)形式依賴于應(yīng)用領(lǐng)域，若曲線上某點處的n階導(dǎo)數(shù)為0,則此點為n階界標(biāo)，即局部極值點是 一階界標(biāo)，拐點是二階界標(biāo).文獻18提出位移、均勻幅度伸縮、均勻時間伸縮、

25、時間彎曲等6種界標(biāo)的變換形式, 具有強大靈活、效果穩(wěn)定的特點.另一種基于界標(biāo)的方法6是通過抽取序列開始、最后、最大和最小元素獲得時間彎曲不變的特征向量，可應(yīng)用于子序列或全序列匹配，與以前的方法相比，在性能上提高了若干數(shù)量級.用字符串表示時間序列的方法已有多種:聚類變換方法19，先由滑動窗口獲得子序列集合，再對子序列聚類，并指定相應(yīng)類符號表示,序列就由這些類符號構(gòu)成;分段劃分方法20，將兩點之間具有相同比率的連續(xù)點劃分成段，并指定某個符號表示;投影方法21，使用SOM(self-organizing map)將高維空間中的模式投影到圖中的位置,這些位置對應(yīng)于相應(yīng)的符號，從而可以有效地減少噪聲，降

26、低序列維度;聚合近似,SAX(symbolicaggregate approximation)方法22先將序列變換為PAA表示,然后符號化為字符串，實現(xiàn)了維度約簡且滿足下邊界引理，這是其獨特的優(yōu)點;限幅(clipping)方法23將一個實數(shù)值序列變換成一個二進制序列，原序列值大于總體均值的為1,否則為0,其離散化方式是SAX方法的特例.界標(biāo)模型將相似度量、數(shù)據(jù)表示和平滑技術(shù)集成于統(tǒng)一的框架內(nèi)，其表現(xiàn)形式和變換方法的 直觀性較好.離散化成字符序列的方法可對原序列的實數(shù)值形成一種自然的劃分表示，有利于應(yīng)用許多成 熟的字符串處理方法，如文法推理方法等.但這些方法的符號表大小、符號、形狀選擇等帶有隨意

27、性容易導(dǎo)致 漏報.3.2 基于模型的方法基于模型的方法假設(shè)數(shù)據(jù)隱含某種強結(jié)構(gòu)，試圖通過數(shù)據(jù)建模，將模型看作是相應(yīng)時態(tài)數(shù)據(jù)的 發(fā)生器.回歸及其混合模型可用于時間序列建模24.ARMA(auto-regression moving average)模 型作為一個信息凝聚器，是時間序列分析中最基本、實際應(yīng)用最廣的模型，但難以實現(xiàn)子序列匹配.ARMA混合模型 可表示變長的時間序列25.對于 ARIMA(auto-regressive integrated moving average)模型，應(yīng)先用差分操作移去序列的非平穩(wěn)性，再對獨立ARMA模型建模,距離度量使用兩序列模型的線性預(yù)言編碼cepstrum

28、的Euclidean 距離26.Markov鏈和隱Markov模型(hidden Markov model,簡稱HMM)是常用的序列建模工具*2729+.HMM能夠同時處理時空維度的不確定性，建模能力更強.文獻30提出采用基于分割的半Markov模型為 時間序列建模，即將序列建模為K狀態(tài)分割的隱Markov模型，每個分割對應(yīng)一個狀態(tài)，并用回歸函數(shù)對應(yīng)生成 序列各成分;分割之間的距離允許沿時間軸變形;一個序列S的模型MS，相對于一個查詢Q,其相似度量定義為p(Q|MS).圖模型是可以通過變量之間的條件獨立關(guān)系直接說明的模型用圖形表示.圖模型是常用的統(tǒng) 計模型,Markov鏈就是一種重要的有向圖模

29、型.Mannila等人31采用有向圖(遞歸圖模型)直觀地表示事件序列中的偏序關(guān)系，并通過順序或并行方式組合事件成為復(fù)雜片段(episode).進一步的工作32將偏序看作是序列的生成潘定等:時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)251模型，并通過偏序的混合模型來描述序列集合.文法模型是表達字符序列的有力工具，已有許 多研究涉及由序列推導(dǎo)出文法的方法.用于推導(dǎo)的文法包括:確定正則文法33、上下文無關(guān)文法34和隨機文法35.前饋神經(jīng)網(wǎng)絡(luò)由于缺少時間機制，不適于為時態(tài)事件建模.遞歸神經(jīng)網(wǎng)絡(luò)(recurrent neural network,簡稱RNN)可以通過內(nèi)部狀態(tài)為序列的時態(tài)關(guān)系明確地建模，遞歸意味著網(wǎng)絡(luò)狀

30、態(tài)不僅依賴于當(dāng)前輸入值而且與此前的輸 出有關(guān)，還可以從RNN中學(xué)習(xí)字符序列的文法，找出序列演化規(guī)律，抽出確定有限狀態(tài)機形式的規(guī)則21.在傳統(tǒng)的時間序列分析中，已對回歸及其混合模型進行了大量的研究，其建模技術(shù)已相當(dāng)成熟, 作為一種全局模型，不適于處理子序列.隱Markov模型具有堅實的基礎(chǔ)，但可伸縮性差.圖模型具有廣泛 的適用性，能靈活地處理序列的全局和局部問題.圖模型還可以與神經(jīng)網(wǎng)絡(luò)以相互補充的方式來使用，如引入隱含 變量減少圖結(jié)構(gòu)的復(fù)雜性.對于文法模型和RNN,由于其復(fù)雜性，其中僅有少數(shù)可用于時間序列的預(yù)測.3.3 其他方法如前所述,基于三角不等式的索引結(jié)構(gòu)可能產(chǎn)生漏報.后綴樹存儲序列的所有

31、后綴，而僅保存 一次相同前綴，通過深度優(yōu)先的遍歷就可取到每個后綴.作為索引的替代方法，后綴樹不涉及距離函數(shù)，可 實現(xiàn)子序列的精確匹配36，但對如何實現(xiàn)最優(yōu)離散化缺乏系統(tǒng)的策略，且龐大的后綴樹易導(dǎo)致全序列匹配的性能問題. 用分段線性模型擬合曲線是經(jīng)典的數(shù)學(xué)方法.分段線性表示是在最小二乘方誤差8的限制下, 循環(huán)合并相鄰的線性分段而得到的，各線段可增加重要性權(quán)重37.在分段線性表示后，可建立基于散列法的搜索機制.其基本方法38是:讓一個等距模板格窗沿序列滑動取得各個子序列的二進制位模式串(Hash關(guān)鍵字),其中, 每位的1對應(yīng)于相應(yīng)模板格中的上升線段,0對應(yīng)相應(yīng)模板格中的不上升線段.相似搜索算法通過

32、全箱修 剪、箱排序和箱內(nèi)修剪技術(shù)快速定位相似子序列，但可能導(dǎo)致漏報;通過將線性分段信息保存在L-index文件中, 并定義一種樂觀邊界距離度量，可以實現(xiàn)無漏報搜索,并可以處理任意長度的子序列匹配39.通常認(rèn)為，取不連接的線性分段比較有利，這樣可以實現(xiàn)下邊界的Euclidean逼近.另外,Povinelli等人40提出使用時間延遲嵌入方式將時間序列映射到重構(gòu)相空間，即X-RQ.在此，時間序列X=xt,t=1,.,N,RQ中的點xt=(xt-(Q-1)Tx,.,zt-2r,xt-T,xt)T,t是時間延遲,t *(Q-1)t+1,N+,t是整數(shù).已經(jīng)證明，若Q足夠大，則相空間與生成時間序列的狀態(tài)空

33、間同胚.很少有文獻涉及交易序列的表示.有關(guān)的表示方法41是:將交易項集對應(yīng)字母表的某個符號串，這樣，有序交易項集就轉(zhuǎn)換成字符序列.為了實現(xiàn)數(shù)據(jù)壓縮，可將相同滑動窗口內(nèi)的交易當(dāng)作一次交易42.可以采用頻繁模式樹43來保存項集關(guān)聯(lián)關(guān)系，這適用于在序列上尋找公共事件和顯著的關(guān)聯(lián)規(guī)則，但不適合分類.大后綴樹的問題在大量數(shù)據(jù)的挖掘中必須予以特別處理.分段線性方法直觀、高比率壓縮、 噪聲不敏感，可使用多種距離度量，但目前還是不可索引的表示方法.不同于上述必須預(yù)先假定序列形狀的 方法，重構(gòu)相空間方式使用優(yōu)化方法搜索最優(yōu)的時態(tài)模式，但在序列表示時，確定合適的Q是一個難題.由于交 易項目的稀疏性和不可比性，如何

34、更有效地表示交易序列仍是值得探索的問題.4 挖掘操作4.1時態(tài)關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)典型地，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的對象是交易序列,目標(biāo)是從交易數(shù)據(jù)集（如超市的購物記錄）中找出相 似的交易關(guān)聯(lián)規(guī)則.傳統(tǒng)的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)不考慮時態(tài)關(guān)系，附加時態(tài)特征的時態(tài)關(guān)聯(lián)規(guī)則可以更好地描述 客觀規(guī)律.一種基于點和間隔時間模型的時態(tài)關(guān)聯(lián)規(guī)則學(xué)習(xí)過程是44:生成初始關(guān)聯(lián)規(guī)則（時態(tài)無關(guān)）;剪裁規(guī)則，生成關(guān)聯(lián)候選集;計算支持度;建立時態(tài)關(guān)聯(lián)規(guī)則.在關(guān)聯(lián)規(guī)則與時間間隔的約束關(guān)系 中，發(fā)現(xiàn)規(guī)則有效周期是重要的，已相應(yīng)地提出發(fā)現(xiàn)規(guī)則持續(xù)有效時間和周期性的算法45.進一步的研究發(fā)現(xiàn):交易項本身也有周期;引入項壽命（第一次與最后一次交易的期間）概

35、念后，可將交易計數(shù)范圍限于項壽命期間46.交易序列的關(guān)聯(lián)規(guī)則常常帶有規(guī)律性的循環(huán),如季節(jié)性的購物高峰.一個循環(huán)規(guī)則是在一定時 間間隔內(nèi)周期性出現(xiàn)的規(guī)則.文獻47提出了兩種循環(huán)關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法:一種是先用Apriori類算法產(chǎn) 生傳統(tǒng)關(guān)聯(lián)規(guī)則，再找出規(guī)則中蘊含的循環(huán)關(guān)系;另一種是先找出循環(huán)的大項集再生成關(guān)聯(lián)關(guān)系.后者更為有效. 實際上，從不同的潘定等:時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)249換為另一個序列所需操作的代價之和.對于由時態(tài)數(shù)據(jù)建立的模型比較,可以通過比較對應(yīng)模型及其參數(shù)來確定兩序列的相似性，如 參數(shù)的Euclidean距離度量，也可以按數(shù)據(jù)匹配模型的程度來確定序列的相似性.對于確定模型（圖

36、模 型、確定文法等)，相似度量是離散的，匹配結(jié)果確定;對于隨機模型(Markov鏈、隨機文法等)，匹配結(jié)果通常是序 列由模型生成的概率.文獻10 介紹一種基于概率模型的相似距離度量，其基本思想是:觀測值是由原型模板按 照一個先驗概率分布“變形”后生成的;距離模型由局部特征組合成全局形狀序列，局部特征可能存在變形, 其程度由先驗概率分布來決定.對于時間序列,Euclidean距離的簡單性使其成為最流行的距離度量，且對各種數(shù)據(jù)類型有很好的適用性.DTW距離能夠克服Euclidean距離在時間軸的弱點，但有O(n2)的時間復(fù)雜性且會產(chǎn)生漏報.DLB的提出避免了 DTW的這兩個問題(時間復(fù)雜性為O(n

37、),但它要求比較的序列是等長的，還存在彎曲路徑的 限制.對于事件序列,其整體相似性由序列的每個對應(yīng)位置的事件相似性決定.模型的相似性則取決于模型參數(shù) 的匹配.3序列表示和搜索面對海量數(shù)據(jù)，直接去操作一個高維的數(shù)據(jù)空間是很困難的.一個具有n個點的序列可以看 成是n維空間的點，若直接用SAM(spatial access method)多維索引結(jié)構(gòu)(如R*樹)來索引這種n維點，則容 易導(dǎo)致維度災(zāi)難.因此，需要研究合適的數(shù)據(jù)表示形式，進行維度約簡,在高效、方便的表示形式上進行有效的挖掘.衡量維度約簡效果的重要標(biāo)準(zhǔn)之一是要滿足“無漏報”原則11，要求數(shù)據(jù)表示滿足以下條件(下邊界引理)：DF(q,s)W

38、D(q,s) (4)即約簡后的距離應(yīng)不大于原先的距離.其中:q是查詢序列;s是數(shù)據(jù)集中的任意序列;DF是約簡空間中的兩序列距離;D是真實的兩序列距離.數(shù)據(jù)表示形式可分為基于變換、基于模型和其他方法.搜索方法與數(shù)據(jù)表示形式密切相關(guān).幾 種主要技術(shù)，如離散傅立葉變換、小波變換和奇異值分解等是精確的方法.為提高相似匹配效率，也有學(xué)者 提倡使用近似的方法，可采用有損耗的數(shù)據(jù)壓縮模式，如分段線性方法、序列離散化、字符串匹配方法等.3.1 基于變換的方法基于變換的方法將時間序列從時間域映射到另一個特征空間，用特征空間的映像點表示原始 序列,從而實現(xiàn)維度約簡，并用多維索引結(jié)構(gòu)存儲映像點.另一方面，也可以將時

39、間序列轉(zhuǎn)換成離散的字符 序列.Agrawal 等人12使用離散傅立葉變換(discrete Fourier transform,簡稱DFT)將時間序列從時域空間變換到頻域空間.根據(jù)Parseval定理,在頻域空間中,DFT保持原序列的Euclidian距離，即滿足下邊 界引理.可取頻域的前k個系數(shù)形成一個k維點來表示原序列,相似度量就是k維點的Euclidian距離,并建立 索引.DFT匹配序列必須等長、系數(shù)相同，且僅對全序列匹配有效.為了解決子序列匹配的問題,Faloutsos等人11提出設(shè)定滑動窗口，對窗口內(nèi)的子序列進行DFT后形成k維特征點軌跡,并對軌跡按照MBR(minimumboun

40、ding rectangle)來劃分，建立相應(yīng)索引.這種方法形成基于變換的GENMINI(generic multimedia indexing)通用框架，其 主要步驟是:建立距離度量;維度約簡后適用于SAM;產(chǎn)生特征空間的距離度量，證明滿足下邊界引理.DFT作為經(jīng)典的信號變換方法,全局性能良好，但丟失了時間局部化的重要特征.離散小波變 換(discretewavelet transform,簡稱DWT)作為一種較新的線性變換技術(shù)，利用變換后生成的少數(shù)小波參 數(shù)近似模擬原始信號.其小波參數(shù)具有時間/頻率特性，可以保持比DFT還要多的信息，滿足多分辨率的表示需 求.文獻12首次提出用DWT代替D

41、FT對時間序列進行約簡，并證明了 Harr小波變換保持Euclidian距離且 滿足下邊界引理，但未考慮小波的多尺度性.還可以使用全特征小波變換方式將一般小波變換應(yīng)用于時間序列13，實驗顯示，許多小波的性能優(yōu)于DFT和Harr小波，且一般小波變換表示也滿足下邊界引理但還有待數(shù)學(xué)證明.奇異值分解(singular value decomposition,稱SVD)可應(yīng)用于壓縮時間序列14，即已知一組n維點,將其投影到k維子空間(kn),變換使得在投影維上的方差最大化.SVD類似于主成分分析(prime component analysis,簡稱PCA),其主要弱點是計算開銷大，隨著數(shù)據(jù)的增量加入

42、，索引性能將產(chǎn)生退化,需要周期性地 重組索引結(jié)構(gòu).252 Journal of Software 軟件學(xué)報 Vol.18, No.2, February 2007時間間隔可以發(fā)現(xiàn)不同的關(guān)聯(lián)規(guī)則.為了改進循環(huán)規(guī)則的表達能力，可以使用日歷代數(shù)表達時態(tài)現(xiàn)象，算法基于用戶定制的日歷模式搜索近似的關(guān)聯(lián)規(guī)則48.更一般的情況是，使用日歷圖式作為框架（類型）發(fā)現(xiàn)時態(tài)模式（具體實例），相應(yīng)的搜索算法使用時態(tài)aprioriGen和水平修剪兩種優(yōu)化技術(shù) 49對于時間序列的規(guī)則發(fā)現(xiàn)問題，可以通過離散化變換成事件序列形式，再用序列模式挖掘方法 導(dǎo)出時態(tài)關(guān)聯(lián)規(guī)則ABT，其中,T是A,B事件的時間間隔約束19.先找出關(guān)聯(lián)

43、規(guī)則再尋找時態(tài)關(guān)系的方法效果顯然有限;直接尋找時態(tài)關(guān)聯(lián)規(guī)則的方法難度較 大.可以先分時間段找出關(guān)聯(lián)規(guī)則，再由各分段的距離推出其規(guī)則的時態(tài)關(guān)系,但如何分段是與領(lǐng)域知識相 關(guān)的.關(guān)鍵問題之一是時間粒度問題，在不同的時間粒度下可能獲得不同的規(guī)則以及規(guī)則集的結(jié)構(gòu)關(guān)系.4.2 序列模式的發(fā)現(xiàn)如果考慮發(fā)生交易的先后順序，傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘可以擴充為序列模式挖掘41.對于超市顧客的交易序列，一個顧客的所有交易按其發(fā)生時間的先后排列成一個交易序列，每個交易對應(yīng)一個項目集.序 列的支持度定義為支持該序列的顧客數(shù)與總顧客數(shù)之比.序列模式發(fā)現(xiàn)的目標(biāo)就是找出所有頻繁模式.序列模 式挖掘算法可分為3類50:基于 Apri

44、ori 的水平格式方法，如 GSP（generalized sequential patterns）算法;基于 Apriori 的垂直格式方法，如 SPADE（sequential pattern discovery using equivalence classes）算法;基于投影的模式生長方法，如PrefixSpan算法.Apriori類方法基于反單調(diào)特性,使用逐步生成-測試候選集、廣度優(yōu)先搜 索策略;模式生長方法不產(chǎn)生候選集,而是利用頻繁模式樹（FP-樹）存儲壓縮的頻繁關(guān)鍵信息,將頻繁模式挖掘問題 轉(zhuǎn)換成FP-樹挖掘問題，并可使用廣度優(yōu)先或深度優(yōu)先搜索策略.Agrawal 等人41基于A

45、priori思路,在滿足最小支持度的序列中發(fā)現(xiàn)最長序列.最長的頻繁序列代表一個序列模式，滿足最小支持度的序列稱為大序列.AprioriAll算法41對所有候選序列計數(shù)，然后修剪非最大序歹列.AprioriSome 和 DynamicSome 算法41只關(guān)注最大序列，采用先計算更長序列計數(shù)的方法，試圖避免對那些包含在更長序列中的大序列計數(shù).改進的GSP算法42減少每次生成的候選數(shù)，利用時間約束減少搜索空間.Mannila 等人31將關(guān)聯(lián)規(guī)則發(fā)現(xiàn)應(yīng)用到事件序列上，提出片段的定義以及從事件序列中發(fā)現(xiàn)頻繁片段的 WINEPI,MINEPI搜索算法.片段是限于一個時間窗口內(nèi)事件的偏序集，其是否頻繁取決于

46、片段 出現(xiàn)的窗口數(shù)與序列總窗口數(shù)之比.進一步考察事件序列的全局偏序關(guān)系32，如果將事件發(fā)生歸于某個模型，則可使用混合建模技術(shù)獲得偏序的描述，得到全局事件數(shù)據(jù)視圖.頻繁片段本質(zhì)上是一個單項目交易序列的頻繁 序列.多數(shù)算法每增加一個頻繁序列長度就需要掃描全數(shù)據(jù)庫，而抽樣又可能因數(shù)據(jù)偏斜使結(jié)果敏感.SPADE 算法51將挖掘頻繁序列問題按格子理論分解為若干子格子，只需3次掃描數(shù)據(jù)庫，就可以分別獨立地在內(nèi)存中 使用格子搜索技術(shù)和簡單連接操作解決頻繁模式搜索問題.MOWCATL(minimal occurrences with constraints and time lags)方法52從序列中找出周期

47、性片段的事件相關(guān)模式并應(yīng)用于預(yù)測其他序列的類似事件.Apriori類算法的性能瓶頸主要是生成大量候選集和多次掃描數(shù)據(jù)庫，作為前綴樹的擴充,FP- 樹方法為解決頻繁模式挖掘問題提供了另一類解決途徑.基于FP-樹的挖掘方法先后主要有3種技 術(shù):FreeSpan方法53將頻繁項目集循環(huán)投影到較小的投影數(shù)據(jù)庫集并在每個投影數(shù)據(jù)庫中生長子序列片，每次測試被 限制在投影數(shù)據(jù)庫內(nèi).其缺點是投影必須保存整個序列，子序列的生長需探測候選序列的所有分裂 點;PrefixSpan 方法54只檢查前綴子序列,僅將它們對應(yīng)的后綴子序列投影到投影數(shù)據(jù)庫中，而且將一個基于內(nèi)存的偽投影 技術(shù)用于加速投影操作.在每個投影數(shù)據(jù)庫

48、，序列模式的生長僅限于局部頻繁模式;gSpan方法50在一個過程中結(jié)合了圖模式生長和頻繁計數(shù)，形成了有效的結(jié)構(gòu)模式挖掘算法.對于事件序列和交易序列，由于隨時間變化的屬性值無法簡單比較，因而難以縮小搜索空間. 為了提高模式發(fā)現(xiàn)的有效性和效率,除了利用其統(tǒng)計特性以外,還應(yīng)使用約束條件.SPIRIT(sequential pattern mining withregular expression constraints)算法55基于Apriori框架，使用正則表達式表達約束，使用戶的需求能合并到挖掘過程中.正則表達式提供了簡單、自然的描述方法，更強大的上下文無關(guān)文法也已應(yīng)用于描述 約束56.在模式生

49、長方法的框架中，基于前綴單調(diào)特性，可以有效地融合約束與搜索方法，其效率和可伸縮性適 合于挖掘大數(shù)潘定等:時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)255Cheung首先考慮了關(guān)聯(lián)規(guī)則的更新問題66.對于序列模式的增量挖掘，應(yīng)考慮時間戳和序列變化，因而比關(guān)聯(lián)規(guī)則的維護問題復(fù)雜得多.為了找出增量后數(shù)據(jù)集的所有序列模式，必須確定DB中的 非頻繁模式，在DB U db中是否已變成頻繁的.同時,必須檢查原有頻繁序列是否由于增量而變成非頻繁的.ISM(incrementalsequence mining )算法67利用SPADE算法51建立增量序列格，使用垂直數(shù)據(jù)存儲方式，保存維護“最大頻繁”和“最小非頻繁”序列信息.

50、ISE(incremental sequence extraction)算法68通過重用以前頻繁序列的支持度信息來降低計算頻繁序列的開銷.IncSpan算法69引入“近似頻繁”序列集、逆向匹配和共享投影等新思路進行增量挖掘.挖掘結(jié)果的規(guī)則常帶有若干參數(shù)(如支持度),多次挖掘后即構(gòu)成規(guī)則參數(shù)序列.高階挖掘(higher ordermining)70試圖從規(guī)則參數(shù)序列中發(fā)現(xiàn)有趣的、更易于理解的高層次語義規(guī)則，即高階規(guī)則.高階規(guī)則發(fā)現(xiàn)需要至少對各原數(shù)據(jù)集執(zhí)行一次一階規(guī)則歸納，可按分布方式進行，因而適合于海量挖掘.從規(guī)則 參數(shù)序列中也可發(fā)現(xiàn)規(guī)則結(jié)構(gòu)的變化，如規(guī)則中前件變量的增加.文獻70研究了對增量數(shù)

51、據(jù)集合的高階規(guī)則建 模和挖掘問題，提出高階規(guī)則的一般建模方法以及獲得新知識的框架.在這個框架中,可以集成現(xiàn)有的規(guī)則進化、 增量挖掘等技術(shù).文獻71基于一階時態(tài)邏輯給出時間序列挖掘的形式化定義以及歸納高階規(guī)則的方法 現(xiàn)有的序列模式增量算法大多存在保存的頻繁和非頻繁信息數(shù)量龐大、容易導(dǎo)致內(nèi)存溢出、 需要多次掃描數(shù)據(jù)庫等問題.高階數(shù)據(jù)挖掘?qū)嶋H上采用了分段挖掘的思路，但對分段挖掘后如何合并獲得 整體規(guī)則尚待研究.另外，規(guī)則結(jié)構(gòu)的演化規(guī)律、規(guī)則的泛化或特化關(guān)系等都是值得深入研究的問題目前，還很 少有對時態(tài)數(shù)據(jù)挖掘的形式化研究,Cotofrei等人71也僅對時間序列規(guī)則給出部分形式化定義且其形式化工作是基

52、于特殊的時序離散化方法，缺少一般性.對于高階數(shù)據(jù)挖掘和時態(tài)數(shù)據(jù)挖掘的形式化問題，我們將另文 加以討論.5 總結(jié)與發(fā)展方向近幾年來，雖然TDM取得了長足進步,但也存在著不足之處.Keogh等人72從340篇已發(fā)表的論文中選擇了最常引用的56篇，并用各行業(yè)（涉及金融、醫(yī)學(xué)、生物、化學(xué)、網(wǎng)絡(luò)等的50種時間序列 數(shù)據(jù)集進行測試后發(fā)現(xiàn):對多數(shù)已發(fā)布的改進算法，若改變少許實現(xiàn)細節(jié)或用多種多樣的實際數(shù)據(jù)集進行測試， 則會發(fā)現(xiàn)其性能明顯下降，所以，這些改進算法只是對某些特定數(shù)據(jù)集和某種實現(xiàn)方式是有效的，而缺少解決現(xiàn) 實數(shù)據(jù)問題的普遍有效性.Keogh等人的工作說明了定量比較多種算法的難度也表明該領(lǐng)域還擁有廣闊

53、的研究 空間.開發(fā)更健壯、更高效和更準(zhǔn)確的時態(tài)數(shù)據(jù)相似性發(fā)現(xiàn)算法是學(xué)術(shù)界面臨的主要挑戰(zhàn)TDM的相似性發(fā)現(xiàn)技術(shù)關(guān)注現(xiàn)實數(shù)據(jù)的發(fā)展變化，試圖從時態(tài)數(shù)據(jù)中發(fā)現(xiàn)事物動態(tài)演化的 相似性規(guī)律.由于時態(tài)數(shù)據(jù)的獨特結(jié)構(gòu)，傳統(tǒng)技術(shù)難以對其進行有效處理，亟需研究新的方法加以解決.對于 時間序列,通過維度約簡等方法變換其表示形式，實現(xiàn)各種相似性發(fā)現(xiàn)任務(wù).對于事件序列和交易序列，其表示 方法較為簡單、直接，需要利用序列的統(tǒng)計特性和約束條件來縮小搜索空間，實現(xiàn)規(guī)則發(fā)現(xiàn)和聚類.時態(tài)數(shù)據(jù)的 增量挖掘與高階挖掘則主要處理規(guī)則維護和規(guī)則變化規(guī)律的發(fā)現(xiàn).我們認(rèn)為，以下幾個方面是未來相似性發(fā)現(xiàn)技術(shù)研究發(fā)展的方向：序列分類方法，應(yīng)研

54、究能 夠克服高特征相關(guān)和噪音的特征提取方法;多維序列的發(fā)現(xiàn)技術(shù)，需要提出一套新理論,能夠有效地對 序列多種屬性值相關(guān)性進行統(tǒng)一建模;將先驗知識、用戶反饋與計算智能方法相結(jié)合以縮小搜索空間，提高 算法效率和規(guī)則有趣性;深入研究增量挖掘和高階挖掘，包括不同粒度數(shù)據(jù)集的規(guī)則變化、已發(fā)現(xiàn)規(guī)則的時 態(tài)特性、規(guī)則結(jié)構(gòu)的演化等;相似性發(fā)現(xiàn)技術(shù)的應(yīng)用,增強算法的實用性和健壯性，將現(xiàn)有成果向應(yīng)用領(lǐng)域 推廣.References:Agrawal R, Faloutsos C, Swami A. Efficient similarity search in sequence databases. In: David

55、 BL, ed. Proc. of the 4th Intl Conf.on Foundations of Data Organization and Algorithms, FODO93. Chicago: Springer -Verlag, 1993. 69-84.Zeng HQ. Research on mining and similarity searching in time series database Ph.D. Thesis. Shanghai: Fudan University, 2003(in Chinese with English abstract).Roddick

56、 J, Spiliopoulou M. A survey of temporal knowledge discovery paradigms and methods. IEEE Trans. on Knowledge andData Engineering, 2002,14(4) :750-768.Keogh EJ, Pazzani MJ. Scaling up dynamic timewarping to massivedataset. In: Zytkow JM, Rauch J, eds. Proc. of the 3rd潘定等:時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)253據(jù)集57.對于時間序列，

57、通常先將連續(xù)值序列變換成有趣形狀或模板序列,即轉(zhuǎn)成事件序列后再進行序 列模式的發(fā)現(xiàn).文獻40基于重構(gòu)相空間的思想，提出了從時間序列中發(fā)現(xiàn)具有特征化和預(yù)測功能的有趣 模式的算法.該算法將空間重構(gòu)法與模式發(fā)現(xiàn)思想相結(jié)合，利用遺傳算法實現(xiàn)了時間序列的模式聚類與模式提 取，其基本步驟是：序列映射到重構(gòu)相空間;形成擴充相空間;形成聚類,獲得滿足最優(yōu)目標(biāo)函數(shù)的類.對于交易項目為布爾值的交易序列,其搜索空間為(2A)P，其中,A是交易項目集,P是最大序列長度.因而，尋找序列模式的搜索空間是巨大的.Apriori類算法的時間復(fù)雜性較高，模式生長方法試圖用頻 繁模式樹降低搜索空間,但會大量占用存儲,增加內(nèi)外存交

58、換開銷.利用格子理論的搜索空間分區(qū)方法，可以有效 分解問題,并使用并行算法提高搜索效率，但生成垂直格式數(shù)據(jù)需要相應(yīng)的開銷.對于搜索的約束條件,使用分 類法(taxonomies)也是一種有效的方法.作為分層的領(lǐng)域知識,分類法可以有效地消除冗余規(guī)則,還支持多層次 的模式發(fā)現(xiàn).傳統(tǒng)的支持-置信度框架容易導(dǎo)致組合爆炸，但目前尚未出現(xiàn)公認(rèn)、通用的度量值.4.3 分類在模式識別、機器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域中，對分類問題的研究一直很活躍，但時態(tài)數(shù)據(jù)的獨 特結(jié)構(gòu)使得許多經(jīng)典算法難以發(fā)揮作用.對序列的分類研究相對較少.時間序列的分類研究的典型特征是:用離散技術(shù)變換搜索空間;注重規(guī)則的可解釋性; 按絕對時間獲取規(guī)

59、則.多數(shù)基于時域的分類方法都假定存在一些簡單的序列基本形狀或模板它們是事 先給定或能從數(shù)據(jù)中學(xué)習(xí)到的.對于以分段線性表示的時間序列，可以通過合并算子獲得兩個原始輸入時間序列的折衷序列.這種基于合并算子的分類方法37對某個類中的正例迭代合并，建立一般模型，并使用影響因子來控制合并算子，正影響因子意味著對輸入序列的泛化;也可以使用負(fù)例來關(guān)注形狀差異，負(fù)影響因子有助于加大 正負(fù)形狀的差異.另一種用決策樹組合局部模式的方法58，可以獲得較好的可解釋分類結(jié)果.它用分段常數(shù)逼近16約簡候選模式的搜索空間，使用回歸樹遞歸離散化序列,獲得有判決力的局部模式后可構(gòu)造出二分類規(guī)則，最后由決策樹組合規(guī)則形成分類能力

60、.對于以模型表示的時間序列，因為容易獲得序列是否屬于某個模型生成的, 所以，確定或隨機模型可以直接用于獲得時間序列分類.基于重構(gòu)相空間的方法來源于對動態(tài)系統(tǒng)和混沌理論的研究有堅實的理論基礎(chǔ)，避免了序列 基本形狀的假設(shè).這種新的分類方法59將時間序列置于重構(gòu)相空間中，用全協(xié)方差高斯混合模型(Gaussian mixture model,簡稱GMM)對其直接建模,EM (expectation maximization)算法估計GMM參數(shù).其基本過程是:數(shù)據(jù)分析；每個序列類學(xué)習(xí)GMM概率分布;分類序列，使用Bayesian最大似然分類器.在事件序列的分類研究中,FeatureMine算法60運用序