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

长沙南方职业学院 刘喜苹 黄国芳 刘雅筠

Fp-growth算法单机运算占用内存大、且耗时耗空间,挖掘大数据集时运算效率差。本文提出了一种基于Fp-growth的面向大数据集的分布式并行关联规则挖掘算法-DFp-growth算法(Distributed Fp-growth)。该算法在确保频繁项集挖掘数目不变的情况下利用数据链表将大数据集分解成多个子集,然后对分解得到的各个数据集子集用分布式并行方式进行挖掘。实验结果表明,数据集很大时,DFp-growth算法的运行速度比Fpgrowth快,而且数据集越大,并行计算节点越多,运算速度越快,分布并行运算的效率越高。但是当计算节点大到一定程度时,运算速度不增反减。

0 引言

关联规则挖掘算法很多,最经典的有Apriori[1]和Fpgrowth[2]等算法。Fp-growth虽然效率比Apriori要高,但由于需要在内存中创建Fp-树,占用内存大、耗时耗空间,所以挖掘大数据集时运算效率差。

为了提高Fp-growth算法的挖掘效率,分布式并行挖掘一直是研究热点。文献[3]提出基于Fp-growth的Multiple Local Frequent Pattern Tree(MLFPT)算法,它是在共享内存的有64个处理器的SGI系统上实现的。文献[4]提出了一种在普通分布PC机集群上的进行分布式并行计算的Fp-growth算法。文献[5]提出了基于Jumbo框架的并行Fp-growth算法。文献[6]提出了一种基于Map/Reduce模型的Fp-growth并行挖掘算法FPPM。文献[7]创建了垂直FP树(VFP)的格式来存放数据,并用任务并行的方式进行分布式挖掘。

以往的Fp-growth改进算法单机运算时,占用内存大、且耗时耗空间。而分布式并行运算时,并行子任务的分解方式差,以至于挖掘大数据集时,挖掘效率差。本文提出一种基于Fp-growth算法的面向大数据集的分布式并行关联规则挖掘算法DFp-growth算法(Distributed Fp-growth)。……