《数据挖掘——第三章关联规则挖掘(2)幻灯片》由会员分享，可在线阅读，更多相关《数据挖掘——第三章关联规则挖掘(2)幻灯片（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 因为a
4、2,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、根据所挖掘的模式类型分类；,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 6 I2 7 I3 6 I4 2 I5 2
7、,扫描D对每个侯选计数,项集 支持度计数 I1 6 I2 7 I3 6 I4 2 I5 2,C1,L1,比较侯选支持度计数与最小支持度计数,有L1产生侯选C2,项集 I1,I2 I1,I3 I1,I4 I1,I5 I2,I3 I2,I4 I2,I5 I3,I4 I3,I5 I4,I5,C2,C2,项集 支持度计数 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 I
8、2，I5 2,比较侯选支持度计数与最小支持度计数,L2,项集 I1,I2,I3 I1,I2,I5,C3,由L2产生侯选C3,扫描D对每个侯选计数,项集 支持度计数 I1,I2,I3 2 I1,I2,I5 2,C3,项集 支持度计数 I1,I2,I3 2 I1,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)项
9、频繁项集产生第k项侯选项集； Ck= apriori_gen(Lk-1); /产生的第k项侯选项集； 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 ea
10、ch 项集l1 Lk-1 /对（k-1）项侯选项集中某项进行连接； for each 项集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)-it
11、emsets) /从第k项侯选项集Ck中，看它的(k-1)项子集是不是 第(k-1)项频繁项集中的项； 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来进一步掌握由频
12、繁项集产生关联规则：,例题5-4：尝试基于表5-1中数据库的例子，假定数据包含频繁项集l=I1，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和最后一个规则可以输出，因为只有这些产生强规则。,注意：与传统的分类规则不同，关联规则的右端可能包含多个合取项。,
13、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,
14、 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
15、, 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.划分：先将数据库划分成两个部分，对每个划分找出
