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

针对并行MRPrePost(parallel prepost algorithm based on MapReduce)频繁项集挖掘算法在大数据环境存在运行时间长、内存占用量大和节点负载不均衡的问题,提出一种基于DiffNodeset的并行频繁项集挖掘算法(parallel frequent itemsets mining using DiffNodeset,PFIMD).该算法首先采用一种数据结构DiffNodeset,有效地避免了N-list基数过大的问题;此外提出一种双向比较策略(2-way comparison strategy,T-wcs),以减少两个DiffNod-eset在连接过程中的无效计算,极大地降低了算法时间复杂度;最后考虑到集群负载对并行算法效率的影响,进一步提出了一种基于动态分组的负载均衡策略(load balancing strategy based on dynamic grouping,LBSBDG),该策略通过将频繁1项集F-list中的每项进行均匀分组,降低了集群中每个计算节点上PPC-Tree树的规模,进而减少了先序后序遍历PPC-Tree树所需的时间.实验结果表明,该算法在大数据环境下进行频繁项集挖掘具有较好的效果.

Research on parallel frequent itemset mining algorithm based on MapReduce

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.