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

Frequent Closed Itemsets Mining Algorithm Based on FP-Tree

作　　者：陈俊杰[1] 崔晓红[1] 

机构地区：[1]太原理工大学计算机与软件学院,太原030024

出　　处：《计算机工程与应用》2006年第34期169-171,共3页Computer Engineering and Applications

摘　　要：目前频繁闭合项目集挖掘算法有很多,例如CLOSET[1]。CLOSET以FP-Growth为基础,采用FP-Tree来表示模式支持集,通过深度优先搜索来挖掘频繁闭合模式。其困难是,递归构造“条件FP-Tree”的CPU开销和存储开销很大。为解决上面的问题,论文提出一种基于FP-Tree和COFI-Tree的频繁闭合项目集挖掘算法,在该算法中引用了COFI-Tree结构,COFI-Tree无需递归地构造“条件FP-Tree”,并且某一时刻只有一个频繁项的COFI-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.

关 键 词：频繁闭合项目集 FP-TREE COFI-Tree 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]