基于约束的关联规则.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章在大型数据库中挖掘关联规则,报告人：张荣祖,2001/11/28,6.6.1 基于约束的挖掘,使用约束的必要性,在数据挖掘中常使用的几种约束：,知识类型约束：,指定要挖掘的知识类型,如关联规则,数据约束：,指定与任务相关的数据集,Find product pairs sold together in,Vancouver,in,Dec.98,.,维/层次约束:,指定所用的维或概念结构中的层,in relevance to,region,price,brand,customer category,.,规则约束：,指定,要挖掘的规则形式(如规则模板),单价,(,price$200).,兴趣度约束：,指定规则兴趣度阈值或统计度量,如(,min_support,3%,min_confidence,60%).,假定,AllElectronics,的一个销售多维数据库有如下关系：,Sales(customer_name,item_name,transaction_id),Lives(customer_name,region,city),Items(item_name,category，price),Transaction(transaction_id,day,month,year),(1)mine associations as,(2)lives(C,_,”,Pudong,”)sales(C,I,S)=sales(C,JT),(3)from sales,(4)where S.year=1999&T.year=1999,&I.category=J.category,(5)group by C,I.category,(6)having sum(I.price=500,(7)with support threshold=1%,(8)with confidence threshold=50%,Lives(C,_,”,Pudong,”)Sales(C,”Census_CD”,_)Sales(C,”MS/Office”,_)=Sales(C,”MS/,SQLSever,”,_)1.5%,65%,6.6.2 约束的分类,单调性约束,(,monotone constraint),反单调性约束,(,anti-monotone constraint),可转变的约束,(,convertibale,constraint),简洁性约束,(,succinct constraint),约束的有关概念,项目集：,I=i1,i2,im,交易：,T=,模式,S,是项目集的子集，,S=i,j1,i,j2,i,jk,模式,S,包含与,T,T=,iff,S=It;,S,是,S,的子模式(,subpattern,),且,S是,S,的,超模式(,superpattern,)，if,有,S=v，v,是,S,的一个项集,约束,C,m,是,单调的,iff,.,对于任给的满足,C,m,的项集(模式),S,每一个,S,的超集都能够满足,C,m,e.g:C,m,:min(S)C(S),则,C(S),是反单调可转变的,可转变性约束的例子1:,Avg,(S),V,令,I,为一组以升序排列数值的项目集,E.g.I=1，3，4，6，8，9,，,R,意指升续,Avg,(S)=,v,是反单调可转变的,如果,S,是,S,的一个后缀,那么,avg,(S),=,avg,(S),6,8,9 is a suffix of 3,4,6,8,9,avg,(6,8,9)=23/3,avg,(3,4,6,8,9)=6,如果,S,满足约束,avg,(S),v,则,S,也满足,可转变的约束 2,单调可转变的,1,.,C(S),既不是单调性约束，也不是反单调性约束；,2.若存在,顺序,R,使得经,R,排序后的,I,具有如下性质：,任给,Ssuffix_S,if C(S)=C(S),则,C(S),是单调可转变的,可转变性约束的例子 2,Avg,(S),V,令,I,为一组以降序排列数值的项目集,E.g.I=9,8,6,4,3,1，,R,意指降续,Avg,(S),v,是单调可转变的,如果,S,是,S,的一个后缀,那么,avg,(S),avg,(S,),8,4,3 is a suffix of 9,8,4,3,avg,(9,8,4,3)=6,avg,(8,4,3)=5,如果,S,满足约束,avg,(S),v,则,S,也满足,8,4,3,satisfies constraint,avg,(S)4,so does 9,8,4,3,简洁性约束,一个项目子集,I,s,是一个,简洁集,(,succinct set),如果对于某些选择性谓词,p,该项目子集能够表示为,p,(I)，,此处，,是一个选择符,SP2,I,是一个,强简洁集,(,succinct,power set),如果有一个数目不变的简洁集,I,1,I,k,I,SP,能够用,I,1,I,k,的并、差运算表示出来,be expressed in terms of the strict power sets of I,1,I,k,using union and minus,约束,C,s,是,简洁的,假如,SAT,Cs,(I),是一个强简洁集,简洁性约束的举例,约束规则,v S,S V,S V,S V,min(S)v,min(S)v,min(S)v,max(S)v,max(S)v,max(S)v,count(S)v,count(S)v,count(S)v,sum(S)v,sum(S)v,sum(S)v,avg,(S)v,(frequent constraint),简洁性,yes,yes,yes,yes,yes,yes,yes,yes,yes,yes,weakly,weakly,weakly,no,no,no,no,(no),几种约束之间的关系,Succinctness,Anti-,monotonicity,Monotonicity,Convertible constraints,Inconvertible constraints,频繁数据集应用举例,交易数据库,TDB,如下所示，,支持度,为 3,频繁项目按照,降续,排列：,a:5;e:4;,b:3;c:3;d:3;f:3,Transaction_ID,Items In Transaction,100,a,e,c,d,f,200,a,b,300,a,e,c,f,400,a,e,b,c,d,f,500,a,e,b,d,频繁数据集应用举例(续),将排序后的每次交易的项目列表的,前缀项目,映射到条件数据库,TDB|f;TDB|d;TDB|c;TDB|b;TDB|e,频繁集的生长过程,性质,:如果模式,在,TDB|f,中是频繁的，则,f,在,TDB|f,中也一定是频繁的,频繁集的生长过程,1,.在,TDB|f,中找到相应的频繁项目集,被称为,f,的条件频繁项目集,2,.对于每一个在,中的频繁项目,e，,找出,TDB|,ef,中相应的频繁项目集，这是一个递归的过程,将约束用于频繁集的生成,CaSum(S)180,如果,不满足约束，则不必产生,的条件项目集,也不必产生,的条件数据库,TDB|,Exam2:Sum(a,b)=200,如果,满足约束，则不必对条件数据库,TDB|,中的其余部分用,Ca,进行约束检查，此处,是在,TDB|,中 的频繁项目集,(No constraint checking in the remaining conditional database TDB|,if satisfies the constraint.),小结,常见的4种约束类型,规则约束的分类及其性质,I.,单调/反单调,ii.,可转变的,iii.,简洁的,CFG,算法及其改进,