一種基于m元樹結構的序列模式挖掘

鄭金彬

（龍巖學院 數學與計算機科學學院，福建 龍巖 3 6 4 0 1 2）

一種基于m元樹結構的序列模式挖掘

鄭金彬

（龍巖學院 數學與計算機科學學院，福建 龍巖 3 6 4 0 1 2）

提出一種基于m元樹結構序列挖掘模式挖掘算法，該算法通過構造m元樹結構，利用滑動窗口不斷對數據集新舊項目的增刪以確保數據庫內容的更新.實驗與理論分析表明，即使算法輸入參數的不同，比如興趣度、最小支持度等，該算法都是非常有效的.

數據挖掘；漸進序列模式；滑動窗口；m元樹

1 引言

數據挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程.序列模式挖掘是數據挖掘技術中一個非常重要的研究課題和領域,旨在從有序事件的數據集中發現有規律的序列模式[1].序列模式挖掘中首次引入了：“給定一個序列數據庫，每個序列由一組有序項目組成，包含不同的項目集列表和一個用戶定義的最小支持度閾值，序列模式挖掘便是找出所有發生頻率不低于序列閾值的子序列”[2].

定義1 令X={x1,x2,…,xn}是不同的項目集，元素 e記為 (xixj)，xi,xj為不同的單項（1≤i≤n,1≤j≤n），元素內的單項不考慮順序關系，一般默認按照序列I D的字典序排列，在用戶事務數據庫里，一個事務就是一個元素；序列 s記為〈e1,e2,…,em〉，是一組有序元素列表，序列數據庫D B則是一序列的集合，其中|D B|表示序列元素個數，即序列長度.在序列數據庫 D B中，設序列 α=〈a1,a2,…,an〉和 β=〈b1,b2,…,bm〉，如果存在整數 1≤i1

序列模式挖掘可應用于數據中的數據不隨時間而改變的靜態數據庫.然而在許多實際應用領域中，數據庫中數據的內容是會不斷更新變化的.正因為在數據庫數據更新過程中，原先數據庫中的非頻繁數據序列也會變成頻繁數據序列，為了找出所有的序列模式，所以挖掘算法不論數據庫數據更新與否都必須一直要執行[4].為此，需采用序列模式挖掘中的增量式更新算法來解決這種超過數據庫數據的挖掘過程.

針對序列數據集和增量數據集來挖掘頻繁項均有廣泛的研究案例了.然而采用漸進序列模式挖掘來發現序列模式是一個新的研究領域，不過漸進序列模式挖掘也面臨新的挑戰，就是如何發現數據項內在的特征以便將新的數據項添加到現有的數據庫中和從數據庫中刪除廢棄的數據項[3].

2 漸近序列模式挖掘概述

根據數據庫相應的管理規則，為此我們提出了序列模式挖掘的一般模型，稱之為“漸近序列模式挖掘”[2]，主要就是如何實現將新的數據項添加到現有的數據庫中和從數據庫中刪除廢棄的數據項，并因此不受廢棄數據項的影響能找到最新序列模式.

2.1 問題描述

先前有許多關于漸近數據庫的討論研究，但提出的方法難以從數據庫中提取重要的隱含信息，比如介于數據庫之外的支持項.本文提出的m元樹結構方法卻有效地解決了這一問題，當然，這方法除了修改項目的標簽、序列I D號和時間戳，還得添加每個項目的支持分支數.

2.2 相關研究

2.2.1 序列模式挖掘

序列模式的概念最早是由A g r a w a l和S r i k a n t提出的[5].一般序列模式挖掘算法可歸納為以下典型的三類：（1）類A p r i o r i算法，該類算法基于A p r i-o r i理論，即序列模式的任一子序列也是序列模式.算法首先自底向上的根據較短的序列模式生成較長的候選序列模式，然后計算候選序列模式的支持度.典型的代表有G S P算法，S P A D E算法等.（2）基于劃分的模式生長算法，該類算法基于分治的思想，迭代的將原始數據集進行劃分，減少數據規模，同時在劃分的過程中動態地挖掘序列模式，并將新發現的序列模式作為新的劃分元.典型的代表有F r e e S p a n算法和P r e f i x S p a n算法.（3）基于序列比較的算法，該類算法首先定義序列的大小度量，接著從小到大地枚舉原始序列數據庫中包含的所有k-序列，理論上所有的k-序列模式都能被找到，典型的代表為D i s c-a l l算法[6,7].其實基于以上三種思想的傳統算法有很多，比如閉序列模式挖掘，最大頻繁序列模式挖掘和約束序列模式挖掘等.

2.2.2 漸進序列模式挖掘

漸序列模式挖掘是一種普遍適用的找出最新頻繁序列模式的模式挖掘方法.該算法在靜態和動態變化的數據庫中均可高效執行，且不受廢棄數據的影響，該算法利用滑動窗口逐步更新數據庫中的序列，隨著時間的推移不斷積累頻繁候選序列模式.所謂滑動窗口就是在一個長為n的原始序列上從頭到尾滑動長為w的窗口[6].

定義2 興趣期（P O I）是一個滑動窗口.P O I長度是由用戶自行定義的時間間隔.那么若序列元素的時間戳屬于P O I的時間范圍內，則將該元素歸入長度為|D B|的序列模式，也就是說，若序列元素的時間戳不屬于P O I的時間范圍內，則應立即將其從序列數據庫中枝剪出，并從此不再并入長度為|D B|的序列[6].

3 漸近序列模式挖掘的改進策略

其實可以通過修改漸近序列樹結構來解決漸近序列模式的挖掘問題，方法就是歸并包容相同支持度的項目以獲得新的支持模式，本文則通過構建m元樹的數據結構來實現這種策略.

3.1 數據結構

m元樹結構用來存儲數據庫的項目的細節特征，該樹的結點總體上分為根結點和葉結點兩種.根結點用于鏈接所有葉結點的頭結點，每個葉結點則包含每個項目的項目名稱、序列I D號、時間戳.

3.1.1 添加新項目

在時間t時往m元樹中插入新的元素，作為時間t+1的更新樹.該算法在時間t采用后序策略遍歷m元樹，直到在漸近數據庫查找到新的數據時中止運行，每當在一序列中存在有一系列元素，就用序列模式各自元素相應的序列號從根結點開始創建一條新的路徑，以作為候選模式.如果這條路徑已經存在，則以各自的信息來更新結點的相關區域.

3.1.2 刪除廢棄項目

應當將廢棄的元素（比如屬于興趣期之外的元素），或者在序列列表中沒有序列號的結點分別從結點序列表中和m元樹中刪除.

3.2 從漸進數據庫中挖掘頻繁模式

序列模式挖掘的主要思想就是利用了m元樹存儲介于不同興趣期的所有序列.當時間刻t+1到來時，該算法便采用后序策略遍歷原先的m元樹，從中刪除廢棄項目并插入新項目以確保漸近序列數據庫內容的更新.其算法如下所述：

3.3 算法實例

3.3.1 頻繁序列模式的最小頻率

如圖1為一實例數據庫，其中S01,S02,…,Sn表示不同I D號的序列，A，B，C，D表示在數據庫中的不同項目，t1,t2,…,tk表示時間戳.隨著時間的推移，會有越來越多的元素添加到漸近數據庫中，比如序列S01在時間 t1,t2,t4,t5分別包含元素 A，B，C和（A D），而D bp,q則表示包含從時間戳p到時間戳q所有元素的數據庫子集.假設最小支持度閥值m i n_s u p=0.5，|D bp,q|=5，那么該實例數據庫頻繁序列模式的最小頻率為：|D b1,5|*m i n_s u p=5*0.5=2.5.

3.3.2 t0-t5的m元樹結構構造實例

假設實例數據庫如3.3.1所述，最小支持度閥值m i n_s u p=0.5，|D bp,q|=5，每一結點信息包含：結點標簽、序列I D號和時間戳，則m元樹在時間段t1-t5的構造過程為：在開始時刻t0m元樹只有根結點；在時刻t1到來時，序列S01,S02,S03分別包含元素：A，(A D)和A，因三個序列均包含有元素A，所以元素A的序列I D號分別標上0 1，0 2，0 3，同樣，元素D、（A D）的序列I D號分別標上0 2，它們的時間戳均為：1；在時刻t2到來時，序列S01,S02,S03,S04分別包含元素：B，B，(B C)和 D，根據 m-a r y算法的后序遍歷，比如在序列S01,S02,S03的結點A，分別在序列表查找是否有新的元素到來，查找結果表明有B，C和（B C）三個新的元素，于是便在結點A后產生三個葉結點B，C和（B C），限于篇幅，其他時間戳所有結點的構造在這就不再說述了，t0-t5m元樹結構構造結果如圖2所示.

4 實驗結果與算法性能分析

實驗結果表明，基于3.3.1數據庫的測試數據之上，該算法能非常有效的執行并完成序列模式的挖掘.以下對測試數據集依據不同的輸入參數分析算法的特性，比如，興趣期（P O I）、遍歷時間等.

4.1 P O I對算法執行時間的影響

這里的執行時間是指該算法的執行所有指令所需的時間.實驗結果如圖3（a）所示，P O I與遍歷模式時間是一種成正比的關系，原因就是：隨著P O I的推進，不斷遍歷m元樹時增加了候選模式，對此需擴展其相應的數據結構用于存儲這些候選式，這必然造成所需時間的遞增.

4.2 P O I及最小支持度對遍歷模式數的影響

實驗結果如圖3（b）表明，遍歷模式數量與P O I和最小支持度有著一定的依賴關系.也就是說，當P O I不斷推進時，模式數量也跟著遞增，若需處理的項目數越多，則產生的模式數就越多；同時，隨著最小支持度的增加，模式數量卻跟著遞減，原因在于：當該項目的支持度小于最小支持度時，支持度較低的模式不會再頻繁出現，也就是說發生的頻繁很小.

5 結論

隨著時間的不斷推進，基于數據庫測試數據所產生的序列模式也會不斷發生更新，對于不斷增加的候選集，通過構造m元樹用于存儲和管理，為此，設計出了相應的m元樹的遍歷算法來查找出所有的最新序列模式，同時刪除了原有的廢棄數據和模式.實驗結果表明：該漸近序列模式挖掘算法不會受到輸入參數的大幅度影響，且當所設置的最小支持閥值很小時，這算法就越顯得高效了，此外，該算法在現實數據集上具有良好的可擴展性.

〔1〕Y.Hirate and h.Yamana, (2006) “Sequential Pattern Mining with Time Interval,”In:10th Pacific– AsiaConf.KnowledgeDiscovery and Data mining(PAKDD’06).

〔2〕C.Luo and S.M.Chung,(2005) “ Efficient Mining of Maxmal Sequential Patterns using Multiple Samples,” In:.5th SIAM Int’l Conf.Data Mining(SDM).

〔3〕S.Cong,J.han and D.Pandu,(2005) “Parallel Mining of Closed sequential Patterns,”In:11 ACM SIGKDD Int’l Conf.Knowledge Discovery and Data Mining(KDD’05).

〔4〕Jiawei Han,Micheline Kamber.數據挖掘:概念與技術(影印版)[M].高等教育出版社,2006.

〔5〕王虎,丁世飛.序列模式挖掘研究與發展[J].計算機科學,2009(12).

〔6〕蔡建山,遲呈英,戰學剛,王丫.基于滑動窗口的動態摘要算法[J].計算機工程,2007(3).

〔7〕陳卓,楊炳儒,宋威,宋澤鋒.序列模式挖掘綜述[J].計算機應用研究,2008(7).

T P 3 0 1.6

A

1673-260X（2010）10-0031-04

福建省教育廳基金資助項目（JA08229）