数据挖掘——第三章关联规则挖掘(2)

挖掘频繁模式、关联和相关1.1.1购物篮分析：引发性例子1.1.2频繁项集、闭项集和关联规则1.1.3频繁模式挖掘：路线图1.1基本概念和线路图1.1.1购物篮分析：引发性例子频繁项集挖掘的一个典型例子是购物篮分析。优点：通过分析顾客的购买习惯，就能帮助零售商了解哪些商品频繁地被顾客同时购买，从而帮助他们开发更好的营销策略。例如：如果顾客在超市购物时购买了牛奶，他们有多大的可能同时购买面包？什么是项？什么是事务？比如说在超市中的每一件商品在我们这里可以看作一个项！每个顾客消费时的购物单可以看作是一个事务！例如：如果顾客购买电脑的同时也倾向于购买杀毒软件，可以将两种产品放在一起销售！通过上面的例子我们来分析和了解下面的两个概念：最小支持度阀值和最小置信度阀值：是由用户或专家来设定的，也就是由他们来定义支持度与置信度的下限值。Confidence：置信度。置信度为60%意味着购买计算机的顾客60%也购买了杀毒软件。support：支持度。支持度为2%意味着所分析的所有事务的2%同时购买计算机和杀毒软件。Computerantivirus_software[support=2%,confidence=60%]什么是支持度？什么是置信度？1.1.2频繁项集、闭项集和关联规则1.频繁项集：这些项集的每一个出现的频率性至少与预定义的最小支持计数min_sup一样。2.闭频繁项集：如果不存在真超项集(数学中真子集相同)Y，使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的。如果X在S中是闭的和频繁的，项集X是数据集S中的闭频繁项集。3.关联规则：Computerantivirus_software[support=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,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.根据所挖掘的规则类型分类；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.该算法的使用是通过下面的两个步骤来完成的：连接步和剪枝步。怎样来理解和掌握Apriori算法呢？我们可以通过下面的例子来理解和掌握：例5-3该例子是基于下表的AllElectronics的事务数据库D，数据库中有9个事务，即|D|=9。TID商品ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3表5-1AllElectronics某分店的是事务数据项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2扫描D对每个侯选计数项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2C1L1比较侯选支持度计数与最小支持度计数有L1产生侯选C2项集{I1,I2}{I1,I3}{I1,I4}{I1,I5}{I2,I3}{I2,I4}{I2,I5}{I3,I4}{I3,I5}{I4,I5}C2C2项集支持度计数{I1,I2}4{I1,I3}4{I1,I4}1{I1,I5}2{I2,I3}4{I2,I4}2{I2,I5}2{I3,I4}0{I3,I5}1{I4,I5}0扫描D，对每个侯选计数项集支持度计数{I1，I2}4{I1，I3}4{I1，I5}2{I2，I3}4{I2，I4}2{I2，I5}2比较侯选支持度计数与最小支持度计数L2项集{I1,I2,I3}{I1,I2,I5}C3由L2产生侯选C3扫描D对每个侯选计数项集支持度计数{I1,I2,I3}2{I1,I2,I5}2C3项集支持度计数{I1,I2,I3}2{I1,I2,I5}2L3比较侯选支持度计数与最小支持度计数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项侯选项集；foreach事务t∈D//扫描数据库D中的每一个事务t；{Ct=subset(Ck,t);//对事务t，产生具有K项的子集赋给Ct；foreach侯选c∈Ct//检查侯选项集中的某一项是否属于Ct；c.count++;//若属于的话，Ck中某一个项集的支持度加1；}Lk={c∈Ck|c.count≥min_sup}//进行最后的剪枝；}returnL=∪kLk怎样产生？Procedureapriori-gen(Lk-1;frequent(k-1)-itemsets){foreach项集l1∈Lk-1//对（k-1）项侯选项集中某项进行连接；foreach项集l2∈Lk-1if(l1[1]=l2[1]^l1[2]=l2[2]^…^l1[k-2]=l2[k-2]^l1[k-1]l2[k-1])then{c=l1连接l2;ifhas_infrequent_subset(c,Lk-1)thendeletec;elseaddctoCk;}returnCk;}根据Apriori算法的性质检查它的每一个(k-1)子集是不是频繁项集！Prodedurehas_infrequent_subset(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets){//从第k项侯选项集Ck中，看它的(k-1)项子集是不是第(k-1)项频繁项集中的项；foreach(k-1)-subsetsofc//侯选项集Ck的(k-1)项子集S；ifs∈Lk-1thenreturntrue;returnfalse;}总之，Apriori算法的步骤就是连接与剪枝两步！1.2.2由频繁项集产生关联规则I1^I2I5confidence=2/4=50%I1^I5I2confidence=2/2=100%I2^I5I1confidence=2/2=100%根据上面讨论的Apriori算法，通过例题5-4来进一步掌握由频繁项集产生关联规则：例题5-4：尝试基于表5-1中数据库的例子，假定数据包含频繁项集l={I1，I2，I5}。可以由l产生哪些关联规则？l的非空子集有{I1,I2}，{I1,I5}，{I2,I5}，{I1}，{I2}，{I5}.结果列出关联规则如下，每个都列出置信度：由L2和L3的支持度直接计算！I1I2^I5confidence=2/6=33%I2I1^I5confidence=2/7=29%I5I1^I2confidence=2/2=100%如果最小置信度阀值为70%，则上面第2、3和最后一个规则可以输出，因为只有这些产生强规则。注意：与传统的分类规则不同，关联规则的右端可能包含多个合取项。1.2.1Apriori算法举例已知事务数据库D如表10.1所示，最小支持度计数为2，即minsupport=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,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.基于散列的技术：将产生的下一项集散列到散列表结构的不同桶中，并增加对应的桶的计数；2.事物压缩：不包含任何频繁k项集事务的事务不可能包含任何频繁(k+1)项集。这种事务在其后的考虑时，可以加上标记或删除因为产生j项集(jk)的数据库扫描不需要它们；怎样才能提高基于Apriori的挖掘的效率？已经提出了许多Apriori算法的变形，旨在提高原算法的效率。其中一些变形汇总如下：1.2.3提高Apriori算法的效率4.抽样：选取给定数据D的随机样本S，然后在S中间搜索频繁项；5.动态项集计数：将数据库划分为用开始点标记的块，可以在任何开始点添加新的侯选项集。3.划分：先将数据库划分成两个部分，对每个划分找出其中的局部频繁项集。D的任何频繁项集必须作为局部频繁项集至少出现在一个划分中。所有频繁项集的集合形成D的全局侯选项集；Apriori算法显著的压缩了侯选项集的大小，并导致很好的性能。然而，它要受到两种平凡的开销的影响：1.它可能需要产生大量侯选项集；2.它可能需要重复地扫描数据库，通过模式匹配检查一个很大的侯选集合。1.2.4不侯选产生挖掘频繁项集为了解决Apriori算法带来的一些缺陷，我们又将设计一种怎样的方法来解决了？关联规则挖掘算法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非空，递归的调用insert_tree(P，N)．FP-growth算法1.ProcedureFP-growth(Tree，a)2.ifTree包含单个路径p