《数据挖掘——第三章关联规则挖掘ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据挖掘——第三章关联规则挖掘ppt课件.ppt（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、挖掘频繁模式、关联和相关1.1.1 购物篮分析：引发性例子1.1.2 频繁项集、闭项集和关联规则1.1.3频繁模式挖掘：路线图n1.1 基本概念和线路图1.1.1 购物篮分析：引发性例子频繁项集挖掘的一个典型例子是购物篮分析。优点：通过分析顾客的购买习惯，就能帮助零售商了解哪些商品频繁地被顾客同时购买，从而帮助他们开发更好的营销策略。例如：如果顾客在超市购物时购买了牛奶，他们有多大的可能同时购买面包？什么是项？什么是事务？比如说在超市中的每一件商品在我们这里可以看作一个项项！每个顾客消费时的购物单可以看作是一个事务事务！例如：如果顾客购买电脑的同时也倾向于购买杀毒软件，可以将两种产品放在一起
2、销售！ 通过上面的例子我们来分析和了解下面的两个概念：最小支持度阀值和最小置信度阀值：是由用户或专家来设定的，也就是由他们来定义支持度与置信度的下限值。Confidence：置信度。置信度为60%意味着购买计算机的顾客60%也购买了杀毒软件。support：支持度。支持度为2%意味着所分析的所有事务的2%同时购买计算机和杀毒软件。Computer antivirus_softwaresupport=2%,confidence=60%什么是支持度？什么是置信度？1.1.2频繁项集、闭项集和关联规则1.频繁项集：这些项集的每一个出现的频率性至少与预定义的最小支持计数min_sup一样。2.闭频繁项
3、集：如果不存在真超项集(数学中真子集相同)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,a45是a1,a2, ,a50:2的子集。(2)a8,
4、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, ,a501.1.3频繁模式挖掘：路线图频繁模式挖掘有多种分类方法：6.根据所挖掘的模式类型分类；5.根据所挖掘的规则类型分类； 4.根据
5、规则中所处理的值类型分类； 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.该算法的使用是通过下面的两个步骤来完成的：连接步和剪枝步。怎样来理解和掌握Apriori算法呢？我
6、们可以通过下面的例子来理解和掌握：例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对每个侯选计数项集 支持度计数I1 6I2 7I3 6I4 2I5 2C1L1比较侯选支持度
7、计数与最小支持度计数有L1产生侯选C2 项集I1,I2I1,I3I1,I4I1,I5I2,I3I2,I4I2,I5I3,I4I3,I5I4,I5C2C2 项集 支持度计数 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,I3I1,I2,I5C3由L2产生侯选C3扫描D对每个侯选计数 项集 支持度计数 I1,I2,I3 2I1,
8、I2,I5 2C3 项集 支持度计数 I1,I2,I3 2I1,I2,I5 2L3比较侯选支持度计数与最小支持度计数Apriori算法算法：输入输入：D：事务数据集；事务数据集；min_sup:min_sup:最小支持度计数阀值；最小支持度计数阀值；输出：输出：L L：D D中的频繁项集中的频繁项集；方法：方法：L1=find_frequent_1-itemsets(D); /先扫描数据库先扫描数据库D D，计数频繁，计数频繁1 1项集的支持度；项集的支持度； for(k=2; Lk-1空集空集; k+) /由由(k-1)(k-1)项频繁项集产生第项频繁项集产生第k k项侯选项集；项侯选项集；
9、 Ck= apriori_gen(Lk-1); /产生的第产生的第k k项侯选项集项侯选项集； for each 事务事务 tD /扫描数据库扫描数据库D D中的每一个事务中的每一个事务t t； Ct= subset(Ck,t); /对事务对事务t t，产生具有，产生具有K K项的子集赋给项的子集赋给CtCt； for each 侯选侯选cCt / / 检查侯选项集中的某一项是否属于检查侯选项集中的某一项是否属于CtCt； c.count+; /若属于的话，若属于的话，CkCk中某一个项集的支持度加中某一个项集的支持度加1 1； Lk=c Ck|c.countmin_sup /进行最后的剪枝；
10、进行最后的剪枝； return L=kLk怎样产生？Procedure apriori-gen(Lk-1;frequent(k-1)-itemsets) for each 项集l1 Lk-1 /对（对（k-1k-1）项侯选项集中某项进行连接；）项侯选项集中某项进行连接； for each 项集l2 Lk-1 if(l11=l21 l12=l22 l1k-2=l2k-2 l1k-1k)的数据库扫描不需要它们； 怎样才能提高基于Apriori的挖掘的效率？已经提出了许多Apriori算法的变形，旨在提高原算法的效率。其中一些变形汇总如下：1.2.3提高Apriori算法的效率4.抽样：选取给定数据
11、D的随机样本S，然后在S中间搜索频繁项；5.动态项集计数：将数据库划分为用开始点标记的块，可以在任 何开始点添加新的侯选项集。3.划分：先将数据库划分成两个部分，对每个划分找出其中的局 部频繁项集。D的任何频繁项集必须作为局部频繁项集 至少出现在一个划分中。所有频繁项集的集合形成D的 全局侯选项集； Apriori算法显著的压缩了侯选项集的大小，并导致很好的性能。然而，它要受到两种平凡的开销的影响：1.它可能需要产生大量侯选项集；2.它可能需要重复地扫描数据库，通过模式匹配检查一个很大的侯选集合。 1.2.4不侯选产生挖掘频繁项集为了解决Apriori算法带来的一些缺陷，我们又将设计一种怎样的
12、方法来解决了？关联规则挖掘算法FP-growthFP-tree构造算法扫描事务数据库一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表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非空，递归的调用in
13、sert_tree(P，N)FP-growth算法1.Procedure FP-growth(Tree，a)2.if Tree包含单个路径 p then3. for路径P中每个节点组合(记做)4. 产生模式a，其支持度support=中节点的最小 支持度;5.else for each ai在tree的头部6.产生一个模式=aia，其支持度support=ai.support;7.构造的条件模式基，构建的条件FP-tree Tree;8.if Tree then9.调用FP-growth(Tree，);10.事务数据库TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I4
14、5I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3第一步、构造FP-tree扫描事务数据库得到频繁1-项目集F定义minsup=20%，即最小支持度为2重新排列FI1I2I3I4I567622I2I1I3I4I576622重新调整事务数据库TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2,I37I1,I38I2, I1,I3,I59I2, I1,I3创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull加入第一个事务(I2,I1,I5)Item-
15、nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:1加入第二个事务(I2,I4)Item-nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1I4:1加入第三个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:1加入第四个事务(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1加入第五个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2
16、:4I1:2I5:1I4:1I3:1I4:1I1:1I3:1加入第六个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:1加入第七个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:2加入第八个事务(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:1加入第九个事务(I2,I1,I3)Item-
17、nameNode-headI2I1I3I4I5NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:2第二步、FP-growth首先考虑I5，得到条件模式基、构造条件FP-tree得到I5频繁项集：I2,I5:2,I1,I5:2,I2,I1,I5:2Item-nameNode-headI2I1NullI2:2I1:2I3:1第二步、FP-growth接着考虑I4，得到条件模式基、构造条件FP-tree得到I4频繁项集：I2,I4:2Item-nameNode-headI2NullI2:2I1:1第二步、FP-growth然后考虑I3，得到条件模式基、 构造条件F
18、P-tree由于此树不是单一路径，因此需要递归挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:2第二步、FP-growth递归考虑I3，此时得到I1条件模式基,即I1I3的条件模式基为构造条件FP-tree得到I3的频繁项目集I2,I3:4,I1,I3:4,I2,I1,I3:2Item-nameNode-headI2NullI2:2第二步、FP-growth最后考虑I1，得到条件模式基构造条件FP-tree得到I1的频繁项目集I2,I1:4Item-nameNode-headI2NullI2:4为此我们设计了如下的一种方法来实现不产生侯选项集的数据挖掘方法：频
19、繁模式树又叫FP树；首先我们通过前面讨论Apriori 算法的例子来了解FP树的算法：1.数据库的扫描跟Apriori算法相同，按支持度计数，再根据支持度按照递减的顺序排列；2.建立频繁模式树：先建立一个空的祖先节点Null；3.构造它的条件模式基；4.构造它的条件FP树；5.产生频繁项集。1.2.4不侯选产生挖掘频繁项集I2 7 I1 6I3 6I4 2I5 2项ID支持度 计数节点链nullI2:7I1:4I3:2I4:1I3:2I1:2I4:1I3:2I5:1I5:1项 条件模式基 条件FP树 产生的频繁模式I5 I2,I1:1 ,I2,I1,I3:1 I2 I5:2I1 I5:2I2
20、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树树(a)扫描事务数据库扫描事务数据库D一次。收集频繁项集的集合一次。收集频繁项集的集合F和它们的支持度计数。对和它们的支持度计数。对F按支按支持度计数降序排序，结果为频繁项列表持度计数降序排序，结果为频繁项列表L。(b)创
21、建创建FP树的节点，以树的节点，以”null”标记它。对于标记它。对于D中每个事务中每个事务Trans，执行：选择，执行：选择Trans中频繁项集，并按中频繁项集，并按L中的次序排序。中的次序排序。 /怎样建立怎样建立FP树？就是根据表树？就是根据表5-1中事务数据库中的数据从根节点开始构造中事务数据库中的数据从根节点开始构造FP树，每经过已经存在的节点就使得该节点的计数增加树，每经过已经存在的节点就使得该节点的计数增加1，否则就从根节点开始，否则就从根节点开始构造它的分枝！构造它的分枝！2.FP树的挖掘通过调用树的挖掘通过调用FP_growth(FP_tree,null)实现，该过程如下：实
22、现，该过程如下： 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.support_count;构造B的条件模式基，然后构造B的条件FP树TreeB;If TreeB空 then 调用FP_growth(TreeB,B);例：
23、最小支持度阈值 为3交易编号交易编号所有购物项所有购物项（排序后的）频繁项排序后的）频繁项100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,pFP-GrowthFP-Growth算法例算法例nullb:1f:3c:1b:1p:1f:1c:1m:1p:1a:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:21.f,c,a,m,p2.f,c,a,b,m3.f,b4.c,b,p5.f,c,a,m,pFP-GrowthFP
24、-Growth算法例算法例头 表项节 点 链 的 头fcabmprootf:4c:1p:2m :2a:3b:1b:1p:1b:1c:3m :1生成的FP树 FP-GrowthFP-Growth算法例算法例节点链性质对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。项项条件模式库条件模式库条件条件FP树树p(f:2,c:2,a:2,m:2),(c:1,b:1)(c:3)| pm(f:4,c:3,a:3,m:2),(f:4,c:3,a:3,b:1,m:1)(f:3,c:3,a:3)| mb(f:4,c:3,a:3,b:1),(f:4,b:1),(c:1,b:1)a
25、(f:3,c:3)(f:3,c:3)| ac(f:3)(f:3)| cf包含m的所有频繁模式的集合有：(m:3),(am:3),(cm:3),(fm:3),(cam:3),(fam:3),(fcam:3),(fcm:3)。这表明对一个单独路径的FP树进行挖掘时，可以通过输出该路径上所有项的组合来实现。FP-GrowthFP-Growth算法例算法例1.2.5使用垂直数据格式挖掘频繁项集 Apriori算法和FP增长方法都是从TID项集格式的事务集挖掘频繁项集模式，其中TID是事务表示符，而itemset是事务TID中购买的商品。这种数据格式称做水平数据格式。下面我们将TID与 itemset两
26、个调换位置来挖掘数据，也就是我们要讨论的垂直数据格式挖掘频繁模式：先看下面的例子来体会垂直数据格式挖掘频繁项集：例题5-6：沿用表5-1中数据，扫描一次数据库可以将其转换为下表所示的垂直数据格式：1.2.5使用垂直数据格式挖掘频繁项集项 集 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使用垂直数据格式挖掘频繁项集现在我
27、们构造频繁2项集如下： 项集 TID集I1,I2 T100,T400,T800,T900I1,I3 T500,T700,T800,T900I1,I4 T400I1,I5 T100,T800I2,I3 T300,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项集如下：
28、查找垂直频繁项集的步骤：1.扫描数据库把水平数据格式转换成垂直数据格式；2.获取项集的支持度计数（也就是TID的长度）；3.通过K项集来构造（k+1）项集，通过取频繁k项集的TID集的交计算对应的(K+1)项集的TID集；4.重复该过程，每次k增值1，直到不能找到频繁项集或侯选项集为止。应用实例 目前很多高校对教学评价主要基于数值计算，把学生的评价作一总结，将结果通报给老师，作为晋升职称、评优等的依据，系里对老师做一奖惩及引导，不做深层的思考。这里我们将对教学评价数据进行关联规则挖掘，试图挖掘教学效果与教师的性别、年龄、职称、学历等的关联，找到课堂教学效果与教师整体素质的关系，从而合理调配一个
29、班的上课老师，使学生能够较好地保持良好的学习状态，从而为教学部门提供决策支持信息，以便更好地开展教学工作，提高教学质量。1.数据准备数据准备 这是我们随机抽取某高校教师教学质量评估表1000份，将教师编号、年龄、性别、职称、学历、公费进修、工作量和评定分数8项输入数据库，忽略其它信息。我们将通过数据挖掘找出性别、年龄、职称、学历、公费进修、工作量和评定分数之间的关系。表10.8给出了部分教学评价信息视图，共有1000条记录。在表10.8中，属性年龄、工作量、成绩都是数量属性(非离散属性)，这里，我们将其离散化。首先，对年龄进行分组:Al22，30，A231，35，A336，49，A450，60
30、；然后对工作量进行分组:B1:0，120学时，B2:120学时以上；对成绩进行分组:C1:教学效果好85，100，C2:教学效果不是很好0，85)。将数量属性离散化后的结果如表10.9所示。 2挖掘关联规则挖掘关联规则利用关联规则挖掘算法Apriori来挖掘关联规则了，找出性别、学历、年龄、职称、公费进修、工作量等因素对教学效果的影响，进而采取一定的措施，提高教学质量。这里，设minsup= 5%，minconf=5%，得到满足最小支持度和最小可信度的关联规则3挖掘结果分析挖掘结果分析 通过得到的关联规则，可得到如下的分析结果及改进措施。 （1）性别对教学效果的影响 规则女Cl和男C1的置信度
31、分别为63.5%和60.4%，这两个关联规则的置信度基本相同，说明性别对教学效果没有什么影响，因此在引进教师时不应该考虑性别因素。 （2）年龄对教学效果的影响 年龄对教学效果的影响可以从下面3种情况进行分析: 3挖掘结果分析挖掘结果分析 随着年龄的增长，规则年龄教学效果好的置信度也增大，说明年龄大的教师的教学质量高。 规则22，30C1的置信度很低，这主要是因为目前高校引入的教师都是硕士以上，30岁以下的教师教学经验很少，应尽量少上课或不上课。 规则50，60C1的置信度很高，说明50，60这个年龄段的教师的教学质量很高，但支持度却很低，说明这部分老师承担的工作量不大。学校应采取一定措施，让老教师多承担教学工作。（3）职称对教学效果的影响 随着年龄的增大，职称也不断提高。反之，职称高的教师一般年龄也偏高，所以职称对教学效果的影响和年龄对教学效果的影响基本是一致的（4）公费进修对教学效果的影响 从表10.10可知，关联规则:进修过Cl比关联规则:没进修过C1的置信度高，说明进修对提高教师的教学水平有很多作用3挖掘结果分析挖掘结果分析 722022-7-28