一種基于m元樹結(jié)構(gòu)的序列模式挖掘

鄭金彬

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

一種基于m元樹結(jié)構(gòu)的序列模式挖掘

鄭金彬

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

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

數(shù)據(jù)挖掘；漸進序列模式；滑動窗口；m元樹

1 引言

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

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

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

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

2 漸近序列模式挖掘概述

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

2.1 問題描述

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

2.2 相關(guān)研究

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

2.2.2 漸進序列模式挖掘

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

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

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

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

3.1 數(shù)據(jù)結(jié)構(gòu)

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

3.1.1 添加新項目

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

3.1.2 刪除廢棄項目

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

3.2 從漸進數(shù)據(jù)庫中挖掘頻繁模式

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

3.3 算法實例

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

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

3.3.2 t0-t5的m元樹結(jié)構(gòu)構(gòu)造實例

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

4 實驗結(jié)果與算法性能分析

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

4.1 P O I對算法執(zhí)行時間的影響

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

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

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

5 結(jié)論

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

〔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.數(shù)據(jù)挖掘:概念與技術(shù)(影印版)[M].高等教育出版社,2006.

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

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

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

T P 3 0 1.6

A

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

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