DATA MINING(CH2)

《DATA MINING(CH2)》由会员分享，可在线阅读，更多相关《DATA MINING(CH2)（42页珍藏版）》请在装配图网上搜索。

1、第第2 2章章 关联规则关联规则 数据挖掘与知识发现(第2版)1李雄飞等2003,2010关联规则关联规则 典型的关联规则发现问题是分析超市中的货篮数典型的关联规则发现问题是分析超市中的货篮数典型的关联规则发现问题是分析超市中的货篮数典型的关联规则发现问题是分析超市中的货篮数据，通过发现顾客放入货篮中商品之间的关系，分据，通过发现顾客放入货篮中商品之间的关系，分据，通过发现顾客放入货篮中商品之间的关系，分据，通过发现顾客放入货篮中商品之间的关系，分析顾客的购买习惯。本章主要介绍如下几个方面的析顾客的购买习惯。本章主要介绍如下几个方面的析顾客的购买习惯。本章主要介绍如下几个方面的析顾客的购买习惯

2、。本章主要介绍如下几个方面的内容：内容：内容：内容：关联规则基本模型关联规则基本模型关联规则基本模型关联规则基本模型AprioriApriori、LIGLIG、FPFP等算法等算法等算法等算法多级关联规则多级关联规则多级关联规则多级关联规则多维关联规则多维关联规则多维关联规则多维关联规则关联规则价值衡量关联规则价值衡量关联规则价值衡量关联规则价值衡量2李雄飞等2003,2010引言引言 关联规则关联规则关联规则关联规则反映一个事物与其他事物之间的相互依存性和关联反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，性。如果两个或者多个事物之间存在一定

3、的关联关系，那么，其中一个事物就能够通过其他事物预测到。其中一个事物就能够通过其他事物预测到。从商业交易记录中发现数据关联关系，用于商家决策。从商业交易记录中发现数据关联关系，用于商家决策。商品分类设计商品分类设计商品分类设计商品分类设计降价经销分析降价经销分析降价经销分析降价经销分析生产安排生产安排生产安排生产安排货架摆放策略货架摆放策略货架摆放策略货架摆放策略 典型应用典型应用典型应用典型应用:超市货篮数据超市货篮数据(Market Basket)(Market Basket)分析。通过发现顾分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。客放入货篮中的不同商品之间的

4、关系来分析顾客的购买习惯。分析以商品分析以商品分析以商品分析以商品C C C C为后件的规则，有助于商家采取相应措施促进该产品的销售；为后件的规则，有助于商家采取相应措施促进该产品的销售；为后件的规则，有助于商家采取相应措施促进该产品的销售；为后件的规则，有助于商家采取相应措施促进该产品的销售；分析以商品分析以商品分析以商品分析以商品A A A A作为前件的规则，可知终止该商品的销售会影响某些商品销售；作为前件的规则，可知终止该商品的销售会影响某些商品销售；作为前件的规则，可知终止该商品的销售会影响某些商品销售；作为前件的规则，可知终止该商品的销售会影响某些商品销售；根据货架根据货架根据货架根

5、据货架A A A A上的商品和货架上的商品和货架上的商品和货架上的商品和货架B B B B上的商品之间的关联规则，合理安排货架布局。上的商品之间的关联规则，合理安排货架布局。上的商品之间的关联规则，合理安排货架布局。上的商品之间的关联规则，合理安排货架布局。3李雄飞等2003,2010关联规则基本模型关联规则基本模型 IBMIBM公司公司AlmadenAlmaden研究中心的研究中心的R.AgrawalR.Agrawal首先提出关联规则模型，并给首先提出关联规则模型，并给出求解算法出求解算法AISAIS。随后又出现了随后又出现了SETMSETM和和AprioriApriori等算法。其中，等算

6、法。其中，AprioriApriori是关联规则模型是关联规则模型中的经典算法。中的经典算法。设设I I=i i1 1,i i2 2,i im m 为所有项目的集合，为所有项目的集合，D D为事务数据库，事务为事务数据库，事务T T是一个项是一个项目子集（目子集（T T I I）。每一个事务具有唯一的事务标识）。每一个事务具有唯一的事务标识TIDTID。设设A A是一个由项目构成的集合，称为是一个由项目构成的集合，称为项集项集项集项集。事务。事务T T包含项集包含项集A A，当且仅当，当且仅当A A T T。如果项集如果项集A A中包含中包含k k个项目，则称其为个项目，则称其为k k k k

7、项集项集项集项集。项集。项集A A在事务数据库在事务数据库D D中出现中出现的次数占的次数占D D中总事务的百分比叫做项集的中总事务的百分比叫做项集的支持度支持度支持度支持度。如果项集的支持度超过。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是用户给定的最小支持度阈值，就称该项集是频繁项集频繁项集频繁项集频繁项集（或大项集）。（或大项集）。关联规则是形如关联规则是形如X XY Y的逻辑蕴含式，其中的逻辑蕴含式，其中X X I I，Y Y I I，且，且X XY Y=。如果。如果事务数据库事务数据库D D中有中有s s%的事务包含的事务包含X XY Y，则称关联规则，则称关联规则X

8、XY Y的支持度为的支持度为s s%。若项集若项集X X的支持度记为的支持度记为supportsupport(X X)，规则的，规则的信任度信任度信任度信任度为为 support support(X XY Y)supportsupport(X X)。supportsupport(X XY Y)=)=P P(X X Y Y)confidenceconfidence(X XY Y)=)=P P(Y Y|X X)4李雄飞等2003,2010关联规则基本模型关联规则基本模型关联规则就是支持度和信任度分别满足用户给定阈关联规则就是支持度和信任度分别满足用户给定阈关联规则就是支持度和信任度分别满足用户给定

9、阈关联规则就是支持度和信任度分别满足用户给定阈值的规则。值的规则。值的规则。值的规则。发现关联规则需要经历如下两个步骤：发现关联规则需要经历如下两个步骤：发现关联规则需要经历如下两个步骤：发现关联规则需要经历如下两个步骤：1.1.找出所有频繁项集。找出所有频繁项集。2.2.由频繁项集生成满足最小信任度阈值的规则。由频繁项集生成满足最小信任度阈值的规则。由由m m个项目形成的不同项集的数目可以达到个项目形成的不同项集的数目可以达到2 2m m11个，个，尤其在海量数据库尤其在海量数据库D D中，找频繁项集是一个中，找频繁项集是一个NPNP难度的难度的问题。问题。为了避免计算所有项集的支持度，为了

10、避免计算所有项集的支持度，AprioriApriori算法引入潜在频繁项集的算法引入潜在频繁项集的概念。若潜在频繁概念。若潜在频繁k k项集的集合记为项集的集合记为C Ck k ，频繁，频繁k k项集的集合记为项集的集合记为L Lk k ，m m个个项目构成的项目构成的k k项集的集合为项集的集合为 ，则三者之间满足关系，则三者之间满足关系 L Lk k C Ck k 。5李雄飞等2003,2010Apriori算法算法关联规则具有如下性质关联规则具有如下性质：性质性质2.1 2.1 频繁项集的子集必为频繁项集。频繁项集的子集必为频繁项集。性质性质2.2 2.2 非频繁项集的超集一定是非频繁的

11、。非频繁项集的超集一定是非频繁的。发现频繁项集的步骤发现频繁项集的步骤:1.1.单趟扫描数据库单趟扫描数据库D D得到频繁得到频繁1 1项集构成的集合项集构成的集合L L1 1。2.2.连接步：由连接步：由JOINJOIN运算得到潜在频繁项集运算得到潜在频繁项集C Ck k的集合。的集合。3.3.剪枝步：当潜在剪枝步：当潜在k k项集的某个项集的某个(k k1)1)子集不是子集不是L Lk k11中的成中的成员时，可以将该潜在频繁项集从员时，可以将该潜在频繁项集从C Ck k中移去。中移去。4.4.单趟扫描数据库单趟扫描数据库D D，计算，计算C Ck k中各个项集的支持度。中各个项集的支持度

12、。5.5.将将C Ck k中不满足最小支持度的项集剔除，形成由频繁中不满足最小支持度的项集剔除，形成由频繁k k项集项集构成的集合构成的集合L Lk k。6李雄飞等2003,2010Apriori算法算法AprioriApriori算法如下：算法如下：(1)(1)L L1 1=频繁频繁1 1项集项集;(2)for(2)for(k k=2;=2;L Lk k-1-1;k k+)do begin+)do begin(3)(3)C Ck k=apriori_gen(=apriori_gen(L Lk k-1-1);/);/新的潜在频繁项集新的潜在频繁项集(4)for all(4)for all tr

13、ansactionstransactions t t D D do begin do begin(5)(5)C Ct t=subset(=subset(C Ck k,t t);/t);/t中包含的潜在频繁项集中包含的潜在频繁项集(6)for all(6)for all candidates ccandidates c C Ct t dodo(7)(7)c c.countcount+;+;(8)end;(8)end;(9)(9)L Lk k=c=c C Ck k|c.count|c.count minsupminsup(10)end;(10)end;(11)Answer=;(11)Answer=

14、;7李雄飞等2003,2010Apriori算法算法Apriori_gen()Apriori_gen()Apriori_gen()Apriori_gen()函数函数函数函数:以以L Lk k11为参数，用为参数，用L Lk k11和和L Lk k11进行连接操作生进行连接操作生成一个超集成一个超集C Ck k作为潜在频繁项集。作为潜在频繁项集。(1)insert into(1)insert into C Ck k(2)select(2)select p p1,1,p p2,2,p p k k-1,-1,q q k k-1-1(3)from(3)from L Lk k11 p p,L Lk k1

15、1 q q(4)where(4)where p p1=1=q q1,1,p p k k-2=-2=q q k k-2,-2,p p k k-1-1 m m m m+1)then begin+1)then begin+1)then begin+1)then begin(7)(7)(7)(7)H H H Hm m m m+1+1+1+1=apriori_gen(=apriori_gen(=apriori_gen(=apriori_gen(H H H Hm m m m););););(8)for all(8)for all(8)for all(8)for all h h h hm m m m+1+1

16、+1+1 H H H Hm m m m+1+1+1+1 do begin do begin do begin do begin(9)conf=support(9)conf=support(9)conf=support(9)conf=support(L L L Lk k k k)/support()/support()/support()/support(L L L Lk k k k-h h h hm+1m+1m+1m+1););););(10)if(10)if(10)if(10)if(confconfconfconfminconfminconfminconfminconf)then)then)

17、then)then(11)output(11)output(11)output(11)output 规则规则规则规则(L L L Lk k k k-h h h hm m m m+1+1+1+1)h h h hm m m m+1+1+1+1 with with with with confidenceconfidenceconfidenceconfidence=confconfconfconf and and and and supportsupportsupportsupport=supportsupportsupportsupport(L L L Lk k k k););););(12)el

18、se(12)else(12)else(12)else(13)delete(13)delete(13)delete(13)delete h h h hm m m m+1+1+1+1 from from from from H H H Hm m m m+1+1+1+1;(14)end;(14)end;(14)end;(14)end;(15)call ap_genrules(15)call ap_genrules(15)call ap_genrules(15)call ap_genrules(L L L Lk k k k,H H H Hm m m m+1+1+1+1););););(16)end;(

19、16)end;(16)end;(16)end;10李雄飞等2003,2010LIG算法算法 定义定义2.1 2.1 设设T T是事务数据库中的一个事务，是事务数据库中的一个事务，T T D D，称，称T T中基本中基本项的个数为事务项的个数为事务T T的规模，记为的规模，记为 T T。定义定义2.2 2.2 若若d d是一个项集，将是一个项集，将d d中元素的个数称为该项集的长中元素的个数称为该项集的长度，记为度，记为 d d。定理定理2.1 2.1 在一个已知事务数量的数据集在一个已知事务数量的数据集D D中，规模小于中，规模小于 A A 的的事务不会影响计算事务不会影响计算 D D(A A

20、)。(A(A在在D D中出现的次数中出现的次数)定理定理2.2 2.2 已知数据集已知数据集D D中的一个频繁中的一个频繁k k项集项集A Ak k，即，即 D D(A Ak k)minsupminsup，令数据集，令数据集DD=d d d d D Dd d m m k k，若若 D D(A Ak k)minsupminsup，则对，则对D D中任意一个频繁中任意一个频繁m m项集项集A Am m而言，而言，一定有一定有A Ak k A Am m。11李雄飞等2003,2010LIG算法算法 定义定义2.3 2.3 当当k kp p q q时，时，s sp p为项集为项集I I在规模为在规模为

21、p p的事务中出现的的事务中出现的次数；当次数；当p p=q q时，时，s sp p是项集是项集I I在规模不低于在规模不低于p p的事务中出现的次的事务中出现的次数。这里数。这里 元组元组(s sk k,s sk+k+1 1,s sq q11,s sq q)称为项集称为项集I I的的多段支持度多段支持度多段支持度多段支持度。定义定义2.4 2.4 若项若项I I能与区间能与区间 i ip p,i iq q，i ir r,i is s，i iu u,i iv v 中中的频繁的频繁1 1项集构成潜在频繁项集构成潜在频繁2 2项集，而与任何区间外的项均不项集，而与任何区间外的项均不构成频繁构成频繁

22、2 2项集，则称这些区间为项项集，则称这些区间为项I I的的相关区间相关区间相关区间相关区间。12李雄飞等2003,2010LIG算法算法 定理定理2.3 2.3 若频繁若频繁k k项集项集itemitemi i和和itemitemj j的多段支持度分别为的多段支持度分别为 (i ik k,i ik+k+1 1,i iq q)和和(j jk k,j jk+k+1 1,j jq q)，满足，满足 1)+=1)+=t t;(7)end;(7)end;(8)(8)L L1 1=large 1-=large 1-itemsetitemset;/满足最小支持度满足最小支持度(9)(9)C C2 2=a

23、a,b b a a L L1 1 and and b b a a.AREAAREA;/潜在频繁潜在频繁2 2项集项集14李雄飞等2003,2010LIG算法算法(10)(10)(10)(10)M M M M2 2 2 2=C C C C2 2 2 2中相异元素中相异元素中相异元素中相异元素;/提取因子提取因子提取因子提取因子(11)(11)(11)(11)k k k k=2,=2,=2,=2,q q q q置初值；置初值；置初值；置初值；(12)do begin(12)do begin(12)do begin(12)do begin(13)for all(13)for all(13)for a

24、ll(13)for all transactions t transactions t transactions t transactions t do begin do begin do begin do begin(14)(14)(14)(14)C C C Ct t t t=subset(=subset(=subset(=subset(C C C Ck k k k ,t t t t)；/t t t t中包含的中包含的中包含的中包含的 潜在频繁项集潜在频繁项集潜在频繁项集潜在频繁项集(15)(15)(15)(15)r r r r=t t t t ;(16)if(16)if(16)if(16)

25、if(r r r r q q q q)then)then)then)then r r r r=q q q q;(17)if(17)if(17)if(17)if(r r r r=k k k k)then )then )then )then t t t t;/;/;/;/剔除剔除剔除剔除 长度为长度为长度为长度为k k k k的事务的事务的事务的事务15李雄飞等2003,2010LIG算法算法(18)else(18)else(18)else(18)else t t t t =M M M Mk k k k;/;/;/;/剔除事务中无价值的项剔除事务中无价值的项剔除事务中无价值的项剔除事务中无价值的项

26、(19)for all(19)for all(19)for all(19)for all Candidates cCandidates cCandidates cCandidates c C C C Ct t t t do do do do(20)(20)(20)(20)c.sc.sc.sc.sr r r r+；(21)end(21)end(21)end(21)end(22)(22)(22)(22)LCLCLCLCk k k k=limit_gen(=limit_gen(=limit_gen(=limit_gen(k k k k,C C C Ck k k k);/);/);/);/生成生成生成

27、生成 L L L Lk k k k 和和和和 LCLCLCLCk k k k(23)(23)(23)(23)C C C Ck k k k+1+1+1+1=JOIN(=JOIN(=JOIN(=JOIN(LCLCLCLCk k k k)；/新的潜在频繁项集的集合新的潜在频繁项集的集合新的潜在频繁项集的集合新的潜在频繁项集的集合(24)(24)(24)(24)M M M Mk k k k+1+1+1+1=C C C Ck k k k+1+1+1+1中相异元素中相异元素中相异元素中相异元素;/;/;/;/提取因子提取因子提取因子提取因子(25)(25)(25)(25)k k k k+;+;+;+;q

28、q q q+;+;+;+;(26)end while(26)end while(26)end while(26)end while(LCLCLCLCk k k k 1);1);1);1);(27)(27)(27)(27)L L L L=16李雄飞等2003,2010LIG算法算法 limit_gen()limit_gen()limit_gen()limit_gen()函数函数函数函数：(1)for all c(1)for all c C Ck k do begin do begin(2)for(p=q,sum=c.sp;sum=k;p-)do(2)for(p=q,sum=c.sp;sum=k;

29、p-)do(3)sum+=c.sp;/(3)sum+=c.sp;/求求c c可能产生的最大潜在项集之长可能产生的最大潜在项集之长(4)if(sum(4)if(sum minsup)then beginminsup)then begin(5)if(p=q)then c.limit=(5)if(p=q)then c.limit=;/;/未确定最大潜未确定最大潜 /在项集之长在项集之长(6)else c.limit=p;(6)else c.limit=p;(7)L(7)Lk k=L=Lk kc;/c;/构成频繁项集的集合构成频繁项集的集合(8)if(pk)then LC(8)if(pk)then L

30、Ck k=LC=LCk kc;/c;/构成种子集构成种子集(9)end;(9)end;(10)end;(10)end;17李雄飞等2003,2010LIG算法算法JOIN(JOIN(JOIN(JOIN(LCLCLCLCk k k k)函数函数函数函数：insert into insert into C Ck k select p.item select p.item1 1,p.item,p.item2 2,p.item,p.itemk-1k-1,q.item,q.itemk-1k-1 from from LCLCk k-1-1 p p,LCLCk k-1-1 q q,C C2 2 s s wh

31、ere(p.item where(p.item1 1=q.item=q.item1 1,p.item,p.itemk-2k-2=q.item=q.itemk-2k-2,p.item p.itemk-1k-1q.itemq.itemk-1k-1,p.item p.itemk-1k-1=s.item=s.item1 1,q.item,q.itemk-1k-1=s.item=s.item2 2)and and minsupminsup;18李雄飞等2003,2010LIG算法算法(例例)19李雄飞等2003,2010LIG算法算法(例例)20李雄飞等2003,2010LIG算法算法(例例)21李雄飞

32、等2003,2010LIG算法算法(例例)22李雄飞等2003,2010LIG算法算法(例例)23李雄飞等2003,2010FP-growth算法算法 频繁模式生长算法频繁模式生长算法频繁模式生长算法频繁模式生长算法(FP-growth)(FP-growth)不用生成潜在频繁项集，而是不用生成潜在频繁项集，而是用分治法把数据库中的频繁项目放入用分治法把数据库中的频繁项目放入FPFP树中，并且保留项集树中，并且保留项集的关联信息；然后把数据库划分为条件数据基，分别在每个的关联信息；然后把数据库划分为条件数据基，分别在每个数据基上挖掘。数据基上挖掘。例：下图的例：下图的FPFP树和数据库树和数据库

33、24李雄飞等2003,2010FP-growth算法算法Procedure FP_growth(Procedure FP_growth(TreeTree,)(1)if Tree(1)if Tree包含一个单一路径包含一个单一路径P thenP then(2)for each(2)for each 路径路径P P中节点组合中节点组合(记为记为)(3)(3)生成模式生成模式，拥有支持度为，拥有支持度为节点中的节点中的 最小支持度最小支持度(4)else for each(4)else for each 树的头列表节点树的头列表节点a ai i (5)(5)生成模式生成模式=a ai i且且supp

34、ort=support=ai.supportai.support(6)(6)构成构成，的条件模式基和，的条件模式基和的条件的条件FP_treeFP_tree TreeTree(7)if(7)if TreeTree then then(8)(8)call call FP_growth(TreeFP_growth(Tree,);,);初始后缀模式初始后缀模式初始后缀模式初始后缀模式：长度为长度为1 1的频繁模式。的频繁模式。条件模式基条件模式基条件模式基条件模式基：是一个子数据集，由是一个子数据集，由FPFP树中与后缀模式一起出现的前缀路径树中与后缀模式一起出现的前缀路径集组成。集组成。25李雄飞

35、等2003,2010FP-growth算法算法 FP_treeFP_treeFP_treeFP_tree结构的优点：结构的优点：结构的优点：结构的优点：(1)(1)在在完完备备性性方方面面，它它不不会会打打破破交交易易中中的的任任何何模模式式，而而且且包含了挖掘序列模式所需的全部信息；包含了挖掘序列模式所需的全部信息；(2)(2)在在紧紧密密性性方方面面，它它剔剔除除不不相相关关信信息息，不不包包含含非非频频繁繁项项，按按支支持持度度降降序序排排列列，支支持持度度高高的的项项在在FP_treeFP_tree中中共共享享的的机机会会也也高。高。FP_treeFP_treeFP_treeFP_tr

36、ee结构的缺点：结构的缺点：结构的缺点：结构的缺点：当当数数据据库库规规模模非非常常大大时时，在在内内存存中中构构建建FP_treeFP_tree是是不不切切实实际的。际的。26李雄飞等2003,2010FP-growth算法算法(例例)用事务数据库建立用事务数据库建立FP_treeFP_tree，如图，如图2.52.5和表和表2.22.2所示。所示。27李雄飞等2003,2010FP-growth算法算法(例例)步骤步骤1 1：从从FP_treeFP_tree的头表开始，按着每个频繁项的连接路径遍历的头表开始，按着每个频繁项的连接路径遍历FP_treeFP_tree，列出可达此项的所有前缀路

37、径，得到条件模式基。，列出可达此项的所有前缀路径，得到条件模式基。28李雄飞等2003,2010FP-growth算法算法(例例)步骤步骤2 2：对每个模式基，计算各个项的支持度，用模式基中的频繁对每个模式基，计算各个项的支持度，用模式基中的频繁项建立项建立FP_treeFP_tree。29李雄飞等2003,2010FP-growth算法算法(例例)步骤步骤3 3：递归挖掘条件递归挖掘条件FP_treeFP_tree。30李雄飞等2003,2010FP-growth算法算法(例例)步骤步骤4 4：单单FP_tree FP_tree 路径生成。假定路径生成。假定FP_tree FP_tree T

38、 T只包含路径只包含路径P P，P P的的子路径所有可能的组合就是该树包含的所有频繁项集。子路径所有可能的组合就是该树包含的所有频繁项集。31李雄飞等2003,2010多级关联规则多级关联规则 由于多维数据空间上的数据稀少，在低层或原始抽象级别上由于多维数据空间上的数据稀少，在低层或原始抽象级别上很难发现数据项间的强关联（很难发现数据项间的强关联（Strong AssociationsStrong Associations）。）。HanHan等人指出强关联在高层概念上可以描述通常意义的知识。等人指出强关联在高层概念上可以描述通常意义的知识。多级关联规则可以在不同的抽象空间上描述多层抽象知识。多

39、级关联规则可以在不同的抽象空间上描述多层抽象知识。多级关联规则可以在不同的抽象空间上描述多层抽象知识。多级关联规则可以在不同的抽象空间上描述多层抽象知识。32李雄飞等2003,2010多级关联规则多级关联规则 多级关联规则的挖掘可以沿用多级关联规则的挖掘可以沿用“支持度和信任度支持度和信任度”的框架。的框架。挖掘多级关联规则时可采用自上而下，深度优先的方法，由挖掘多级关联规则时可采用自上而下，深度优先的方法，由较抽象的概念层开始向下，到较低的具体概念层（如原始概较抽象的概念层开始向下，到较低的具体概念层（如原始概念层），对每个概念层的频繁项集累加计数，直到再也找不念层），对每个概念层的频繁项集

40、累加计数，直到再也找不到频繁项集为止。到频繁项集为止。AprioriApriori算法及其变种算法均可以应用到每一级频繁项集的发算法及其变种算法均可以应用到每一级频繁项集的发现上。现上。多级关联规则模型分类多级关联规则模型分类:所有级别采用统一的最小支持度阈值所有级别采用统一的最小支持度阈值所有级别采用统一的最小支持度阈值所有级别采用统一的最小支持度阈值;低级别上采用较小的最小支持度阈值。低级别上采用较小的最小支持度阈值。低级别上采用较小的最小支持度阈值。低级别上采用较小的最小支持度阈值。33李雄飞等2003,2010多级关联规则多级关联规则 可以用如下几种策略来设置不同的支持度阈值。可以用如

41、下几种策略来设置不同的支持度阈值。1.1.各级间相互独立。在深度优先的检索中没有任何频繁项集的各级间相互独立。在深度优先的检索中没有任何频繁项集的背景知识用于剪枝。对每个节点的处理与其父节点是否为频背景知识用于剪枝。对每个节点的处理与其父节点是否为频繁项集无关。繁项集无关。2.2.各级之间单项过滤。算法考察第各级之间单项过滤。算法考察第i i级项目的充分必要条件为级项目的充分必要条件为(ii1)1)级的相应父节点为频繁项集。也就是在一般关联关系级的相应父节点为频繁项集。也就是在一般关联关系的基础上研究更详尽的关联规则。的基础上研究更详尽的关联规则。3.3.各级之间项集过滤。如果考察第各级之间项

42、集过滤。如果考察第i i级的级的k k项集，当且仅当项集，当且仅当(ii1)1)级的相应父节点中级的相应父节点中k k项集为频繁项集。项集为频繁项集。34李雄飞等2003,2010多级关联规则多级关联规则 规则冗余问题规则冗余问题规则冗余问题规则冗余问题 概念分层允许在不同抽象层上发现知识，所以多级关联概念分层允许在不同抽象层上发现知识，所以多级关联规则在数据挖掘中能发挥较大的作用。但由于规则在数据挖掘中能发挥较大的作用。但由于“祖先祖先”关系关系的原因，有些规则可能是冗余的。的原因，有些规则可能是冗余的。(1)(1)如果同时挖掘到这两条规则且后者不能提供更新的信如果同时挖掘到这两条规则且后者

43、不能提供更新的信息，就把这个规则剔除。息，就把这个规则剔除。(2)(2)设规则设规则R R1 1是规则是规则R R2 2的祖先，如果通过修改的祖先，如果通过修改R R2 2的前件使的前件使之提升到上一级概念抽象后，能够得到规则之提升到上一级概念抽象后，能够得到规则R R1 1，则规则，则规则R R2 2就是就是冗余的，可以从规则集中把冗余的，可以从规则集中把R R2 2删去。删去。35李雄飞等2003,2010多维关联规则多维关联规则 在多维数据库中，将每个不同的谓词层称作维。在多维数据库中，将每个不同的谓词层称作维。规则规则 购买购买(X X,“,“牛奶牛奶”)”)购买购买(X X,“,“面

44、包面包”)”)为单维或者维内关联规则。为单维或者维内关联规则。多维关联规则是涉及两个或多个属性或谓词的规则。多维关联规则是涉及两个或多个属性或谓词的规则。例如：例如：年龄年龄(X X,“20.30”)and,“20.30”)and 职业职业(X X,“,“学生学生”)”)购买购买(X X,“,“笔记本电脑笔记本电脑”)”)如果在规则的每一维上使用不同的断言，就把包含两个或两如果在规则的每一维上使用不同的断言，就把包含两个或两个以上断言的关联规则称为个以上断言的关联规则称为多维关联规则多维关联规则多维关联规则多维关联规则。如果规则中的断言不重复，就称这样的规则为维间关联规则如果规则中的断言不重复

45、，就称这样的规则为维间关联规则如果规则中的断言不重复，就称这样的规则为维间关联规则如果规则中的断言不重复，就称这样的规则为维间关联规则（Interdimension Association ruleInterdimension Association ruleInterdimension Association ruleInterdimension Association rule）；）；）；）；如果规则中的断言可以重复，就称之为混合维关联规则（如果规则中的断言可以重复，就称之为混合维关联规则（如果规则中的断言可以重复，就称之为混合维关联规则（如果规则中的断言可以重复，就称之为混合维关联规则（

46、Hybrid-Hybrid-Hybrid-Hybrid-dimension Association Ruledimension Association Ruledimension Association Ruledimension Association Rule）。）。）。）。36李雄飞等2003,2010数据属性与多维关联规则数据属性与多维关联规则数据库属性分为定性和定量两种。定性的属性有有数据库属性分为定性和定量两种。定性的属性有有限个可能取值；定量的属性不能给出确切取值范围限个可能取值；定量的属性不能给出确切取值范围的数量值。的数量值。数量属性的处理方法分为三种：数量属性的处理方法分为

47、三种：（1 1）把数量值划分为若干个离散区间，用区间值描述数量属）把数量值划分为若干个离散区间，用区间值描述数量属性，这样就可以把定量的问题转化为定性的问题。也就是通性，这样就可以把定量的问题转化为定性的问题。也就是通过数量属性静态离散化挖掘多维关联规则。过数量属性静态离散化挖掘多维关联规则。（2 2）对离散数据而言，为适应数据挖掘需要，离散化进程可）对离散数据而言，为适应数据挖掘需要，离散化进程可以是动态的，这样的关联规则称为数量相关规则。以是动态的，这样的关联规则称为数量相关规则。（3 3）如果在离散化时考虑数据点间的距离，就将这样的数量）如果在离散化时考虑数据点间的距离，就将这样的数量关

48、联规则称为基于距离的关联规则。关联规则称为基于距离的关联规则。37李雄飞等2003,2010关联规则价值衡量关联规则价值衡量 对对关关联联规规则则的的评评价价与与价价值值衡衡量量涉涉及及两两个个层层面面：系系统统客客观观的的层层面面和和用用户户主主观的层面。观的层面。1.1.系统客观层面系统客观层面系统客观层面系统客观层面 规规则则的的兴兴兴兴趣趣趣趣度度度度是是在在基基于于统统计计独独立立性性假假设设下下真真正正的的强强度度与与期期望望的的强强度之比度之比。收收收收集集集集强强强强度度度度（Collective Collective StrengthStrength），使使用用“大大于于期期

49、望望值值”为为条条件件来来发发现现有有意意义义的的关关联联规规则则。项项集集的的收收集集强强度度是是0,0,区区间间上上的的一一个个数数值值，其中，其中，0 0表示完备的否定相关性，表示完备的否定相关性，表示完备的正相关性。表示完备的正相关性。2.2.用户主观层面用户主观层面用户主观层面用户主观层面 只有用户才能决定规则的有效性、可行性。可以采用基于约束的数据只有用户才能决定规则的有效性、可行性。可以采用基于约束的数据挖掘方法。具体约束的内容有：挖掘方法。具体约束的内容有：(1)(1)数据约束数据约束数据约束数据约束。用户可以指定数据挖掘的范围，而不一定是全部数据。用户可以指定数据挖掘的范围，

50、而不一定是全部数据。(2)(2)维和层次约束维和层次约束维和层次约束维和层次约束。用户可以指定在数据的某些维以及这些维的某些层。用户可以指定在数据的某些维以及这些维的某些层次上进行数据挖掘。次上进行数据挖掘。(3)(3)规规则约束则约束则约束则约束。可以引入模板（。可以引入模板（TemplateTemplate）的概念，用以指定需要的规）的概念，用以指定需要的规则类型。用户使用模板确定感兴趣的规则。如果一条规则与包含模板则类型。用户使用模板确定感兴趣的规则。如果一条规则与包含模板（Inclusive TemplateInclusive Template）相匹配，就是感兴趣的规则，如果一条规则与

51、限）相匹配，就是感兴趣的规则，如果一条规则与限制模板（制模板（Restrictive TemplateRestrictive Template）相匹配，就是不感兴趣的规则。）相匹配，就是不感兴趣的规则。38李雄飞等2003,2010基于约束的关联规则基于约束的关联规则 基于约束的关联规则就是利用用户给出的各种约束关系，基于约束的关联规则就是利用用户给出的各种约束关系，使挖掘出的规则更有效。这些约束包括：使挖掘出的规则更有效。这些约束包括：1.1.知识类型约束知识类型约束知识类型约束知识类型约束：用以指明挖掘知识的类型。如关联规则等。：用以指明挖掘知识的类型。如关联规则等。2.2.数据约束数据约

52、束数据约束数据约束：用以确定所挖掘的数据集。：用以确定所挖掘的数据集。3.3.维数或层约束维数或层约束维数或层约束维数或层约束：说明挖掘规则的数据维数或抽象层次。：说明挖掘规则的数据维数或抽象层次。4.4.兴趣度约束兴趣度约束兴趣度约束兴趣度约束：给出反映度量规则兴趣程度的统计度量或阈值。：给出反映度量规则兴趣程度的统计度量或阈值。如支持度、信任度等。如支持度、信任度等。5.5.规则约束规则约束规则约束规则约束：指明挖掘规则的形式。强调规则模板，包括出现：指明挖掘规则的形式。强调规则模板，包括出现在规则前件、后件的断言数量，属性关系，属性值以及聚合度在规则前件、后件的断言数量，属性关系，属性值

53、以及聚合度等。等。39李雄飞等2003,2010基于约束的关联规则基于约束的关联规则 在规则挖掘中加入前件和后件重要度的比较限制，称为在规则挖掘中加入前件和后件重要度的比较限制，称为对对对对比度比度比度比度 。一个项集的一个项集的重要度重要度重要度重要度为所有组成元素重要度之和。为所有组成元素重要度之和。定义定义定义定义2.52.5 若一个关联规则前件和后件的对比度的值大于某个指若一个关联规则前件和后件的对比度的值大于某个指定的阈值，则称过于重要的前件推出非常次要的后件，该规则定的阈值，则称过于重要的前件推出非常次要的后件，该规则是冗余规则。是冗余规则。定义定义定义定义2.62.6 若有两个或

54、两个以上有相同后件的有意义关联规则，若有两个或两个以上有相同后件的有意义关联规则，分别为：分别为：R R1 1:A Ai i1 1,A Aj j1 1B B，R R2 2:A Ai i2 2,A Aj j2 2B B，R Rmm,R Rn n，R Rk k:A Aik ik ,A Ajk jkB B，信任度分别为：，信任度分别为：C C1 1,C C2 2,C Cmm ,C Cn n,C Ck k ，规定一个阈值，规定一个阈值 ，若规则，若规则R Rmm的前件属于规则的前件属于规则R Rn n的前的前件，即件，即R Rmm A A R Rn n A A，且，且 C Cmm C Cn n ，则称

55、规则，则称规则R Rn n是冗余是冗余规则。规则。例如例如例如例如，存在规则，存在规则R R1 1:1,2:1,244，信任度为，信任度为70%70%；规则；规则R R2 2:1,2,3:1,2,344，信，信任度为任度为71%71%；=2%=2%，则规则，则规则R R2 2是冗余的。是冗余的。40李雄飞等2003,2010基于约束的关联规则基于约束的关联规则 定义定义定义定义2.72.7 若有两个或两个以上有相同前件的有意义关联规则，分别为：若有两个或两个以上有相同前件的有意义关联规则，分别为：R R1 1:A AB Bi i1 1,B Bj j1 1，R R2 2:A AB Bi i2 2

56、,B Bj j2 2，R Rmm,R Rn n，R Rk k :A AB Bik ik ,B Bjk jk ，信任度分别为：，信任度分别为：C C1 1,C C2 2,C Cmm,C Cn n,C Ck k ，规定一个阈值，规定一个阈值，若规则，若规则R Rmm的后件属于规则的后件属于规则R Rn n的后件，即的后件，即R Rmm B B R Rn n B B，且，且 C Cmm C Cn n ，则称，则称规则规则R Rn n是冗余规则。是冗余规则。例如例如例如例如，存在规则，存在规则R R1 1:1:12,32,3，信任度为，信任度为70%70%；规则；规则R R2 2:1:12,3,42,

57、3,4，信，信任度为任度为69%69%；=2%=2%，则规则，则规则R R1 1是冗余的。是冗余的。定理定理定理定理2.42.4 若有两个有意义的关联规则，分别为：若有两个有意义的关联规则，分别为：R R1 1:A A1 1B B1 1，R R2 2:A A2 2 B B2 2，信任度分别为：，信任度分别为：C C1 1,C C2 2，规定一个阈值，规定一个阈值 ，若，若R R1 1 A A1 1 R R2 2 A A2 2且且R R2 2 B B2 2 R R1 1 B B1 1，同时，同时 C C1 1 C C2 2 ，则称规则，则称规则R R2 2是冗余规则。是冗余规则。例如例如例如例如

58、，存在规则，存在规则R R1 1:1:13,4,53,4,5，信任度为，信任度为70%70%；规则；规则R R2 2:1,2:1,23,43,4，信任度为信任度为68%68%；=2%=2%，则规则，则规则R R2 2是冗余的。是冗余的。定理定理定理定理2.52.5 如果关联规则如果关联规则R R:A AB B，同时满足定义，同时满足定义2.52.5和定理和定理2.42.4，则其必满，则其必满足定义足定义2.62.6。该定理剪除冗余规则的同时，得到简洁的规则。该定理剪除冗余规则的同时，得到简洁的规则。41李雄飞等2003,2010课外阅读课外阅读1.R.R.AgrawalAgrawal and

59、R.and R.SrikantSrikant,Fast algorithms for,Fast algorithms for mining association rules,In mining association rules,In Proc.1994 Int.Conf.Proc.1994 Int.Conf.Very Large Data BasesVery Large Data Bases,pp487-499,pp487-4992.J.Han,J.Pei,and Y.Yin,Mining frequent J.Han,J.Pei,and Y.Yin,Mining frequent patterns without candidate generation.In patterns without candidate generation.In Proc.Proc.2000 ACM-SIGMOD Int.Conf.Management of 2000 ACM-SIGMOD Int.Conf.Management of DataData,pp1-12,pp1-1242