基于Fp-growth的分布式并行挖掘算法

長(zhǎng)沙南方職業(yè)學(xué)院 劉喜蘋 黃國(guó)芳 劉雅筠

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

0 引言

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

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

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

1 DFp-growth算法

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

圖1 分布式并行架構(gòu)Fig.1 Distributed parallel architecture

1.1 DFp-growth算法描述

如圖1所示。

(1)服務(wù)器S1在確保頻繁項(xiàng)集不變的情況下,利用數(shù)據(jù)鏈表將數(shù)據(jù)集分解為多個(gè)子集,設(shè)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各項(xiàng)數(shù)據(jù)鏈表的生成Fig.3 The generation of the data link list of data set D

(2)將各項(xiàng)數(shù)據(jù)鏈表刪除時(shí)導(dǎo)出即可得到各項(xiàng)的數(shù)據(jù)子集。

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

(4)當(dāng)所有數(shù)據(jù)集子集的頻繁項(xiàng)集、依次挖掘出來(lái)后,服務(wù)器S1合并這些約束頻繁項(xiàng)集便可得到數(shù)據(jù)集的所有頻繁項(xiàng)集,結(jié)束挖掘過(guò)程。

1.2 偽碼說(shuō)明

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

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

{

服務(wù)器取出數(shù)據(jù)鏈表組中第一項(xiàng)事務(wù)組Vi導(dǎo)出成數(shù)據(jù)集子集Di

服務(wù)器將第一項(xiàng)事務(wù)組Vi的頭元素去除

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

引用

[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的頻繁項(xiàng)目集并行挖掘算法[J].計(jì)算機(jī)工程與應(yīng)用,2014(2):103-106.

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