方向 张功萱

摘 要： 随着数据量的增大，FP?Growth算法压缩数据思想的优势就体现出来，基于MapReduce框架的PFP?Growth算法实现该算法在Hadoop平台上的并行化，但是MapReduce框架每次对作业进行操作都要将中间结果输出存储到磁盘，影响算法的效率。为了提高关联挖掘的效率，基于Spark平台，运用均衡分组的思想对该算法进行改进，同时在对具有很长前缀情况进行共享前缀的拆分，通过4个步骤使IPFP?Growth算法在Spark上实现。实验结果表明在Spark平台上优化过后的算法在性能上要优于PFP?Growth算法。

关键词： 并行化； Spark； 关联挖掘； PFP?Growth

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2016）08?0009?05

Optimization of parallel FP?Growth algorithm based on Spark

FANG Xiang， ZHANG Gongxuan

（School of Computer Science and Engineering， Nanjing University of Science and Technology， Nanjing 210094， China）

Abstract：The advantage of the FP?Growth algorithm for compressing data is reflected with the increasing of the data size. With the MapReduce framework， the PFP?Growth algorithm can be parallelized on the Hadoop platform. However， when processing tasks with the MapReduce framework， the intermediate results need to be written to the disk， which will affect the efficiency of the algorithm. Therefore， based on Spark platform， this algorithm was improved according to the concept of balanced grouping to improve the efficiency of association mining. In addition， if there is a long prefix， the improved algorithm will split the shared prefix. The IPFP?Growth is implemented in Spark through four steps. The experimental results show that the performance of the algorithm optimized in Spark is superior to that of the PFP?Growth algorithm.

Keywords：parallelization； Spark； association mining； PFP?Growth

0 引 言

由于频繁项挖掘Apriori算法需要频繁的访问数据库，造成了很大的开销，Han等人在2000年提出了一种基于内存存储结构的挖掘算法FP?Growth[1]，它将数据库所有的事务压缩到一个FP?Tree数据结构中使整个数据库能够保存在内存中，只需要访问两次数据库就可以完成频繁项的挖掘。Li等人在2008年基于MapReduce框架实现了该算法的并行化即PFP?Growth算法[2]。但是MapReduce框架处理数据时会造成巨大的I/O开销，因为每一次MapReduce过程就是对磁盘进行一次读/写操作，其中shuffle过程为了容错还需要将中间结果存储到磁盘，增加了计算的时间，影响算法的效率。由于数据量的不断增加，传统的数据挖掘算法不能充分的发挥算法的效率，分布式并行处理是挖掘大规模数据的理想解决方案，文献[3]就是利用分布式来解决频繁项集的挖掘。文献[4?6]基于MapReduce框架对该算法的并行化实现，文献[7]从数据压缩的结构上考虑提出了一种使用位存储来进行挖掘频繁项，文献[8]在原算法的基础上添加了负载均衡的思想，对算法的性能有一定的提升。……