陆 可 桂 伟 江雨燕 杜萍萍

(安徽工业大学管理科学与工程学院 安徽 马鞍山 243000)

基于Spark的并行FP-Growth算法优化与实现

陆 可 桂 伟 江雨燕 杜萍萍

(安徽工业大学管理科学与工程学院 安徽 马鞍山 243000)

频繁模式挖掘作为模式识别的重要问题，一直受到研究者的广泛关注。FP-Growth算法因其高效快速的特点，被大量应用于频繁模式的挖掘任务中。然而，该算法依赖于内存运行的特性，使其难以适应大规模数据计算。针对上述问题，围绕大规模数据集下频繁模式挖掘展开研究，基于Spark框架，通过对支持度计数和分组过程的优化改进了FP-Growth算法，并实现了算法的分布式计算和计算资源的动态分配。运算过程中产生的中间结果均保存在内存中，因此有效减少数据的I/O消耗，提高算法的运行效率。实验结果表明，经优化后的算法在面向大规模数据时要优于传统的FP-Growth算法。

频繁模式挖掘 FP-Growth算法 分布式计算 Spark框架

0 引 言

R.Agrawal提出Apriori算法用于解决关联规则的挖掘问题后[1]，频繁模式的挖掘就一直受到广泛关注。之后，Han提出的FP-Growth算法由于其自身在计算效率上的优势[2]，得到了更为广泛的运用。然而，随着数据规模的不断增大，该算法在实际运用中也存在一些尚待改进的问题。一方面，FP-Growth算法在统计各元素项的支持度计数过程中会消耗大量时间；另一方面，大规模数据集的维度跨越过大，导致算法构建的频繁模式树(FP-Tree)难以存入内存，影响了算法的运行。因此，大规模数据集上如何有效挖掘关联规则成为近年来研究人员关注的重点。……