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

1、关联规则挖掘7/27/2022 1、Apriori算法Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。 Apriori的性质： 性质1：频繁项集的所有非空子集必为频繁项集。性质2：非频繁项集的超集一定是非频繁的。 Apriori的步骤： 连接步：为找Lk ，通过将Lk-1与自身连接产生候选k项集的集合剪枝步：Ck是Lk 的超集，也就

2、是说，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 tD do begin /扫描计数(5) Ct=subset(Ck,t); /得到t的子集，它们是候选 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.count

3、minsup (10) end; (11) Answer= Apriori算法实例现有A、B、C、D、E五种商品的交易记录表，试找出三种商品关联销售情况(k=3)，最小支持度=50%。实例解答K=1支持度50K=2支持度50支持度50支持度50支持度50Apriori算法的不足Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。提高Apriori算法的方

4、法Hash-based itemset counting（散列项集计数）Transaction reduction（事务压缩）Partitioning（划分）Sampling（采样）Hash-based itemset counting（散列项集计数）将每个项集通过相应的hash函数映射到hash表 中的不同的桶中，这样可以通过将桶中的项集 计数跟最小支持计数相比较先淘汰一部分项集。Transaction reduction（事务压缩）减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的频集，则必然不包含长度为k+1的频集。从而我们就可以将这些事务加上标记或者删除，这样

5、在下一遍的扫描中就可以减少进行扫描的事务集的个数。这个就是AprioriTid的基本思想。Partitioning（划分）挖掘频繁项集只需要两次数据库扫描D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中第一次扫描：将数据划分为多个部分并找到局部频繁项集第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集Sampling（采样）基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式可以通过一次全局扫描来验证从样本中发现的模式可以通过第二

6、此全局扫描来找到遗漏的模式2000年，Han等提出了一个称为FP-tree的算法。 FP-tree算法只进行2次数据库扫描。它不使用候选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。FP-tree算法由两个主要步骤完成：利用事务数据库中的数据构造FP-tree；从FP-tree中挖掘频繁模式。2、FP-tree 算法（不用生成候选项集）具体过程：扫描数据库一次，得到频繁1-项集把项按支持度递减排序再一次扫描数据库，建立FP-tree步骤1：构造 FP-tree树完备: 不会打破交易中的任何模式包含了频繁模式挖掘所需的全部信息紧密去除不相关信息不包含非频繁项支持度降序排列: 支

7、持度高的项在FP-tree中共享的机会也高决不会比原数据库大（如果不计算树节点的额外开销)FP-tree 结构的好处步骤2：频繁模式的挖掘具体过程:(1 ) 根据事务数据库D 和最小支持度min_sup， 调用建树过程建立FP-tree;(2 ) if (FP-tree 为简单路径) 将路径上支持度计数大于等于min_sup 的节点任意组合，得到所需的频繁模式 else 初始化最大频繁模式集合为空(3 ) 按照支持频率升序，以每个1 频繁项为后缀，调用挖掘算法挖掘最大频繁模式集(4 ) 根据最大频繁模式集合中最大频繁模式，输出全部的频繁模式 FP-tree算法的一个例子TidItems1I1,

8、I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事物数据库 ： 第一步、构造FP-tree扫描事务数据库得到频繁1-项目集F定义minsup=20%，即最小支持度为2重新排列F，把项按支持度递减排序：I1I2I3I4I567622I2I1I3I4I576622 重新调整事务数据库TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2,I37I1,I38I2, I1,I3,I59I2, I1,I3 创建根结点和频繁项目表Item-nameNode-headI2NullI1

9、NullI3NullI4NullI5NullNull 加入第一个事务(I2,I1,I5)Item-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:1

10、I4:1 加入第五个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2: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

11、:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:1 加入第九个事务(I2,I1,I3)Item-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，得到条件模式基、 构造条件FP-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-