基于约束的关联规则.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=ij1,ij2,ijk模式S包含与T,T=,iff S=It;S是S的子模式(subpattern)且S 是S的超模式(superpattern)，if 有S=S.,约束的有关概念（续）,定义约束:C是作用于项目集I的幂集(powerset)上的谓词,C(S)=True/False;满意模式集(satisfying pattern set)SATc(I)是指那些完全满足约束C的项目集的全体将约束条件用于频繁集的查询无非是找出那些满足C的频繁集,单调和反单调的规则约束,规则 Ca 是 反单调的(anti-monotone)iff 对于任给的不满足Ca的项集(模式)S,不存在S的超集能够满足 Ca e.g:Ca:min(S)=v，v是S的一个项集约束Cm 是单调的iff.对于任给的满足Cm的项集(模式)S,每一个S的超集都能够满足 Cm e.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,(frequent constraint),yesyesnopartlyyesnopartlynoyespartlynoyespartlynoyespartlyconvertible(no),nonoyespartlynoyespartlyyesnopartlyyesnopartlyyesnopartlyconvertible(yes),反单调,单调,约束规则,可转变的约束 1,反单调可转变的 1.C(S)既不是单调性约束，也不是反单调性约束；2.若存在顺序R,使得经R排序后的I具有如下性质：任给 Ssuffix_S,if C(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,9avg(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,3avg(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,简洁性约束,一个项目子集Is 是一个 简洁集(succinct set),如果对于某些选择性谓词p,该项目子集能够表示为p(I)，此处，是一个选择符SP2I 是一个强简洁集(succinct power set),如果有一个数目不变的简洁集 I1,Ik I,SP 能够用I1,Ik 的并、差运算表示出来 be expressed in terms of the strict power sets of I1,Ik using union and minus约束 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,(frequent constraint),简洁性yesyesyesyesyesyesyesyesyesyesweaklyweaklyweakly nononono(no),几种约束之间的关系,Succinctness,Anti-monotonicity,Monotonicity,Convertible constraints,Inconvertible constraints,频繁数据集应用举例,交易数据库TDB如下所示，支持度为 3 频繁项目按照降续排列：a:5;e:4;b:3;c:3;d:3;f:3,频繁数据集应用举例(续),将排序后的每次交易的项目列表的前缀项目映射到条件数据库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使用图表2的交易数据库:support=3 a,s,b,c,d,e,f=50,150,10,200,20,80,将约束用于挖掘的几种策略,去除不满足约束的单个项目 Exam1:Sum(d)=200180如果不满足约束，则不必产生的条件项目集,也不必产生的条件数据库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算法及其改进,
