基于约束的关联规则VIP免费

第六章在大型数据库中挖掘关联规则报告人：张荣祖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=•模式S是项目集的子集，S={ij1,ij2,…,ijk}•模式S包含与T,T=,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)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)succinctset),如果对于...