Apriori算法和FP-growth算法

1、 by王晨曦1.Apriori算法详解 关联分析是一种在大规模数据集中寻找有趣关系的任务。频繁项集是经常出现在一块的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。 频繁项集是指那些经常出现在一起的物品的集合，上表的集合葡萄酒，尿布，豆奶就是频繁项集的一个例子，从上面的数据集也可以找到诸如尿布葡萄酒的关联规则。交易号码交易号码商品商品0豆奶，莴苣1莴苣，尿布，葡萄酒，甜菜2豆奶，尿布，葡萄酒，橙汁3莴苣，豆奶，尿布，葡萄酒4莴苣，豆奶，尿布，橙汁 如何定义这些有趣的关系呢？谁来定义什么是有趣的？当寻找频繁项集时，频繁的定义是什么？有许多概念可以解答上述问题，不过其中最重要的是支持度和置

2、信度。 一个项集的支持度被定义为数据集中包含该项集的记录所占的比例。从表中可以得到，在5条交易记录中有3条包含豆奶，尿布，因此豆奶，尿布的支持度是3/5。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。 置信度或可信度是针对一条诸如尿布葡萄酒的关联规则定义的。这条规则的可信度被定义为“支持度(尿布，葡萄酒) /支持度(尿布)”。从表中可以看到，由于尿布，葡萄酒的支持度为3/5，尿布的支持度为4/5，所以“尿布葡萄酒”的可信度为3/4=0.75。这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适用。 支持度和可信度是用来量化关联分析是否成功的方

3、法。假设想找到支持度大于0.8的所有项集，应该如何去做？一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，可是当物品成千上万时，上述做法非常非常慢。为了降低所需的计算时间，研究人员发现一种所谓的Apriori原理。 Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。例如：项集豆奶,尿布是频繁的，那么豆奶、尿布也一定是频繁的，也就是说如果一个项集是非频繁项集，那么它的所有超集也是非频繁的。如已知项集橙汁是非频繁的，我们就知道莴苣，橙汁、牛奶，尿布，橙汁也是非频繁的。使用该原理可以避免项集数目的指数增长，从而在合理的时间内计算出频繁项集。 TID

4、 项目【例3】一个Apriori的具体例子，该例基于右图某商店的事务DB。DB中有9个事务，Apriori假定事务中的项按字典次序存放。1 1，2，5 2，4 2 2，3 3 1，2，4 4 1，3 5 6 2，3 1，3 7 1，2，3，5 8 1，2，3 9 （1）在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事务，对每个项的出现次数计数。 C1 项集 支持度计数 1 6 扫描D,对每 个候选计数 2 7 3 6 4 2 5 2 （2）设最小支持计数为2，可以确定1-频集的集合L 1。它由具有最小支持度的候选1-项集组成。L1 项集 支持度计数 1 6 比

5、较候选支持度计数 2 7 与最小支持度计数 3 6 4 2 5 2 （3）为发现繁-频集的集合L2，算法 使用L1L1 产生候选2-项集集合C2。C2 项集 1，2 1，3 1，4 1，5 由L1产生候选C2 2，3 2，4 2，5 3，4 3，5 4，5 （4）扫描D中事务，计算C2中每个候选项 集的支持计数。 C2 项集 支持度计数 1，2 4 1，3 4 1，4 1 1，5 2 扫描D,对每 个候选计数 2，3 4 2，4 2 2，5 2 3，4 0 3，5 1 4，5 0 （5）确定2-频集的集合L2 ，它由具 有最小支持度的C2中的候选2-项集组成。 L2 项集 支持度计数 1，2

6、4 1，3 4 比较候选支持度计数 与最小支持度计数 1，5 2 2，3 4 2，4 2 2，5 2 （6）候选3-项集的集合C3 的产生如下：连接：C3=L2 L2 项集项集1,2,31,2,51,3,52,3,42,3,52,4,5项集项集1,21,31,52,32,42,5L2C3利用Apriori性质剪枝：频繁项集的所有子集必须是频繁的。存在候选项集， 判断其子集是否频繁。l 1,2,3的2-项子集是1,2，1,3和2,3, 它们都是L2的元素。因此保留1,2,3在C3中。 l 1,2,5的2-项子集是1,2，1,5和2,5, 它们都是L2的元素。因此保留1,2,5在C3中。 l 1,

7、3,5的2-项子集是1,3，1,5和3,5, 3,5不是L2的元素，因而不是频繁的，由C3中 删除1,3,5。l 2,3,4的2-项子集是2,3，2,4和3,4,其中3,4不是L2的元素，因而不是频繁的， 由C3中删除2,3,4。l 2,3,5的2-项子集是2,3，2,5和3,5, 其中3,5不是L2的元素，因而不是频繁的， 由C3中删除 2,3,5。 l 2,4,5的2-项子集是2,4，2,5和4,5, 其中4,5不是L2的元素，因而不是频繁的， 由C3中删除2,4,5 。 l 这样，剪枝后C3=1,2,3，1,2,5。 （7）扫描D中事务，以确定L3 ，它由C3中具有 最小支持度的的候选3

8、-项集组成。 C3 项集 由L2产生候选C3 1，2，3 1，2，5 C3 项集 支持度计数 扫描D,对每 个候选计数 1，2，3 2 1，2，5 2 （8）算法使用L3L3 产生候选4-项集的集合C4。尽管连接产生结果 1,2,3,5, 这个项集被剪去，因为它的子集2,3,5 不是频繁的。则C4= ,因此算法终止， 找出了所有的频繁项集。 L3 项集 支持度计数 比较候选支持度计数 1，2，3 2 与最小支持度计数 1，2，5 2 算法：Apriori。使用逐层迭代方法基于候选产生找出频繁项集。输入： D:实物数据库； Min_sup:最小支持度计数阈值。输出：L：D中的频繁项集。方法： L

9、1=find_frequent_1-itemsets(D); for(k=2;Lk-1 !=；k+) Ck=apriori_gen(Lk-1); For each 事务 tD/扫描D用于计数 Ct=subset(Ck,t);/得到t的子集，它们是候选 for each候选cC; C.count+; Lk=cC|c.count=min_stp return L=UkLk；1.5 实验一# 加载数据集def loadDataSet(): return 1, 3, 4, 2, 3, 5, 1, 2, 3, 5, 2, 51.5 实验二使用UCI蘑菇数据集进行实验 for item in L1: if

10、 ersection(2): print item输出：frozenset(2, 85)1.6 Apriori算法的缺点从以上的算法执行过程可以看到Apriori算法的缺点:第一:在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;第二:每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。2. FP-growth算法详解 FP-growth算法是在2000年提出的频繁项集挖掘算法，前面我们介绍了Apriori挖掘

11、频繁项集并且进行关联分析，这次的FP-growth和Apriori选择频繁集有点类似的地方，但是本质和Apriori完全不一样。 FP-growth算法只需要对数据库进行两次扫描，而Apriori算法对每个潜在的频 繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快。 FP-growth算法发现频繁项集的基本过程如下：2.1 构建FP树为构建FP树，需要对原始数据集扫描两遍。 第一遍对所有元素项的出现次数进行计数，统计各个元素项的出现频率，去掉不满足最小支持度的元素项。 L= s: 3, r: 3, t: 3, y: 3, x: 4, z: 5

12、FP-growth算法还需要一个称为头指针表来指定给定元素项的第一个树节点并记录各个元素项的出现次数。这样每个元素项都构成一条单链表，可以快速访问FP树中一个给定元素项的所有元素。 事务事务ID事务中的元素项事务中的元素项001r, z, h, j, p002z, y, x, w, v, u, t, s003z004r, x, n, o, s005y, r, x, z, q, t, p006y, z, x, e, q, s, t, m第二遍扫描数据集用来构建FP树。在构建时，读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。在将每条事务加到树之前，需要对每个集合

13、进行排序。排序基于元素项的绝对出现频率由高到低来进行，并过滤出不在L中的非频繁项。过滤及重排后的事务如下：事务事务ID事务中的元素项事务中的元素项过及重排序后的事务过及重排序后的事务001r, z, h, j, pz,r002z, y, x, w, v, u, t, sz,x,y,s,t003zz,004r, x, n, o, sx,s,r005y, r, x, z, q, t, pz,x,y,r,t006y, z, x, e, q, s, t, mz,x,y,s,t 在对事务记录过滤和排序之后，就可以构建FP树了。从空集开始，将过滤和重排序后的频繁项集一次添加到树中。如果树中已存在现有元素，

14、则增加现有元素的值；如果现有元素不存在，则向树添加一个分支。对前两条事务进行添加的过程： 依次将每个事务都加到FP树，最后构成的带头指针表(HeaderTable)的FP树如下图所示：2.2 从FP树中挖掘频繁项集从FP树中抽取频繁项集的三个基本步骤如下：1. 从FP树中获得条件模式基；2. 利用条件模式基，构建一个条件FP树；3. 迭代重复步骤1步骤2，直到树包含一个元素项为止。第一步：从FP树中获得条件模式基 首先从头指针表中的每个频繁元素项开始，对每个元素项，获得其对应的条件模式基（conditional pattern base）。条件模式基是以所查找元素项为结尾的路径集合。每一条路径

15、其实都是一条前缀路径（prefix path）。简而言之，一条前缀路径是介于所查找元素项与树根节点之间的所有内容。 每一个频繁项的所有前缀路径（频繁模式基）为：频繁项频繁项前缀路径前缀路径z: 5rx, s: 1, z, x, y: 1, z: 1xz: 3, : 1yz, x: 3sz, x, y: 2, x: 1tz, x, y, s: 2, z, x, y, r: 1第二步：根据条件模式基构建条件FP树 对于每一个频繁项，都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据，并通过相同的建树代码来构建这些树。例如对于为频繁项t构建一个条件模式树，然后对t,y,t,x重复该过程

16、。元素t的条件模式树构建过程如下图所示：注意到元素项s以及r是条件模式基的一部分，但是它们并不属于条件FP树。第三步：递归查找频繁项集 有了FP树和条件FP树，就可以在前两步的基础上递归得查找频繁项集。仍然以元素项t为例，下图为查找元素项t的频繁项集的步骤： 图中红色的部分即频繁项集。2.3 实验 以上述数据集为例运行FP-growth程序的结果如下： 最后得到的所有频繁项集为 set(y), set(y, x), set(y, z), set(y, x, z), set(s), set(x, s), set(t), set(y, t), set(x, t), set(y, x, t), set(z, t), set(y, z, t), set(x, z, t), set(y, x, z, t), set(r), set(x), set(x, z), set(z)实验二使用同Apriori算法相同的蘑菇数据集和相同的支持度，FP算法的运行结果如下：3 总结 FP-growth算法是一种用于发现数据集中频繁模式的有效方法。由于只