采用N-list结构的混合并行频繁项集挖掘算法

Hybrid Parallel Frequent Itemsets Mining Algorithm by Using N-List Structure

针对大数据环境下并行MRPrePost频繁项集挖掘算法中存在计算节点负载不均衡,N-list合并效率低以及冗余搜索等问题,提出了基于N-list结构的混合并行频繁项集挖掘算法HP-FIMBN。首先,设计负载量估计函数(LE)来计算出频繁1项集F-list中每一项的负载量,同时提出基于贪心策略的分组方法(GM-GS)将F-list中的每一项根据其负载量进行均匀分组,既解决了数据划分中计算节点负载不均衡的问题,又降低了集群中各节点上子PPC-Tree树的规模;其次,提出预先放弃策略(EAS),该策略不仅能有效避免合并过程中的无效计算,而且不需要遍历初始N-list结构就能得到最终的N-list,极大地提高了N-list结构的合并效率;最后,采用集合枚举树作为搜索空间,并提出超集等价剪枝策略(SES)来避免挖掘过程中的冗余搜索,生成最终的挖掘结果。实验结果表明,该算法在大数据环境下进行频繁项集挖掘具有较好的效果。

Aiming at the problem of unbalanced load,bad efficiency of N-list merge and redundant search for each node based on parallel frequent itemset mining algorithm MRPrePost(parallel PrePost algorithm based on MapReduce),this paper proposes a hybrid parallel frequent itemset mining algorithm based on N-list(HP-FIMBN).Firstly,a load estimation function(LE)is designed to calculate the load of each item in F-list,and a grouping method based on greedy strategy(GM-GS)is proposed,which not only deals with the problem of unbalanced load in the process of data partitioning,but also decreases the size of sub-PPC-tree on local node.Secondly,in order to accelerate the completion of the merging of two N-list structures,it designs an early abandon strategy(EAS),which can not only efficiently avoid invalid calculations in the merging process,but also does not need to traverse the initial N-list structure to get the final result.Finally,the set-enumeration tree is adopted as the search space,a superset equivalent strategy(SES)is proposed to avoid redundant search in the mining process and the final mining results are generated.Experimental results show that the modified algorithm has better performance on mining frequent itemsets in big data environment.