,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章,基于,数据仓库的,决策支持系统,(,4),1,第5章基于数据仓库的决策支持系统1,5.5,数据挖掘的决策支持,5.5.3,关联规则的挖掘及其应用,基本原理,Apriori,算法,3.,实例,5.5数据挖掘的决策支持5.5.3 关联规则的挖掘及其应用,2,关联规则（,Association Rule,）挖掘是发现大量数据库中项集之间的关联关系。,从大量商业事务中发现有趣的关联关系，可以帮助许多商业决策的制定，如分类设计、交叉购物等。,Agrawal,等人于,1993,年首先提出了挖掘顾客交易数据库中项集间的关联规则问题。,关联规则（Association Rule）挖掘是发现大量数,3,1,关联规则的挖掘原理,关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式。,例,1,：,在购买铁锤的顾客当中，有,70,的人同时购买了铁钉。,1关联规则的挖掘原理 关联规则是发现交易数据库中不同,4,例,2,：年龄在,40,岁以上，工作在,A,区的投保人当中，有,45,的人曾经向保险公司索赔过。,可以看出来，,A,区可能污染比较严重，环境比较差，索赔率也相对比较高。,例2：年龄在40 岁以上，工作在A区的投保人当中，,5,（,1,）,基本原理,设,I=i,1,i,2,i,m,是项（,Item,）的集合。,记,D,为事务（,Transaction,）的集合，,事务,T,是项的集合，并且,T,I,。,设,A,是,I,中一个项集，如果,A,T,，称事务,T,包含,A,。,定义,1,：关联规则是形如,A,B,的蕴涵式，这里,A,I,，,B,I,，并且,A,B=,。,（1）基本原理设I=i1,i2,im是项（Item,6,定义,2,：规则的支持度。,规则,A,B,在数据库,D,中具有支持度,S,，表示,S,是,D,中事务同时包含,AB,的百分比，它是概率,P(AB),，即：,其中,|D|,表示事务数据库,D,的个数，表示,A,、,B,两个项集同时发生的事务个数。,定义2：规则的支持度。,7,定义,3,：规则的可信度,规则,A,B,具有可信度,C,，表示,C,是包含,A,项集的同时也包含,B,项集，相对于包含,A,项集的百分比，这是条件概率,P(B|A),，即：,其中 表示数据库中包含项集,A,的事务个数。,定义3：规则的可信度,8,定义,4,：阈值。,在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：,最小支持度,（,min_sup,）和,最小可信度,（,min_conf,）。,定义,5,：项的集合称为项集（,Itemset,），包含,k,个项的项集称之为,k-,项集。,如果项集满足最小支持度，则它称之为,频繁项集,（,Frequent Itemset,）。,定义4：阈值。,9,定义,6,：关联规则。,同时满足最小支持度（,min_sup,）和最小可信度（,min_conf,）的规则称之为关联规则，即,成立时，规则称之为,关联规则,，也可以称为,强关联规则,。,定义6：关联规则。,10,（,2,）关联规则挖掘过程,关联规则的挖掘一般分为两个过程：,1,）,找出所有的频繁项集,：找出支持度大于最小支持度的项集，即频繁项集。,2,）,由频繁项集产生关联规则,：根据定义，这些规则必须满足最小支持度和最小可信度。,（2）关联规则挖掘过程关联规则的挖掘一般分为两个过程：,11,（,3,）关联规则的兴趣度,例子：讨论不购买商品与购买商品的关系。,设，交易集,D,，经过对,D,的分析，得到表格,:,买咖啡,不买咖啡,合计,买牛奶,20,5,25,不买牛奶,70,5,75,合计,90,10,100,（3）关联规则的兴趣度例子：讨论不购买商品与购买商品的关系,12,设定,minsupp=0.2,minconf=0.6,得到如下的,关联规则：,买牛奶,买咖啡,s=0.2 c=0.8,即,80,的人买了牛奶就会买咖啡。,同时得到结论：,90,的人肯定会买咖啡。,关联规则：,买咖啡,不买牛奶,s=0.7 c=0.78,支持度和可信度分别为,0.7,和,0.78,，更具有商业销售的指导意义。,设定minsupp=0.2,minconf=0.6,得到,13,定义,7,：兴趣度：,公式反映了项集,A,与项集,B,的相关程度。,若 即,表示项集,A,出现和项集,B,是相互独立的。,若,表示,A,出现和,B,出现是负相关的。,若,表示,A,出现和,B,出现是正相关的。意味着,A,的出现蕴含,B,的出现。,定义7：兴趣度：,14,一条规则的兴趣度越大于,1,说明我们对这条规则越感兴趣（即其实际利用价值越大）；,一条规则的兴趣度越小于,1,说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；,兴趣度,I,不小于,0,。,一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际,15,所有可能的关联规则,Rules,S,C,I,1,买牛奶,买咖啡,0.2,0.8,0.89,2,买咖啡,买牛奶,0.2,0.22,0.89,3,买牛奶,不买咖啡,0.05,0.2,2,4,不买咖啡,买牛奶,0.05,0.5,2,5,不买牛奶,买咖啡,0.7,0.93,1.037,6,买咖啡,不买牛奶,0.7,0.78,1.037,7,不买牛奶,不买咖啡,0.05,0.067,0.67,8,不买咖啡,不买牛奶,0.05,0.2,0.87,所有可能的关联规则 1 买牛奶买咖啡0.20.80.8,16,讨论,I,1,I,2,I,3,I,6,共,4,条规则：,由于,I,1,、,I,2,1,，规则才有价值。,兴趣度也称为作用度（,Lift,）,表示关联规则,AB,的“提升”。如果作用度（兴趣度）不大于,1,，则此关联规则就没有意义了,。,讨论I1I2I3I6共4条规则：,17,概括地说：,可信度,是对关联规则地准确度的衡量。,支持度,是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。,有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。,兴趣度,（作用度）描述了项集,A,对项集,B,的影响力的大小。兴趣度（作用度）越大，说明项集,B,受项集,A,的影响越大。,概括地说：,18,2.,Apriori,算法,Apriori,是挖掘关联规则的一个重要方法。,算法分为两个子问题：,找到所有支持度大于最小支持度的项集（,Itemset,），这些项集称为,频繁集,（,Frequent Itemset,）。,使用第,1,步找到的,频繁集产生规则,。,2.Apriori算法Apriori是挖掘关联规则的一,19,Apriori,使用一种称作逐层搜索的迭代方法，“,K-,项集”用于探索“,K+1-,项集”。,首先，找出频繁“,1-,项集”的集合。该集合记作,L,1,。,L,1,用于找频繁“,2-,项集”的集合,L,2,，而,L,2,用于找,L,3,，,如此下去，直到不能找到“,K-,项集”。找每个,L,K,需要一次数据库扫描,。,Apriori 使用一种称作逐层搜索的迭代方法，“K-项集”,20,1,）,Apriori,性质,性质：频繁项集的所有非空子集都必须也是频繁的。,如果项集,B,不满足最小支持度阈值,min-sup,，则,B,不是频繁的，即,P,（,B,）,min-sup,。,如果项,A,添加到,B,，则结果项集（即,BA,）不可能比,B,更频繁出现。因此，,BA,也不是频繁的，即,P,（,BA,）,min-sup,。,1）Apriori 性质性质：频繁项集的所有非空子集都必须,21,设,K-,项集,L,K,，,K+1,项集,L,K+1,，产生,L,K+1,的候选集,C,K+1,。有公式：,C,K+1,=L,K,L,K,=XY,，其中,X,，,Y L,K,，,|XY|=K+1,其中,C,1,是,1-,项集的集合，取自所有事务中的单项元素。,2,）“,K-,项集”产生“,K+1-,项集”,设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK,22,如,L1=A,，,B,C2=AB=A,，,B,，且,|AB|=2,L2=A,，,B,，,A,，,C,C3=A,，,BA,，,C=A,，,B,，,C,，,|ABC|=3,如 L1=A，B,23,3.,实例,事务,ID,事务的项目集,T1,A,B,E,T2,B,D,T3,B,C,T4,A,B,D,T5,A,C,T6,B,C,T7,A,C,T8,A,B,C,E,T9,A,B,C,3.实例事务ID事务的项目集T1A,B,ET2B,DT3B,24,1),在算法的第一次迭代，每个项都是候选,1-,项集的集合,C,1,的成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第,1,列。,2),假定最小事务支持计数为,2,（即,min-sup=2/9=22%,），可以确定频繁,1-,项集的集合,L,1,。它由具有最小支持度的候选,1-,项集组成。见图中第,2,列。,3),为发现频繁,2-,项集的集合,L,2,，算法使用,L,1,*L,1,来产生候选集,C,2,。见图中第,3,列。,4),扫描,D,中事务，计算,C,2,中每个候选项集的支持度计数，如图中的第,4,列。,5),确定频繁,2-,项集的集合,L2,，它由具有,最小支持度的,C2,中的候选,2-,项集组成。见图第,5,列,。,1)在算法的第一次迭代，每个项都是候选1-项集的集合C1的,25,6),候选,3-,项集的集合,C,3,的产生，得到候选集：,C,3,=A,，,B,，,C,，,A,，,B,，,E,，,A,，,C,，,E,，,B,，,C,，,D,，,B,，,C,，,E,，,B,，,D,，,E,按,Apriori,性质，频繁项集的所有子集必须是频繁的。由于,A,，,D,，,C,，,D,，,C,，,E,，,D,，,E,不是频繁项集，故,C,3,中后,4,个候选不可能是频繁的，在,C,3,中删除它们。见图第,6,列。,扫描,D,中事务，对,C,3,中的候选项集计算支持度计数，见图第,7,列。,7),确定,L,3,，它由具有最小支持度的,C,3,中候选,3,项集组成，见图第,8,列。,8,）,按公式产生候选,4,项集的集合,C,4,，产生结果,A,B,C,E,这个项集被剪去，因为它的子集,B,C,E,不是频繁的。这样,L,4,=,。此算法终止。,L,3,是最大的频繁项集，即：,A,B,C,和,A,B,E,。,6)候选3-项集的集合C3的产生，得到候选集：,26,具体产生过程用图表示,具体产生过程用图表示,27,候选集与频繁项集的产生,项集,支持度计数,A,B4,A,C4,A,E2,B,C4,B,D2,B,E2,项集,A,B,，,C,A,B,，,E,C,3,候选集,L,2,频繁,2-,项集,计算,支持度,项集,支持度计数,A,B,C2,A,B,E2,项集 支持度计数,A,B,C2,A,B,E2,C,3,候选集,L,3,频繁,3-,项集,候选集与频繁项集的产生 项集支持度计数A,B4项集C3候,28,产生关联规则,根据前面提到的可信度的定义，关联规则的产生如下：,（,1,）对于每个频繁项集,L,，产生,L,的所有非空子集；,（,2,）对于,L,的每个非空子集,S,，如果,则输出规则“,S L,S”,。,注：,L,S,表示在项集,L,中除去,S,子集的项集,。,产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：,29,频繁项集,L=A,，,B,，,E,，可以由,L,产生哪些关联规则？,L,的非空子集,S,有：,A,B,A,E,B,E,A,B,E,。可得到关联规则如下：,A B E conf=2/4=50%,A E B conf=2/2=100%,B E A conf=2/2=100%,A B E conf=2/6=33%,B A E conf=2/7=29%,E A B conf=2/2=100%,假设最