一种新型的基于Hadoop框架的分布式并行FP-Growth算法
2016-05-10张振友丁铁凡刘鹏飞
张振友,孙 燕,丁铁凡,刘鹏飞
(华北理工大学信息工程学院,河北唐山 063009)
一种新型的基于Hadoop框架的分布式并行FP-Growth算法
张振友,孙 燕,丁铁凡,刘鹏飞
(华北理工大学信息工程学院,河北唐山 063009)
摘 要:针对传统FP-Growth算法在大规模数据环境下存在的挖掘效率低和内存溢出问题,在传统FP-Growth算法的基础上,提出一种新的并行FP-Growth算法,并在分布式计算框架Hadoop 的MapReduce编程模式下实现并行化处理。实验数据表明,并行的FP-Growth算法与传统的FPGrowth算法相比,具有相同数据量下计算时间短,相同时间内处理数据量增大的优点,并在一定条件下解决了大数据挖掘的内存溢出问题。
关键词:并行处理;分布式;数据挖掘;闭频繁项集;Hadoop;FP-Growth
E-mail:youzhenadd@163.com
张振友,孙 燕,丁铁凡,等.一种新型的基于Hadoop框架的分布式并行FP-Growth算法[J].河北工业科技,2016,33(2):169-177.
ZHANG Zhenyou,SUN Yan,DING Tiefan,et al.A novel distributed parallel FP-Growth algorithm based on Hadoop framework[J].Hebei Journal of Industrial Science and Technology,2016,33(2):169-177.
关联规则挖掘的基本算法主要有Apriori算法和FP-Growth算法。1993年,AGRAWAL等在美国IBM Almaden Research Center首先提出了关联规则的概念,用于挖掘顾客交易数据库中的频繁模式。至此,诸多的研究人员对关联规则的挖掘问题进行了大量的研究[1]。AGRAWAL提出了经典的Apriori算法来挖掘数据集中的频繁模式,从而挖掘出数据项集之间的关联规则。为了更好地提高挖掘效率,研究人员提出了基于Hash表的项集计数技术(利用Hash表提高项集计数效率),基于事务压缩的算法(压缩进一步迭代扫描的事务数),基于分区的算法(对原始数据进行划分各找候选项集),基于事务抽样技术的算法(关联挖掘在数据样本上而不是整个数据集上进行)以及动态项集计数的算法(在扫描的不同点添加候选项集)等的改进算法[2]。……
