基于FP-Tree含正负项目的频繁项集挖掘算法  

Mining Frequent Itemsets with Positive and Negative Items Based on FP-Tree

作　　者：张玉芳[1] 熊忠阳[2] 彭燕[3] 赵鹰[1] 

机构地区：[1]重庆大学计算机学院,重庆400030 [2]重庆大学电气工程博士后流动站,重庆400030 [3]华为深圳技术有限公司,深圳518129

出　　处：《模式识别与人工智能》2008年第2期246-253,共8页Pattern Recognition and Artificial Intelligence

基　　金：中国博士后科学基金资助项目(No.20070420711)

摘　　要：借鉴 FP_growth 算法中频繁模式树的思想,提出包含正负项目的频繁模式树的构造方法.通过对该频繁模式树进行模式扩展,可以挖掘出包含正负项目的频繁项集.该算法与直接使用 FP_growth 算法挖掘含负项目的频繁项集相比,无需对原始数据库进行负项目的扩展,也不用再构造并销毁额外的数据结构,只需在原始的频繁模式树上修改,在时间和空间的开销上都具有一定优势.实验表明,本文算法比现有的同类挖掘算法和直接 FP_growth 算法具有更好的效率.Using the concept of frequent pattern tree of FP_growth, a new frequent pattern tree containing positive and negative items is constructed. The frequent itemsets with positive and negative items are mined through extending frequent patterns on the tree. Compared with the algorithms of directly using FP_growth, the proposed algorithm has no requirement for growing negative item to original database as well as the construction or destruction of additional data structures. Only some modifications to the original frequent pattern tree are needed. Therefore it has certain advantages in time and space costs. Experiments show that the algorithm has better efficiency than the existing mining algorithms and algorithms of directly using FP_growth.

关 键 词：负项目 关联规则 频繁模式树 模式扩展 频繁项集 

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