一种基于压缩FP-树的最大频繁项集挖掘算法

A Compressed FP-Tree Based on Algorithm for Mining Maximal Frequent Itemsets

针对基于FP-树挖掘最大频繁项集的算法需要大量的递归调用导致挖掘效率降低的问题,本文提出一种减枝策略并结合FP-树的结构,依据构造Patricia-树的基本原理提出一种PFP-树,将FP-树中满足一定条件的结点进行合并来保存事务数据库,对事务数据库进行进一步压缩以达到降低内存开销和递归调用次数的目的。实验表明,当最小支持度较小时,在执行效率尤其在内存开销方面都有一定的改善。

As to the problem of when mining the maximal frequent itemsets based on FP-tree, it need a great lot ofrecursion call to lead to reduce efficiency. This present paper proposed a prune strategy, and proposed a PFP-tree after considering the structure of FP-tree and the principle of Patricia-tree. The PFP-tree is constructed from FP-tree by combining the nodes that satisfy some conditions. Using PFP-tree can achieve more compress storage of the database, so can obtain the purpose of reduce the main memory requirements and the count ofrecursion calls. Experimental results show that this method can achieve the improvement of in efficiency and in the main memory requirement particularly when the minimal support is small.