FP-Growth

FP-GrowthFP-tree汇报人：crstyal-yang12背景意义Apriori算法在产生频繁模式完全集前需要对数据库进行多次扫描，同时产生大量的候选频繁集，这就使Apriori算法时间和空间复杂度较大。且Apriori算法在挖掘长频繁模式的时候性能往往低下。JiaweiHan提出了FP-Growth算法。3关联规则的基本概念•支持度：P(AUB)，即A和B这两个项集在事务集D中同时出现的概率．•置信度：P(BIA)，即在出现项集A的事务集D中，项集B也同时出现的概率．•性质：频繁项集的所有子集必须是频繁的•FP-Tree：将事务数据表中的各个事务数据项按照支持度排序后，把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中，同时在每个结点处记录该结点出现的支持度。•条件模式基：包含FP-Tree中与后缀模式一起出现的前缀路径的集合•条件树：将条件模式基按照FP-Tree的构造原则形成的一个新的FP-TreeFP-Growth算法4步骤•FP-tree构建•递归挖掘FP-tree(FP-Growth)5FP-Growh：递归的挖掘每个条件FP-tree，累加后缀频繁项集，直到找到FP-tree为空或者FP-tree只有一条路径（只有一条路径情况下，所有路径上item的组合都是频繁项集）6事务数据库TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I37第一步、构造FP-tree•扫描事务数据库得到频繁1-项集F•定义min_sup=2，即最小支持度为2•重新排列FI1I2I3I4I567622I2I1I3I4I5766228重新调整事务数据库TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3I27I16I36I42I529创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull10加入第一个事务(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:111加入第二个事务(I2,I4)Item-nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1I4:112加入第三个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:113加入第四个事务(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:114加入第五个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:115加入第六个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:116加入第七个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:217加入第八个事务(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:118加入第九个事务(I2,I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:219第二步、FP-growth•首先考虑I5，得到条件模式基：(I2,I1:1)、I2,I1,I3:1•构造条件FP-tree•得到I5频繁项集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}Item-nameNode-headI2I1NullI2:2I1:2I3:120第二步、FP-growth•接着考虑I4，得到条件模式基：(I2,I1:1)、I2:1•构造条件FP-tree•得到I4频繁项集：{{I2,I4:2}}Item-nameNode-headI2NullI2:2I1:121第二步、FP-growth•然后考虑I3，得到条件模式基：(I2,I1:2)、I2:2、I1:2•构造条件FP-tree•由于此树不是单分支路径，因此需要递归挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:222第二步、FP-growth•递归考虑I3，此时得到I1条件模式基(I2:2),即I1,I3的条件模式基为(I2:2)•构造条件FP-tree•得到I3的频繁项目集{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}}Item-nameNode-headI2NullI2:223第二步、FP-growth•最后考虑I1，得到条件模式基：(I2:4)•构造条件FP-tree•得到I1的频繁项目集：{{I2,I1:4}Item-nameNode-headI2NullI2:4频繁项目表按item降序排序原因•共用前缀，不排序会造成不能共用前缀•频繁的item会在树的上层，可以被更多的共享；升序排序会造成那些频繁出现的item出现在树的分支中，不能更多的共用前缀24与Apriori算法最大的不同•第一，不产生候选集，•第二，只需要两次遍历数据库，大大提高了效率。25算法效率•依赖于数据集•适用于公共项大的数据集•如果没有公共项，那么效率不会提高。因为构建FP-tree还需要其他开销26Thanks！27