关联规则算法.ppt

一种基于Hadoop的并行关联规则算法 关联规则的动机 动机: 从数据中发现规律 什么产品被一起购买? — 啤酒和尿布?! 客户在购买了计算机之后还会购买什么产品? 哪种病菌的DNA对一种新开发的药物非常敏感? 对web文档进行分类 对于 A ? C： support = support({A 、C}) = 50% confidence = support({A 、C})/support({A}) = 66.6% Apriori算法 连接: 用 Lk-1自连接得到Ck 修剪: 一个k-项集，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。 伪代码: Ck: Candidate itemset of size k Lk : frequent itemset of size k C1＝｛all Candidate itemset of size from Database} 　　　　L1={candidates in C1 with min_support} for (k = 1; Lk !=?; k++) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return ?k Lk; 用 FP-tree挖掘频繁项集 韩家炜等人于2000年提出一种富有创新性的方法FP-growth,这种算法采用了一种分而治之的策略。 基本思想 ：分而治之 用FP-tree递归增长频繁集 方法 ： 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree 对每个新生成的条件FP-tree，重复这个步骤 直到结果FP-tree为空, 或只含唯一的一个路径 (此路径的每个子路径对应的都是频繁集) FP-tree算法的一个例子 第一步、构造FP-tree 扫描事务数据库得到频繁1-项目集F 定义minsup=20%，即最小支持度为2 重新排列F，把项按支持度递减排序： 重新调整事务数据库 创建根结点和频繁项目表 加入第一个事务(I2,I1,I5) 加入第二个事务(I2,I4) 加入第三个事务(I2,I3) 加入第四个事务(I2,I1,I4) 加入第五个事务(I1,I3) 加入第六个事务(I2,I3) 加入第七个事务(I1,I3) 加入第八个事务(I2,I1,I3,I5) 加入第九个事务(I2,I1,I3) 第二步、FP-growth 首先考虑I5，得到条件模式基 (I2,I1:1)、I2,I1,I3:1 构造条件FP-tree 得到I5频繁项集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}} 第二步、FP-growth 接着考虑I4，得到条件模式基 (I2,I1:1)、I2:1 构造条件FP-tree 得到I4频繁项集：{{I2,I4:2}} 第二步、FP-growth 然后考虑I3，得到条件模式基 (I2,I1:2)、I2:2、 I1:2 构造条件FP-tree 由于此树不是单一路径，因此需要递归挖掘I3 第二步、FP-growth 递归考虑I3，此时得到I1条件模式基 (I2:2),即I1I3的条件模式基为(I2:2) 构造条件FP-tree 得到I3的频繁项目集{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}} 第二步、FP-growth 最后考虑I1，得到条件模式基 (I2:4) 构造条件FP-tree 得到I1的频繁项目集{{I2,I1:4} 存在的问题 Apriori算法和FP-tree算法是基于单节点的算法。但是,现在的数据库越来越大,达到了TB级甚至更大，采用传统的算法将非常缓慢，甚至不能服务于有时限性的问题。 为此，研究人员提出了多种并行挖掘算法，主要有CD、DD、CaD等。CD算法是Apriori的并行实现，其基本思想是将数据平均分配到N个计算节点上，在每个节点是采用类似Apriori的算法。 这些并行算法解决了挖掘效率的问题，但是由于并行计算是由很多计算节点组成，节点失效、负载不易均衡带来的问题仍然会给计算带来很多障碍。 存在的问题 例如，CD算法有两个严重缺陷: 1) 某个