颜雪松,-关联规则挖掘综述收稿日期:20011214;修返日期:20020428基金项目:湖北省自然科学基金资助项目(2001ABB006)关联规则挖掘综述*颜雪松,蔡之华,蒋良孝,贺毅(中国地质大学信息工程学院,湖北武汉430074)摘要:介绍了关联规则挖掘的一般概念,并进一步导出它的一般框架;同时对一些典型算法进行了分析和比较,介绍了关联规则的应用;最后展望了关联规则挖掘的未来研究方向。关键词:关联规则;频繁项目集;深度优先遍历;宽度优先遍历中图法分类号:TP3016文献标识码:A文章编号:10113695(2002)11000104SurveyofAssociationRuleMiningYANXuesong,CAIZhihua,JIANGLiangxiao,HEYi(CollegeofInformationEngineering,ChinaUniversityofGeosciences,WuhanHubei430074,China)Abstract:Inthispaperweexplainthefundamentsofassociationruleminingandmoreoverderiveageneralframework.Atthesametimecomparesandanalysessometypicalalgorithms,introducestheapplicationoftheassociationrules.Attheend,viewssomefuturedirectionsinassociationrulegeneration.Keywords:AssociationRule;FrequentItemsets;DFS;BFS1引言面对海量的存储数据,如何从中发现有价值的信息或知识是一项非常艰巨的任务。数据挖掘就是为了满足这种要求而迅速发展起来的。数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。数据挖掘是人工智能和数据库发展相结合的产物,是目前国际上数据库和信息决策系统最前沿的研究方向之一,已引起了学术界和工业界的广泛关注。目前研究的主要目标是发展有关理论、方法和工具,以支持从大量数据中提取有价化的知识和模式。在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。它是由R.Agrawal等人首先提出的。关联规则的一个典型例子就是:90%的客户在购买面包的同时也会购买牛奶,其直观意义为顾客在购买某些商品的时候有多大的倾向会购买另外一些商品。2关联规则的基本概念假设T是事务的集合,在T中的每一个事务都是项目集I的子集。假设C是I的一个子集,我们定义C的支持度如下:(C)=|{t|t!T,Ct}|。(C)表示包含在C中的事务的数目。例如图1所示的事务集。事务的项目集I是{Bread,Beer,Coke,Diaper,Milk}。{Diaper,Milk}的支持度是{Diaper,Milk}=3,而{Diaper,Milk,Beer}=2。TIDItems1Bread,Coke,Milk2Beer,Bread3Beer,Coke,Diaper,Milk4Beer,Bread,Diaper,Milk5Coke,Diaper,Milk图1TransactionsfromSupermarket关联规则可描述为:!XY,XI,YI。关联规则X!Y的支持度s定义为:(X?Y)/|T|,置信度定义为(X?Y)/(X)。例如,假设一条规则{Diaper,Milk}!{Beer},表示如果Diaper和Milk在一个事务中,就意味着Beer也包含在这个事务中。这条规则的支持度是:(Diaper,Milk,Beer)/5=40%。置信度为(Diaper,Milk,Beer)/(Diaper,Milk)=66%。如果一条规则的置信度很高的话,就说明这条规则很重要,因为它可以在规则中给项目关联提供精确的预测。同样的,规则的支持度也很重要,它可以暗示在事务中这条规则的出现频率有多高。支持度很低的规则通常是引不起人们的兴趣的。这就是为什么大多数的算法[2]忽视那些不能满足用户给定的最小支持度条件的规则的原因。这种用给定最小支持度过滤规则的方法可以减少产生的关联规则的数量,以便于管理。因为算法可能产生的规则的数量和项目集I的子集的数量是成比例的,可能达到2|I|,因此,这种过滤在实际应用中是必需的。发现关联规则的任务就是发现所有形如X!Y的规则,规则的支持度大于或等于给定的最小支持度,规则的置信度大于或等于给定的最小置信度。发现关联规本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！