第八章 关联规则挖掘.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 关联规则的挖掘,一、关联规则挖掘的含义,关联规则用于表示,OLTP,数据库中诸多属性（项集）之间的关联程度。,关联规则挖掘（,Association Rules Mining,）则是利用数据库中的大量数据通过关联算法寻找属性间的相关性。,例：,(,超级市场,),在购买商品,A,的客户中有,90%,的人会同时购买商品,B,，则可用关联规则表示为：,关联规则,支持度,(Support),：,同时购买,A,和,B,的客户人数占总客户数的百分比称为规则的支持度。,置信度,(Confidence),：,同时购买,A,和,B,的客户人数占购买,A,的客户人数的百分比称为规则的置信度。,由于在实际应用中，概率,P,一般是无法事先给出的，所以常以频度代替,购买,A,的顾客,购买,B,的顾客,同时购买,A,和,B,的顾客（,A,B,）,关联规则（图示）,有意义的关联规则,为了发现出有意义的关联规则，需要给定两个阈值：,最小支持度和最小置信度,。,关联规则挖掘的实质是在数据集合中寻找满足用户给定的最小支持度和最小置信度的规则。例：交易情况如下表，要求最小支持度为,50%,最小可信度为,50%,则可得到：,ID号,购买的商品,001,A,，,B,，,C,002,A,，,C,003,A,，,D,004,B,，,E,，,F,A,C (50%,66.6%),C,A (50%,100%),二、关联规则挖掘算法,Apriori,1,、术语,项集：,在数据库中出现的属性值的集合。,K_,项集：包含,K,个项的项集。,频繁项集：,满足最小支持度要求的项集。,关联规则一定是在满足用户的最小支持度要求的频繁项集中产生的，因此，关联规则挖掘也就是在数据库中寻找频繁项集的过程。,示例,交易号,购买的商品,001,A,，,B,，,C,002,A,，,C,003,A,，,D,004,B,，,E,，,F,例：,项集：,A,，,B,，,C,，,D,，,E,，,F,，,.,1_,项集：,A,，,B,，,C,，,.,，,F,2_,项集：,A,，,B,，,A,，,C.,频繁项集的任何子集也一定是频繁的！,2,、关联规则分类,1,）根据规则中所处理的,值类型,布尔关联规则：规则考虑的关联项是否存在,量化关联规则：规则描述的是量化的项或属性间的规则,2,、关联规则分类,2,）根据规则中所涉及的,数据维,是单维的，涉及,buys;,多维，涉及年龄、收入和,buys,3,）根据规则中所涉及的,抽象层,商品位于不同层，计算机的抽象层高，称为,多层关联规则,3,、,Apriori,算法,符号定义：,L,k,:k,项,频繁,集的集合；,C,k,：,k,项集的候补集合,步骤：,连接,:,用,L,k-1,自连接得到,C,k,，（,k2),设,l,1,l,2,是有,两个有,k-1,个有序项的项集，,l,j,i,代表,k-1,个项的第,i,项,(j=1,2;i=1,2,k-1),。,l,1,和,l,2,是可连接的,l,1,X,l,2,，,需满足：,l,1,1=l,2,1,l,1,2=l,2,2,，,.,，,l,1,k-2=l,2,k-2,，,l,1,k-1,l,2,k-1,，,产生的项是：,l,1,1l,1,2.l,1,k-2l,1,k-1l,2,k-1,(l,j,i,是有序的）,*注：,C,2,=,由,1_,项集两两组合生成，共,C,2,m,(m,为,1_,项集合的项数）,修剪,:,一个,k-,项集，如果它的一个,k-1,项子集不是频繁的，那它本身也不可能是频繁的。,例：,l,1,=A,B,C,，,l,2,=A,B,D,，,l,3,=A,C,F,则：,l,1,X,l,2,=A,B,C,D l,1,X,l,3,，,l,2,X,l,3,均为空,为什么,l,1,X,l,3,不生成,A,B,C,F?,A,，,B,，,C,，,A,，,B,，,F,4,、算法伪代码,L,1,=,找频繁,1_,项集；,for,(,k,=2;,L,k,!=,;,k,+),C,k,=,由,L,k-1,生成候补集合；,for each,t,C,k,计算,t,在数据集合中出现的次数；,/,min_support,为最小支持度,if (,出现计数小于,minsupport,),从,C,k,中剔除；,L,k,=,C,k,；,return,k,L,k,;,5,、关联规则挖掘示例（,最小支持数,2,）,数据库,D,扫描,D,C,1,itemset,sup,1 2,1,1 3,2,1 5,1,2 3,2,2 5,3,C,2,3 5,2,C,2,扫描,D,C,3,扫描,D,L,3,L,1,L,2,6,、产生的关联规则,前面的例子中，得到一个频繁集,2,，,3,，,5,，非空真子集有,2,，,3,，,5,，,2,，,3,，,2,，,5,，,3,，,5,L,1,L,3,L,2,规则：,2,35,3,25,5,23,23,5,25,3,35,2,置信度：,2/3=66%,（,2,，,3,，,5,频度,/2,频度）,2/3=66%,（,2,，,3,，,5,频度,/3,频度）,2/3=66%,（,2,，,3,，,5,频度,/5,频度）,2/2=100%,（,2,，,3,，,5,频度,/2,，,3,频度）,2/3=66%,（,2,，,3,，,5,频度,/2,，,5,频度）,2/2=100%,（,2,，,3,，,5,频度,/3,，,5,频度）,支持度：,2/4=50%,7,、,Apriori,的性能瓶颈,Apriori,算法的核心,:,用频繁的,(,k-,1)_,项集生成,候选,的频繁,k,_,项集,用数据库扫描和模式匹配计算候选集的支持度,Apriori的瓶颈,:,候选集生成,巨大的候选集,:,104,个频繁,1,_,项集要生成,107,个候选,2_,项集,要找尺寸为,100,的频繁模式，如,a1,a2,a100,你必须先产生,2100,1030,个候选集（,1_,项集）,多次扫描数据库,：,如果最长的模式是,n,的话，则需要,n,次数据库扫描,为提高,Apriori,算法的性能，有许多改进的算法。,8,、如何在概念分层挖掘多层关联规则,一般采用自顶向下策略，由概念的顶层开始向下，到较低的更特定的概念层，对每个概念层的频繁集累加计数，直到不能再找到频繁项集。,对于所有层使用一致的最小支持度,计算机,支持度,=10%,台式机,支持度,=6%,笔记本,支持度,=4%,层,1:,minsup,=5%,层,2:,minsup,=5%,非频繁,8,、如何在概念分层挖掘多层关联规则,一般采用自顶向下策略，由概念层,1,开始向下，到较低的更特定的概念层，对每个概念层的频繁集累加计数，直到不能再找到频繁项集。,对于所有层使用一致的最小支持度,在较低层使用递减的最小支持度,计算机,支持度,=10%,台式机,支持度,=6%,笔记本,支持度,=4%,层,1:,minsup,=5%,层,2:,minsup,=3%,9,、冗余的多层关联规则处理,买笔记本,买打印机,支持度,=8%,置信度,=70%(1),买,IBM,笔记本,买打印机,支持度,=2%,置信度,=72%(2),规则,2,有用吗？它提供了新颖的信息吗？,从（,1,）的,置信度,=70%,推断：,买笔记本,同时买打印机的交易数,/,买笔记本交易数,=70%,。,IBM,笔记本属于笔记本，因此,置信度也应该在,70%,左右。由（,2),实际为,72%,，基本无差异。,如果后一个具有较小一般性的规则，它不提供新的信息，应当删除它！,9,、冗余的多层关联规则处理,从（,1,）的,支持度,=8%,推断：,买笔记本,同时买打印机的交易数,/,总交易数,=8%,，假定从数据集中还发现，,IBM,笔记本在占整个笔记本销量的,25%,。则：买,IBM,笔记本的支持度应该为,8%*25%=2%,，由（2),实际为,2%,，两者相同。,如果一个规则的祖先，它的支持度和置信度都接近于该规则的“期望”值，这个规则是冗余的。,结论：规则（,2,）不是有趣的，因为它不提供有趣的信息,10,、关联规则的相关分析,强关联规则不一定有趣,例：在,10000,个交易中，,6000,个顾客交易包含计算机游戏，,7500,个顾客交易包含影碟机，,4000,个交易包含计算机游戏和影碟机。,规则其实是误导，因为购买影碟机的可能性是,75%,，比,66%,还大。事实是：计算机游戏和影碟机是负相关的。,10,、关联规则的相关分析,A,和,B,的相关性：,corr,AB,:1,，正相关，每一个出现蕴涵另一个出现,p(,游戏,)=0.6,，,p(,影碟机,)=0.75,，,p(,游戏,影碟机,)=0.4,corr,AB,=0.4/0.6*0.75=0.891,负相关，规则无意义！,