基于MapReduce的并行频繁项集挖掘算法研究  

Research on parallel frequent itemset mining algorithm based on MapReduce

作　　者：刘卫明[1] 张弛 毛伊敏[1] Liu Weiming;Zhang Chi;Mao Yimin(School of Information Engineering Jiangxi University of Science&Technology,Ganzhou Jiangxi 341099,China)

机构地区：[1]江西理工大学信息工程学院,江西赣州341099

出　　处：《计算机应用研究》2021年第3期689-695,共7页Application Research of Computers

基　　金：国家自然科学基金资助项目(41562019);国家重点研发计划资助项目(2018YFC1504705)。

摘　　要：针对并行MRPrePost(parallel prepost algorithm based on MapReduce)频繁项集挖掘算法在大数据环境存在运行时间长、内存占用量大和节点负载不均衡的问题,提出一种基于DiffNodeset的并行频繁项集挖掘算法(parallel frequent itemsets mining using DiffNodeset,PFIMD)。该算法首先采用一种数据结构DiffNodeset,有效地避免了N-list基数过大的问题;此外提出一种双向比较策略(2-way comparison strategy,T-wcs),以减少两个DiffNodeset在连接过程中的无效计算,极大地降低了算法时间复杂度;最后考虑到集群负载对并行算法效率的影响,进一步提出了一种基于动态分组的负载均衡策略(load balancing strategy based on dynamic grouping,LBSBDG),该策略通过将频繁1项集F-list中的每项进行均匀分组,降低了集群中每个计算节点上PPC-Tree树的规模,进而减少了先序后序遍历PPC-Tree树所需的时间。实验结果表明,该算法在大数据环境下进行频繁项集挖掘具有较好的效果。Aiming at the problem of excessive time,space complexity and unbalanced load for each node based on the parallel frequent itemset mining algorithm MRPrePost,this paper proposed an optimization parallel frequent itemset mining algorithm based on MapReduce,named PFIMD.Firstly,this algorithm adopted a data structure called DiffNodeset,which effectively avoided the defect that the N-list cardinality got very large in the MRPrePost algorithm.Secondly,in order to reduce the time complexity of this algorithm,it designed the T-wcs to avoid the invalid calculation in the procession of two DiffNodesets connection.Finally,considering the impact of cluster load on the efficiency of parallel algorithm,it proposed the LBSBDG,which decreased the size of PPC-Tree on each computing node and reduced the amount of time required to traverse the PPC-Tree by evenly grouping each item in the F-list.The experimental results show that the modified algorithm has better performance on mining frequent itemset in a big data environment.

关 键 词：DiffNodeset数据结构 MAPREDUCE T-wcs策略 LBSBDG策略 频繁项集挖掘 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]