计算机应用 ›› 2012, Vol. 32 ›› Issue (02): 326-329.DOI: 10.3724/SP.J.1087.2012.00326

• 数据库技术 • 上一篇    下一篇

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

马丽生,姚光顺,杨传健   

  1. 滁州学院 计算机与信息工程学院,安徽 滁州 239000
  • 收稿日期:2011-08-10 修回日期:2011-10-07 发布日期:2012-02-23 出版日期:2012-02-01
  • 通讯作者: 马丽生
  • 作者简介:马丽生(1982-),男,山西柳林人,讲师,硕士研究生,主要研究方向为:数据挖掘;
    姚光顺(1982-),男,安徽肥东人,讲师,硕士研究生,主要研究方向为:人工智能;
    杨传健(1979-),女,安徽滁州人,副教授,硕士研究生,主要研究方向为:粗糙集、数据挖掘。
  • 基金资助:
    安徽省高校省级自然科学研究项目(KJ2010B421,KJ2011Z276);安徽省高校省级优秀青年人才基金项目(2010SQRL137,2011SQRL123)

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

Ma Li-sheng,YAO Guang-shun,YANG Chuan-jian   

  1. College of Computer and Information Engineering, Chuzhou University, Chuzhou Anhui 239000, China
  • Received:2011-08-10 Revised:2011-10-07 Online:2012-02-23 Published:2012-02-01
  • Contact: Ma Li-sheng

摘要: 针对已有算法为了减少PF-tree中路径被重复遍历的次数,需要保存FP-tree中所有频繁1-项集的条件模式基的问题,对FP-tree的数据结构进行修改,使得只需要保存FP-tree中每个叶子节点的父节点到根节点路径上项目组成的条件模式基,降低了保存条件模式基的存储空间开销。在分析最大频繁项目集挖掘算法中搜索空间以及数据表示方法的基础上,通过理论分析和证明,设计了剪枝策略和压缩策略,缩小了算法搜索空间,压缩了FP-tree的规模,提高了算法的执行效率。最后将新算法分别与NHTFPG算法、FpMAX算法进行对比,验证算法的正确性和有效性。实验结果表明,新算法保存FP-tree条件模式基所需要的存储空间不到NHTFPG算法的50%,执行效率比FpMAX算法提高了2~3倍。

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

Abstract: 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 〖BP(〗the improved FP-tree could reduc 〖BP)〗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 by 2 to 3 times than FpMAX algorithm.

Key words: frequent itemset, maximal frequent itemset, conditional pattern base, item header table, pruning strategy, compression strategy

中图分类号: