基于格的快速頻繁項(xiàng)集挖掘算法

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61072121）；湖南省自然科學(xué)基金資助項(xiàng)目（12JJ2035） ；“中央高校基本科研業(yè)務(wù)費(fèi)”資助項(xiàng)目

作者簡(jiǎn)介：劉彩蘋（1978-），女，湖南邵陽(yáng)人，湖南大學(xué)教師，博士

江西 撫州344000；3.湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長(zhǎng)沙410082）

摘要：隨著數(shù)據(jù)庫(kù)規(guī)模的增加或支持度閾值的減少，頻繁模式的數(shù)量將以指數(shù)形式增長(zhǎng)，F(xiàn)Pgrowth算法運(yùn)行的時(shí)空效率將大為降低本文提出一種基于格的快速頻繁項(xiàng)集挖掘算法LFPgrowth，算法利用等價(jià)關(guān)系將原來的搜索空間（格）劃分成若干個(gè)較小的子空間（子格），通過子格間的迭代分解，將對(duì)網(wǎng)格P（I）的頻繁項(xiàng)集挖掘轉(zhuǎn)化為對(duì)多個(gè)子格的并集進(jìn)行的約束頻繁項(xiàng)集挖掘?qū)嶒?yàn)結(jié)果和理論分析表明，在挖掘大型數(shù)據(jù)庫(kù)時(shí)，LFPgrowth算法的時(shí)間和空間性能均優(yōu)于FPgrowth算法

關(guān)鍵詞：數(shù)據(jù)挖掘；FP樹；頻繁項(xiàng)集；格

中圖分類號(hào)：TP31113文獻(xiàn)標(biāo)識(shí)碼：A

頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘中的一類重要挖掘問題，廣泛應(yīng)用于關(guān)聯(lián)規(guī)則挖掘、相關(guān)性分析、入侵檢測(cè)、序列挖掘、分類分析、聚類分析、Web挖掘、XML挖掘等諸多數(shù)據(jù)挖掘任務(wù)長(zhǎng)期以來， 人們對(duì)頻繁模式的挖掘進(jìn)行了大量深入的研究工作Han等人提出了一種比Apriori算法快一個(gè)數(shù)量級(jí)的FPgrowth算法隨后，各國(guó)的研究者們提出了許多其他改進(jìn)算法，如Koh等人提出的基于樹的高效頻繁項(xiàng)集挖掘算法，李也白等人用一種輔助存儲(chǔ)結(jié)構(gòu)提高了查詢的效率，Nguyen利用矩陣提出的頻繁項(xiàng)集挖掘算法，郭宇紅等人提出的反向頻繁項(xiàng)集挖掘算法，Zeng等人提出了加權(quán)關(guān)聯(lián)規(guī)則挖掘算法Jalan提出了一種非遞歸頻繁項(xiàng)集挖掘算法Adnan提出一種自適應(yīng)的頻繁項(xiàng)集挖掘算法趙強(qiáng)利提出一種快速選擇性集成算法范明提出一種不生成條件FP樹的算法譚軍提出了一種單遍掃描頻繁模式算法

FPgrowth 算法開辟了有效挖掘頻繁模式的新途徑然而，它的時(shí)間和空間效率還不足夠高，仍需改進(jìn)FPgrowth 算法的主要問題是建樹過程中必須將提供頻繁項(xiàng)集的數(shù)據(jù)全部壓縮到一棵頻繁模式樹（或FP樹），在挖掘時(shí)，由長(zhǎng)度為1的頻繁模式（初始后綴模式）開始，遞歸的構(gòu)造條件FP樹進(jìn)行挖掘，在建樹和挖掘過程中都需要占用大量的內(nèi)存當(dāng)數(shù)據(jù)庫(kù)很大，或者數(shù)據(jù)庫(kù)中的頻繁1項(xiàng)集的數(shù)目很大時(shí)，運(yùn)行速度將大為降低；更有甚者，可能由于無(wú)法構(gòu)造基于內(nèi)存的FP樹，該算法將不能有效地工作

本文結(jié)合大型數(shù)據(jù)庫(kù)本身的特性，在分析FPgrowth算法的基礎(chǔ)上，提出了一種基于格的大型數(shù)據(jù)庫(kù)頻繁模式挖掘算法LFPgrowth實(shí)驗(yàn)和分析表明，在挖掘大型數(shù)據(jù)庫(kù)時(shí)，LFPgrowth算法具有較好的時(shí)間和空間效率

1基本概念和問題的描述

為方便討論，以事務(wù)數(shù)據(jù)庫(kù)為背景設(shè)為所有項(xiàng)目的集合，為事務(wù)數(shù)據(jù)庫(kù)， 其中每個(gè)事務(wù)有一個(gè)惟一的標(biāo)識(shí)TID表1中的事務(wù)數(shù)據(jù)庫(kù)是本文的示例數(shù)據(jù)庫(kù)該數(shù)據(jù)庫(kù)中事務(wù)已經(jīng)按照各項(xiàng)的支持度計(jì)數(shù)遞增地將各事務(wù)中的項(xiàng)重新排列

在事務(wù)數(shù)據(jù)庫(kù)中挖掘頻繁項(xiàng)集的問題可以描述為：給定事務(wù)數(shù)據(jù)庫(kù)D和最小支持度閾值minsup ，挖掘所有的頻繁項(xiàng)集

由定理3得到以下結(jié)論，對(duì)網(wǎng)格P（I）的頻繁項(xiàng)集挖掘轉(zhuǎn)化為對(duì)多個(gè)子網(wǎng)格的并集進(jìn)行的約束頻繁項(xiàng)集的挖掘，不會(huì)影響頻繁項(xiàng)集完全集的正確輸出

22算法步驟

實(shí)現(xiàn)LFPgrowth算法的關(guān)鍵是子格（子搜索空間）所對(duì)應(yīng)的事務(wù)的迭加，如果復(fù)制所有的子格對(duì)應(yīng)的事務(wù)進(jìn)行迭加，時(shí)間和空間的效率會(huì)非常低為此，可以借鑒Christian Borgelt教授在研究Recursive elimination算法時(shí)提出的事務(wù)鏈表（transaction list array）來實(shí)現(xiàn)迭加

事務(wù)鏈表是由一組單向數(shù)據(jù)鏈表組成，每一個(gè)單向數(shù)據(jù)鏈記錄一個(gè)子格P（k）所對(duì)應(yīng)的事務(wù)集（以下簡(jiǎn)稱為P（k）事務(wù)集）的信息，每一個(gè)單向數(shù)據(jù)鏈都包括一個(gè)計(jì)數(shù)器（support counter）和一個(gè)指針計(jì)數(shù)器的值表示P（k）事務(wù)集的總數(shù)，指針則用于保存P（k）事務(wù)集的關(guān)聯(lián)信息將所有單向數(shù)據(jù)鏈表按P（k）處理的順序排列，便組成了事務(wù)鏈表樣例數(shù)據(jù)庫(kù)的事務(wù)鏈表組如圖3所示

當(dāng)數(shù)據(jù)庫(kù)為海量數(shù)據(jù)庫(kù)時(shí)，可將它分解迭加成多個(gè)P（k）^進(jìn)行挖掘，而當(dāng)某個(gè)P（k）^對(duì)應(yīng)的事務(wù)很多，依然無(wú)法在內(nèi)存中構(gòu)造Fp樹時(shí)，挖掘就難以順利進(jìn)行根據(jù)定理5可知 P（k）^是格，因此我們可將P（k）^再次進(jìn)行迭加分解，如果分解后擴(kuò)展子格依然無(wú)法在內(nèi)存中構(gòu)造Fp樹時(shí)，就再繼續(xù)分解直到可以在內(nèi)存中構(gòu)造擴(kuò)展子格的Fp樹為止

3實(shí)驗(yàn)結(jié)果和分析

31實(shí)驗(yàn)結(jié)果

本節(jié)對(duì)LFPgrowth算法和FPgrowth算法進(jìn)行比較，程序代碼均用Visual C++實(shí)現(xiàn)實(shí)驗(yàn)在PetiumⅣ28G，內(nèi)存512M，硬盤80G的PC機(jī)上運(yùn)行實(shí)驗(yàn)結(jié)果如圖5～圖7所示

圖5是采用accidents數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫(kù)大小為336 M，是比利時(shí)國(guó)家統(tǒng)計(jì)院提供的1991-2000年期間Flanders地區(qū)的交通事故數(shù)據(jù)庫(kù)由圖5可知，當(dāng)最小支持度大于等于05%時(shí)，F(xiàn)Pgrowth算法的運(yùn)行速度比LFPgrowth算法略快但是，當(dāng)最小支持度小于05%時(shí)，LFPgrowth算法的運(yùn)行速度比FPgrowth算法快而且隨著支持度的減少，差別越明顯

圖6是采用bio_train數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫(kù)是KDD Cup 2004所提供的關(guān)于蛋白質(zhì)同源性的訓(xùn)練數(shù)據(jù)庫(kù)該數(shù)據(jù)庫(kù)有145 751行，每行包含有1個(gè)塊號(hào)、1個(gè)試驗(yàn)號(hào)和74個(gè)特征值圖6是在事務(wù)數(shù)據(jù)庫(kù)大小為664 M條件下，最小支持度從3%減少到005%的兩種算法運(yùn)行時(shí)間的比較，由圖6可知，當(dāng)最小支持度等于3%時(shí)，F(xiàn)Pgrowth算法的運(yùn)行速度比LFPgrowth算法快但是，當(dāng)最小支持度小于等于1%時(shí)，LFPgrowth算法的運(yùn)行速度比FPgrowth算法快而且隨著支持度的減少，差別越大

32實(shí)驗(yàn)結(jié)果分析

FPgrowth算法要將事務(wù)數(shù)據(jù)庫(kù)中所有產(chǎn)生頻繁項(xiàng)集的數(shù)據(jù)壓縮到一棵FP樹中，該樹中存儲(chǔ)的關(guān)聯(lián)信息從建樹開始到挖掘完畢都完整地保存在內(nèi)存里，挖掘時(shí)又通過遞歸創(chuàng)建條件FPtree生成頻繁模式，條件FPtree個(gè)數(shù)等于頻繁模式數(shù)，所以建樹挖掘的時(shí)間和空間開銷都很大，尤其是隨著數(shù)據(jù)庫(kù)規(guī)模的增加或支持度閾值的減少而導(dǎo)致頻繁模式的數(shù)量以指數(shù)形式增長(zhǎng)時(shí)， FPgrowth算法無(wú)法構(gòu)造基于內(nèi)存的FP樹，從而導(dǎo)致挖掘失敗而LFPgrowth算法雖然多次迭加子格，但它是在擴(kuò)展格中構(gòu)造FPtree，規(guī)模比原始的FPtree要小，而且挖掘過程比FPgrowth算法簡(jiǎn)單，時(shí)間消耗遠(yuǎn)小于FPgrowth算法

本文算法不僅時(shí)間效率明顯優(yōu)于FPgrowth算法，而且空間效率也明顯優(yōu)于FPgrowth算法因?yàn)?，LFPgrowth算法構(gòu)建的是基于擴(kuò)展格的FP樹，其規(guī)模遠(yuǎn)遠(yuǎn)小于在整體事務(wù)數(shù)據(jù)庫(kù)上構(gòu)建的FP樹，而且由以上運(yùn)行時(shí)間效率實(shí)驗(yàn)和分析已表明，LFPgrowth可以在更小的支持度閥度水平上運(yùn)行，而FPgrowth算法常因耗盡物理內(nèi)存而無(wú)法運(yùn)行

4結(jié)論

提出了一種基于格的快速頻繁項(xiàng)集挖掘算法LFPgrowth這種算法不僅減少了對(duì)內(nèi)存的需求，也較大地提高了挖掘效率，尤其適合挖掘大型數(shù)據(jù)庫(kù)的頻繁項(xiàng)集本文的實(shí)驗(yàn)結(jié)果很好地證明了這一點(diǎn)

今后的工作在于進(jìn)一步的研究如何精簡(jiǎn)事務(wù)數(shù)據(jù)鏈表組的結(jié)構(gòu)，進(jìn)一步提高現(xiàn)有算法的效率，減少對(duì)內(nèi)存的需求同時(shí)考慮可將本文格迭加分解的策略和已有的各種分布式頻繁模式挖掘算法結(jié)合起來，設(shè)計(jì)新的基于分布式數(shù)據(jù)庫(kù)的頻繁模式挖掘算法

參考文獻(xiàn)

[1]HAN J， PEI J， YIN Y Mining frequent patterns without candidate generation[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data New York： ACM Press， 2000：1-12

[2]KOH J L， TU Y L A treebased approach for efficiently mining approximate frequent itemsets[C]//Proceedings of the Fourth International Conference on Research Challenges in Information Science （RCIS） Nice， France： 2010： 1349-1357

[3]李也白，唐輝，張淳，等基于改進(jìn)的FPtree的頻繁模式挖掘算法[J]計(jì)算機(jī)應(yīng)用， 2011， 31（1）：101-103.

LI Yebai， TANG Hui， ZHANG Chun，et al Frequent pattern mining algorithm based on improved FPtree[J] Journal of Computer Applications， 2011， 31（1）：101-103. （In Chinese）

[4]NGUYEN T T An improved algorithm for frequent patterns mining problem[C]//Proceedings of the International Symposium on Computer Communication Control and AtomationTainan，2010：503-507.

[5]郭宇紅， 童云海， 唐世渭基于FPTree的反向頻繁項(xiàng)集挖掘[J]軟件學(xué)報(bào)， 2008，19（2）：338-350

GUO Yuhong， TONG Yunhai， TANG Shiwei Inverse frequent itemset mining based on FPtree[J]Journal of Software， 2008，19（2）：338-350 （In Chinese）

[6]ZENG B， JIANG X L， ZHAO W The improvement of weighted association rules arithmetic based on FPtree[C]//Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering Chengdu，2010：549-552.

[7]JALAN S， SRIVASTAVA A， SHARMA G KA nonrecursive approach for FPtree based frequent pattern generation[C]//2009 IEEE Student Conference on Research and Development （SCOReD） UPM Serdang，2009：160-163.

[8]ADNAN M， ALHAJJ R A bounded and adaptive memorybased approach to mine frequent patterns from very large databases[J] IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2011，41（1）： 154-172.

[9]趙強(qiáng)利，蔣艷凰，徐明 基于FPTree的快速選擇性集成算法[J] 軟件學(xué)報(bào)，2011，22（4）：709-720.

ZHAO Qiangli， JIANG Yanhuang， XU Ming Fast ensemble pruning algorithm based on FPtree[J] Journal of Software，2011，22（4）：709-720（In Chinese）

[10]范明，李川在FP樹中挖掘頻繁模式而不生成條件FP樹[J]計(jì)算機(jī)研究與發(fā)展，2003，40（8）： 1216-1222

FAN Ming， LI ChuanMining frequent patterns in an FPtree without conditional FPtree generation[J]Journal of Computer Research and Development， 2003， 40（8）： 1216-1222 （In Chinese）

[11]譚軍，卜英勇，楊勃一種單遍掃描頻繁模式樹結(jié)構(gòu)[J]計(jì)算機(jī)工程，2010，36（14）：32-33.

TAN Jun，BU Yingyong，YANG Bo Singlepass frequent pattern tree structure[J]Computer Engineering， 2010， 36（14）： 32-33（In Chinese）

[12]郭耀煌，劉家誠(chéng)，劉常青， 等 格序決策[M] 上海：上海科學(xué)技術(shù)出版社， 2003.