Apriori算法和FP-growth算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Apriori,算法和,FP-growth,算法详解,by,王晨曦,1.Apriori算法详解,1.1,关联分析,关联分析,是一种在大规模数据集中寻找有趣关系的任务。,频繁项集,是经常出现在一块的物品的集合，,关联规则,暗示两种物品之间可能存在很强的关系。,频繁项集是指那些经常出现在一起的物品的集合，上表的集合,葡萄酒，尿布，豆奶,就是频繁项集的一个例子，从上面的数据集也可以找到诸如尿布,葡萄酒的关联规则。,交易号码,商品,0,豆奶，莴苣,1,莴苣，尿布，葡萄酒，甜菜,2,豆奶，尿布，葡萄酒，橙汁,3,莴苣，豆奶，尿布，葡萄酒,4,莴苣，豆奶，尿布，橙汁,如何定义这些有趣的关系呢？谁来定义什么是有趣的？当寻找频繁项集时，频繁的定义是什么？有许多概念可以解答上述问题，不过其中最重要的是支持度和置信度。,一个项集的,支持度,被定义为数据集中包含该项集的记录所占的比例。从表中可以得到，在,5,条交易记录中有,3,条包含,豆奶，尿布,，因此,豆奶，尿布,的支持度是,3/5,。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。,置信度,或,可信度,是针对一条诸如,尿布,葡萄酒,的关联规则定义的。这条规则的可信度被定义为,“,支持度,(,尿布，葡萄酒,) /,支持度,(,尿布,)”,。从表中可以看到，由于,尿布，葡萄酒,的支持度为,3/5,，尿布的支持度为,4/5,，所以,“,尿布,葡萄酒,”,的可信度为,3/4=0.75,。这意味着对于包含,“,尿布,”,的所有记录，我们的规则对其中,75%,的记录都适用。,1.2 Apriori,原理,支持度和可信度是用来量化关联分析是否成功的方法。假设想找到支持度大于,0.8,的所有项集，应该如何去做？一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，可是当物品成千上万时，上述做法非常非常慢。为了降低所需的计算时间，研究人员发现一种所谓的,Apriori,原理。,Apriori,原理,是说,如果某个项集是频繁的，那么它的所有子集也是频繁的,。例如：项集,豆奶,尿布,是频繁的，那么,豆奶,、,尿布,也一定是频繁的，也就是说,如果一个项集是非频繁项集，那么它的所有超集也是非频繁的,。如已知项集,橙汁,是非频繁的，我们就知道,莴苣，橙汁,、,牛奶，尿布，橙汁,也是非频繁的。使用该原理可以避免项集数目的指数增长，从而在合理的时间内计算出频繁项集。,1.3,使用,Apriori,算法发现频繁项集实例,TID,项,目,【,例,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-,项集,的集合,C,1,的成员。算法简单地扫描所有的事务，对每个项的出现次数计数。,C,1,项集,支持度计数,1,6,扫描,D,对每 个候选计数,2,7,3,6,4,2,5,2,（,2,）,设最小支持计数为,2,，可以确定,1,-,频集,的集合,L,1,。它由具有最小支持度的,候选,1,-,项集,组成。,L,1,项集,支持度计数,1,6,比较候选支持度计数,2,7,与最小支持度计数,3,6,4,2,5,2,（,3,）,为发现,繁,-,频集,的集合,L,2,，算法,使用,L,1,L,1,产生,候选,2-,项集,集合,C,2,。,C,2,项集,1,，,2,1,，,3,1,，,4,1,，,5,由,L,1,产生候选,C,2,2,，,3,2,，,4,2,，,5,3,，,4,3,，,5,4,，,5,（,4,）,扫描,D,中事务，计算,C,2,中每个候选项,集的支持计数。,C,2,项集,支持度计数,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-,频集,的集合,L,2,，它由具,有最小支持度的,C,2,中的,候选,2-,项集,组成。,L,2,项集,支持度计数,1,，,2,4,1,，,3,4,比较候选支持度计数,与最小支持度计数,1,，,5,2,2,，,3,4,2,，,4,2,2,，,5,2,（,6,）,候选,3-,项集,的集合,C,3,的产生如下：,连接：,C,3,=,L,2,L,2,项集,1,2,3,1,2,5,1,3,5,2,3,4,2,3,5,2,4,5,项集,1,2,1,3,1,5,2,3,2,4,2,5,L,2,C,3,利用,Apriori,性质剪枝：,频繁项集的所有子集必须是频繁的。,存在候选项集， 判断其子集是否频繁。,1,2,3,的,2-,项子集,是,1,2,，,1,3,和,2,3,它们都是,L,2,的元素。因此保留,1,2,3,在,C,3,中。,1,2,5,的,2-,项子集,是,1,2,，,1,5,和,2,5,它们都是,L,2,的元素。因此保留,1,2,5,在,C,3,中。,1,3,5,的,2-,项子集,是,1,3,，,1,5,和,3,5, 3,5,不是,L,2,的元素，因而不是频繁的，由,C,3,中 删除,1,3,5,。,2,3,4,的,2-,项子集,是,2,3,，,2,4,和,3,4,其中,3,4,不是,L,2,的元素，因而不是频繁的， 由,C,3,中删除,2,3,4,。,2,3,5,的,2-,项子集,是,2,3,，,2,5,和,3,5,其中,3,5,不是,L,2,的元素，因而不是频繁的， 由,C,3,中删除,2,3,5,。,2,4,5,的,2-,项子集,是,2,4,，,2,5,和,4,5,其中,4,5,不是,L,2,的元素，因而不是频繁的， 由,C,3,中删除,2,4,5,。,这样，剪枝后,C,3,=,1,2,3,，,1,2,5,。,（,7,）,扫描,D,中事务，,以确定,L,3,，它由,C,3,中具有,最小支持度的的,候选,3-,项集,组成。,C3,项集,由,L,2,产生候选,C,3,1,，,2,，,3,1,，,2,，,5,C3,项集,支持度计数,扫描,D,对每 个候选计数,1,，,2,，,3,2,1,，,2,，,5,2,（,8,）,算法使用,L,3,L,3,产生,候选,4-,项集,的集合,C,4,。尽管连接产生结果,1,2,3,5,这个项集被剪去，因为它的子集,2,3,5,不是频繁的。则,C,4,=,因此算法终止， 找出了所有的频繁项集。,L,3,项集,支持度计数,比较候选支持度计数,1,，,2,，,3,2,与最小支持度计数,1,，,2,，,5,2,1.4 Apriori,算法的伪代码,算法：,Apriori,。使用逐层迭代方法基于候选产生找出频繁项集。,输入：,D:,实物数据库；,M,in_sup:,最小支持度计数阈值。,输出：,L,：,D,中的频繁项集。,方法：,L,1,=find_frequent_1-itemsets(D);,f,or(k=2;L,k-1,!=,；,k+),C,k,=apriori_gen(L,k-1,);,For each,事务,t,D/,扫描,D,用于计数,Ct=subset(Ck,t);/,得到,t,的子集，它们是候选,for each,候选,cC,;,C,.count,+;,L,k,=cC|c.count=min_stp,return L=U,k,L,k,；,1.5 实验一,# 加载数据集,def loadDataSet():,return 1, 3, 4, 2, 3, 5, 1, 2, 3, 5, 2, 5,1.5,实验二,使用UCI蘑菇数据集进行实验,for item in L1:,if item.intersection(2): print item,输出：,frozenset(2, 85),1.6,Apriori,算法的缺点,从以上的算法执行过程可以看到,Apriori,算法的缺点,:,第一,:,在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素,;,第二,:,每次计算项集的支持度时，都对数据库,D,中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的,I/O,开销。而这种代价是随着数据库的记录的增加,呈现出几何级数的增加。,2. FP-growth,算法详解,FP-growth,算法是在2000年提出的频繁项集挖掘算法，前面我们介绍了Apriori挖掘频繁项集并且进行关联分析，这次的,FP-growth,和Apriori选择频繁集有点类似的地方，但是本质和Apriori完全不一样。,FP-growth,算法只需要,对数据库进行两次扫描,，而,Apriori,算法对每个潜在的频 繁项集都会扫描数据集判定给定模式是否频繁，因此,FP-growth,算法的速度要比,Apriori,算法快。,FP-growth,算法发现频繁项集的基本过程如下：,构建,FP,树,从,FP,树中挖掘频繁项集,2.1 构建FP树,为构建,FP,树，需要对原始数据集扫描两遍。,第一遍对所有元素项的出现次数进行计数，统计各个元素项的出现频率，去掉不满足最小支持度的元素项。,L= s: 3, r: 3, t: 3, y: 3, x: 4, z: 5,FP-growth算法还需要一个称为,头指针表,来指定给定元素项的第一个树节点并,记录各个元素项的出现次数。这样每个元素项都构成一条单链表，可以快速访问,FP,树中一个给定元素项的所有元素。,事务ID,事务中的元素项,001,r, z, h, j, p,002,z, y, x, w, v, u, t, s,003,z,004,r, x, n, o, s,005,y, r, x, z, q, t, p,006,y, z, x, e, q, s, t, m,第二遍扫描数据集用来构建,FP,树。在构建时，读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。在将每条事务加到树之前，需要对每个集合进行排序。排序基于元素项的绝对出现频率由高到低来进行，并过滤出不在,L,中的非频繁项。,过滤及重排后的事务如下：,事务ID,事务中的元素项,过及重排序后的事务,001,r, z, h, j, p,z,r,002,z, y, x, w, v, u, t, s,z,x,y,s,t,003,z,z,004,r, x, n, o, s,x,s,r,005,y, r, x, z, q, t, p,z,x,y,r,t,006,y, z, x, e, q, s, t, m,z,x,y,s,t,在对事务记录过滤和排序之后，就可以构建FP树了。从空集开始，将过滤和重排序后的频繁项集一次添加到树中。如果树中已存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分支。对前两条事务进行添加的过程：,依次将每个事务都加到,FP,树，最后构成的带头指针表,(HeaderTable),的,FP,树如下图所示：,2.2 从FP树中挖掘频繁项集,从FP树中抽取频繁项集的三个基本步骤如下：,从FP树中获得,条件模式基,；,利用条件模式基，构建一个条件FP树；,迭代重复步骤1步骤2，直到树包含一个元素项为止。,第一步：从FP树中获得,条件模式基,首先从头指针表中的每个频繁元素项开始，对每个元素项，获得其对应的,条件模式基,（conditional pattern base）。条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径（prefix path）。简而言之，一条前缀路径是介于所查找元素项与树根节点之间的所有内容。,每一个频繁项的所有前缀路径（频繁模式基）为：,频繁项,前缀路径,z,: 5,r,x, s: 1, z, x, y: 1, z: 1,x,z: 3, : 1,y,z, x: 3,s,z, x, y: 2, x: 1,t,z, x, y, s: 2, z, x, y, r: 1,第二步：根据条件模式基构建条件FP树,对于每一个频繁项，都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据，并通过相同的建树代码来构建这些树。例如对于为频繁项,t,构建一个条件模式树，然后对,t,y,t,x,重复该过程。元素,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算法是一种用于发现数据集中频繁模式的有效方法。由于只对数据集扫描两次，因此FP-growth算法执行更快。在FP-growth算法中，数据集存储在一个称为FP树的结构中。FP树构建完成后，可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。该过程不断以更多元素作为条件重复进行，直到FP树只包含一个元素为止。,二者运行时间的比较,对于,8124,条数据,:,Apriori,算法的平均运行时间：,Running time: 0.65245983013 Seconds,FP-growth,算法的平均运行时间：,