鄭金彬

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

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

鄭金彬

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

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

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

1 引言

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

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

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

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

2 漸近序列模式挖掘概述

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

2.1 問題描述

先前有許多關(guān)于漸近數(shù)據(jù)庫的討論研究，但提出的方法難以從數(shù)據(jù)庫中提取重要的隱含信息，比如介于數(shù)據(jù)庫之外的支持項(xiàng).本文提出的m元樹結(jié)構(gòu)方法卻有效地解決了這一問題，當(dāng)然，這方法除了修改項(xiàng)目的標(biāo)簽、序列I D號(hào)和時(shí)間戳，還得添加每個(gè)項(xiàng)目的支持分支數(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ù)較短的序列模式生成較長的候選序列模式，然后計(jì)算候選序列模式的支持度.典型的代表有G S P算法，S P A D E算法等.（2）基于劃分的模式生長算法，該類算法基于分治的思想，迭代的將原始數(shù)據(jù)集進(jìn)行劃分，減少數(shù)據(jù)規(guī)模，同時(shí)在劃分的過程中動(dòng)態(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].其實(shí)基于以上三種思想的傳統(tǒng)算法有很多，比如閉序列模式挖掘，最大頻繁序列模式挖掘和約束序列模式挖掘等.

2.2.2 漸進(jìn)序列模式挖掘

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

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

3 漸近序列模式挖掘的改進(jìn)策略

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

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

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

3.1.1 添加新項(xiàng)目

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

3.1.2 刪除廢棄項(xiàng)目

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

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

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

3.3 算法實(shí)例

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

如圖1為一實(shí)例數(shù)據(jù)庫，其中S01,S02,…,Sn表示不同I D號(hào)的序列，A，B，C，D表示在數(shù)據(jù)庫中的不同項(xiàng)目，t1,t2,…,tk表示時(shí)間戳.隨著時(shí)間的推移，會(huì)有越來越多的元素添加到漸近數(shù)據(jù)庫中，比如序列S01在時(shí)間 t1,t2,t4,t5分別包含元素 A，B，C和（A D），而D bp,q則表示包含從時(shí)間戳p到時(shí)間戳q所有元素的數(shù)據(jù)庫子集.假設(shè)最小支持度閥值m i n_s u p=0.5，|D bp,q|=5，那么該實(shí)例數(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è)實(shí)例數(shù)據(jù)庫如3.3.1所述，最小支持度閥值m i n_s u p=0.5，|D bp,q|=5，每一結(jié)點(diǎn)信息包含：結(jié)點(diǎn)標(biāo)簽、序列I D號(hào)和時(shí)間戳，則m元樹在時(shí)間段t1-t5的構(gòu)造過程為：在開始時(shí)刻t0m元樹只有根結(jié)點(diǎn)；在時(shí)刻t1到來時(shí)，序列S01,S02,S03分別包含元素：A，(A D)和A，因三個(gè)序列均包含有元素A，所以元素A的序列I D號(hào)分別標(biāo)上0 1，0 2，0 3，同樣，元素D、（A D）的序列I D號(hào)分別標(biāo)上0 2，它們的時(shí)間戳均為：1；在時(shí)刻t2到來時(shí)，序列S01,S02,S03,S04分別包含元素：B，B，(B C)和 D，根據(jù) m-a r y算法的后序遍歷，比如在序列S01,S02,S03的結(jié)點(diǎn)A，分別在序列表查找是否有新的元素到來，查找結(jié)果表明有B，C和（B C）三個(gè)新的元素，于是便在結(jié)點(diǎn)A后產(chǎn)生三個(gè)葉結(jié)點(diǎn)B，C和（B C），限于篇幅，其他時(shí)間戳所有結(jié)點(diǎn)的構(gòu)造在這就不再說述了，t0-t5m元樹結(jié)構(gòu)構(gòu)造結(jié)果如圖2所示.

4 實(shí)驗(yàn)結(jié)果與算法性能分析

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

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

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

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

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

5 結(jié)論

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

〔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].計(jì)算機(jī)科學(xué),2009(12).

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

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

T P 3 0 1.6

A

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

福建省教育廳基金資助項(xiàng)目（JA08229）