一種序列模式發(fā)現(xiàn)的新方法

摘要：針對(duì)序列模式挖掘，提出頻繁2序列圖（F2SG）來表示數(shù)據(jù)庫(kù)中的序列信息，通過掃描一次數(shù)據(jù)庫(kù)，將與挖掘任務(wù)相關(guān)的信息映射到F2SG中，并在此基礎(chǔ)上提出一種新的序列模式發(fā)現(xiàn)算法——GBSP。GBSP算法充分利用F2SG中表示的項(xiàng)目之間的次序關(guān)系進(jìn)行頻繁序列挖掘，提高了其生成效率。理論分析與實(shí)驗(yàn)表明，該算法較傳統(tǒng)的序列模式發(fā)現(xiàn)算法在時(shí)間和空間性能上具有優(yōu)越性。

關(guān)鍵詞：數(shù)據(jù)挖掘； 序列模式； 圖

中圖分類號(hào)：TP182文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)04－1003－03

序列模式發(fā)現(xiàn)作為重要的KDD分支，在交易數(shù)據(jù)分析、疾病分析、Web日志分析、通信網(wǎng)絡(luò)分析等領(lǐng)域已經(jīng)開展了較為廣泛的研究和應(yīng)用。由于序列的排列方式隨其包含項(xiàng)目的個(gè)數(shù)呈指數(shù)增長(zhǎng)，關(guān)于如何改進(jìn)序列模式的發(fā)現(xiàn)效率一直是數(shù)據(jù)挖掘領(lǐng)域里的一個(gè)研究熱點(diǎn)。

經(jīng)典的序列模式發(fā)現(xiàn)有R.Agrawal等人提出的基于apriori特性和逐層（level－wize）的發(fā)現(xiàn)方法，包括AprioriAll、AprioriSome、DynamicSome三種算法[1]以及后來提出的泛化序列模式挖掘算法GSP[2]。GSP算法避開了頻繁項(xiàng)目集的挖掘步驟而使得其效率最佳。但這類算法需要保存大量的候選序列，并且在每一次迭代過程中需要掃描序列數(shù)據(jù)庫(kù)以計(jì)算候選序列的支持?jǐn)?shù)。掃描數(shù)據(jù)庫(kù)的次數(shù)取決于最長(zhǎng)頻繁序列的長(zhǎng)度。基于分而治之(divide－and－conquer)的思想，Han等人又提出了一種稱為基于序列模式增長(zhǎng)的方法，包括FreeSpan[3]、Prefix－Span[4]算法。這類算法利用頻繁項(xiàng)遞歸地將序列數(shù)據(jù)庫(kù)投影到更小的投影數(shù)據(jù)庫(kù)集中，在每個(gè)投影數(shù)據(jù)庫(kù)中生成子序列片段。其中，F(xiàn)reeSpan算法基于任何頻繁子序列對(duì)序列數(shù)據(jù)庫(kù)投影，并在子序列的任何位置上增長(zhǎng)；PrefixSpan算法基于頻繁前綴子序列投影，并通過在其后添加后綴來實(shí)現(xiàn)序列的增長(zhǎng)。投影數(shù)據(jù)庫(kù)的規(guī)模小于原始數(shù)據(jù)庫(kù)，然而構(gòu)造投影數(shù)據(jù)庫(kù)的開銷巨大，且其規(guī)模的總和可能是原始數(shù)據(jù)庫(kù)的很多倍。這類算法在挖掘過程中仍需要反復(fù)掃描投影數(shù)據(jù)庫(kù)。多次掃描數(shù)據(jù)庫(kù)需要花費(fèi)大量的時(shí)間，降低了算法的執(zhí)行效率。此外，候選序列的生成也成為影響算法執(zhí)行效率的關(guān)鍵。

本文將圖結(jié)構(gòu)引入到序列模式的挖掘過程中，借助圖結(jié)構(gòu)表示數(shù)據(jù)庫(kù)中的序列信息，以改善序列模式挖掘效率的問題。首先定義了一種稱為頻繁2序列圖(frequent 2－sequence graph，F(xiàn)2SG)的結(jié)構(gòu)來表示序列數(shù)據(jù)庫(kù)中與挖掘任務(wù)相關(guān)的信息；在此基礎(chǔ)上提出一種新的序列模式發(fā)現(xiàn)算法GBSP（graph－based sequential pattern），主要策略是用頻繁k-1序列和頻繁2序列進(jìn)行時(shí)序連接逐層迭代生成k序列。由于存儲(chǔ)在內(nèi)存中的圖保留了原交易數(shù)據(jù)庫(kù)中與挖掘任務(wù)相關(guān)的所有信息，不必反復(fù)掃描數(shù)據(jù)庫(kù)，提高了算法的時(shí)間性能。同時(shí)，F(xiàn)2SG過濾了所有不可能成為頻繁2序列的組合，因而在生成頻繁序列的過程中有效縮小了搜索空間，避免了不必要候選序列的產(chǎn)生。實(shí)驗(yàn)證明，該算法是精確和有效的。

4結(jié)束語(yǔ)

序列模式發(fā)現(xiàn)是近幾年越來越受到關(guān)注的研究方向。本文提出的序列模式發(fā)現(xiàn)算法GBSP采用了圖結(jié)構(gòu)，克服了經(jīng)典算法在時(shí)間性能方面的不足，具有一定的優(yōu)越性。未來的研究問題包括如何進(jìn)一步降低圖的規(guī)模，如何加入有效的約束條件以及與閉合序列相結(jié)合，在改善時(shí)空性能的同時(shí)挖掘出更加有價(jià)值的序列模式。

參考文獻(xiàn)：

[1]AGRAWAL R，SRIKANT R.Mining sequential patterns[C]//Proc of the 11th Int Conf on Data Engineering.Taipei:[s.n.]，1995:3－14.

[2]SRIKANT R， AGRAWAL R. Mining sequential patterns: generalizations and performance improvements[C]//Proc of the 5th Int Conf on Extending Database Technology. Avignon:[s.n.]， 1996.

[3]PEI Jian， HAN Jia－wei， MORTAZAVI－ASL B， et al. PrefixSpan: mining sequential patterns efficiently by prefix－projected pattern growth[J]. IEEE Trans on Knowledge and Data Engineering， 2004，16(11):1424－1440.

[4]YAN Xi－feing， HAN Jia－wei. gSpan: graph－based substructure pattern mining[C]//Proc of IEEE Int Conf on Data Mining. Maebashi City:[s.n.]， 2002:721－724.

[5]ZAKI M J. SPADE: an efficient algorithm for mining frequent sequence[J]. Machine Learning， 2001，42(1－2):31－60.

[6]MASSEGLIA F， CATHALA F， PONCELET P. The PSP approach for mining sequential patterns[C]//Proc of European Symp Principle of Data Mining and Knowledge Discovery. Nantes:[s.n.]， 1998.

[7]HUANG Yin－fu， LIN Shao－yuan. Mining sequential patterns using graph search techniques[C]//Proc of the 27th Annual International on Computer Software and Applications Conference. 2003:4－9.

[8]鄧明榮，葉福根，史烈，等.挖掘泛化序列模式的一種有效方法[J].浙江大學(xué)學(xué)報(bào):理學(xué)版，2002，29(4):415－422.

[9]朱立運(yùn)，朱建秋.帶時(shí)間特征的序列模式挖掘算法TESP[J].計(jì)算機(jī)工程，2004，30(10):51－54.

[10]周斌，吳泉源.序列模式挖掘的一種漸進(jìn)算法[J].計(jì)算機(jī)學(xué)報(bào)，1999，22(10):882－887.

[11]陳金玉，樊興華.序列模式的一種挖掘算法[J].重慶大學(xué)學(xué)報(bào)，2001，24(1):92－94.

[12]劉月波，陸階平，劉同明.基于CTID序列模式的一種改進(jìn)算法[J].微機(jī)發(fā)展，2005，15(3):20－22.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”