数据流上近似非可导项集的挖掘算法  

An Approximate Non-Derivable Itemset Mining Algorithm over Data Streams

作　　者：黄崇争[1,2] 李海峰[3] 陈红[1] 

机构地区：[1]中国人民大学信息学院,北京100872 [2]广西建设职业技术学院计算机与信息技术系,南宁530003 [3]中央财经大学信息学院,北京100081

出　　处：《计算机学报》2010年第8期1427-1436,共10页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2008AA01Z120)资助

摘　　要：频繁项集是通过对大规模数据进行挖掘获取的代表数据模式的知识结构.非可导频繁项集作为频繁项集的有效压缩方式,能够高效深入地挖掘海量数据、稠密数据与数据流当中的规律.针对项集在计算界限值时代价昂贵的缺点,提出了近似可导项集的概念,并基于纵向数据格式实现了挖掘算法MANDI,能够提高支持度计算和项集间操作的速度.另外,为了满足数据流实时、快速的特点,讨论并证明了近似可导项集的增量性质,提出了可动态更新的算法UANDI.通过实验验证了两种算法的可行性和有效性.Frequent itemset mining is one of the traditional and important problems in data mining.Non-derivable frequent itemsets are the condensed reprentation of frequent itemsets,and they can not only reduce the memory cost,but also make association rules more understandable for user.Because the bound computations of non-derivable frequent itemsets are high,the authors propose the conception of approximate non-derivable itemsets,and present an approximate non-derivable frequent itemset mining algorithm MANDI based on itemset idlist.In addition,the authors present the stream mining algorithm UNADI,which maintains the negative borders of approximate non-derivable frequent itemsets to conduct efficient incremental mining.The experimental results show that both algorithms are effective and efficient.

关 键 词：近似非可导频繁项集 纵向数据格式 数据流 数据流挖掘 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]