关联规则挖掘理论和算法.ppt
《关联规则挖掘理论和算法.ppt》由会员分享,可在线阅读,更多相关《关联规则挖掘理论和算法.ppt(89页珍藏版)》请在三一办公上搜索。
1、主讲:赵宏庆,数据挖掘原理与算法,Chinese Academy of Science,2,第三章 关联规则挖掘理论和算法,Chinese Academy of Science,3,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.6 项目集格空间和它的操作3.7 基于项目序列集操作的关联规则挖掘算法3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法,Chinese
2、 Academy of Science,4,关联规则挖掘是数据挖掘研究的基础,关联规则挖掘(Association Rule Mining)是数据挖掘中研究较早而且至今仍活跃的研究方法之一。最早是由Agrawal等人提出的(1993)。最初提出的动机是针对购物篮分析(Basket Analysis)问题提出的,其目的是为了发现交易数据库(Transaction Database)中不同商品之间的联系规则。关联规则的挖掘工作成果颇丰。例如,关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘(Parallel Association Rule Mining)以及数量关联规则挖掘
3、(Quantitive Association Rule Mining)等。关联规则挖掘是数据挖掘的其他研究分支的基础。,Chinese Academy of Science,5,3.1 基本概念与解决方法,事务数据库设I=i1,i2,im 是一个项目集合,事务数据库D=t1,t2,tn 是由一系列具有唯一标识TID的事务组成,每个事务ti(i=1,2,n)都对应I上的一个子集。一个事务数据库可以用来刻画:购物记录:I是全部物品集合,D是购物清单,每个元组ti是一次购买物品的集合(它当然是I的一个子集)。其它应用问题,Chinese Academy of Science,6,支持度与频繁项目集
4、,定义(项目集的支持度).给定一个全局项目集I和数据库D,一个项目集I1I在D上的支持度(Support)是包含I1的事务在D中所占的百分比:support(I1)=|t D|I1 t|/|D|。,Chinese Academy of Science,7,支持度与频繁项目集,定义(频繁项目集).给定全局项目集I和数据库D,D中所有满足用户指定的最小支持度(Minsupport)的项目集,即大于或等于minsupport的I的非空子集,称为频繁项目集(频集:Frequent Itemsets)或者大项目集(Large Iitemsets)。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为
5、最大频繁项目集(最大频集:Maximum Frequent Itemsets)或最大大项目集(Maximum Large Iitemsets)。,Chinese Academy of Science,8,可信度与关联规则,定义(关联规则与可信度).给定一个全局项目集I和数据库D,一个定义在I和D上的关联规则形如I1I2,并且它的可信度或信任度或置信度(Confidence)是指包含I1和I2的事务数与包含I1的事务数之比,即Confidence(I1I2)=support(I1I2)/support(I1),其中I1,I2I,I1I2=。定义(强关联规则).D在I上满足最小支持度和最小信任度(
6、Minconfidence)的关联规则称为强关联规则(Strong Association Rule)。,Chinese Academy of Science,9,关联规则挖掘基本过程,关联规则挖掘问题可以划分成两个子问题:1.发现频繁项目集:通过用户给定Minsupport,寻找所有频繁项目集或者最大频繁项目集。2.生成关联规则:通过用户给定Minconfidence,在频繁项目集中,寻找关联规则。第1个子问题是近年来关联规则挖掘算法研究的重点。,Chinese Academy of Science,10,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生
7、成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.6 项目集格空间和它的操作3.7 基于项目序列集操作的关联规则挖掘算法3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法,Chinese Academy of Science,11,项目集格空间理论,Agrawal等人建立了用于事务数据库挖掘的项目集格空间理论(1993,Apriori 属性)。定理(Apriori 属性1).如果项目集X 是频繁项目集,那么它的所有非空子集都是频繁项目集。证明:设X是
8、一个项目集,事务数据库T 中支持X 的元组数为s。对X的任一非空子集为Y,设T中支持Y的元组数为s1。根据项目集支持数的定义,很容易知道支持X 的元组一定支持Y,所以s1 s,即support(Y)support(X)。按假设:项目集X 是频繁项目集,即support(X)minsupport,所以support(Y)support(X)minsupport,因此Y是频繁项目集。,Chinese Academy of Science,12,项目集格空间理论,定理(Apriori 属性2).如果项目集X 是非频繁项目集,那么它的所有超集都是非频繁项目集。证明(略),Chinese Academy
9、 of Science,13,经典的发现频繁项目集算法,1994年,Agrawal 等人提出了著名的Apriori 算法。算法3-1 Apriori(发现频繁项目集)输入:数据集D;最小支持数 minsup_count.输出:频繁项目集L。,(1)L1=large 1-itemsets;/所有1-项目频集(2)FOR(k=2;Lk-1;k+)DO BEGIN(3)Ck=apriori-gen(Lk-1);/Ck是k-候选集(4)FOR all transactions tD DO BEGIN(5)Ct=subset(Ck,t);/Ct是所有t包含的候选集元素(6)FOR all candida
10、tes c Ct DO(7)c.count+;(8)END(9)Lk=cCk|c.countminsup_count(10)END(11)L=Lk;,Chinese Academy of Science,14,apriori-gen过程,算法apriori中调用了apriori-gen(Lk-1),是为了通过(k-1)-频集产生K-侯选集。输入(k-1)-频繁项目集Lk-1输出k-候选项目集Ckhas_infrequent_subset(c,Lk-1),判断c是否加入到k-侯选集中。,(1)FOR all itemset p Lk-1 DO(2)FOR all itemset qLk-1 DO
11、(3)IF p.item1=q.item1,p.itemk-2=q.itemk-2,p.itemk-1 q.itemk-1 THEN BEGIN(4)c=pq;/把q的第k-1个元素连到p后(5)IF has_infrequent_subset(c,Lk-1)THEN(6)delete c;/删除含有非频繁项目子集的侯选元素(7)ELSE add c to Ck;(8)END(9)Return Ck;,Chinese Academy of Science,15,Apriori算法例子,Minsupport=50%(即挑选minsup_count=50%*4=2的项目集),Database D,
12、C1,L2,C2,C2,C3,L3,Chinese Academy of Science,16,关联规则的生成问题,根据上面介绍的关联规则挖掘的两个步骤,在得到了所有频繁项目集后,可以按照下面的步骤生成关联规则:对于每一个频繁项目集l,生成其所有的非空子集;对于l 的每一个非空子集x,计算Conference(x),如果Confidence(x)minconfidence,那么“x(l-x)”成立。,Chinese Academy of Science,17,关联规则的生成问题,算法3-4 从给定的频繁项目集中生成强关联规则算法3-4的核心是genrules递归过程,它实现一个频繁项目集中所有
13、强关联规则的生成。,Rule-generate(L,minconf)(1)FOR each frequent itemset lk in L(2)genrules(lk,lk);,Chinese Academy of Science,18,算法-递归测试一个频集中的关联规则,genrules(lk:frequent k-itemset,xm:frequent m-itemset)(1)X=(m-1)-itemsets xm-1|xm-1 in xm;(2)FOR each xm-1 in X BEGIN(3)conf=support(lk)/support(xm-1);(4)IF(conf m
14、inconf)THEN BEGIN(5)print the rule“xm-1(lk-xm-1),with support=support(lk),confidence=conf”;(6)IF(m-1 1)THEN/generate rules with subsets of xm-1 as antecedents(7)genrules(lk,xm-1);(8)END(9)END;,Chinese Academy of Science,19,Rule-generate算法例子,序号lkxm-1confidencesupport规则(是否是强规则)123523100%50%235(是)22352
15、67%50%235(否)3235367%50%325(否)42352567%50%253(否)5235567%50%523(否)623535100%50%352(是),Database D,前面的例子最大频繁项目集为2 3 5,conf=support(lk)/support(xm-1),Minconfidence=80%,Chinese Academy of Science,20,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.6 项目
16、集格空间和它的操作3.7 基于项目序列集操作的关联规则挖掘算法3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法,Chinese Academy of Science,21,Apriori算法的性能瓶颈,Apriori作为经典的频繁项目集生成算法,在数据挖掘中具有里程碑的作用。Apriori算法有两个致命的性能瓶颈:1多次扫描事务数据库,需要很大的I/O负载 对每次k循环,侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项目集包含10个项的话,那么就至少需要扫描事务数据库10遍。,C
17、hinese Academy of Science,22,Apriori算法的性能瓶颈,Apriori算法有两个致命的性能瓶颈:2可能产生庞大的侯选集 由Lk-1产生k-侯选集Ck是指数增长的,例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集对时间和主存空间都是一种挑战。,Chinese Academy of Science,23,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.6 项目集格空间和它的操作
18、3.7 基于项目序列集操作的关联规则挖掘算法3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法,Chinese Academy of Science,24,提高Apriori算法效率的技术,一些算法虽然仍然遵循Apriori 属性,但是由于引入了相关技术,在一定程度上改善了Apriori算法适应性和效率。,Chinese Academy of Science,25,提高Apriori算法效率的技术,主要的改进方法有:基于数据分割(Partition)的方法:基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能
19、是全局频繁的”。基于散列(Hash)的方法:基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。基于采样(Sampling)的方法:基本思想是先使用数据库的抽样数据得到一些可能成立的规则,然后利用数据库的剩余部分验证这些关联规则是否正确。其他:动态删除没有用的事务:“不包含任何Lk的事务对未来的扫描结果不会产生影响,因而可以删除”。,Chinese Academy of Science,26,基于数据分割的方法,定理3-5 设数据集D被分割成分块D1,D2,Dn,全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数minsup_coun
20、ti(i=1,2,n),按着如下方法生成:minsup_counti=minsup_count*|Di|/|D|则所有的局部频繁项目集涵盖全局频繁项目集。,Chinese Academy of Science,27,基于数据分割的方法,作用:1合理利用主存空间:数据分割将大数据集分成小的块,为块内数据一次性导入主存提供机会。2支持并行挖掘算法:每个分块的局部频繁项目集是独立生成的,因此提供了开发并行数据挖掘算法的良好机制。,Chinese Academy of Science,28,基于散列的方法,1995,Park等发现寻找频繁项目集的主要计算是在生成2-频繁项目集上。因此,Park等利用了
21、这个性质引入杂凑技术来改进产生2-频繁项目集的方法。,Chinese Academy of Science,29,基于散列的方法,例子:桶地址=(10 x+y)mod 7;minsupport_count=3,TID Items1 I1,I2,I52 I2,I43 I2,I34 I1,I2,I45 I1,I36 I2,I37 I1,I38 I1,I2,I3,I59 I1,I2,I3,桶地址 0 1 2 3 4 5 6,桶计数,TID=1,取(x=1,y=2),得到桶地址=5,即在地址5下列出I1,I2,I1,I2,I1,I5,I1,I5,桶内,同理取(x=1,y=5),(x=2,y=5),得的
22、地址1和4列出I1,I5,I2,I5,Chinese Academy of Science,30,基于散列的方法,例子:桶地址=(10 x+y)mod 7;minsupport_count=3,TID Items1 I1,I2,I52 I2,I43 I2,I34 I1,I2,I45 I1,I36 I2,I37 I1,I38 I1,I2,I3,I59 I1,I2,I3,桶地址 0 1 2 3 4 5 6桶计数 2 2 4 2 2 4 4桶内 I1,I4 I1,I5 I2,I3 I2,I4 I2,I5 I1,I2 I1,I3 I3,I5 I1,I5 I2,I3 I2,I4 I2,I5 I1,I2
23、I1,I3 I2,I3 I1,I2 I1,I3 I2,I3 I1,I2 I1,I3,L2=I2,I3,I1,I2,I1,I3 后面的方法的步骤与Apriori算法相同,所以当TID=1,2.,9 可以得到下面的内容,Chinese Academy of Science,31,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.6 项目集格空间和它的操作3.7 基于项目序列集操作的关联规则挖掘算法3.8 改善关联规则挖掘质量问题3.9 约束数据
24、挖掘问题3.10 关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法,Chinese Academy of Science,32,探索新的理论,随着数据库容量的增大,重复访问数据库(外存)将导致性能低下。因此,探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用,已经成为近年来关联规则挖掘研究的热点之一。两个典型的方法:Close算法 FP-tree算法,Chinese Academy of Science,33,Close算法对应的原理,一个频繁闭合项目集的所有闭合子集一定是频繁的;一个非频繁闭合项目集的所有闭合超集一定是非频繁的。什么是一个闭合的项目集?一个项目集C是闭合的,
25、当且仅当对于在C中的任何元素,不可能在C中存在小于或等于它的支持度的子集。例如,C1=AB3,ABC2是闭合的;C2=AB2,ABC2不是闭合的;,Chinese Academy of Science,34,Close算法对应的原理,Close 算法最终需要通过频繁闭合项目集得到频繁项目集。首先对频繁闭合项目集FC中的每个闭合项目集,计算它的项目个数,把所有项目个数相同的归入相应的i-频繁项目集Li中。例如,闭合项目集AB,它的个数为2(ABC它的个数为3),则把它加入L2中。依此类推,将所有闭合项目集分配到相应的Li中,同时得到最大的个数记为k。然后从k开始,对每个Li中的所以项目集进行分解
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关联 规则 挖掘 理论 算法
链接地址:https://www.31ppt.com/p-6091945.html