基于改进FP-tree的最大频繁项目集挖掘算法  

Mining algorithm for maximal frequent itemsets based on improved FP-tree

作　　者：马丽生[1] 姚光顺[1] 杨传健[1] 

机构地区：[1]滁州学院计算机与信息工程学院,安徽滁州239000

出　　处：《计算机应用》2012年第2期326-329,共4页journal of Computer Applications

基　　金：安徽省高校省级自然科学研究项目(KJ2010B421;KJ2011Z276);安徽省高校省级优秀青年人才基金项目(2010SQRL137;2011SQRL123)

摘　　要：针对已有算法为了减少PF-tree中路径被重复遍历的次数,需要保存FP-tree中所有频繁1-项集的条件模式基的问题,对FP-tree的数据结构进行修改,使得只需要保存FP-tree中每个叶子节点的父节点到根节点路径上项目组成的条件模式基,降低了保存条件模式基的存储空间开销。在分析最大频繁项目集挖掘算法中搜索空间以及数据表示方法的基础上,通过理论分析和证明,设计了剪枝策略和压缩策略,缩小了算法搜索空间,压缩了FP-tree的规模,提高了算法的执行效率。最后将新算法分别与NHTFPG算法、FpMAX算法进行对比,验证算法的正确性和有效性。实验结果表明,新算法保存FP-tree条件模式基所需要的存储空间不到NHTFPG算法的50%,执行效率比FpMAX算法提高了2～3倍。In order to reduce the repeated traversal times of path in the FP-tree, the conditional pattern bases of all frequent 1-itemsets in the FP-tree need to be saved in the existing algorithms. Concerning this problem, in the new algorithm, the data structure of FP-tree was improved that only the conditional pattern bases were saved which were constituted by the items in the path from every leaf node＇ parents to the root in the FP-tree, and the storage space of the conditional pattern bases was reduced. After studying search space and the method of data representation in the algorithm for mining maximal frequent itemsets, the pruning and compression strategies were developed through theoretical analysis and verification, which could decrease the search space and the scale of FP-tree. Finally, the new algorithm was compared with NHTFPG algorithm and FpMAX algorithm respectively in terms of accuracy and efficiency. The experimental results show that the new FP-tree algorithm saves the required conditions for model-based storage space more than 50% than NHTFPG algorithm, and the efficiency ratio improves be 2 to 3 times than FpMAX algorithm.

关 键 词：频繁项目集 最大频繁项目集 条件模式基 项头表 剪枝策略 压缩策略 

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