基于FP-Tree的频繁闭合项目集挖掘算法的研究

目前频繁闭合项目集挖掘算法有很多,例如CLOSET1]。CLOSET以FP-Growth为基础,采用FP-Tree来表示模式支持集,通过深度优先搜索来挖掘频繁闭合模式。其困难是,递归构造“条件FP-Tree”的CPU开销和存储开销很大。为解决上面的问题,论文提出一种基于FP-Tree和COFI-Tree的频繁闭合项目集挖掘算法,在该算法中引用了COFI-Tree结构,COFI-Tree无需递归地构造“条件FP-Tree”,并且某一时刻只有一个频繁项的COFI-Tree在内存,所以大大减少了内存消耗。通过实验证明:当挖掘大型数据库时,在执行时间方面,该算法比其它算法更有效。

Frequent Closed Itemsets Mining Algorithm Based on FP-Tree

There are many mining algorithms about frequent closed itemsets,such as CLOSET.The CLOSET algorithm based on FP-Growth.It denotes pattern support set by FP-Tree and mines frequent closed itemsets through depth-first approach.But this algorithm has some problems,it builds conditional FP-Tree recursively so that it requires more memory and CPU resources.To solve this problem,this paper proposes a frequent closed itemsets mining algorithm based on FP-tree and COFI-tree and adopts COFI-Tree in this algorithm.The COFI-Tree doesn't need to build conditional FP-Tree recursively.There is only one COFI-Tree in memory at a time,therefore,this new mining algorithm reduces memory usage.The experiment shows that this approach outperforms similar state-of-the-art algorithms when mining extremely large datasets in terms of execution time.