(数据挖掘)关联规则挖掘——Apriori算法、fp—Tree算法.ppt

关联规则挖掘;1、Apriori算法;Apriori的性质： ;Apriori的步骤： ;Apriori算法;Apriori算法实例;实例解答;支持度50;Apriori算法的不足;提高Apriori算法的方法;Hash-based itemset counting（散列项集计数）;Transaction reduction（事务压缩）;Partitioning（划分）;Sampling（采样）;2000年，Han等提出了一个称为FP-tree的算法。 FP-tree算法只进行2次数据库扫描。它不使用候选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。 FP-tree算法由两个主要步骤完成：①利用事务数据库中的数据构造FP-tree；②从FP-tree中挖掘频繁模式。 ;具体过程： 扫描数据库一次，得到频繁1-项集 把项按支持度递减排序 再一次扫描数据库，建立FP-tree;完备: 不会打破交易中的任何模式 包含了频繁模式挖掘所需的全部信息 紧密 去除不相关信息—不包含非频繁项 支持度降序排列: 支持度高的项在FP-tree中共享的机会???高 决不会比原数据库大（如果不计算树节点的额外开销);步骤2：频繁模式的挖掘; FP-tree算法的一个例子; 第一步、构造FP-tree; 重新调整事务数据库; 创建根结点和频繁项目表; 加入第一个事务(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; 第二步、FP-growth; 第二步、FP-growth; 第二步、FP-growth; 第二步、FP-growth;FP - tree 算法的优缺点; 谢谢大家！