文档介绍：第三章关联规则挖掘理论和算法 内容提要基本概念与解决方法经典的频繁项目集生成算法分析Apriori算法的性能瓶颈问题Apriori的改进算法对项目集空间理论的发展基于项目集操作的关联规则挖掘算法改善关联规则挖掘质量问题约束数据挖掘问题关联规则挖掘中的一些更深入的问题数量关联规则挖掘方法2019/4/281关联规则挖掘是数据挖掘研究的基础关联规则挖掘(AssociationRuleMining)是数据挖掘中研究较早而且至今仍活跃的研究方法之一。最早是由Agrawal等人提出的(1993)。最初是针对购物篮分析(BasketAnalysis)问题提出的,其目的是为了发现交易数据库(TransactionDatabase)中不同商品之间的联系规则。关联规则的挖掘工作成果颇丰。例如,关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘(ParallelAssociationRuleMining)以及数量关联规则挖掘(QuantitiveAssociationRuleMining)等。2019/4/282事务数据库设I={i1,i2,…,im}是一个项目集合,事务数据库D={t1,t2,…,tn}是由一系列具有唯一标识TID的事务组成,每个事务ti(i=1,2,…,n)都对应I上的一个子集。一个事务数据库可以用来刻画:购物记录:I是全部物品集合,D是购物清单,每个元组ti是一次购买物品的集合(它当然是I的一个子集)。其它应用问题2019/4/283支持度与频繁项目集定义(项目集的支持度).给定一个全局项目集I和数据库D,一个项目集I1I在D上的支持度(Support)是包含I1的事务在D中所占的百分比:support(I1)=||{tD|I1t}||/||D||。定义(频繁项目集).给定全局项目集I和数据库D,D中所有满足用户指定的最小支持度(Minsupport)的项目集,即大于或等于minsupport的I的非空子集,称为频繁项目集(频集:FrequentItemsets)或者大项目集(LargeIitemsets)。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集(最大频集:MaximumFrequentItemsets)或最大大项目集(MaximumLargeIitemsets)。2019/4/284可信度与关联规则定义(关联规则与可信度).给定一个全局项目集I和数据库D,一个定义在I和D上的关联规则形如I1I2,并且它的可信度或信任度或置信度(Confidence)是指包含I1和I2的事务数与包含I1的事务数之比,即Confidence(I1I2)=support(I1∪I2)/support(I1),其中I1,I2I,I1∩I2=Ф。定义(强关联规则).D在I上满足最小支持度和最小信任度(Minconfidence)的关联规则称为强关联规则(StrongAssociationRule)。2019/4/285关联规则挖掘基本过程关联规则挖掘问题可以划分成两个子问题::通过用户给定Minsupport,寻找所有频繁项目集或者最大频繁项目集。:通过用户给定Minconfidence,在频繁项目集中,寻找关联规则。第1个子问题是近年来关联规则挖掘算法研究的重点。2019/4/286第三章关联规则挖掘理论和算法 内容提要基本概念与解决方法经典的频繁项目集生成算法分析Apriori算法的性能瓶颈问题Apriori的改进算法对项目集格空间理论的发展基于项目序列集操作的关联规则挖掘算法改善关联规则挖掘质量问题约束数据挖掘问题关联规则挖掘中的一些更深入的问题数量关联规则挖掘方法2019/4/287项目集空间理论Agrawal等人建立了用于事务数据库挖掘的项目集空间理论(1993,Appriori属性)。定理(Appriori属性1).如果项目集X是频繁项目集,那么它的所有非空子集都是频繁项目集。证明设X是一个项目集,事务数据库T中支持X的元组数为s。对X的任一非空子集为Y,设T中支持Y的元组数为s1。根据项目集支持数的定义,很容易知道支持X的元组一定支持Y,所以s1≥s,即support(Y)≥support(X)。按假设:项目集X是频繁项目集,即support(X)≥minsupport,所以support(Y)≥support(X)≥minsupport,因此Y是频繁项目集。□定理(Appriori属性2).如果项目集X是非频繁项目集,那么它的所有超集都是非频繁项目集。证明(略)2019/4/288经典的发现频繁项目集算法1994年,Agrawal等人提出了著名的Apriori算法。算法3-1Apriori(发现频繁项目集)输入:数据集D;最小支持数输出