资源描述：
《基于约束的关联规则》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章 在大型数据库中 挖掘关联规则报告人：张荣祖2001/11/286.6.1基于约束的挖掘使用约束的必要性在数据挖掘中常使用的几种约束：知识类型约束：指定要挖掘的知识类型如关联规则数据约束：指定与任务相关的数据集FindproductpairssoldtogetherinVancouverinDec.’98.维/层次约束:指定所用的维或概念结构中的层inrelevancetoregion,price,brand,customercategory.规则约束：指定要挖掘的规则形式(如规则模板)单
2、价(price<$10)的交易项目可能引发购买总额(sum>$200).兴趣度约束：指定规则兴趣度阈值或统计度量如(min_support3%,min_confidence60%).假定AllElectronics的一个销售多维数据库有如下关系：Sales(customer_name,item_name,transaction_id)Lives(customer_name,region,city)Items(item_name,category，price)Transaction(trans
3、action_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)withsupport
4、threshold=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)简洁性约束(succi
5、nctconstraint)约束的有关概念项目集：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)SA
6、Tc(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的一个项集单调/反单调性约束描述vSSVSVSVmin(S)vmin(S
7、)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)nonoyespartlynoyespartlyyesnopartlyyesnopartlyyesn
8、opartlyconvertible(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,
