王曉曄，肖迎元，張德干

(1.天津理工大學(xué)智能計(jì)算及軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津300191;2.天津理工大學(xué)計(jì)算機(jī)視覺與系統(tǒng)省部共建教育部重點(diǎn)實(shí)驗(yàn)室，天津300191)

時(shí)間序列部分周期模式的挖掘是一類重要的數(shù)據(jù)挖掘任務(wù)，在許多場合都有重要的應(yīng)用，如電力負(fù)荷時(shí)序數(shù)據(jù)的高峰期往往具有部分周期性，發(fā)現(xiàn)這種周期就可以避開高峰用電，減輕電廠的負(fù)擔(dān).

對于時(shí)間序列數(shù)據(jù)挖掘的研究主要集中在相似性問題和時(shí)態(tài)模式挖掘的研究［1-2］.其中相似性問題研究主要是面向查詢的需要［3-4］，包括各種相似性搜索算法［1］的研究.時(shí)態(tài)模式挖掘則主要包括各種序列的模式挖掘，進(jìn)行時(shí)態(tài)因果、周期模式、關(guān)聯(lián)規(guī)則和重要事件的預(yù)測［5］等內(nèi)容.

在時(shí)態(tài)模式的挖掘方面，從時(shí)間序列中抽取模式是一個(gè)比較新穎的方向.從研究內(nèi)容來分，目前研究重點(diǎn)主要集中在2個(gè)方面:對時(shí)序中的事件出現(xiàn)加以模式發(fā)現(xiàn)和預(yù)測，如時(shí)態(tài)因果和關(guān)聯(lián)規(guī)則;挖掘時(shí)序數(shù)據(jù)的周期模式，包括全周期模式和部分周期模式.部分周期模式的研究大多采用了Apriori-like啟發(fā)式挖掘算法的思想和理論.

由于Apriori-like不能發(fā)現(xiàn)不同周期之間的模式和計(jì)算復(fù)雜度過大等，文獻(xiàn)［6］提出了一種對單周期和多周期都適用的部分周期模式挖掘算法:最大子模式迎合樹算法(the max-subpattern hit set tree，Mht).但是該算法只能對現(xiàn)有時(shí)間序列數(shù)據(jù)庫進(jìn)行挖掘，不能進(jìn)行在線部分周期模式的挖掘.文獻(xiàn)［7］在此基礎(chǔ)上提出了一種增量式的在線挖掘算法，可以根據(jù)新增的數(shù)據(jù)對最大子模式樹進(jìn)行調(diào)整，但是由于數(shù)據(jù)量會越來越大，因此總的計(jì)算量還是很大的.

文中提出了一種帶移動窗的部分周期模式挖掘算法，由于在某些應(yīng)用場合數(shù)據(jù)的分布特性會隨著時(shí)間的變化而有所變化，所以從較早的數(shù)據(jù)中提取的模式已經(jīng)不能反映現(xiàn)有數(shù)據(jù)所隱含的模式.因此只要求對近期的時(shí)間序列數(shù)據(jù)進(jìn)行挖掘，每次挖掘過程都是在最近的時(shí)間窗口［8］中進(jìn)行，所挖掘的模式反映了最新的數(shù)據(jù)集中的知識.本算法對最新窗口中的數(shù)據(jù)搜索次數(shù)不多于2次，因此計(jì)算量要大大降低，非常適用于大型時(shí)間序列數(shù)據(jù)庫的挖掘.

1 時(shí)間序列的部分周期模式

1.1 問題定義

假設(shè)一個(gè)含有n個(gè)時(shí)間標(biāo)記的特征序列，對于每個(gè)時(shí)刻i，Di為該時(shí)刻的特征值(由原始時(shí)間序列導(dǎo)出)，特征序列的所有特征集定義為L，因此特征時(shí)間序列可以表示為

例如對于某支股票的原始時(shí)間序列，是以天為單位記錄該股票的收盤價(jià)，則每個(gè)時(shí)間點(diǎn)的數(shù)據(jù)為具體的數(shù)值，因此需要將其量化為某些特征值(如高、中、低等)，然后用一系列字母來表示，則量化所得特征集 L 可以表示為{a，b，c，…}.

定義1 模式是一個(gè)非空序列s=s1，s2，…，sp，長度p叫做模式的周期，對于?i，si是一個(gè)特征集(若該特征集只包含一個(gè)字母，則省略集合符號，如{a}可以寫成a，具有j維特征的模式也可以叫做j-模式，在模式中允許符號“*”出現(xiàn)，它表示可以與任意單個(gè)字母相匹配.

定義2 如果模式s'=s1'，s2'…，sp'與s具有相同的長度，且對于?i，si'?si，則稱模式 s'為模式 s的子模式.

如對于模式 a{b，c}*{a，c}f，第 2 個(gè)位置可以是b或c，它是一個(gè)長度為5的模式，即周期為5，而模式中含有4個(gè)字母，因此又叫做4-模式.顯然模式ac*cf和a＊＊cf是模式a{b，c}*{a，c}f的子模式，而模式ab*ac不是它的子模式.由定義可知，任意模式的特征維數(shù)要大于或等于它的子模式的特征維數(shù).

定義3 一個(gè)特征時(shí)間序列S形式如式(1)所示，可以被分割成長度相等(長度為p)相互獨(dú)立的模式，則 S=S1，S2，…，Si，…，其中 Si=Dip+1，…，Dip+p，i=0，…，［n/p］-1，則每個(gè)模式 Si叫做一個(gè)周期段，其周期為p.

如果一個(gè)周期段Si是模式s的子模式，則稱周期段Si與模式s相匹配.

定義4 一個(gè)模式s在某個(gè)特征時(shí)間序列中的頻率值是指這個(gè)時(shí)間序列中與模式相匹配的周期段的個(gè)數(shù)，記作frequency_count(s).顯然若時(shí)間序列有m個(gè)周期段，則頻率值應(yīng)小于m，在極端情況下(所有周期段都與該模式匹配)等于m.

定義5 一個(gè)模式s在某個(gè)特征時(shí)間序列中的置信度是指它在該模式中的頻率值與周期段數(shù)m的比值，記作confidence(s).則

定義6 如果一個(gè)模式在特征時(shí)間序列中的置信度不小于某個(gè)閾值(該閾值記作min_conf)，則稱這個(gè)模式是頻繁部分周期模式，j維頻繁部分周期模式集簡稱為j-頻繁模式集，記作Fj.

1.2 部分周期模式挖掘

部分周期模式挖掘算法基于文獻(xiàn)［6］中提出的最大子模式迎合樹算法(Mht).算法中通過掃描特征時(shí)間序列構(gòu)建了一個(gè)叫做最大子模式的樹T(如圖1所示)，樹上的節(jié)點(diǎn)代表了時(shí)間序列的所有候選頻繁模式.子節(jié)點(diǎn)是父節(jié)點(diǎn)的子模式，由子模式的定義知，子節(jié)點(diǎn)的特征維數(shù)要小于父節(jié)點(diǎn)的特征維數(shù).因此當(dāng)將父節(jié)點(diǎn)的某個(gè)字母用*代替時(shí)，將形成子節(jié)點(diǎn)，由圖中可知子節(jié)點(diǎn)和父節(jié)點(diǎn)之間的連接用被取代的字母所標(biāo)識.構(gòu)建最大子模式樹的關(guān)鍵是產(chǎn)生根節(jié)點(diǎn)，它在所有候選頻繁模式中特征維數(shù)最大，因此叫做最大模式Cmax.Cmax由1-頻繁模式集F1的所有元素合并而產(chǎn)生.2個(gè)模式s和t的合并操作定義為(s∪t)i=si∪ti.如模式 a*bc*與模式bc*r*合并的結(jié)果為模式{a，b}cb{c，r}*，若F1={a＊＊，*b* ，*c* ，＊＊d}，則 Cmax=a{b，c}d.

樹的子節(jié)點(diǎn)的生長是將Cmax與時(shí)間序列中的周期段進(jìn)行求交集時(shí)所產(chǎn)生的迎合(hit)的過程.迎合是指 Cmax與周期段的交集，如果 Cmax=a{b，c}d，Si=aba，則他們的迎合為ab*，若樹中沒有此節(jié)點(diǎn)，則在其相應(yīng)的父節(jié)點(diǎn)下面增加該節(jié)點(diǎn)，此節(jié)點(diǎn)與父節(jié)點(diǎn)之間的連接用它與父節(jié)點(diǎn)相匹配所錯(cuò)失的字符來標(biāo)識，并將此節(jié)點(diǎn)的迎合值置為1，若此節(jié)點(diǎn)已經(jīng)存在，則將它的迎合值加1，圖1中迎合值標(biāo)注在該節(jié)點(diǎn)的旁邊，是該節(jié)點(diǎn)所代表的模式的迎合次數(shù)值(簡稱迎合值).很顯然，某個(gè)節(jié)點(diǎn)的迎合值并不是它的頻率值，因?yàn)樵谒乃须[含祖先節(jié)點(diǎn)中都包含有該節(jié)點(diǎn)所代表的模式(如圖1中虛線所連接的都是隱含的父子節(jié)點(diǎn)關(guān)系)，如模式*bd的直接父節(jié)點(diǎn)是*{b，c}d，隱含父節(jié)點(diǎn)是 adb，祖先節(jié)點(diǎn)是a{b，c}d，當(dāng)然隱含父節(jié)點(diǎn)往往不止1個(gè)，因此求取模式*bd的頻率值需要加入它的所有祖先節(jié)點(diǎn)的迎合值(即10+0+12+20).樹中的節(jié)點(diǎn)構(gòu)成了候選頻繁模式集，當(dāng)某個(gè)節(jié)點(diǎn)的頻率值大于min_conf×m時(shí)，則認(rèn)為該節(jié)點(diǎn)所代表的模式是頻繁模式.

圖1 最大模式樹舉例Fig.1 Example of max pattern tree

Mht算法的實(shí)現(xiàn)步驟如下:

1)給定周期p，將特征時(shí)間序列S分割成長度為p的一系列周期段S1，S2，…，Sm，m為周期段的段數(shù).

2)掃描所有的周期段，得到所有的1-模式集L1及每個(gè)模式的頻率值，將頻率值不小于min_conf×m的1-模式抽取出來組成1-頻繁模式集F1.

3)將F1的所有元素合并，產(chǎn)生Cmax.

4)重新掃描所有周期段，求取周期段與Cmax的交集，若所得到的模式已經(jīng)存在，則將節(jié)點(diǎn)的迎合值加1，否則在相應(yīng)的父節(jié)點(diǎn)下插入新的節(jié)點(diǎn)(若它的祖先節(jié)點(diǎn)不存在，則插入祖先節(jié)點(diǎn)，并將祖先節(jié)點(diǎn)的迎合值置0)，將新節(jié)點(diǎn)的迎合值置1.樹的葉節(jié)點(diǎn)應(yīng)該含有2個(gè)非*字母，因?yàn)橐呀?jīng)有1-頻繁模式集僅含有1個(gè)非*字母.

5)將每個(gè)節(jié)點(diǎn)的迎合值與它的所有隱含父節(jié)點(diǎn)的迎合值相加，得到該節(jié)點(diǎn)的頻率值，若某個(gè)模式的頻率值不小于min_conf×m，則該節(jié)點(diǎn)所代表的模式為頻繁模式.

2 帶移動窗的的部分周期模式挖掘算法

某些時(shí)間序列挖掘過程中只要求在近期數(shù)據(jù)庫中進(jìn)行，因此在挖掘過程中引入時(shí)間窗口的概念，時(shí)間窗口［8］是指在某個(gè)時(shí)間區(qū)域之前的時(shí)間序列數(shù)據(jù)都是過時(shí)的，不用于當(dāng)前部分周期模式挖掘過程的，即部分周期模式的挖掘過程只是在當(dāng)前時(shí)間區(qū)域中進(jìn)行，提高了挖掘結(jié)果的時(shí)效性.

令當(dāng)前時(shí)間窗口為Cur_window，起止時(shí)間為Ttart和Tend，SC為當(dāng)前時(shí)間窗口中的特征時(shí)間序列，D為周期段的段數(shù)，F(xiàn)為SC中的頻繁模式集.從時(shí)間Tend到Tnow為時(shí)間序列新增的數(shù)據(jù)，新數(shù)據(jù)集合為sc，d為sc的周期段的段數(shù)，則新時(shí)間窗口 New_window的起止時(shí)間為 Tstart+(Tnow-Tend)和 Tnow.在Tstart和Tstart+(Tnow-Tend)之間的數(shù)據(jù)為老數(shù)據(jù)應(yīng)淘汰，記為retire，周期段數(shù)為 r，則新時(shí)間窗口New_window的時(shí)間序列記為NewSC，NewSC=SC∪sc/retire.模式 X 在 SC、retire、sc和 NewSC中的頻率值記為X.frequencyS、X.frequencyr、X.frequencys和 X.frequencyN.

經(jīng)過時(shí)間序列數(shù)據(jù)庫的更新，在新時(shí)間窗口中的1-模式存在4種情況:

1)1-模式在Cur_window和New_window都是非頻繁的即 X.frequencyS＜min_conf×D，且 X.frequencyN＜min_conf(D+d-r).

2)1-模式在Cur_window和New_window都是頻繁的即 X.frequencyS＞min_conf×D，且 X.frequencyN＞min_conf×(D+d-r).

3)1-模式在Cur_window是頻繁的，而在New_window中是非頻繁的即X.frequencyS＞min_conf×D，但X.frequencyN＜min_conf×(D+d-r).

4)1-模式在 Cur_window是非頻繁的，而在New_window中是頻繁的即 X.frequencyS＜min_conf×D，但X.frequencyN＞min_conf×(D+d-r).

顯然，只需考察3)和4)2種情況即可.

MW算法包括2步:

1)根據(jù)頻繁1-模式集的更新算法對F1集進(jìn)行更新產(chǎn)生F1';

2)由 F1'合并產(chǎn)生的最大模式為 C'max，若C'max=Cmax，則保留原來的樹T，只需更新各節(jié)點(diǎn)的迎合值即可.考慮淘汰的時(shí)間序列retire的周期段，求取與C'max的交集，若所得到的模式存在，則將相應(yīng)節(jié)點(diǎn)的迎合值減1;考慮新增時(shí)間序列sc的所有周期段，求取與C'max的交集，若所得到的模式存在，則將相應(yīng)節(jié)點(diǎn)的迎合值加1;

若C'max≠Cmax，則采用更新算法MTU對最大子模式樹進(jìn)行更新;

下面分別介紹頻繁1-模式集的更新算法和最大子模式的樹的更新算法MTU.

2.1 頻繁1-模式集的更新算法

1)遍歷淘汰數(shù)據(jù)庫retire，計(jì)算所有的模式X∈F1在retire中的頻率值X.frequencyr;遍歷新增數(shù)據(jù)庫sc，計(jì)算所有的模式X∈F1在sc中的頻率值X.frequencys，從而得到F1的所有模式在NewSC中的頻率值，X.frequencyN=X.frequencyS+X.frequencyS-X.frequencyr.若 X.frequencyN＜ min_conf×(D+d-r)，則將其淘汰，否則保留.

2)在遍歷retire和sc的同時(shí)，根據(jù)sc的每一個(gè)周期段構(gòu)造不在F1中的候選1-模式集C1，對C1中的任一模式Y(jié)，若Y.frequencyS＜ min_conf×(d-r)+Y.frequencyr，依據(jù)文獻(xiàn)［7］中的引理2，那么 Y 在更新后序列中就必是非頻繁的，可將其從C1中刪除.

3)對原部分時(shí)間序列SC/retire進(jìn)行遍歷，計(jì)算C1中各個(gè)候選 Y在 SC/retire中的頻率值，加上Y.frequencyS，便得到Y(jié)在更新后時(shí)間序列NewSC中的頻率值Y.frequencyN，若Y.frequencyN不低于min_conf×(D+d-r)，則Y為頻繁模式，從而得到新的頻繁模式集F1'為保留的F1和C1中的頻繁模式的集合.

2.2 最大子模式的樹的更新算法

假設(shè)C'max為更新后的最大模式，顯然C'max由更新后的1-頻繁模式集F1'的所有元素合并而產(chǎn)生.若cj為Cmax第j個(gè)位置特征值符號，cj'為C'max第j個(gè)位置特征值符號，如果cj≠cj'，則cj將被更新為cj'.更新過程分 2 步［7］，即先刪除 cj，形成 Ctmax，然后在相應(yīng)位置增加cj'形成C'max，記錄F1與F1相比較有所更新的1-模式集記為U1.

同樣，相應(yīng)的最大子模式樹的更新過程也分為2步:1)更新是生成樹Tt，它的根節(jié)點(diǎn)是，很顯然是Cmax的子模式，因此，如果在T中有節(jié)點(diǎn)代表了，則這個(gè)節(jié)點(diǎn)變成Tt的根節(jié)點(diǎn)，否則，創(chuàng)造一個(gè)新的節(jié)點(diǎn).考慮圖1的樹，若C'max=a{b，e}d，則=abd，abd以及它的直接后代節(jié)點(diǎn)ab*便是初始的Tt，而此時(shí)樹Tt還不完整，需要加上它所有的非直接的后代節(jié)點(diǎn)，以及相應(yīng)的迎合值，掃描樹T，對于樹T的每一個(gè)節(jié)點(diǎn)，求它與的交集，然后將所得節(jié)點(diǎn)連同其在T中的迎合值插入樹Tt中(若該節(jié)點(diǎn)已存在，則將迎合值累加).則在樹Tt中加入如下模式:abd(10+12)，*bd(0+20)，a*d(50+10)，ab*(8+32).結(jié)果如圖2所示，同時(shí)考慮淘汰的時(shí)間序列retire，只需求取那些不包含 U1中的1-模式的周期段與的交集，若所得到的模式存在，則將相應(yīng)節(jié)點(diǎn)的迎合值減1.

圖2 插入所有后代節(jié)點(diǎn)后的樹TtFig.2 Tree Ttafter inserting all the posterity node

顯然，含有新增字符的子模式的迎合值不能確定.同時(shí)一些其他的新模式或許會出現(xiàn)，如模式aed，因此需要重新搜索時(shí)間序列.對原部分時(shí)間序列SC/retire進(jìn)行遍歷，只需求取那些包含U1中的1-模式的周期段與C'max的交集，若所得到的模式已經(jīng)存在，則將節(jié)點(diǎn)的迎合值加1，否則在相應(yīng)的父節(jié)點(diǎn)下插入新的節(jié)點(diǎn)(若它的祖先節(jié)點(diǎn)不存在，則插入祖先節(jié)點(diǎn)，并將祖先節(jié)點(diǎn)的迎合值置0)，將它的迎合值置1.搜索新增時(shí)間序列sc的所有周期段，將它與Cmax'的交集加入樹T'中，過程如上述.

3 計(jì)算復(fù)雜度分析

本文提出的MW算法，對于長度為D+d的時(shí)間序列，掃描次數(shù)最多為2次.在第1)步中的工作主要是檢查F1中的頻繁模式是否保持頻繁，是在對sc和retire進(jìn)行1次搜索完成的，同時(shí)對sc構(gòu)造出的候選集C1進(jìn)行修剪，搜索Sc/retire，從C1中發(fā)現(xiàn)新的頻繁1-模式.總共在1)對Sc+sc搜索了1次，但是由于算法計(jì)算很簡單，因此計(jì)算量很小.在2)中，若C'max=Cmax，則只需對retire和sc搜索1次，只有在C'max≠Cmax時(shí)，才需要對當(dāng)前時(shí)間窗口Sc和新增窗口sc進(jìn)行搜索，而且對Sc進(jìn)行搜索時(shí)，只是對某些符合條件的周期段進(jìn)行搜索，因此在第2)步中，最壞的情況下搜索1次，關(guān)于最大子模式樹的構(gòu)建中計(jì)算復(fù)雜度分析見文獻(xiàn)［5］.

4 算法測試及結(jié)果分析

在實(shí)驗(yàn)中使用2個(gè)數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)，其中一個(gè)是人工合成數(shù)據(jù)庫，用一個(gè)隨機(jī)時(shí)間序列生成器產(chǎn)生所需的1 000 000個(gè)含有4個(gè)特征值的時(shí)間序列數(shù)據(jù).另一個(gè)是某城市某個(gè)主干道某檢測面的交通流量檢測數(shù)據(jù)，其檢測間隔為5 min，數(shù)據(jù)庫大小為12 M，截取的數(shù)據(jù)片度如圖3所示，其中的連續(xù)數(shù)據(jù)通過行業(yè)專家的經(jīng)驗(yàn)被量化為5個(gè)等級:很小、小，中等、大和很大.

圖3 交通流量數(shù)據(jù)Fig.3 Traffic flow data

實(shí)驗(yàn)中分別將增量長度d和置信度閾值min_conf作了變化，其周期分別定為4和24.算法實(shí)現(xiàn)采用Matlab編程工具，運(yùn)行機(jī)型為賽揚(yáng)M，1.46GHz的主頻，256M內(nèi)存的PC機(jī)，為分析其計(jì)算效率，結(jié)果如下.實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)周期為24時(shí)，可以得到明顯的符合實(shí)際的周期模式.而由于周期為4時(shí)，周期過短而造成無法很好的識別部分周期的結(jié)果.

表1 在人工合成時(shí)間序列上的運(yùn)行結(jié)果Table 1 Run time on the synthetic data

表2 在交通時(shí)間序列上的運(yùn)行時(shí)間比較Table 2 Run time on the traffic time series data

表1和表2分別給出了當(dāng)窗口長度分別固定為2 000和2 400，min_conf=30%時(shí)，2種算法在合成時(shí)間序列和交通流時(shí)間序列中的運(yùn)行時(shí)間比較.由表中可以發(fā)現(xiàn)，本文所提出的基于移動窗的MW算法所用的時(shí)間要比最大子模式迎合樹Mht算法要少的多，而且MW算法的運(yùn)行時(shí)間幾乎不隨新增數(shù)據(jù)長度的變化而變化，對于大型時(shí)間序列數(shù)據(jù)運(yùn)行時(shí)間比較穩(wěn)定，這是因?yàn)镸W算法每次的計(jì)算對象都是新窗口中的數(shù)據(jù)，而且當(dāng)新窗口中的1-模式?jīng)]有變化時(shí)，則不需要對最大子模式樹的結(jié)構(gòu)進(jìn)行更新.而Mht算法隨著新增數(shù)據(jù)長度的增長運(yùn)行時(shí)間而減少，這是因?yàn)樵诳偟臄?shù)據(jù)長度不變的情況下，增加新增數(shù)據(jù)的長度將會減少最大子模式樹總的更新次數(shù)，從而降低了計(jì)算時(shí)間.因此，MW算法更適合于大型時(shí)間序列數(shù)據(jù).

圖4 當(dāng)min_conf值變化時(shí)的運(yùn)行時(shí)間Fig.4 The run time when min_conf change

為說明置信度閾值對計(jì)算時(shí)間的影響，圖4給出了當(dāng)窗口長度D=2 000和新增數(shù)據(jù)長度d=200，而改變置信度閾值min_conf時(shí)，2種算法對于合成時(shí)間序列的計(jì)算時(shí)間比較結(jié)果.由圖4可見，2種算法隨著置信度閾值的增大，計(jì)算時(shí)間都在減小，這是因?yàn)殡S著置信度閾值的增大，1-頻繁模式越來越少，因此總的計(jì)算量也越來越小，而且當(dāng)置信度閾值超過50%時(shí)，計(jì)算時(shí)間變化會很小，這是因?yàn)榇藭r(shí)，滿足條件的1-頻繁模式很少，而且變化不大，從而使得不必進(jìn)行過多的計(jì)算.

5 結(jié)束語

提出了一種帶移動時(shí)間窗的時(shí)間序列部分周期模式挖掘算法.在挖掘過程中數(shù)據(jù)不斷的被采集，數(shù)據(jù)的性能分布也會有相應(yīng)的變化，為了挖掘最新的模式，利用移動時(shí)間窗，在先前挖掘結(jié)果的基礎(chǔ)上，對最近的時(shí)間序列進(jìn)行部分周期模式挖掘.文中提出的算法最多對指定時(shí)間窗口中的數(shù)據(jù)搜索2次即可.既保證了挖掘結(jié)果的時(shí)效性又降低了算法的計(jì)算復(fù)雜度.實(shí)驗(yàn)中在各種條件下，對算法進(jìn)行了不同側(cè)面的比較，搜索速度加快，使得該算法更適用于大型時(shí)間序列數(shù)據(jù)庫的部分周期模式挖掘.

［1］RODDICK J F，SPILIOPOULOU M.A survey of temporal knowledge discovery paradigms and methods［J］.IEEE Trans on Knowledge and Data Engineering，2002，14(4):750-767.

［2］HU X，XU P，WU Sh，et al.A data mining framework for time series estimation［J］.J Biomed Inform，2010，43(2):190-199.

［3］LIAN X，CHEN L.Efficient similarity search over future stream time series［J］.IEEE Trans on Knowledge and Data Engineering，2008，20(1):40-54.

［4］MARTEAU P F.Time warp edit distance with stiffness adjustment for time series matching［J］.IEEE Trans On Pattern A-nalysis and Machine Intelligence，2009，31(2):306-318.

［5］RICHARD J.POVINELLI XIN F.A new temporal pattern identification methord for characterization and prediction of complex time series events［J］.IEEE Trans on Knowledge and Data Engineering，2003，15(2):339-352.

［6］HAN J，GONG W，YIN Y.Efficient mining of partial periodic patterns in time series database［C］//Proc 15th Int'l Conf Data Eng Sydney，Australia，1999:106-115.

［7］AREF W G，ELFEKY M G，ELMAGARMID A K.Incremental，online，and merge mining of partial periodic patterns in time-series databases［J］.IEEE Trans on Knowledge and Data Engineering，2004，16(3):332-342.

［8］歐陽為民，蔡慶生.基于時(shí)間窗口的增量式關(guān)聯(lián)規(guī)則更新技術(shù)［J］.軟件學(xué)報(bào)，1999，10(4):427-429.

OUYANG Weimin，CAI Qingsheng.A Time-window based incremental technique for updating association rules［J］.Journal of software，1999，10(4):427-429