(数据挖掘)关联规则挖掘——Apriori算法、fp—Tree算法

关联规则挖掘 * 1、Apriori算法 Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 Apriori算法将发现关联规则的过程分为两个步骤： 通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集； 利用频繁项集构造出满足用户最小信任度的规则。 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。 Apriori的性质： 性质1：频繁项集的所有非空子集必为频繁项集。 性质2：非频繁项集的超集一定是非频繁的。 Apriori的步骤： 连接步：为找Lk ，通过将Lk-1与自身连接产生候选k项集的集合 剪枝步：Ck是Lk 的超集，也就是说，Ck的成员可以是也可以不是频繁的，但所有的频繁k项集都包含在Ck中。 任何非频繁的（k-1）项集都不是频繁k项集的子集。 Apriori算法 (1) L1={频繁1项集}; (2) for(k=2;Lk-1;k++) do begin (3) Ck=apriori_gen(Lk-1); //新的候选频繁项集 (4) for all transactions tD do begin //扫描计数 (5) Ct=subset(Ck,t); //得到t的子集，它们是候选 (6) for all candidates cCt do (7) c.count++; (8) end; (9) Lk={cCk|c.countminsup} (10) end; (11) Answer= Apriori算法实例 现有A、B、C、D、E五种商品的交易记录表，试找 出三种商品关联销售情况(k=3)，最小支持度=50%。 Sheet1 交易号 商品代码 100 A、C、D min_support 20% 200 B、C、E 300 A、B、C、E 400 B、E 项集 支持度 L1 ｛A｝ 50% ｛B｝ 75% {C} 75% ｛D｝ 25% ｛E｝ 75% k=1 Sheet2 Sheet3 实例解答 K=1 支持度<50 Sheet1 交易号 商品代码 100 A、C、D min_support 20% 200 B、C、E 300 A、B、C、E 400 B、E 项集 支持度 C1 ｛A｝ 50% ｛B｝ 75% {C} 75% ｛D｝ 25% ｛E｝ 75% k=1 Sheet2 Sheet3 Sheet1 交易号 商品代码 100 A、C、D 200 B、C、E 300 A、B、C、E 400 B、E 项集 支持度 项集 支持度 L1 ｛A｝ 50% L2 ｛A,B｝ 25% ｛B｝ 75% ｛A,C｝ 50% {C} 75% {A,E} 25% ｛D｝ 25% ｛B,C｝ 50% ｛E｝ 75% ｛B,E｝ 50% K1 ｛A｝ 50% ｛C,E｝ 50% ｛B｝ 75% L2 ｛A,C｝ 50% {C} 75% ｛B,C｝ 50% ｛E｝ 75% ｛B,E｝ 75% 从K2中求可用来计算的的三项集 ｛C,E｝ 50% ｛A,C｝+{B,C} {A,B,C} {A,B,C} 25% ｛A,C｝+{B,E} 超过三项 ｛A,C｝+{C,E} {A,C，E} {A,C，E} 25% ｛B,C｝+{B,E} {B,C，E} {B,C，E} 50% ｛B,C｝+{C,E} {B,C，E} ｛B,E｝+{C,E} {B,C，E} Sheet2 Sheet3 Apriori算法的不足 Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。 提高Apriori算法的方法 Hash-based itemset counting（散列项集计数） Transaction reduction（事务压缩） Partitioning（划分） Sampling（采样） Hash-based itemset counting（散列项集计数） 将每个项集通过相应的hash函数映射到hash表 中的不同的桶中，这样可以通过将桶中的项集 计数跟最小支持计数相比较先淘汰一部分项集。 Transaction reduction（事务压缩） 减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的频集，则必然不包含长度为k+1的频集。从而我们就可以将这些事务加上标记或者删除，这样在下一遍的扫描中就可以减少进行扫描的事务集的个数。这个就是AprioriTid的基本思想。 Partitioning（划分） 挖掘频繁项集只需要两次数据库扫描 D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中 第一次扫描：将数据划分为多个部分并找到局部频繁项集 第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集 Sampling（采样） 基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式 通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式 可以通过一次全局扫描来验证从样本中发现的模式 可以通过第二此全局扫描来找到遗漏的模式 2000年，Han等提出了一个称为FP-tree的算法。 FP-tree算法只进行2次数据库扫描。它不使用候选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。 FP-tree算法由两个主要步骤完成：①利用事务数据库中的数据构造FP-tree；②从FP-tree中挖掘频繁模式。 2、FP-tree 算法（不用生成候选项集） 具体过程： 扫描数据库一次，得到频繁1-项集 把项按支持度递减排序 再一次扫描数据库，建立FP-tree 步骤1：构造 FP-tree树 完备: 不会打破交易中的任何模式 包含了频繁模式挖掘所需的全部信息 紧密 去除不相关信息—不包含非频繁项 支持度降序排列: 支持度高的项在FP-tree中共享的机会也高 决不会比原数据库大（如果不计算树节点的额外开销) FP-tree 结构的好处 步骤2：频繁模式的挖掘 具体过程: (1 ) 根据事务数据库D 和最小支持度min_sup， 调用建树过程建立FP-tree; (2 ) if (FP-tree 为简单路径) 将路径上支持度计数大于等于min_sup 的节点任意组合，得到所需的频繁模式 else 初始化最大频繁模式集合为空 (3 ) 按照支持频率升序，以每个1 － 频繁项为后缀，调用挖掘算法挖掘最大频繁模式集 (4 ) 根据最大频繁模式集合中最大频繁模式，输出全部的频繁模式． FP-tree算法的一个例子 事物数据库 ： Tid Items 1 I1,I2,I5 2 I2,I4 3 I2,I3 4 I1,I2,I4 5 I1,I3 6 I2,I3 7 I1,I3 8 I1,I2,I3,I5 9 I1,I2,I3 第一步、构造FP-tree 扫描事务数据库得到频繁1-项目集F 定义minsup=20%，即最小支持度为2 重新排列F，把项按支持度递减排序： I1 I2 I3 I4 I5 6 7 6 2 2 I2 I1 I3 I4 I5 7 6 6 2 2 重新调整事务数据库 Tid Items 1 I2, I1,I5 2 I2,I4 3 I2,I3 4 I2, I1,I4 5 I1,I3 6 I2,I3 7 I1,I3 8 I2, I1,I3,I5 9 I2, I1,I3 创建根结点和频繁项目表 Null Item-name Node-head I2 Null I1 Null I3 Null I4 Null I5 Null 加入第一个事务(I2,I1,I5) Null I2:1 I1:1 I5:1 Item-name Node-head I2 I1 I3 Null I4 Null I5 加入第二个事务(I2,I4) Null I2:2 I1:1 I5:1 I4:1 Item-name Node-head I2 I1 I3 Null I4 I5 加入第三个事务(I2,I3) Null I2:3 I1:1 I5:1 I4:1 I3:1 Item-name Node-head I2 I1 I3 I4 I5 加入第四个事务(I2,I1,I4) Null I2:4 I1:2 I5:1 I4:1 I3:1 I4:1 Item-name Node-head I2 I1 I3 I4 I5 加入第五个事务(I1,I3) Null I2:4 I1:2 I5:1 I4:1 I3:1 I4:1 I1:1 I3:1 Item-name Node-head I2 I1 I3 I4 I5 加入第六个事务(I2,I3) Null I2:5 I1:2 I5:1 I4:1 I3:2 I4:1 I1:1 I3:1 Item-name Node-head I2 I1 I3 I4 I5 加入第七个事务(I1,I3) Null I2:5 I1:2 I5:1 I4:1 I3:2 I4:1 I1:2 I3:2 Item-name Node-head I2 I1 I3 I4 I5 加入第八个事务(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 Item-name Node-head I2 I1 I3 I4 I5 加入第九个事务(I2,I1,I3) Null I2:7 I1:4 I5:1 I4:1 I3:2 I4:1 I1:2 I3:2 I5:1 I3:2 Item-name Node-head I2 I1 I3 I4 I5 第二步、FP-growth 首先考虑I5，得到条件模式基 <(I2,I1:1)>、 构造条件FP-tree 得到I5频繁项集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}} Null I2:2 I1:2 I3:1 Item-name Node-head I2 I1 第二步、FP-growth 接着考虑I4，得到条件模式基 <(I2,I1:1)>、 构造条件FP-tree 得到I4频繁项集：{{I2,I4:2}} Null I2:2 I1:1 Item-name Node-head I2 第二步、FP-growth 然后考虑I3，得到条件模式基 <(I2,I1:2)>、、 构造条件FP-tree 由于此树不是单一路径，因此需要递归挖掘I3 Null I2:4 I1:2 I1:2 Item-name Node-head I2 I1 第二步、FP-growth 递归考虑I3，此时得到I1条件模式基 <(I2:2)>,即I1I3的条件模式基为<(I2:2)> 构造条件FP-tree 得到I3的频繁项目集{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}} Null I2:2 Item-name Node-head I2 第二步、FP-growth 最后考虑I1，得到条件模式基 <(I2:4)> 构造条件FP-tree 得到I1的频繁项目集{{I2,I1:4}} Null I2:4 Item-name Node-head I2 FP - tree 算法的优缺点 FP-tree 算法只需对事务数据库进行二次扫描，并且避免产生的大量候选集． 但由于该算法要递归生成条件数据库和条件FP-tree，所以内存开销大，而且只能用于挖掘单维的布尔关联规则． 谢谢大家！