基于约束的关联规则.ppt
第六章在大型数据库中挖掘关联规则报告人：张荣祖2001/11/286.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=v，v是S的一个项集约束Cm 是单调的iff.对于任给的满足Cm的项集(模式)S,每一个S的超集都能够满足 Cm e.g:Cm: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,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)succinct set),如果对于某些选择性谓词p,该项目子集能够表示为p(I)，此处，是一个选择符SP2I 是一个强简洁集(succinct power set)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)几种约束之间的关系SuccinctnessAnti-monotonicityMonotonicityConvertible constraintsInconvertible 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算法及其改进
