《Apriori算法和FP-growth算法.ppt》由会员分享，可在线阅读，更多相关《Apriori算法和FP-growth算法.ppt（36页珍藏版）》请在三一办公上搜索。
1、Apriori算法和FP-growth算法详解,by王晨曦,1.Apriori算法详解,1.1 关联分析 关联分析是一种在大规模数据集中寻找有趣关系的任务。频繁项集是经常出现在一块的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。频繁项集是指那些经常出现在一起的物品的集合，上表的集合葡萄酒，尿布，豆奶就是频繁项集的一个例子，从上面的数据集也可以找到诸如尿布葡萄酒的关联规则。,如何定义这些有趣的关系呢？谁来定义什么是有趣的？当寻找频繁项集时，频繁的定义是什么？有许多概念可以解答上述问题，不过其中最重要的是支持度和置信度。一个项集的支持度被定义为数据集中包含该项集的记录所占的比例。从表中可
2、以得到，在5条交易记录中有3条包含豆奶，尿布，因此豆奶，尿布的支持度是3/5。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。置信度或可信度是针对一条诸如尿布葡萄酒的关联规则定义的。这条规则的可信度被定义为“支持度(尿布，葡萄酒)/支持度(尿布)”。从表中可以看到，由于尿布，葡萄酒的支持度为3/5，尿布的支持度为4/5，所以“尿布葡萄酒”的可信度为3/4=0.75。这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适用。,1.2 Apriori原理,支持度和可信度是用来量化关联分析是否成功的方法。假设想找到支持度大于0.8的所有项集，应该如何去
3、做？一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，可是当物品成千上万时，上述做法非常非常慢。为了降低所需的计算时间，研究人员发现一种所谓的Apriori原理。Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。例如：项集豆奶,尿布是频繁的，那么豆奶、尿布也一定是频繁的，也就是说如果一个项集是非频繁项集，那么它的所有超集也是非频繁的。如已知项集橙汁是非频繁的，我们就知道莴苣，橙汁、牛奶，尿布，橙汁也是非频繁的。使用该原理可以避免项集数目的指数增长，从而在合理的时间内计算出频繁项集。,1.3 使用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,L2,C3,利用Apriori性质剪枝：频繁项集的所有子集必须是频繁的。存在候选项集，判断其子集是否频繁。1,2,3的2-项子集是1,2，1,3和2,3,它们都是L2的元素。因此保留1,2,3在C3中。1,2,5的2-项子集是1,2，1,5和2,5,它们都是L2的元素。因此保留1,2,5在C3中。1,3,5的2-项子集是1,3，1,5和3,5,3,5不是L2的元素，因而不是频繁的，由C3中 删除1,3,5。,2,3,4的2-项子
7、集是2,3，2,4和3,4,其中3,4不是L2的元素，因而不是频繁的，由C3中删除2,3,4。2,3,5的2-项子集是2,3，2,5和3,5,其中3,5不是L2的元素，因而不是频繁的，由C3中删除 2,3,5。2,4,5的2-项子集是2,4，2,5和4,5,其中4,5不是L2的元素，因而不是频繁的，由C3中删除2,4,5。这样，剪枝后C3=1,2,3，1,2,5。,（7）扫描D中事务，以确定L3，它由C3中具有,最小支持度的的候选3-项集组成。,C3,项集,由L2产生候选C3,1，2，3,1，2，5,C3,项集,支持度计数,扫描D,对每 个候选计数,1，2，3,2,1，2，5,2,（8）算法使
8、用L3L3 产生候选4-项集的集合C4。尽管连接产生结果 1,2,3,5,这个项集被剪去，因为它的子集2,3,5 不是频繁的。则C4=,因此算法终止，找出了所有的频繁项集。,L3,项集,支持度计数,比较候选支持度计数,1，2，3,2,与最小支持度计数,1，2，5,2,1.4 Apriori算法的伪代码,算法：Apriori。使用逐层迭代方法基于候选产生找出频繁项集。输入：D:实物数据库；Min_sup:最小支持度计数阈值。输出：L：D中的频繁项集。方法：L1=find_frequent_1-itemsets(D);for(k=2;Lk-1!=；k+)Ck=apriori_gen(Lk-1);F
9、or each 事务 tD/扫描D用于计数Ct=subset(Ck,t);/得到t的子集，它们是候选for each候选cC;C.count+;Lk=cC|c.count=min_stpreturn L=UkLk；,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
10、算法的缺点:第一:在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;第二:每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。,2.FP-growth算法详解,FP-growth算法是在2000年提出的频繁项集挖掘算法，前面我们介绍了Apriori挖掘频繁项集并且进行关联分析，这次的FP-growth和Apriori选择频繁集有点类似的地方，但是本质和Apriori完全不一样。FP-growth算法只需要对数据库进行两次扫描，
11、而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树中一个给定元素项的所有
12、元素。,第二遍扫描数据集用来构建FP树。在构建时，读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。在将每条事务加到树之前，需要对每个集合进行排序。排序基于元素项的绝对出现频率由高到低来进行，并过滤出不在L中的非频繁项。过滤及重排后的事务如下：,在对事务记录过滤和排序之后，就可以构建FP树了。从空集开始，将过滤和重排序后的频繁项集一次添加到树中。如果树中已存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分支。对前两条事务进行添加的过程：,依次将每个事务都加到FP树，最后构成的带头指针表(HeaderTable)的FP树如下图所示：,2.2 从
13、FP树中挖掘频繁项集,从FP树中抽取频繁项集的三个基本步骤如下：从FP树中获得条件模式基；利用条件模式基，构建一个条件FP树；迭代重复步骤1步骤2，直到树包含一个元素项为止。,第一步：从FP树中获得条件模式基,首先从头指针表中的每个频繁元素项开始，对每个元素项，获得其对应的条件模式基（conditional pattern base）。条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径（prefix path）。简而言之，一条前缀路径是介于所查找元素项与树根节点之间的所有内容。每一个频繁项的所有前缀路径（频繁模式基）为：,第二步：根据条件模式基构建条件FP树,对于每一个
14、频繁项，都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据，并通过相同的建树代码来构建这些树。例如对于为频繁项t构建一个条件模式树，然后对t,y,t,x重复该过程。元素t的条件模式树构建过程如下图所示：注意到元素项s以及r是条件模式基的一部分，但是它们并不属于条件FP树。,第三步：递归查找频繁项集,有了FP树和条件FP树，就可以在前两步的基础上递归得查找频繁项集。仍然以元素项t为例，下图为查找元素项t的频繁项集的步骤：图中红色的部分即频繁项集。,2.3 实验,以上述数据集为例运行FP-growth程序的结果如下：,最后得到的所有频繁项集为 set(y),set(y,x),set(
15、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 SecondsFP-growth算法的平均运行时间：,
