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

A PARALLEL FREQUENT ITEMSETS MINING ALGORITHM BASED ON MAPREDUCE

现有FP-growth频繁集挖掘算法在处理大数据时存在时空效率不高的问题,且内存的使用随着数据的增加已经无法满足把待挖掘数据压缩存储在单个内存中,为此,提出一种基于MapReduce模型的频繁项集并行挖掘算法。该算法采用一种基于key/value键值对直接扫描value寻找条件模式基的方式,同时通过在原有FP-tree树节点中新增一个带频繁项前缀的域空间来构建一颗新的条件模式树NFP-tree,使得对一项频繁项的条件模式基进行一次建树一次遍历就可以得到相应的频繁项集。对所提出的算法在Hadoop平台进行了验证与分析,实验结果表明该算法效率较传统FP-growth算法平均提高16.6%。

Existing mining algorithms of FP-growth frequent itemset has low time and space efficiency problem when dealing with large data, and with the data increase the memory usage can no longer satisfy to compress and store the data to be minded in a single memory. Therefore, the paper proposes a MapReduce model-based parallel mining algorithm for frequent itemset. The algorithm adopts a way which directly scans value based on key-value pairs to look for the conditional pattern base. Meanwhile, it also constructs a new condition pattern tree NFP-tree by adding a domain space with frequent item prefix in original FP-tree tree node, and that makes it possible to get the corresponding frequent itemsets by constructing the tree once and traverse once on the condition pattern base of a frequent item. This algorithm is verified and analysed on Hadoop platform, experimental results show that the algorithm is more efficient than the traditional FP-growth algorithm by an average increase of 16.6%.