基于约束的关联规则

第六章在大型数据库中挖掘关联规则报告人：张荣祖2001/11/286.6.1基于约束的挖掘•使用约束的必要性•在数据挖掘中常使用的几种约束：–知识类型约束：指定要挖掘的知识类型如关联规则–数据约束：指定与任务相关的数据集•FindproductpairssoldtogetherinVancouverinDec.’98.–维/层次约束:指定所用的维或概念结构中的层•inrelevancetoregion,price,brand,customercategory.–规则约束：指定要挖掘的规则形式(如规则模板)•单价(price$10)的交易项目可能引发购买总额(sum$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)mineassociationsas(2)lives(C,_,”Pudong”)^sales(C,{I},{S})=sales(C,{J}{T})(3)fromsales(4)whereS.year=1999&&T.year=1999&&I.category=J.category(5)groupbyC,I.category(6)havingsum(I.price=100)&&min(J.price)=500(7)withsupportthreshold=1%(8)withconfidencethreshold=50%Lives(C,_,”Pudong”)^Sales(C,”Census_CD”,_)^Sales(C,”MS/Office”,_)=Sales(C,”MS/SQLSever”,_)[1.5%,65%]6.6.2约束的分类•单调性约束(monotoneconstraint)•反单调性约束(anti-monotoneconstraint)•可转变的约束(convertibaleconstraint)•简洁性约束(succinctconstraint)约束的有关概念•项目集：I={i1,i2,……,im},•交易：T=tid,It•模式S是项目集的子集，S={ij1,ij2,…,ijk}•模式S包含与T,T=tid,It,iffS=It;S’是S的子模式(subpattern)且S是S’的超模式(superpattern)，if有S’=S.约束的有关概念（续）•定义约束:C是作用于项目集I的幂集(powerset)上的谓词,C(S)=True/False;•满意模式集(satisfyingpatternset)SATc(I)是指那些完全满足约束C的项目集的全体•将约束条件用于频繁集的查询无非是找出那些满足C的频繁集单调和反单调的规则约束•规则Ca是反单调的(anti-monotone)iff对于任给的不满足Ca的项集(模式)S,不存在S的超集能够满足Cae.g:Ca:min(S)=v，v是S的一个项集•约束Cm是单调的iff.对于任给的满足Cm的项集(模式)S,每一个S的超集都能够满足Cme.g:Cm:min(S)=v,v是S的一个项集单调/反单调性约束描述vSSVSVSVmin(S)vmin(S)vmin(S)vmax(S)vmax(S)vmax(S)vcount(S)vcount(S)vcount(S)vsum(S)vsum(S)vsum(S)vavg(S)v,{,,}(frequentconstraint)yesyesnopartlyyesnopartlynoyespartlynoyespartlynoyespartlyconvertible(no)nonoyespartlynoyespartlyyesnopartlyyesnopartlyyesnopartlyconvertible(yes)反单调单调约束规则可转变的约束1•反单调可转变的1.C(S)既不是单调性约束，也不是反单调性约束；2.若存在顺序R,使得经R排序后的I具有如下性质：任给S’∈{suffix_S},ifC(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}isasuffixof{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具有如下性质：任给S’∈{suffix_S},ifC(S’)=C(S)则C(S)是单调可转变的可转变性约束的例子2Avg(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}isasuffixof{9,8,4,3}•avg({9,8,4,3})=6avg({8,4,3})=5–如果S’满足约束avg(S’)v,则S也满足•{8,4,3}satisfiesconstraintavg(S)4,sodoes{9,8,4,3}简洁性约束•一个项目子集Is是一个简洁集(succinctset),如果对于某些选择性谓词p,该项目子集能够表示为p(I)，此处，是一个选择符•SP2I是一个强简洁集(succinctpowerset),如果有一个数目不变的简洁集I1,…,IkI,SP能够用I1,…,Ik的并、差运算表示出来beexpressedintermsofthestrictpowersetsofI1,…,Ikusingunionandminus•约束Cs是简洁的假如SATCs(I)是一个强简洁集简洁性约束的举例约束规则vSSVSVSVmin(S)vmin(S)vmin(S)vmax(S)vmax(S)vmax(S)vcount(S)vcount(S)vcount(S)vsum(S)vsum(S)vsum(S)vavg(S)v,{,,}(frequentconstraint)简洁性yesyesyesyesyesyesyesyesyesyesweaklyweaklyweaklynononono(no)几种约束之间的关系SuccinctnessAnti-monotonicityMonotonicityConvertibleconstraintsInconvertibleconstraints频繁数据集应用举例•交易数据库TDB如下所示，支持度为3频繁项目按照降续排列：a:5;e:4;b:3;c:3;d:3;f:3Transaction_IDItemsInTransaction100a,e,c,d,,f200a,b300a,e,c,f400a,e,b,c,d,f500a,e,b,d频繁数据集应用举例(续)•将排序后的每次交易的项目列表的前缀项目映射到条件数据库TDB|f;TDB|d;TDB|c;TDB|b;TDB|eTDB{aecdf,ab,aecf,aebedf,aebd}Frequentitems:a,e,b,c,d,ff-ConditionaldatabaseTDB|B{aecd,aed,adbcd}frequentitems:a,e,cTDB|dTDB|cTDB|eTDB|b频繁集的生长过程•性质:如果模式α在TDB|f中是频繁的，则α∪f在TDB|f中也一定是频繁的•频繁集的生长过程1.在TDB|f中找到相应的频繁项目集β,β被称为f的条件频繁项目集2.对于每一个在β中的频繁项目e，找出TDB|ef中相应的频繁项目集，这是一个递归的过程将约束用于频繁集的生成•Ca≡Sum(S)=180•使用图表2的交易数据库:support=3{a,s,b,c,d,e,f}={50,150,10,200,20,80}Transaction_IDItemsInTransaction100a,e,c,d,,f200a,b300a,e,c,f400a,e,b,c,d,f500a,e,b,d将约束用于挖掘的几种策略•去除不满足约束的单个项目Exam1:Sum(d)=200180•如果α不满足约束，则不必产生α的条件项目集,也不必产生α的条件数据库TDB|αExam2:Sum({a,b})=200•如果α∪β满足约束，则不必对条件数据库TDB|α中的其余部分用Ca进行约束检查，此处β是在TDB|α中的频繁项目集(NoconstraintcheckingintheremainingconditionaldatabaseTDB|α,ifα∪βsatisfiestheconstraint.)小结•常见的4种约束类型•规则约束的分类及其性质I.单调/反单调ii.可转变的iii.简洁的•CFG算法及其改进