含正负项目的基于位串频繁项集挖掘算法研究  

Study on association rules with negative items based on bit string

作　　者：张玉芳[1] 熊忠阳[2] 王灿[3] 刘春泳[1] 

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

出　　处：《控制与决策》2010年第1期37-42,共6页Control and Decision

基　　金：教育部留学回国人员启动基金项目(教外司留[2007]1108-10);中国博士后科学基金项目(20070420711)

摘　　要：对频繁模式树中的每个节点引入一个位串存储前缀路径,提出了包含正负项目的频繁模式树的构造方法,它不需要反复遍历节点就可获得包含正负项目的频繁项集.与直接使用FP-growth算法相比,无需对原始数据库进行负项目的扩展,也不用再构造并销毁额外的数据结构,只需在原始的频繁模式树上修改,因而在时空开销上都具有一定的优势.实验表明,所提出的算法比现有的同类挖掘算法和直接FP-growth算法具有更好的效率.A bit string for each node of the frequent pattern tree is imported to store the prefix.A method for constructing frequent pattern tree which contains positive and negative items is proposed,and frequent item sets with negative items are mined through extending frequent patterns on the tree.Comparing to direct using FP-growth algorithms,this algorithm needs not expand negative item to original database,and construct or destruct additional data structures,which only makes some changes on the original frequent pattern tree,so it has certain advantages in time and space costs.Experiments show that the algorithm has better efficiency than the existing similar mining algorithms and direct FP-growth algorithms.

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

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