基于格的快速頻繁項集挖掘算法

基金項目：國家自然科學基金資助項目（61072121）；湖南省自然科學基金資助項目（12JJ2035） ；“中央高校基本科研業務費”資助項目

作者簡介：劉彩蘋（1978-），女，湖南邵陽人，湖南大學教師，博士

江西 撫州344000；3.湖南大學 電氣與信息工程學院，湖南 長沙410082）

摘要：隨著數據庫規模的增加或支持度閾值的減少，頻繁模式的數量將以指數形式增長，FPgrowth算法運行的時空效率將大為降低本文提出一種基于格的快速頻繁項集挖掘算法LFPgrowth，算法利用等價關系將原來的搜索空間（格）劃分成若干個較小的子空間（子格），通過子格間的迭代分解，將對網格P（I）的頻繁項集挖掘轉化為對多個子格的并集進行的約束頻繁項集挖掘實驗結果和理論分析表明，在挖掘大型數據庫時，LFPgrowth算法的時間和空間性能均優于FPgrowth算法

關鍵詞：數據挖掘；FP樹；頻繁項集；格

中圖分類號：TP31113文獻標識碼：A

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

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

本文結合大型數據庫本身的特性，在分析FPgrowth算法的基礎上，提出了一種基于格的大型數據庫頻繁模式挖掘算法LFPgrowth實驗和分析表明，在挖掘大型數據庫時，LFPgrowth算法具有較好的時間和空間效率

1基本概念和問題的描述

為方便討論，以事務數據庫為背景設為所有項目的集合，為事務數據庫， 其中每個事務有一個惟一的標識TID表1中的事務數據庫是本文的示例數據庫該數據庫中事務已經按照各項的支持度計數遞增地將各事務中的項重新排列

在事務數據庫中挖掘頻繁項集的問題可以描述為：給定事務數據庫D和最小支持度閾值minsup ，挖掘所有的頻繁項集

由定理3得到以下結論，對網格P（I）的頻繁項集挖掘轉化為對多個子網格的并集進行的約束頻繁項集的挖掘，不會影響頻繁項集完全集的正確輸出

22算法步驟

實現LFPgrowth算法的關鍵是子格（子搜索空間）所對應的事務的迭加，如果復制所有的子格對應的事務進行迭加，時間和空間的效率會非常低為此，可以借鑒Christian Borgelt教授在研究Recursive elimination算法時提出的事務鏈表（transaction list array）來實現迭加

事務鏈表是由一組單向數據鏈表組成，每一個單向數據鏈記錄一個子格P（k）所對應的事務集（以下簡稱為P（k）事務集）的信息，每一個單向數據鏈都包括一個計數器（support counter）和一個指針計數器的值表示P（k）事務集的總數，指針則用于保存P（k）事務集的關聯信息將所有單向數據鏈表按P（k）處理的順序排列，便組成了事務鏈表樣例數據庫的事務鏈表組如圖3所示

當數據庫為海量數據庫時，可將它分解迭加成多個P（k）^進行挖掘，而當某個P（k）^對應的事務很多，依然無法在內存中構造Fp樹時，挖掘就難以順利進行根據定理5可知 P（k）^是格，因此我們可將P（k）^再次進行迭加分解，如果分解后擴展子格依然無法在內存中構造Fp樹時，就再繼續分解直到可以在內存中構造擴展子格的Fp樹為止

3實驗結果和分析

31實驗結果

本節對LFPgrowth算法和FPgrowth算法進行比較，程序代碼均用Visual C++實現實驗在PetiumⅣ28G，內存512M，硬盤80G的PC機上運行實驗結果如圖5～圖7所示

圖5是采用accidents數據庫進行實驗，該數據庫大小為336 M，是比利時國家統計院提供的1991-2000年期間Flanders地區的交通事故數據庫由圖5可知，當最小支持度大于等于05%時，FPgrowth算法的運行速度比LFPgrowth算法略快但是，當最小支持度小于05%時，LFPgrowth算法的運行速度比FPgrowth算法快而且隨著支持度的減少，差別越明顯

圖6是采用bio_train數據庫進行實驗，該數據庫是KDD Cup 2004所提供的關于蛋白質同源性的訓練數據庫該數據庫有145 751行，每行包含有1個塊號、1個試驗號和74個特征值圖6是在事務數據庫大小為664 M條件下，最小支持度從3%減少到005%的兩種算法運行時間的比較，由圖6可知，當最小支持度等于3%時，FPgrowth算法的運行速度比LFPgrowth算法快但是，當最小支持度小于等于1%時，LFPgrowth算法的運行速度比FPgrowth算法快而且隨著支持度的減少，差別越大

32實驗結果分析

FPgrowth算法要將事務數據庫中所有產生頻繁項集的數據壓縮到一棵FP樹中，該樹中存儲的關聯信息從建樹開始到挖掘完畢都完整地保存在內存里，挖掘時又通過遞歸創建條件FPtree生成頻繁模式，條件FPtree個數等于頻繁模式數，所以建樹挖掘的時間和空間開銷都很大，尤其是隨著數據庫規模的增加或支持度閾值的減少而導致頻繁模式的數量以指數形式增長時， FPgrowth算法無法構造基于內存的FP樹，從而導致挖掘失敗而LFPgrowth算法雖然多次迭加子格，但它是在擴展格中構造FPtree，規模比原始的FPtree要小，而且挖掘過程比FPgrowth算法簡單，時間消耗遠小于FPgrowth算法

本文算法不僅時間效率明顯優于FPgrowth算法，而且空間效率也明顯優于FPgrowth算法因為，LFPgrowth算法構建的是基于擴展格的FP樹，其規模遠遠小于在整體事務數據庫上構建的FP樹，而且由以上運行時間效率實驗和分析已表明，LFPgrowth可以在更小的支持度閥度水平上運行，而FPgrowth算法常因耗盡物理內存而無法運行

4結論

提出了一種基于格的快速頻繁項集挖掘算法LFPgrowth這種算法不僅減少了對內存的需求，也較大地提高了挖掘效率，尤其適合挖掘大型數據庫的頻繁項集本文的實驗結果很好地證明了這一點

今后的工作在于進一步的研究如何精簡事務數據鏈表組的結構，進一步提高現有算法的效率，減少對內存的需求同時考慮可將本文格迭加分解的策略和已有的各種分布式頻繁模式挖掘算法結合起來，設計新的基于分布式數據庫的頻繁模式挖掘算法

參考文獻

[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]李也白，唐輝，張淳，等基于改進的FPtree的頻繁模式挖掘算法[J]計算機應用， 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的反向頻繁項集挖掘[J]軟件學報， 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]趙強利，蔣艷凰，徐明 基于FPTree的快速選擇性集成算法[J] 軟件學報，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]計算機研究與發展，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]譚軍，卜英勇，楊勃一種單遍掃描頻繁模式樹結構[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]郭耀煌，劉家誠，劉常青， 等 格序決策[M] 上海：上?？茖W技術出版社， 2003.