《数据挖掘——第三章关联规则挖掘ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据挖掘——第三章关联规则挖掘ppt课件.ppt（72页珍藏版）》请在三一办公上搜索。
1、关联规则挖掘技术,挖掘频繁模式、关联和相关,1.1.1 购物篮分析：引发性例子,1.1.2 频繁项集、闭项集和关联规则,1.1.3频繁模式挖掘：路线图,1.1 基本概念和线路图,1.1.1 购物篮分析：引发性例子,频繁项集挖掘的一个典型例子是购物篮分析。,优点：通过分析顾客的购买习惯，就能帮助零售商了解哪些商品频繁地被顾客同时购买，从而帮助他们开发更好的营销策略。,例如：如果顾客在超市购物时购买了牛奶，他们有多大的可能同时购买面包？,什么是项？什么是事务？,比如说在超市中的每一件商品在我们这里可以看作一个项！每个顾客消费时的购物单可以看作是一个事务！,例如：如果顾客购买电脑的同时也倾向于购买杀
2、毒软件，可以将两种产品放在一起 销售！ 通过上面的例子我们来分析和了解下面的两个概念：,最小支持度阀值和最小置信度阀值：是由用户或专家来设定的，也就是由他们来定义支持度与置信度的下限值。,Confidence：置信度。置信度为60%意味着购买计算机的顾客60%也购买了杀毒软件。,support：支持度。支持度为2%意味着所分析的所有事务的2%同时购买计算机和杀毒软件。,Computer antivirus_softwaresupport=2%,confidence=60%,什么是支持度？什么是置信度？,1.1.2频繁项集、闭项集和关联规则,1.频繁项集：这些项集的每一个出现的频率性至少与预定义
3、的最小支持计数min_sup一样。,2.闭频繁项集：如果不存在真超项集(数学中真子集相同)Y，使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的。如果X在S中是闭的和频繁的，项集X是数据集S中的闭频繁项集。,3.关联规则： Computer antivirus_softwaresupport=2%,confidence=60%可以改写如下所示的关联规则：buys(X,”computer”) buys(X,”antivirus_software”),例5-2：闭的和极大的频繁项集。,闭频繁项集的集合包含了频繁项集的完整信息。例如，我们可以从C推出(1)a2,a45:2 因为a2,a
4、45是a1,a2, ,a50:2的子集。(2)a8,a55:1因为a8,a55不是a1,a2, ,a50:2的子集，而是a1,a2, ,a100:1的子集。然而，从最大频繁项集我们只能断言两个项集（ a2,a45 和a8,a55 ）是频繁的。,最小支持度计数阀值min_sup=1。我们发现两个闭频繁项集和他们的支持度,即C= a1,a2, ,a100 :1;a1,a2, ,a50:2只有一个极大频繁项集：M= a1,a2, ,a100 :1,假定事务数据库只有两个事务： a1,a2, ,a100 ;a1,a2, ,a50,1.1.3频繁模式挖掘：路线图,频繁模式挖掘有多种分类方法：,6.根据所
5、挖掘的模式类型分类；,5.根据所挖掘的规则类型分类；,4.根据规则中所处理的值类型分类；,3.根据规则中涉及的数据维数分类；,2.根据规则集所涉及的抽象层分类；,1.根据挖掘模式的完全性分类；,1.2有效的和可伸缩的频繁项集挖掘方法,5.2.1Apriori算法：使用侯选产生发现频繁 项集； 5.2.2由频繁项集产生关联规则； 5.2.3提高Apriori算法的效率； 5.2.4不侯选产生挖掘频繁项集； 5.2.5使用垂直数据格式挖掘频繁项集；,1.2.1Apriori算法：使用侯选产生发现频繁项集,1.Apriori性质：频繁项集的所有非空子集也必须是频繁的。,2.该算法的使用是通过下面的两
6、个步骤来完成的：连接步和剪枝步。,怎样来理解和掌握Apriori算法呢？,我们可以通过下面的例子来理解和掌握：,例5-3该例子是基于下表的AllElectronics的事务数据库D，数据库中有9个事务，即|D|=9。,TID 商品ID的列表,T100 I1,I2,I5 T200 I2,I4 T300 I2,I3 T400 I1,I2,I4 T500 I1,I3 T600 I2,I3 T700 I1,I3 T800 I1,I2,I3,I5 T900 I1,I2,I3,表5-1 AllElectronics某分店的是事务数据,项集 支持度计数I1 6I2 7I3 6I4 2I5 2,扫描D对每个侯
7、选计数,项集 支持度计数I1 6I2 7I3 6I4 2I5 2,C1,L1,比较侯选支持度计数与最小支持度计数,有L1产生侯选C2,项集I1,I2I1,I3I1,I4I1,I5I2,I3I2,I4I2,I5I3,I4I3,I5I4,I5,C2,C2,项集 支持度计数 I1,I2 4I1,I3 4I1,I4 1I1,I5 2I2,I3 4I2,I4 2I2,I5 2I3,I4 0I3,I5 1I4,I5 0,扫描D，对每个侯选计数,项集 支持度计数I1，I2 4I1，I3 4I1，I5 2I2，I3 4I2，I4 2I2，I5 2,比较侯选支持度计数与最小支持度计数,L2,项集I1,I2,I3
8、I1,I2,I5,C3,由L2产生侯选C3,扫描D对每个侯选计数,项集 支持度计数 I1,I2,I3 2I1,I2,I5 2,C3,项集 支持度计数 I1,I2,I3 2I1,I2,I5 2,L3,比较侯选支持度计数与最小支持度计数,Apriori算法：输入：D：事务数据集；min_sup:最小支持度计数阀值；输出：L：D中的频繁项集；方法：L1=find_frequent_1-itemsets(D); /先扫描数据库D，计数频繁1项集的支持度； for(k=2; Lk-1空集; k+) /由(k-1)项频繁项集产生第k项侯选项集； Ck= apriori_gen(Lk-1); /产生的第k项
9、侯选项集； for each 事务 tD /扫描数据库D中的每一个事务t； Ct= subset(Ck,t); /对事务t，产生具有K项的子集赋给Ct； for each 侯选cCt / 检查侯选项集中的某一项是否属于Ct； c.count+; /若属于的话，Ck中某一个项集的支持度加1； Lk=c Ck|c.countmin_sup /进行最后的剪枝； return L=kLk,怎样产生？,Procedure apriori-gen(Lk-1;frequent(k-1)-itemsets) for each 项集l1 Lk-1 /对（k-1）项侯选项集中某项进行连接； for each 项集
10、l2 Lk-1 if(l11=l21 l12=l22 l1k-2=l2k-2 l1k-1l2k-1) thenc=l1连接l2; if has_infrequent_subset(c,Lk-1)then delete c; else add c to Ck; return Ck; ,根据Apriori算法的性质检查它的每一个(k-1)子集是不是频繁项集！,Prodedure has_infrequent_subset (c:candidate k-itemset;Lk-1:frequent(k-1)-itemsets) /从第k项侯选项集Ck中，看它的(k-1)项子集是不是 第(k-1)项频繁
11、项集中的项； for each (k-1)-subset s of c /侯选项集Ck的(k-1)项子集S； if sLk-1 then return true; return false; ,总之，Apriori算法的步骤就是连接与剪枝两步！,1.2.2由频繁项集产生关联规则,I1I2 I5 confidence=2/4=50%I1I5 I2 confidence=2/2=100%I2I5 I1 confidence=2/2=100%,根据上面讨论的Apriori算法，通过例题5-4来进一步掌握由频繁项集产生关联规则：,例题5-4：尝试基于表5-1中数据库的例子，假定数据包含频繁项集l=I1
12、，I2，I5。可以由l产生哪些关联规则？,l的非空子集有I1,I2，I1,I5，I2,I5，I1，I2，I5.结果列出关联规则如下，每个都列出置信度：,由L2和L3的支持度直接计算！,I1 I2I5 confidence=2/6=33%I2 I1I5 confidence=2/7=29%I5 I1I2 confidence=2/2=100%如果最小置信度阀值为70%，则上面第2、3和最后一个规则可以输出，因为只有这些产生强规则。,注意：与传统的分类规则不同，关联规则的右端可能包含多个合取项。,1.2.1Apriori算法举例已知事务数据库D如表10.1所示，最小支持度计数为2，即 minsup
13、port=2/9，利用Apriori算法挖掘所有满足minsup的频繁集。,(1)第一次扫描，扫描数据库获得每个候选项的计数，从而获得频繁1-项集。如表10-2所示。,(2)根据L1生成2-候选集C2，然后扫描数据库D，计算各项集的支持度，如表10.3所示。从而得到频繁2-项集，如表10.4所示。,(3) L2进行自连接得到C3=I1, I4, I5， I1, I2, I4， I1, I3, I4， I1, I3, I5， I2, I3, I4， I3, I4, I5 因为 I1, I2, I4的子集 I1, I2,和 I1, I3, I4、 I1, I3, I5的子集 I1, I3,及 I2
14、, I3, I4的子集 I2, I3不在L2中 因此，从C3中删除 I1, I2, I4、 I1, I3, I4、 I1, I3, I5、 I2, I3, I4得： C3= I1, I4, I5， I3, I4, I5。然后再扫描数据库D，计算各项集的支持度计数，如表10.5所示，从而得到频繁3-项集L3，如表10.6所示。,(4)L3进行自连接得到C4= I1, I3, I4 , I5，由于 I1, I3, I4 , I5的子集 I1, I3, I4 ,不在L3中，因此删除 I1, I3, I4 , I5后C4=，进而L4=，算法终止。,1.2.3提高Apriori算法的效率,1.基于散列的
15、技术：将产生的下一项集散列到散列表结构的不同桶中，并增加对应的桶的计数；2.事物压缩：不包含任何频繁k项集事务的事务不可能包含任何 频繁(k+1)项集。这种事务在其后的考虑时，可以加上标记或删除因为产生j项集(jk)的数据库扫描不需要它们；,怎样才能提高基于Apriori的挖掘的效率？已经提出了许多Apriori算法的变形，旨在提高原算法的效率。其中一些变形汇总如下：,1.2.3提高Apriori算法的效率,4.抽样：选取给定数据D的随机样本S，然后在S中间搜索频繁项；,5.动态项集计数：将数据库划分为用开始点标记的块，可以在任 何开始点添加新的侯选项集。,3.划分：先将数据库划分成两个部分，
16、对每个划分找出其中的局 部频繁项集。D的任何频繁项集必须作为局部频繁项集 至少出现在一个划分中。所有频繁项集的集合形成D的 全局侯选项集；,Apriori算法显著的压缩了侯选项集的大小，并导致很好的性能。然而，它要受到两种平凡的开销的影响：1.它可能需要产生大量侯选项集；2.它可能需要重复地扫描数据库，通过模式匹配检查一个很大的侯选集合。,1.2.4不侯选产生挖掘频繁项集,为了解决Apriori算法带来的一些缺陷，我们又将设计一种怎样的方法来解决了？,关联规则挖掘算法FP-growth,FP-tree构造算法,扫描事务数据库一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频
17、繁项表L。创建FP-tree的根结点(null)。对于D中每个事务：选择事务中的频繁项，并按L中的次序排序。设排序后的频繁项表为p|P，其中p是第一个元素，而P是剩余元素的表调用insert_tree(p| P，T)。如果T有子女N使得N.item-name=p.item-name，则N的计数增加1；否则创建一个新节点N，将其计数设置为1，连接到他的父节点T，并通过节点链结构将其连接到具有相同item-name的节点如果P非空，递归的调用insert_tree(P，N),FP-growth算法,Procedure FP-growth(Tree，a)if Tree包含单个路径 p then fo
18、r路径P中每个节点组合(记做) 产生模式a，其支持度support=中节点的最小 支持度;else for each ai在tree的头部产生一个模式=aia，其支持度support=ai.support;构造的条件模式基，构建的条件FP-tree Tree;if Tree then调用FP-growth(Tree，);,事务数据库,第一步、构造FP-tree,扫描事务数据库得到频繁1-项目集F定义minsup=20%，即最小支持度为2重新排列F,重新调整事务数据库,创建根结点和频繁项目表,Null,加入第一个事务(I2,I1,I5),Null,I2:1,I1:1,I5:1,加入第二个事务(I
19、2,I4),Null,I2:2,I1:1,I5:1,I4:1,加入第三个事务(I2,I3),Null,I2:3,I1:1,I5:1,I4:1,I3:1,加入第四个事务(I2,I1,I4),Null,I2:4,I1:2,I5:1,I4:1,I3:1,I4:1,加入第五个事务(I1,I3),Null,I2:4,I1:2,I5:1,I4:1,I3:1,I4:1,I1:1,I3:1,加入第六个事务(I2,I3),Null,I2:5,I1:2,I5:1,I4:1,I3:2,I4:1,I1:1,I3:1,加入第七个事务(I1,I3),Null,I2:5,I1:2,I5:1,I4:1,I3:2,I4:1,I
20、1:2,I3:2,加入第八个事务(I2,I1,I3,I5),Null,I2:6,I1:3,I5:1,I4:1,I3:2,I4:1,I1:2,I3:2,I5:1,I3:1,加入第九个事务(I2,I1,I3),Null,I2:7,I1:4,I5:1,I4:1,I3:2,I4:1,I1:2,I3:2,I5:1,I3:2,第二步、FP-growth,首先考虑I5，得到条件模式基、构造条件FP-tree得到I5频繁项集：I2,I5:2,I1,I5:2,I2,I1,I5:2,Null,I2:2,I1:2,I3:1,第二步、FP-growth,接着考虑I4，得到条件模式基、构造条件FP-tree得到I4频繁
21、项集：I2,I4:2,Null,I2:2,I1:1,第二步、FP-growth,然后考虑I3，得到条件模式基、 构造条件FP-tree由于此树不是单一路径，因此需要递归挖掘I3,Null,I2:4,I1:2,I1:2,第二步、FP-growth,递归考虑I3，此时得到I1条件模式基,即I1I3的条件模式基为构造条件FP-tree得到I3的频繁项目集I2,I3:4,I1,I3:4,I2,I1,I3:2,Null,I2:2,第二步、FP-growth,最后考虑I1，得到条件模式基构造条件FP-tree得到I1的频繁项目集I2,I1:4,Null,I2:4,为此我们设计了如下的一种方法来实现不产生侯
22、选项集的数据挖掘方法：频繁模式树又叫FP树；首先我们通过前面讨论Apriori 算法的例子来了解FP树的算法：1.数据库的扫描跟Apriori算法相同，按支持度计数，再根据支持度按照递减的顺序排列；2.建立频繁模式树：先建立一个空的祖先节点Null；3.构造它的条件模式基；4.构造它的条件FP树；5.产生频繁项集。,1.2.4不侯选产生挖掘频繁项集,I2 7 I1 6I3 6I4 2I5 2,项ID,支持度 计数,节点链,null,I2:7,I1:4,I3:2,I4:1,I3:2,I1:2,I4:1,I3:2,I5:1,I5:1,项 条件模式基 条件FP树 产生的频繁模式I5 I2,I1:1
23、,I2,I1,I3:1 I2 I5:2I1 I5:2I2 I1 I5:2I4 I2,I1:1,I2:1 I2 I4:2I3 I2,I1:2, I2:2,I1:2 I2 I3:4I1 I3:4I2 I1 I3:2I1 I2:4 I2 I1:4,输入：D：事务数据库； min_sup：最小支持度计数阀值输出：频繁模式的完全集。方法：1.按以下步骤构造FP树扫描事务数据库D一次。收集频繁项集的集合F和它们的支持度计数。对F按支持度计数降序排序，结果为频繁项列表L。创建FP树的节点，以”null”标记它。对于D中每个事务Trans，执行：选择Trans中频繁项集，并按L中的次序排序。 /怎样建立FP树
24、？就是根据表5-1中事务数据库中的数据从根节点开始构造FP树，每经过已经存在的节点就使得该节点的计数增加1，否则就从根节点开始构造它的分枝！2.FP树的挖掘通过调用FP_growth(FP_tree,null)实现，该过程如下： Procedure FP_growth(Tree,a) /此算法是一个递归算法； If Tree 含单个路径P then for each 路径P中节点的每个组合（记作B）,产生模式Ba，其支持度计数support_count 等于B中节点的最小支持度计数；Else for Tree的头表中的每个ai产生模式B=aia,其支持度计support_count=ai.su
25、pport_count;构造B的条件模式基，然后构造B的条件FP树TreeB;If TreeB空 then 调用FP_growth(TreeB,B);,例：最小支持度阈值 为3,FP-Growth算法例,null,1.f,c,a,m,p,2.f,c,a,b,m,3.f,b,4.c,b,p,5.f,c,a,m,p,FP-Growth算法例,生成的FP树,FP-Growth算法例,节点链性质对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。,包含m的所有频繁模式的集合有：(m:3),(am:3),(cm:3),(fm:3),(cam:3),(fam:3),(fca
26、m:3),(fcm:3)。这表明对一个单独路径的FP树进行挖掘时，可以通过输出该路径上所有项的组合来实现。,FP-Growth算法例,1.2.5使用垂直数据格式挖掘频繁项集,Apriori算法和FP增长方法都是从TID项集格式的事务集挖掘频繁项集模式，其中TID是事务表示符，而itemset是事务TID中购买的商品。这种数据格式称做水平数据格式。下面我们将TID与 itemset两个调换位置来挖掘数据，也就是我们要讨论的垂直数据格式挖掘频繁模式：先看下面的例子来体会垂直数据格式挖掘频繁项集：例题5-6：沿用表5-1中数据，扫描一次数据库可以将其转换为下表所示的垂直数据格式：,1.2.5使用垂直
27、数据格式挖掘频繁项集,项 集 TID集 I1 T100,T400,T500,T700,T800,T900 I2 T100,T200,T300,T400,T600,T800,T900 I3 T300,T500,T600,T700,T800,T900 I4 T200,T400 I5 T100,T800,表5-3 表5-1事务数据库D的垂直数据格式,1.2.5使用垂直数据格式挖掘频繁项集,现在我们构造频繁2项集如下：,项集 TID集I1,I2 T100,T400,T800,T900I1,I3 T500,T700,T800,T900I1,I4 T400I1,I5 T100,T800I2,I3 T300
28、,T600,T800,T900 I2,I4 T200,T400I2,I5 T100,T800I3,I4 空I3,I5 T800I4,I5 空,表5-4 垂直数据格式的2项集,I1与I2的TID的交集,Sup为TID的长度，然后去掉min_sup的项集,1.2.5使用垂直数据格式挖掘频繁项集,项 集 TID集I1,I2,I3 T800,T900I1,I2,I5 T100,T800,构造频繁3项集如下：,查找垂直频繁项集的步骤：1.扫描数据库把水平数据格式转换成垂直数据格式；2.获取项集的支持度计数（也就是TID的长度）；3.通过K项集来构造（k+1）项集，通过取频繁k项集的TID集的交计算对应的
29、(K+1)项集的TID集；4.重复该过程，每次k增值1，直到不能找到频繁项集或侯选项集为止。,应用实例,目前很多高校对教学评价主要基于数值计算，把学生的评价作一总结，将结果通报给老师，作为晋升职称、评优等的依据，系里对老师做一奖惩及引导，不做深层的思考。这里我们将对教学评价数据进行关联规则挖掘，试图挖掘教学效果与教师的性别、年龄、职称、学历等的关联，找到课堂教学效果与教师整体素质的关系，从而合理调配一个班的上课老师，使学生能够较好地保持良好的学习状态，从而为教学部门提供决策支持信息，以便更好地开展教学工作，提高教学质量。,1. 数据准备 这是我们随机抽取某高校教师教学质量评估表1000份，将教
30、师编号、年龄、性别、职称、学历、公费进修、工作量和评定分数8项输入数据库，忽略其它信息。我们将通过数据挖掘找出性别、年龄、职称、学历、公费进修、工作量和评定分数之间的关系。表10.8给出了部分教学评价信息视图，共有1000条记录。,在表10.8中，属性年龄、工作量、成绩都是数量属性(非离散属性)，这里，我们将其离散化。首先，对年龄进行分组:Al22，30，A231，35，A336，49，A450，60；然后对工作量进行分组:B1:0，120学时，B2:120学时以上；对成绩进行分组:C1:教学效果好85，100，C2:教学效果不是很好0，85)。将数量属性离散化后的结果如表10.9所示。,2挖
31、掘关联规则利用关联规则挖掘算法Apriori来挖掘关联规则了，找出性别、学历、年龄、职称、公费进修、工作量等因素对教学效果的影响，进而采取一定的措施，提高教学质量。这里，设minsup= 5%，minconf=5%，得到满足最小支持度和最小可信度的关联规则,3挖掘结果分析 通过得到的关联规则，可得到如下的分析结果及改进措施。 （1）性别对教学效果的影响 规则女Cl和男C1的置信度分别为63.5%和60.4%，这两个关联规则的置信度基本相同，说明性别对教学效果没有什么影响，因此在引进教师时不应该考虑性别因素。 （2）年龄对教学效果的影响 年龄对教学效果的影响可以从下面3种情况进行分析:,3挖掘结
32、果分析 随着年龄的增长，规则年龄教学效果好的置信度也增大，说明年龄大的教师的教学质量高。 规则22，30C1的置信度很低，这主要是因为目前高校引入的教师都是硕士以上，30岁以下的教师教学经验很少，应尽量少上课或不上课。 规则50，60C1的置信度很高，说明50，60这个年龄段的教师的教学质量很高，但支持度却很低，说明这部分老师承担的工作量不大。学校应采取一定措施，让老教师多承担教学工作。,（3）职称对教学效果的影响 随着年龄的增大，职称也不断提高。反之，职称高的教师一般年龄也偏高，所以职称对教学效果的影响和年龄对教学效果的影响基本是一致的（4）公费进修对教学效果的影响 从表10.10可知，关联规则:进修过Cl比关联规则:没进修过C1的置信度高，说明进修对提高教师的教学水平有很多作用,3挖掘结果分析,72,2022/12/27,
