長沙南方職業(yè)學院 劉喜蘋 黃國芳 劉雅筠

Fp-growth算法單機運算占用內(nèi)存大、且耗時耗空間,挖掘大數(shù)據(jù)集時運算效率差。本文提出了一種基于Fp-growth的面向大數(shù)據(jù)集的分布式并行關聯(lián)規(guī)則挖掘算法-DFp-growth算法(Distributed Fp-growth)。該算法在確保頻繁項集挖掘數(shù)目不變的情況下利用數(shù)據(jù)鏈表將大數(shù)據(jù)集分解成多個子集,然后對分解得到的各個數(shù)據(jù)集子集用分布式并行方式進行挖掘。實驗結果表明,數(shù)據(jù)集很大時,DFp-growth算法的運行速度比Fpgrowth快,而且數(shù)據(jù)集越大,并行計算節(jié)點越多,運算速度越快,分布并行運算的效率越高。但是當計算節(jié)點大到一定程度時,運算速度不增反減。

0 引言

關聯(lián)規(guī)則挖掘算法很多,最經(jīng)典的有Apriori[1]和Fpgrowth[2]等算法。Fp-growth雖然效率比Apriori要高,但由于需要在內(nèi)存中創(chuàng)建Fp-樹,占用內(nèi)存大、耗時耗空間,所以挖掘大數(shù)據(jù)集時運算效率差。

為了提高Fp-growth算法的挖掘效率,分布式并行挖掘一直是研究熱點。文獻[3]提出基于Fp-growth的Multiple Local Frequent Pattern Tree(MLFPT)算法,它是在共享內(nèi)存的有64個處理器的SGI系統(tǒng)上實現(xiàn)的。文獻[4]提出了一種在普通分布PC機集群上的進行分布式并行計算的Fp-growth算法。文獻[5]提出了基于Jumbo框架的并行Fp-growth算法。文獻[6]提出了一種基于Map/Reduce模型的Fp-growth并行挖掘算法FPPM。文獻[7]創(chuàng)建了垂直FP樹(VFP)的格式來存放數(shù)據(jù),并用任務并行的方式進行分布式挖掘。

以往的Fp-growth改進算法單機運算時,占用內(nèi)存大、且耗時耗空間。而分布式并行運算時,并行子任務的分解方式差,以至于挖掘大數(shù)據(jù)集時,挖掘效率差。本文提出一種基于Fp-growth算法的面向大數(shù)據(jù)集的分布式并行關聯(lián)規(guī)則挖掘算法DFp-growth算法(Distributed Fp-growth)。

1 DFp-growth算法

新算法的主要思想是利用多個計算機節(jié)點分布式并行挖掘大型數(shù)據(jù)庫的關聯(lián)規(guī)則,如圖1所示。新算法在確保頻繁項集挖掘數(shù)目不變的情況下利用數(shù)據(jù)鏈表將數(shù)據(jù)集分解成頻繁1-項集的項總數(shù)個數(shù)據(jù)集子集,然后分別對各個數(shù)據(jù)集子集用Fp-growth算法分布式并行地進行挖掘,得到各個子集的頻繁項集。最后合并各個子集的頻繁項集便得到數(shù)據(jù)集的所有頻繁項集。

圖1 分布式并行架構Fig.1 Distributed parallel architecture

1.1 DFp-growth算法描述

如圖1所示。

(1)服務器S1在確保頻繁項集不變的情況下,利用數(shù)據(jù)鏈表將數(shù)據(jù)集分解為多個子集,設min_sup=40%,分解的方式如圖2和圖3所示。

圖2 數(shù)據(jù)集D數(shù)據(jù)鏈表組的生成Fig.2 The generation of data linked list group of data set D

圖3 數(shù)據(jù)集D各項數(shù)據(jù)鏈表的生成Fig.3 The generation of the data link list of data set D

(2)將各項數(shù)據(jù)鏈表刪除時導出即可得到各項的數(shù)據(jù)子集。

(3)用多個客戶端計算節(jié)點,分別對各個數(shù)據(jù)集子集分布式并行地進行頻繁項集挖掘,挖掘過程如下:1)服務器將數(shù)據(jù)集分解后,將數(shù)據(jù)集子集動態(tài)分配發(fā)送給空閑的客戶端。2)空閑客戶端Ck得到數(shù)據(jù)子集后,將狀態(tài)設為忙碌,并重新構成FP-樹,利用Fp-growth算法進行頻繁項集挖掘。3)Ck將挖掘出的頻繁項集發(fā)送給服務器端,并將狀態(tài)改為空閑,等待下一次任務。

(4)當所有數(shù)據(jù)集子集的頻繁項集、依次挖掘出來后,服務器S1合并這些約束頻繁項集便可得到數(shù)據(jù)集的所有頻繁項集,結束挖掘過程。

1.2 偽碼說明

服務器S1將數(shù)據(jù)集D排序后,將支持度小于最小支持度的項刪除,放入數(shù)據(jù)鏈表組中。

for(數(shù)據(jù)鏈表組中的每一項Vi,i=(1…..數(shù)據(jù)集D的頻繁1-項集的項總數(shù)))

{

服務器取出數(shù)據(jù)鏈表組中第一項事務組Vi導出成數(shù)據(jù)集子集Di

服務器將第一項事務組Vi的頭元素去除

將去掉頭元素的事務根據(jù)Vi中后繼元素的不同,迭加到其他項的事務組中

形成新數(shù)據(jù)鏈表組

2 實驗結果

為了分析比較Fp-growth算法和DFp-growth算法的性能,利用C語言實現(xiàn)了Fp-growth算法和DFpgrowth算法,并在PetiumⅣ2.8G、內(nèi)存1.5G的環(huán)境下的進行了仿真實驗。實驗數(shù)據(jù)是WebDocs數(shù)據(jù)集,實驗結果如圖4,圖5所示。圖4和圖5分別是從數(shù)據(jù)集WebDocs中抽取了500MB包含58萬條左右的數(shù)據(jù)和1GB包含119萬條左右的數(shù)據(jù),在最小支持度設為(30%)時進行測試所得的結果。

圖4 DFp-growth算法在WebDocs數(shù)據(jù)集上(500M)的測試結果Fig.4 Test results of the DFp-growth algorithm on the WebDocs data set (500M)

圖5 在DFp-growth算法WebDocs數(shù)據(jù)集上(1G)的測試結果Fig.5 Test results on the DFp-growth algorithm WebDocs data set (1G)

(1)Fp-growth算法挖掘WebDocs數(shù)據(jù)集(500M)時,所需時間是11,452s,而DFp-growth算法的運行速度比Fp-growth快,而且并行計算節(jié)點越多,運算速度越快,測試結果如圖4所示。但由于WebDocs數(shù)據(jù)集上(500M)不是很大的數(shù)據(jù)集,所以計算節(jié)點的增加對運算速度影響不大。

(2)Fp-growth算法挖掘WebDocs數(shù)據(jù)集(1G)時,因所需內(nèi)存太大了,所以Fp-growth算法無法計算出結果,而Dis-Fp-growth算法可以運行出來,測試結果如圖5所示。而且因WebDocs數(shù)據(jù)集上(1G)是較大的數(shù)據(jù)集,所以計算節(jié)點的增加對運算速度影響大,分布運算的效率高。

(3)通過圖4和圖5可知,數(shù)據(jù)集越大,分布計算節(jié)點越多,DFp-growth算法分布并行運算的效率越高,運算速度越快。但是當計算節(jié)點大到一定程度時,運算速度不增反減。

3 結語

本文在Fp-growth算法的基礎上,提出了一種分布式并行關聯(lián)規(guī)則挖掘算法——DFp-growth算法。該算法將大型數(shù)據(jù)集利用數(shù)據(jù)鏈表分解成多個子集,然后對分解得到的各個數(shù)據(jù)集子集用Fp-growth算法進行分布式并行挖掘,得到含有各個子集的頻繁項集。最后合并各個子集的頻繁項集便得到數(shù)據(jù)集的所有頻繁項集。實驗結果表明DFp-growth算法所采用的數(shù)據(jù)鏈表劃分子集策略克服了Fp-growth算法對大型數(shù)據(jù)集進行挖掘時,占用內(nèi)存大,運行速度慢的不足。且DFp-growth算法采用分布式并行挖掘也極大地提高了挖掘效率。測試結果如圖4和圖5所示,測試結果表明數(shù)據(jù)集越大,分布計算節(jié)點越多,DFpgrowth算法分布并行運算的效率越高,運算速度越快。但是當計算節(jié)點大到一定程度時,運算速度不增反減。

引用

[1] Rakesh Agrawal,Tomasz Imielienski,and Arum Swami.Mining Association Rules between Sets of Items in large Databases[A].Proc Conf on Management of Data[C].ACM Press,New York,NY,USA 1993.

[2] Jiawen Han,Jian Pei,and Yiwen Yin.Mining frequent patterns without candidate generation[A].In Proc.2000 ACM-SIGMOD Int.Conf.Management of Data(SIGMOD 2000) [C].New York:ACM Press,2000.

[3] ZAIANE O R,EI-HAJJ M,LU P.Fast parallel association rule mining without candidate Generation[A].Technical Report TR01-12,Department of Computing Science,University of Alberts[C],Canada,2001.

[4] Pramudiono I,Kitsuregawa M.Parallel FP-Growth on PC cluster[A].In:proceeding of Advances in Knowledge Discovery and Data Mining[C].Springer Berlin Heidelberg,2003.

[5] S.Groot,M.Kitsuregawa.Jumbo:Beyond MapReduce for workload balancing[A].In:Proceedings of 36th International Conference on Very Large Data Bases[C].Singapore,Sep.2010.

[6] 章志剛,吉根林.一種基于Fp-growth的頻繁項目集并行挖掘算法[J].計算機工程與應用,2014(2):103-106.

[7] 徐杰,李云,劉博,等.基于垂直FP樹的并行頻繁項集挖掘[J].計算機與數(shù)字工程,2012,40(10):12-15.