基于约束的挖掘(上课)

1、中南大学信息科学与工程学院2004.3l 使用约束的必要性 - 基于约束的关联规则挖掘可以促进交互式探查与分析。 - 在实际的挖掘过程中，用户往往希望参与到挖掘的全过程中，以便对挖掘过程进行指导和控制；用户所关心的通常只是关联规则的某个子集，而不是泛泛地发现全部规则，这就需要有效地利用约束条件缩减数据库中事务的数量，提高挖掘效率。 l在数据挖掘中常使用的几种约束：知识类型约束：指定要挖掘的知识类型 如关联规则数据约束： 指定与任务相关的数据集 lFind product pairs sold together in Vancouver in Dec.98.维/层次约束:指定所用的维或概念结构中

2、的层lin relevance to region, price, brand, customer category.规则约束：指定要挖掘的规则形式(如规则模板)l单价 (price $200).兴趣度约束：指定规则兴趣度阈值或统计度量l如 (min_support 3%, min_confidence 60%).l假定AllElectronics的一个销售多维数据库有如下关系：lSales(customer_name,item_name,transaction_id)lLives(customer_name,region,city)lItems(item_name,category，pric

3、e)lTransaction(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 thr

4、eshold=50%Lives(C,_,”Pudong”)Sales(C,”Census_CD”,_)Sales(C,”MS/Office”,_)=Sales(C,”MS/SQLSever”,_) 1.5%,65%l单调性约束(monotone constraint)l反单调性约束(anti-monotone constraint)l可转变的约束(convertible constraint)l简洁性约束(succinct constraint)l不可转变的约束(inconvertible constraint) 设Ii1，i2，im是项的集合。设X是一个项集，关联规则是形如XY的蕴含式，其中

5、XI，YI，XY。支持度s是DB中事务包含XY（即X和Y二者）的百分比。置信度c是DB中包含X的事务也包含Y的百分比。满足最小支持度阈值min_sup的项集称为频繁项集。挖掘关联规则就是在给定的交易集合中产生所有满足最小支持度阈值和最小置信度的强规则。 关联规则的挖掘是一个两步的过程：（1）找出所有频繁项集；（2）由频繁项集产生强关联规则。第二步相对来说比较简单。挖掘关联规则的总体性能由第一步决定。l项目集：I = i1，i2，iml交易：T = l模式S是项目集的子集，S = ij1,ij2,ijkl模式S约束于T，T = ，if and only if S It; S是S的子模式(subp

6、attern)且S 是S的超模式(superpattern)， if and only if有SS。l定义约束: C是作用于项目集I的幂集(powerset)上的谓词,C(S)=True/False;l满意模式集(satisfying pattern set) SATc(I)是指那些完全满足约束C的项目集的全体l将约束条件用于频繁集的查询无非是找出那些满足C的频繁集l规则 Ca 是 反单调的(：如果对于任给的不满足Ca的项集(模式) S，不存在S的任何超集能够满足 Ca。 - e.g: Ca : min(S)=v ， v是S的一个项集 诸如“min(J.Price) =500”的约束，对于一个

7、不满足该约束的项集，无论添加多少项得到的超集都不可能满足该约束。 - Apriori性质（频繁项集的任何非空子集也必然是频繁的）也是反单调的。l约束Cm 是单调的(monotone )：如果对于任给的满足Cm的项集(模式) S, 每一个S的超集都能够满足 Cm。 - e.g: Cm : min(S)=v, v是S的一个项集 诸如“min(J.Price) C(S) 则C(S)是反单调可转变的l令I为一组以升序排列数值的项目集E.g. I=1，3，4，6，8，9 ， R指升序lAvg(S) = v 是反单调可转变的如果 S 是S的一个后缀, 那么avg(S) = avg(S)l6,8,9 is

8、a suffix of 3,4,6,8,9lavg(6,8,9)=23/3 avg(3,4,6,8,9)=6如果 S满足约束 avg(S) v, 则 S也满足l单调可转变的 1. C(S)既不是单调性约束，也不是反单调性约束； 2. 若存在顺序R,使得经R排序后的I具有如下性质： 任给 Ssuffix_S, if C(S)=C(S) 则C(S)是单调可转变的l令I为一组以降序排列数值的项目集E.g. I=9, 8, 6, 4, 3, 1， R指降序lAvg(S) v 是单调可转变的如果 S 是S的一个后缀, 那么avg(S) avg(S)l8, 4, 3 is a suffix of 9, 8

9、, 4, 3lavg(9, 8, 4, 3)=6 avg(8, 4, 3)=5如果 S满足约束 avg(S) v, 则 S也满足l8, 4, 3 satisfies constraint avg(S) 4, so does 9, 8, 4, 3l一个项目子集Is 是一个 简洁集(, 如果对于某些选择性谓词p,该项目子集能够表示为p(I) ，此处， 是一个选择符lSP2I 是一个强简洁集( succinct ,如果有一个数目不变的简洁集 I1, , Ik I, SP 能够用I1, , Ik 的并、差运算表示出来 be expressed in terms of the strict power

10、sets of I1, , Ik using union and minusl约束 Cs 是 假如 SATCs(I)是一个强简洁集l如果一个约束是简洁的，我们可以直接精确地产生满足它的集合，甚至在支持计数之前。即这种约束是计数前可剪枝的。l例如“min(J.Price) =500”是简洁的。我们能够准确无误地产生满足该约束的所有项集。在挖掘过程中不必迭代地检验规则约束。约束规则约束规则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) v

11、sum(S) vavg(S) v, , , (frequent constraint)简洁性简洁性yesyesyesyesyesyesyesyesyesyesweaklyweaklyweakly nononono(no)2004年12月14日星期二Data Mining: Concepts and Techniques77Classification of ConstraintsConvertibleanti-monotoneConvertiblemonotoneStronglyconvertibleInconvertibleSuccinctAntimonotoneMonotonel CFG(

12、Constrained Frequent pattern Growth)算法： - 基于FP-Growth算法， 针对可转变约束条件 - Can we push more constraints into frequent pattern mining? (J.Pei, J.Han KDD00)l MultipleJoins、Reorder和Direct算法： - 约束条件为布尔表达式形式 - Mining Association Rules with Item Constraints(Srikant, Vu&Agrawal 1997) Transaction_ID Items In

13、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 l交易数据库TDB如下所示，支持度为 3 频繁项目按照降续排列 ：a:5; e:4; b:3; c:3; d:3; f:3l将排序后的每次交易的项目列表的前缀项目映射到条件数据库TDB|f; TDB|d; TDB|c; TDB|b; TDB|e中l例如：对于交易号为100的交易(a,e,c,d,f)。将f的前缀a,e,c,d插入f的条件数据库TDB|f中；将d的前缀a,e,c插入d的条件数据库TDB|d中；将c的前缀a,e插入c的条件数据库TDB|

14、c中；将e的前缀a插入e的条件数据库TDB|e中。TD Baecdf,ab,aecf,aebcdf,aebd Frequent items: a,e,b,c,d,f f-Conditional database TD B |f aecd,aec,aebcd frequent items:a,e,c TDB|d TDB|c TDB|e TDB|b l条件数据库的性质:如果模式在 TDB|f 中是频繁的，则f 在TDB|f中也一定是频繁的l频繁集的生长过程 1. 在 TDB|f 中找到相应的频繁项目集, 被称为f的条件频繁项目集 2. 对于每一个在中的频繁项目e，找出TDB|ef 中相应的频繁项目

15、集，这是一个递归的过程lCaSum(S)180，所以可以不必考虑项集d。l如果不满足约束，则不必产生的条件项目集,也不必产生的条件数据库TDB | 例如： Sum(a,b)=200 180 ，不满足约束条件Ca ，项集a,b的任何超集都不满足约束，因此不必产生a,b的条件数据库。l如果满足约束，则不必对条件数据库TDB| 中的其余部分用Ca进行约束检查，此处是在TDB | 中的频繁项目集。 (No constraint checking in the remaining conditional database TDB| , if satisfies the constraint.) 例如：对

16、于条件数据库TDB| f，只存在3个频繁1-项集a, e, c，sum(a, c, e, f)160 180。显然，项集a, c, e, f的任何子集均满足约束条件Ca ，因此在对这个条件数据库的挖掘过程中，就不必进行约束条件检查了。TDB aecdf,ab,aecf,aebcdf,aebd Frequent items: a,e,b,c,d,fC(a)=true; C(e)=true; C(b)=true; C(c)=true; C(f)=true; C(d)=false TDB|f aecd,aec,aebcd Frequent items: a,e,c因为C(aecf)=true;所以C

17、(af)=true; C(ef)=true; C(cf)=true; C(aef)=true; C(acf)=true; TDB|c ae,ae,aeb Frequent items: a,e因为C(aec)=true;所以C(ac)=true; C(ec)=true; TDB|b a,ae,ae Frequent items: a,e因为C(ab)=false;所以ab的所有超集均不满足约束条件C TDB|e a,a,a,a Frequent items: aC(ae)=true;l我们所讨论的约束条件为项约束条件，即要求关联规则中至少包含用户定义的一个项集中的某个项。设给定项约束条件B，B

18、为I上的一个布尔 表 达 式 。 假 设 B 已 经 转 变 为 D N F 形 式 ：d1 d2 dm， 其 中 每 个 di形 如 ：ai1ai2ain。l定义1 如果aij为i或i，其中iI，那么分别称为项包含条件或项不包含条件。如果项集X包含di中所有项包含条件，而且不包含di中所有项不包含条件，那么称项集X满足约束条件项di。如果X满足约束条件B中某个约束条件项di，那么称X满足约束条件B。 lDirect算法能直接从约束条件B中产生候选项集。l候选项集产生方法： 11kBkBkDFLC具体步骤：1. 2. Delete all candidates in that do not satisfy B3. Delete all candidates in with a k-subset that satisfies B but does not have minimum support4. For each disjunct di=ai1ai2ain，in B with exactly k+1 non-negated elements ,add the itemset to if all the are fre