時間序列部分周期模式的更新算法

王曉曄，肖迎元，張德干

(1.天津理工大學智能計算及軟件新技術重點實驗室，天津300191;2.天津理工大學計算機視覺與系統(tǒng)省部共建教育部重點實驗室，天津300191)

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

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

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

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

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

1 時間序列的部分周期模式

1.1 問題定義

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

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

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

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

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

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

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

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

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

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

1.2 部分周期模式挖掘

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

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

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

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

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

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

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

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

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

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

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

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

經過時間序列數(shù)據(jù)庫的更新，在新時間窗口中的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集進行更新產生F1';

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

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

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

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

1)遍歷淘汰數(shù)據(jù)庫retire，計算所有的模式X∈F1在retire中的頻率值X.frequencyr;遍歷新增數(shù)據(jù)庫sc，計算所有的模式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的同時，根據(jù)sc的每一個周期段構造不在F1中的候選1-模式集C1，對C1中的任一模式Y，若Y.frequencyS＜ min_conf×(d-r)+Y.frequencyr，依據(jù)文獻［7］中的引理2，那么 Y 在更新后序列中就必是非頻繁的，可將其從C1中刪除.

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

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

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

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

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

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

3 計算復雜度分析

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

4 算法測試及結果分析

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

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

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

表1 在人工合成時間序列上的運行結果Table 1 Run time on the synthetic data

表2 在交通時間序列上的運行時間比較Table 2 Run time on the traffic time series data

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

圖4 當min_conf值變化時的運行時間Fig.4 The run time when min_conf change

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

5 結束語

提出了一種帶移動時間窗的時間序列部分周期模式挖掘算法.在挖掘過程中數(shù)據(jù)不斷的被采集，數(shù)據(jù)的性能分布也會有相應的變化，為了挖掘最新的模式，利用移動時間窗，在先前挖掘結果的基礎上，對最近的時間序列進行部分周期模式挖掘.文中提出的算法最多對指定時間窗口中的數(shù)據(jù)搜索2次即可.既保證了挖掘結果的時效性又降低了算法的計算復雜度.實驗中在各種條件下，對算法進行了不同側面的比較，搜索速度加快，使得該算法更適用于大型時間序列數(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］歐陽為民，蔡慶生.基于時間窗口的增量式關聯(lián)規(guī)則更新技術［J］.軟件學報，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