基于Spark的并行频繁项集挖掘优化算法的研究

作     者：吴斌 

作者单位：江西理工大学 

学位级别：硕士

导师姓名：毛伊敏

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：大数据 Spark框架 并行频繁项集挖掘 FP-Growth算法 

摘      要：频繁项集挖掘作为数据挖掘的主要手段之一,其动机是为了寻找数据中潜在的价值,帮助企业和机构调整工艺生产的进度、提高产品的质量、作出更有效的策略以满足客户的需求。近年来,随着各行业应用频繁项集挖掘算法,其问题也逐渐显露出来,这些算法可以在数据规模较小的时候显现出优势,而由于存储和计算能力的上限,当数据量达到G级甚至更高的水平时,这些算法并不适合对海量数据进行挖掘。因此,将改进的频繁项集挖掘算法与分布式计算模型相结合,从而实现并行计算,并行计算的思想也因此成为当前研究的主要方向。目前已提出的基于Spark的FP-Growth算法相较于传统FP-Growth算法,虽然解决了需要对数据库进行多次扫描的问题,且结合Spark框架带来的并行化性能使得频繁项集挖掘效率得到了提升,但仍然面临如何有效提高创建条件FP-tree时空效率、如何降低节点间的通信开销、如何解决冗余搜索以及如何动态设置支持度阈值的问题。基于此,本文主要研究工作如下:针对基于Spark的FP-Growth算法在大数据环境下存在创建条件FP-tree时空效率低,节点间通信开销大,以及冗余搜索等问题,提出了基于Spark的并行频繁项集挖掘算法。首先,该算法提出非负矩阵分解策略,通过提供支持度计数查询和分解储存支持度计数的矩阵,解决了创建条件FP-tree的时空效率低的问题;其次,提出基于遗传算法的分组策略,均衡分配频繁1项集至各节点之间,解决了节点间的通信开销大的问题;最后,提出高效缩减树结构策略,缩减FP-tree树结构,解决了冗余搜索的问题。实验结果验证了该算法的可行性以及相较于其它挖掘算法的性能优势,所提算法能有效适应各种数据的频繁项集挖掘。针对大数据环境下基于Spark的FP-Growth算法存在支持度阈值无法动态设置,节点间通信开销大,以及冗余搜索等问题。提出基于Spark和遗传算法的并行频繁项集挖掘算法。首先,该算法提出基于动态规划的寻优策略,获得最优的支持度阈值,解决了支持度阈值无法动态设置的问题;其次,提出基于负载估计函数的分组策略,均匀分组频繁1项集,缩减各分组生成的FP-tree结构,解决了节点间的通信开销大的问题;最后,提出超团模式剪枝策略,修剪FP-tree,解决了冗余搜索的问题。实验结果验证了该算法的可行性以及相较于其它挖掘算法的性能优势,所提算法能有效适应各种数据的频繁项集挖掘。