【摘要】 FP-growth算法是目前较高效的频繁模式挖掘算法之一.它只需扫描数据库两次,而且不需要产生和测试候选集,避免了这些费时的工作,因此该算法具有较高的效率.然而,FP-growth算法需要递归地生成大量的条件FP-树,这耗费了大量的存储空间和时间.综合已有的几项优势技术,提出了一种频繁模式挖掘算法CFPmine.一是采用了基于压缩FP-树的约束子树的挖掘方法,避免在挖掘过程中生成条件FP-树,减少内存占用;二是采用基于数组的技术,减少FP-树的遍历时间,提高算法的效率.另外,在算法中还实现了统一的内存管理.实验结果表明,CFPmine是一个高效的频繁模式挖掘算法,其性能优于Apriori,Eclat和FP-growth算法,而需要的内存却少于FP-growth算法.更多还原

【Abstract】 FP-growth algorithm is an efficient algorithm for mining frequent patterns. It scans database only twice and does not need to generate and test the candidate sets that is quite time consuming. The efficiency of the FP-growth algorithm outperforms previously developed algorithms. But, it must recursively generate huge number of conditional FP-trees that requires huge volume of memory and costs a lot of time.In this paper, it is presented an algorithm, CFPmine, which is inspired by several previous works. CFPmine algorithm combines several advantages of existing techniques. One is using constrained subtrees of a compact FP-tree to mine frequent pattern, so that it is doesn’t need to construct conditional FP-trees in the mining process and reduces the memory consume. Second is using an array-based technique to reduce the traverse time to the CFP-tree. And a unified memory management is also implemented in the algorithm. The experimental evaluation shows that CFPmine algorithm is a high performance algorithm. It outperforms Apriori, Eclat and FP-growth and requires less memory than FP-growth.更多还原