Abstract: PFP_Growth algorithm is the parallelization of FP_Growth algorithm on the Hadoop platform based on MapReduce. The algorithm does not consider the balance of the load while grouping the transaction set, which causes the time inconsistency of different nodes to accomplish the tasks and even a bigger difference. Thus, it reduces the efficiency of the algorithm. To improve the efficiency of the algorithm, this paper proposes a Spark-based RPFP algorithm, which optimizes PFP_Growth algorithm through balancing the groups and reducing the time complexity. To balance the group, the large load is placed into the group with the smallest total load. The address of the element is fast accessed by adding a Hash table to the head table, which reduces the time complexity. Experimental results show that RPFP algorithm effectively improves the mining efficiency of the frequent itemsets.

Key words: FP_Growth algorithm, frequent itemset mining, load balance, head table, Spark

摘要： PFP_Growth算法是FP_Growth算法在Hadoop平台上基于MapReduce的并行化，该算法在分组过程中没有考虑负载均衡问题，导致各个节点完成任务时间不一致，甚至相差很大，从而降低了算法的执行效率。为了提高算法的执行效率，提出了一种基于Spark的RPFP算法，该算法对PFP_Growth算法在均衡分组和降低时间复杂度两方面进行优化，通过把负载大的项放在负载总和最小的组里面实现均衡分组，通过在链头表结构中加入一张哈希表达到快速访问元素地址的目的，从而降低时间复杂度。实验结果表明，RPFP通过优化PFP算法，有效提高了频繁项集的挖掘效率。

关键词: FP_Growth算法, 频繁项集挖掘, 负载均衡, 链头表结构, Spark