关联规则挖掘课件

《关联规则挖掘课件》由会员分享，可在线阅读，更多相关《关联规则挖掘课件（49页珍藏版）》请在金锄头文库上搜索。

1、第 8 章 集合论方法（二）关联规则挖掘,8.2关联规则挖掘,8.2.1关联规则的挖掘原理 8.2.2Apriori算法基本思想 8.2.3Apriori算法 8.2.4基于Fp-tree的关联规则挖掘算法,8.2关联规则挖掘,关联规则（Association Rule）挖掘是发现大量数据库中项集之间的关联关系。 从大量商业事务中发现有趣的关联关系，可以帮助许多商业决策的制定，如分类设计、交叉购物等。 Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题 。,821关联规则的挖掘原理,关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式

2、。 例1： 在购买铁锤的顾客当中，有70的人同时购买了铁钉。,例2：年龄在40 岁以上，工作在A区的投保人当中，有45的人曾经向保险公司索赔过。 可以看出来，A区可能污染比较严重，环境比较差，索赔率也相对比较高。,1. 基本原理,设I=i1,i2,im是项（Item）的集合。记D为事务（Transaction）的集合（事务数据库），事务T是项的集合，并且TI。 设A是I中一个项集，如果AT，那么称事务T包含A。 定义1：关联规则是形如AB的蕴涵式，这里AI，BI，并且AB=。,定义2：规则的支持度。 规则AB在数据库D中具有支持度S，表示S是D中事务同时包含AB的百分比，它是概率P(AB)，即

3、： 其中|D|表示事务数据库D的个数，表示A、B两个项集同时发生的事务个数。,定义3：规则的可信度 规则AB具有可信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P(B|A)，即： 其中 表示数据库中包含项集A的事务个数。,定义4：阈值。 在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：最小支持度（min_sup）和最小可信度（min_conf）。 定义5：项的集合称为项集（Itemset），包含k个项的项集称之为k-项集。 如果项集满足最小支持度，则它称之为频繁项集（Frequent Itemset）。,定义6：关联规则。 同时满足最小支持度（m

4、in_sup）和最小可信度（min_conf）的规则称之为关联规则，即 成立时，规则称之为关联规则，也可以称为强关联规则。,2. 关联规则挖掘过程,关联规则的挖掘一般分为两个过程： （1）找出所有的频繁项集：找出支持度大于最小支持度的项集，即频繁项集。 （2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。,3. 关联规则的兴趣度,例子：讨论不购买商品与购买商品的关系。 设，交易集D，经过对D的分析，得到表格:,设定minsupp=0.2, minconf=0.6, 得到如下的关联规则： 买牛奶 买咖啡 s=0.2 c=0.8 即80的人买了牛奶就会买咖啡。 同时得到

5、结论：90的人肯定会买咖啡。 规则 买咖啡 不买牛奶 s=0.7 c=0.78 支持度和可信度分别为0.7和0.78，更具有商业销售的指导意义。,定义7：兴趣度： 公式反映了项集A与项集B的相关程度。 若 即 表示项集A出现和项集B是相互独立的。 若 表示A出现和B出现是负相关的。 若 表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。,一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）； 一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）； 兴趣度I不小于0。,所有可能的关联规则,讨论I1I2I3I6共4条规则： 由

6、于I1,I21,规则才有价值。 兴趣度也称为作用度（Lift）,表示关联规则AB的“提升”。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。,概括地说： 可信度是对关联规则地准确度的衡量。 支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。 兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度（作用度）越大，说明项集B受项集A的影响越大。,822 Apriori算法基本思想,Apriori是挖掘关联规则的一个重要方法。 算法分为两个子问题： 找到所有支持度大于最小

7、支持度的项集（Itemset），这些项集称为频繁集（Frequent Itemset）。 使用第1步找到的频繁集产生规则。,Apriori 使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。 首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3， 如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。,1Apriori 性质,性质：频繁项集的所有非空子集都必须也是频繁的。（这个性质可以否定频繁项集，但是不能肯定频繁项集） 如果项集B不满足最小支持度阈值min-sup，则B不是频繁的，即 P（B）min-sup。

8、 如果项A添加到B，则结果项集（即BA）不可能比B更频繁出现。因此，BA也不是频繁的，即 P（BA）min-sup。,2“K-项集”产生“K+1-项集” 设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK+1。有公式： CK+1=LKLK=XY，其中X，Y LK， |XY|=K+1 其中C1是1-项集的集合，取自所有事务中的单项元素。,如 L1=A，B C2=AB=A，B，且|AB|=2 L2=A，B，A，C C3=A，BA，C=A，B，C，且 |ABC|=3,3Apriori 算法中候选项集 与频繁项集的产生实例,1) 在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算

9、法扫描所有的事务，对每个项的出现次数计数。见图中第1列。 2) 假定最小事务支持计数为1 （即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。见图中第2列。 3) 为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2。见图中第3列。 4) 扫描D中事务，计算C2中每个候选项集的支持度计数，如图中的第4列。 5) 确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。见图第5列。,6) 候选3-项集的集合C3的产生，得到候选集： C3=A，B，C，A，B，E，A，C，E，B，C，D，B，C，E，B，D，E 按

10、Apriori 性质，频繁项集的所有子集必须是频繁的。由于A，D，C，D，C，E，D，E不是频繁项集，故C3中后4个候选不可能是频繁的，在C3中删除它们。见图第6列。 扫描D中事务，对C3中的候选项集计算支持度计数，见图第7列。 7) 确定L3，它由具有最小支持度的C3中候选3项集组成，见图第8列。 8）按公式产生候选4项集的集合C4，产生结果A,B,C,E,这个项集被剪去，因为它的子集B,C,E不是频繁的。这样L4=。此算法终止。L3是最大的频繁项集，即：A,B,C和A,B,E。,具体产生过程用图表示,候选集与频繁项集的产生,4产生关联规则,根据前面提到的可信度的定义，关联规则的产生如下：

11、（1）对于每个频繁项集L，产生L的所有非空子集； （2）对于L的每个非空子集S，如果 则输出规则“S LS”。 注：LS表示在项集L中除去S子集的项集。,在事务数据库中，频繁项集L=A，B，E，可以由L产生哪些关联规则？ L的非空子集S有：A, B, A, E, B, E, A, B,E。可得到规则如下： A B E conf=2/4=50% A E B conf=2/2=100% B E A conf=2/2=100% A B E conf=2/6=33% B A E conf=2/7=29% E A B conf=2/2=100% 假设最小可信度为60，则最终输出的关联规则为： A E B

12、 100% B E A 100% E A B 100% 对于频繁项集A，B，C，同样可得其它关联规则。（给大家15分钟，大家把第2个频繁项集，对应的关联规则找出来）,8.2.3 Apriori算法程序,首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，算法停止。 在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频繁集做一个连接来产生的。Ck中的项集是用来产生频繁集的候选集，最后的频繁集Lk必须是Ck的一个子集。 Agrawal等引入了修剪技术来减小候选集Ck的大小 。 一个项集是频繁集当且仅当它的所有子集都是

13、频繁集。 如果Ck中某个候选项集有一个（k-1）-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑 。,8.2.4基于FP-tree的关联规则挖掘算法,Jiawei Han等人提出了一种基于FP-树的关联规则挖掘算法FP_growth，它采取“分而治之”的策略，将提供频繁项目集的数据库压缩成一棵频繁模式树（FP-树） 。 理论和实验表明该算法优于Apriori算法。,仍用上例事务数据库来说明FP-树的构造过程和频繁模式挖掘过程。 (1)FP-树构造过程 数据库的第一次扫描与Apriori相同，它导出频繁项（1-项集）的集合，并得到他们的支持度计数。设最小支持度为2，频繁项的集合按支持度计数

14、的递减顺序排序，结果表记作L。这样，我们有：,FP-树构造如下：首先，创建树的根节点，用“null”标记。第二次扫描事务数据库。每个事务中的项按L中的次序处理（即按递减支持度计数排序）并对每个事务创建一个分枝。 例如，第一个事务“T1：A，B，E”，按L的次序包括三个项B，A，E，导致构造树的第一个分枝。该分枝具有三个节点，其中B作根节点的子链接，A链接到B，E链接到A。从L表中节点链中，项B，A，E的指针分别指向树中、节点,第二个事务“：，”按的次序也是，D仍以B开头，这样在B节点中产生一个分枝，该分枝与T1项集存在路径共享前缀B。这样，将节点B的计数增加1，即（B:2），并创造一个D的新节

15、点（D:1），作为（B:2）的子链接。 第三个事务“T3：B，C”同第二个事务一样处理，因为有相同的B为头，在B节点又产生一个分枝，产生新节点，记为（C:1），节点B的计数再增加1（为3），即（B:3）。,第四个事务“T4：A，B，D”，按L的次序为B，A，D。在FP-树中B，A，已有节点，将共享前缀路径，从A节点分枝产生D的另一新节点，记为（D:1），共享节点B，A的计数均增加1，即（B:4），（A:2）。此（D:1）节点用指针指向前面产生的（D:1）节点，在L表中节点链接中指针指向该（D:1）节点。,第五个事务“T5：A，C”，按L表的次序为A，C。在FP-树中，由于该事务不含节点，不能共

16、享分枝。从null节点产生FP-树的第二个分枝，建新节点，记为（A:），由该节点产生分枝，建新C节点，即为（C:1）。由于B分枝中有（A:2）节点。这样，从（A:2）节点用指针指向此（A:1）节点，B分枝中有（C:1）节点，它用指针指向此（C:1）节点。,第六个事务“T6：B，C”，同第三个事务那样，沿FP-树的B-C分枝的节点计数各增加1，变为（B:5）和（C:2）。 第七个事务“T7：A，C”，同第五个事务，沿FP-树的A-C分枝的节点计数各增加1，变为（A:2）和（C:2）。,第八个事务“T8：A，B，C，E”，按L表的次序为B，A，C，E，可沿分枝B-A方向，在A节点处新建分枝，建C结点，记（C:1），由该节点再建分枝，建E节点，记为（E，1），前面B，节点计数各增加，变为：（B:6），（A:3）。FP-树中原E节点（E:1）中的指针指向该（E，1）节点。,第九个事务“T9：A，B，C