《关联规则挖掘理论和算法.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中的所以项目集进行分解
26、，找到它的所有的(i-1)-项子集。对每个子集，如果它不属于Li-1，则把它加入到Li-1，直到i=2，就找到所有的频繁项目集。,Chinese Academy of Science,35,Close算法的例子,例子：minsup=2 TID Itemset TID Itemset 1 ABE 6 BC 2 BD 7 AC 3 BC 8 ABCE 4 ABD 9 ABC 5 AC,Chinese Academy of Science,36,Close算法的例子,(1)计算FCC1各个产生式的闭合和支持度首先得到FCC1的产生式：A、B、C、D、E。然后计算闭集合：如计算A的闭集合，取含A的It
27、emset 每行的交集可得到closure A=A,supprot=6得到FCC1的所有闭集合,Chinese Academy of Science,37,Close算法的例子,(2)进行修剪将支持度小于最小支持度(minsup=2)候选闭合项删除，得到FC1。本例FCC1=FC1,Chinese Academy of Science,38,Close算法的例子,(3)利用FC1的generator生成FCC2先用Apriori相同的方法生成2-项目集。然后将FC1中是FCC2中的某个候选项的子集项选出来，记为Sp。如果FCC1的这一项是Sp的字母的闭合项则删除，得到FCC2。对于本例，FC1
28、自身连接后得到的候选项为：ABACADAEBCBDBECDCEDE,均不含有非频繁子集(即把他们分别拆开后各个项都能在前一步中找到)。在利用FC1筛选：由于AE是子集E的闭合ABE的子集，BE是子集E的闭合ABE的子集，所以将这两项删除，得到的候选项FCC2=AB,AC,AD,BC,BD,CD,CE,DE。值得注意的是在FCC2的元素中我们简单地用AB来代替上面的AB，主要的目的是在不会引起混淆的情况下表达简洁。,Chinese Academy of Science,39,Close算法的例子,(4)计算各产生式的闭合和支持度由于FCC2不空，CD和DE的闭合为空，所以将它们从FCC2中删除，
29、且得到各产生式的支持度。,Chinese Academy of Science,40,Close算法的例子,(5)进行修剪将支持度小于最小支持度(minsup=2)候选闭合项删除，得到FC2。这时候ADCE的支持度为1被删除。FC2=AB,AC,BC,BD(6)利用FC2的generator生成FCC3,并进行剪裁FC2连接后得到：ABC,BCD,其中BCD有非频繁子集CD,所以将这两项删除。剩下为ABC，得到的候选项FCC3=ABC.,Chinese Academy of Science,41,Close算法的例子,(7)FCC3不为空，计算各产生式的闭合和支持度ABC的闭合为ABC，支持度
30、为2(8)进行修剪将支持度小于最小支持度(minsup=2)候选闭合项删除，得到FC3。对本例FC3只有一项，支持度为2，保留。(9)利用FC3生成FCC4。为空，算法结束。,Chinese Academy of Science,42,Close算法的例子,将所有的不重复的闭合加入到FC中，得到FC=A,B,ABE,BD,C,AB,AC,BC,ABC以下生成频繁项目集(10)统计项目集元素数将所有的闭合项目集(上面的FC)按元素的个数统计，得到L3=ABC,ABE；L2=AB,AC,BC,BD；L1=A,B,C。最大个数为3,Chinese Academy of Science,43,Clos
31、e算法的例子,(11)将L3频繁项分解先分解ABC的所有2-项子集为ABAC和BC这3项均在L2中。再分解ABE，所有2-项子集为ABAE和BE,后两项不存在，将它们加入到L2中，他们的支持度等于ABE的支持度。最后L2为BD,AB,AC,BC,AE,BE(12)将L2频繁项分解方法同上，得到L1=A,B,C,D,E,Chinese Academy of Science,44,FP-tree算法的基本原理,进行2次数据库扫描：一次对所有1-项目的频度排序；一次将数据库信息转变成紧缩内存结构。不使用侯选集，直接压缩数据库成一个频繁模式树，通过频繁模式树可以直接得到频集。基本步骤是：两次扫描数据库
32、，生成频繁模式树FP-Tree：扫描数据库一次，得到所有1-项目的频度排序表T；依照T，再扫描数据库，得到FP-Tree。使用FP-Tree，生成频集：为FP-tree中的每个节点生成条件模式库；用条件模式库构造对应的条件FP-tree；递归挖掘条件FP-trees同时增长其包含的频繁集：如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。,Chinese Academy of Science,45,例子3-4,对于一个给定的事务数据库，通过第一遍扫描后去掉不频繁的项目（本例最小支持数阈值是3），并且把一个元组中的项目按出现频率降序排列。下图给出了相应的数据,Chinese Aca
33、demy of Science,46,例子3-4,根据Build_FP-tree算法，构造FP-tree1 第一次扫描数据库，导出1-频繁项目集L=f4,c4,a3,b3,m3,o3,p3（后面的数字代表支持数）。因此，可以通过去掉不频繁的单项目来简化原始的数据库元组，整理后得到,Chinese Academy of Science,47,例子3-4,根据Build_FP-tree算法，构造FP-tree2 创造树的根节点，用root标记。第二次扫描DB，对每个事务创建一个分支：第一个事务“T100:f,a,c,d,g,i,m,p”按L的次序包含5个项f,c,a,m,p,导出构造树的第一个分支
34、,Chinese Academy of Science,48,例子3-4,根据Build_FP-tree算法，构造FP-tree对于第二个事务，由于其排序后的频繁项目表与已有的分支路径共享前缀，所以前缀中的每个节点计数加1，只创建两个新的结点b1,o1，形成的分支链接在,Chinese Academy of Science,49,例子3-4,根据Build_FP-tree算法，构造FP-tree重复以上方法，得到FP-TREE,Chinese Academy of Science,50,例子3-5,从FP-tree中挖掘频繁模式由于初始参数a=null（由程序得到），没有单通路，所以在项头表中
35、找到最后一项P（倒序）。P出现在三个分支中，因此在研究与p一起出现的项目集时，只统计p 的前缀路径就行，于是得到三个路径：,（书上有误）由上面的条件模式可知包含p的频繁模式为：(fp:3)(这是因为p的条件FP-tree只包含一个频度结点,以此类推得到下表),Chinese Academy of Science,51,例子3-5,得到空集是因为要求阈值为3，该项不满足条件,Chinese Academy of Science,52,生成频繁模式树FP-Tree,最小支持数阈值是3min_support=0.5,TIDOriginal Items(ordered)frequent items10
36、0f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300 b,f,h,j,of,b400 b,c,k,s,pc,b,p500 a,f,c,e,l,p,m,nf,c,a,m,p,Chinese Academy of Science,53,从FP-TREE中挖掘频繁模式方法,为每个节点，寻找它的所有前缀路径并记录其频度，形成频繁模式,频繁模式itemcond.频繁模式 cf:3 fc:3afc:3 fa:3 ca:3 fca:3b fca:1,f:1,c:1 空m fca:2,fcab:1 空p fcam:2,cb:1 空,Chinese Acad
37、emy of Science,54,第三章 关联规则挖掘理论和算法,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 Academy of Science,55,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成
38、算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.6 项目集格空间和它的操作(略)3.7 基于项目序列集操作的关联规则挖掘算法(略)3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法,Chinese Academy of Science,56,衡量关联规则挖掘结果的有效性,应该从多种综合角度来考虑准确性：挖掘出的规则必须反映数据的实际情况。实用性：挖掘出的规则必须是简洁可用的。新颖性：挖掘出的关联规则可以为用户提供新的有价值信息。改善关联规则挖掘质量是
39、一件很困难的工作必须采用事先预防、过程控制以及事后评估等多种方法，其中使用合适的机制（如约束），让用户主动参与挖掘工作是解决问题的关键。粗略地说，可以在用户主观和系统客观两个层面上考虑关联规则挖掘的质量问题。,Chinese Academy of Science,57,用户主观层面,一个规则的有用与否最终取决于用户的感觉。用户可以在不同的层面、不同的阶段、使用不同的方法来主观设定约束条件。,Chinese Academy of Science,58,用户主观层面,从被约束的对象来看，有下面几种常用的方法：知识类型的约束：针对应用问题选择有效的知识表达模式。例如，如果一个商业企业希望根据客户特点
40、进行有针对性地销售，那么使用分类或聚类形式可以帮助用户形成客户群。数据的约束：对数据的约束可以起到减少数据挖掘算法所用的数据量、提高数据质量等作用。维/层次约束：限制聚焦的维数或粒度层次，也可以针对不同的维设置约束条件。知识内容的约束：可以通过限定要挖掘的知识的内容，如指定单价大于10的交易项目，减少探索的代价和加快知识的形成过程。针对具体知识类型的约束：针对具体知识类型的进行约束挖掘形式和实现机制的研究。,Chinese Academy of Science,59,系统客观层面,使用“支持度-可信度”的关联规则挖掘度量框架，在客观上也可能出现与事实不相符的结果。例如，“计算机游戏和录象产品是
41、负相关的”问题。重新考虑关联规则的客观度量问题。例如，Brin等考虑的蕴涵规则（Implication Rule）；Chen等给出的R-兴趣（R-Interesting）规则度量方法等。这些工作都期望通过引入新的度量机制和重新认识关联规则的系统客观性来改善挖掘质量。,Chinese Academy of Science,60,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.6 项目集格空间和它的操作(略)3.7 基于项目序列集操作的关联规
42、则挖掘算法(略)3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法,Chinese Academy of Science,61,约束在数据挖掘中的作用,1 聚焦挖掘任务，提高挖掘效率：利用约束，可以把具体的挖掘任务转换成对系统工作的控制，从而使挖掘工作按着我们期望的方向发展。约束的使用可以在知识发现的任何阶段进行，快速聚焦挖掘任务，进而提高挖掘效率。,Chinese Academy of Science,62,约束在数据挖掘中的作用,2 保证挖掘的精确性：挖掘结果的精确性，不仅体现在它的可信程度，而且取决于它的有用性。
43、约束的使用可以帮助我们发现问题，并及时加以调整，使知识发现的各个阶段按着正确的方向发展。,Chinese Academy of Science,63,约束在数据挖掘中的作用,3 控制系统的使用规模：数据挖掘和知识发现应用最常犯的错误就是无限制的扩大规模。约束数据挖掘的思想为系统的增量式扩充提供条件。当基本的原则和目标确定后，可以把一些有待验证和优化的问题以约束参数的形式交互式输入，通过实验找到最佳值。,Chinese Academy of Science,64,约束的类型,约束的常见类型有(掌握)单调性约束（Monotone Constraint）；反单调性约束（Anti-monotone C
44、onstraint）；可转变的约束（Convertibale Constraint）；简洁性约束（Succinct Constraint）。,Chinese Academy of Science,65,第三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 时态约束关联规则挖掘3.11关联规则挖掘中的一些更深入的问题3.12数量关联规则挖掘方法,Chinese Academy of S
45、cience,66,3.10 时态约束关联规则挖掘,约束关联规则挖掘是将来研究的重要问题。由于涉及的范围很广，目前的研究和时间大多集中在某种形态的约束或特定问题上。时间是现实世界的重要属性。大容量数据集中的时间属性对用户来说可能是很关键的。,Chinese Academy of Science,67,3.10 时态约束关联规则挖掘,用户关心的往往是某一时间区域的数据而不是整个数据。而特定时间区域的数据又可能导致特定的效据间的关联规则。时态约束可以应用到数据挖掘和知识发现中。并且可以起到过滤过时数据、聚焦用户目标以及加速形成关联规则生成等作用。,Chinese Academy of Scienc
46、e,68,3.10 时态约束关联规则挖掘,为了更好地挖掘这样的数据库我们对时态约束下的关联规则挖掘问题进行了专门研究首先从时态区间格空间的代数形式化开始，定义两个基本时态区间操作。然后把它们应用到数据库的过滤和时态区间的合并等预处理工作上,Chinese Academy of Science,69,3.10 时态约束关联规则挖掘,我们做这些工作的主要目的有两个：其一是通过对数据库的过滤减少数据集的容量：其二是通过时态区间合并使过滤后可能生成的时态区间碎片合并成互不相交的挖掘时区集，并对每个挖掘时区单独通过内存演算来生成关联规则。这样就可以大幅度减少进入内存的数据集的大小，进而增强处理大型数据库
47、的能力。,Chinese Academy of Science,70,3.10 时态约束关联规则挖掘,对大型事务数据库而言，利用约束条件过滤数据库是减少 I/O代价和提高主机效率的重要途径。对事务数据库进行过滤和挖掘时区合并等预处理。以使挖掘过程集中在较小的用户感兴趣数据上。可以提高挖掘效率和增强对大型数据库挖掘的能力。利用时态约束对数据库进行过滤等预处理，使得被挖掘数据的质量得到改善。进一步的工作可以通过合适的算法生成频繁项目集和关联规则。这些关联规则可以和确定的时态区间联系起来，使关联规则正确地反映特定时间段的项目之间的联系。,Chinese Academy of Science,71,第
48、三章 关联规则挖掘理论和算法,3.1 基本概念与解决方法 3.2 经典的频繁项目集生成算法分析 3.3 Apriori算法的性能瓶颈问题3.4 Apriori的改进算法3.5 对项目集格空间理论的发展3.8 改善关联规则挖掘质量问题3.9 约束数据挖掘问题3.10 时态约束关联规则挖掘3.11关联规则挖掘中的一些更深入的问题3.12数量关联规则挖掘方法,Chinese Academy of Science,72,多层次关联规则挖掘,根据规则中涉及到的层次，多层次关联规则可以分为：同层关联规则：如果一个关联规则对应的项目是同一个粒度层次，那么它是同层关联规则。层间关联规则：如果在不同的粒度层次上
49、考虑问题，那么可能得到的是层间关联规则。,Chinese Academy of Science,73,多层次关联规则挖掘,多层次关联规则挖掘的度量方法可以沿用“支持度-可信度”的框架。不过，多层次关联规则挖掘有两种基本的设置支持度的策略：统一的最小支持度：算法实现容易，而且很容易支持层间的关联规则生成。但是弊端也是显然的：不同层次可能考虑问题的精度不同、面向的用户群不同。对于一些用户，可能觉得支持度太小，产生了过多不感兴趣的规则。而对于另外的用户来说，又认为支持度太大，有用信息丢失过多。,Chinese Academy of Science,74,多层次关联规则挖掘,不同层次使用不同的最小支持
50、度：每个层次都有自己的最小支持度。较低层次的最小支持度相对较小，而较高层次的最小支持度相对较大。这种方法增加了挖掘的灵活性。但是，也留下了许多相关问题需要解决：首先，不同层次间的支持度应该有所关联，只有正确地刻画这种联系或找到转换方法，才能使生成的关联规则相对客观。其次，由于具有不同的支持度，层间的关联规则挖掘也是必须解决的问题。例如，有人提出层间关联规则应该根据较低层次的最小支持度来定。,Chinese Academy of Science,75,多维关联规则挖掘,多层次关联规则的挖掘方法自上而下方法先找高层的规则。如“冬季服装 牛奶”，再找它的下一层规则。如“羽绒服 鲜奶”。如此逐层自上而
