FP树、FPGrowth算法PPT课件

FP树FP Growth算法 1 FP Growth算法 AProiri算法需要产生大量候选项集 而且需要多次扫描数据库 然后通过模式匹配检查一个很大的候选集合 在挖掘长模式时 算法性能退化很快 Hna提出了一种频繁模式增长算法 FP Growth 不产生候选集而直接产生全部频繁项集 FP Growth算法采用了分而治之策略 首先 将提供频繁项集的数据库压缩成一棵频繁模式树 FP 该树仍保留项集关联信息 然后 将这种压缩后的数据库划分成一组条件数据库 每个数据库关联一个频繁项 并分别挖掘每个条件数据库 2 FP Growth算法 先举一个例子 数据库中有9个事务 即 D 9 如表1 1所示 事务中的项按字典次次序存放 表1 1有9个交易的数据库使用FP Growth算法挖掘频繁模式 3 FP树构造 首先扫描事务数据库一次 产生频繁项集 并得到它们的支持度计数 同时为了方便后期的查询 创建一个表头 使得每个表项通过一个节点链指向它在树中的出现 初始时为空 表头称为频繁项表头 频繁项的表头按支持度计数的递减顺序排序 频繁项的集记为L 即L I2 7 I1 6 I3 6 I4 2 I5 2 频繁项表头表项域信息item name域 记录了该节点所代表的项的名字 count support域 记录相应节点链中项的总的计数 即该项的支持度 node 1ink域 记录了指向Fp树中具与该表项相同item name域的第一个节点 4 FP树构造 然后 FP 树构造如下 1 创建树的根节点 用 null 标记 2 第二次扫描数据库 每个事务中的项按L中的次序处理 处理后的数据库见表1 2 并对每个事务创建一个分枝 若节点或分枝已经存在 则共享节点或分枝 同时将共享前缀上的每个结点的计数加1 为前缀之后的项创建结点和链接 若不存在 则以根结点为父结点将该事务中的项按L中的次序依次插入 扫描所有的事务之后得到的树如图1 1所示 表1 2处理后的数据库 5 此后 数据库频繁模式挖掘问题转化为挖掘FP 树问题 图1 1FP树FP树结点域信息item name域 记录了该节点所代表的项的名字count域 记录了从根到此节点的部分包含的项集的计数child link和parent link域 分别指向孩子和父节点node link域 指向下一个具有同样的item name域的节点 要是没有这样一个节点就为null 6 前缀路径集 后缀路径集 前缀子森林 以节点N为树根的子树T包含此节点和它所有的子女 定义1 2 项l1 l2 lk k 1 I1 I2 Ik 是子树T的前缀路径 若每个Ij 1 J k 1 出现在从根到子树的根节点N的路径中 T称为具有前缀 I1 I2 Ik 的一棵前缀子树 I1 I2 Ik 是其前缀 T或者N称为路径 I1 I2 Ik 的后缀项集或者后缀模式 定义1 2 具有相同前缀 I1 I2 Ik 的所有前缀子树表示为PSF I1 I2 Ik 作具有前缀 I1 I2 Ik 的一个前缀子森林 7 FP 树挖掘 过程如下 由长度为1的频繁模式开始 构造它的条件模式基 由FP 树中与后缀模式一起出现的前缀路径集组成 代表此频繁模式的投影库 然后构造它的条件FP 树 并递归地在该树上进行挖掘 模式增长通过后缀模式与由条件FP 树产生的频繁模式连接实现 FP 树的挖掘是至底向上进行的 总结在表2 1中 I5是L中的最后一个项 首先考虑I5 图1 2与I5相关的条件FP树 图1 2与I5相关的条件FP树 8 表2 1通过创建条件模式基挖掘FP树的结果 9 FP树结构的优点 完整性保留了频繁模式挖掘的完整信息不会破坏任何一个事务的长模式紧致性减少非相关信息 非频繁项被丢弃1项集按频率降序排列不会比原始数据库大 10 FP Growth算法的优点 分治策略 根据当前已获得的频繁模式分解挖掘任务和DB搜索更小的数据库其它因素无需产生候选 从而测试候选项压缩的数据库 FP tree结构无需重复扫描整个数据库基本操作 统计局部频繁项 建立子FP tree 无需模式搜索和匹配 11 FP Growth算法评估 FP Growth算法开辟了有效挖掘频繁模式的新途径 然而 它的时间和空间效率还不足够高 仍需进一步改进 FP Growth算法的主要问题是 1 在挖掘频繁模式时 它需要递归地生成条件FP 树 并且每产生一个频繁模式就要生成一个条件FP 树 2 在支持度阀值较小时 即使对于很小的数据库 也将产生数以十万计的频繁模式 动态的生成和释放数以十万计的条件FP 树 将耗费大量时间和空间 3 此外 FP 树和条件FP 树需要自顶向下生成 而频繁模式的挖掘需要自底向上处理 由于递归地生成条件FP 树 因此FP 树和条件FP 树必须双向可遍历 这样 FP 树和条件FP 树的节点中就需要更多的指针 从而需要更大的内存空间来维护FP 树和条件FP 树 12 FP 树的改进 法一 引入哈希表 提高查询频繁项表的时间 其中哈希函数f key 中的key为项的支持度计数 表项域信息减少item name 频繁项表头表项域信息 13 算法改进 对于FP树的挖掘选择置顶向下的顺序 在原FP树基础上进行搜索与挖掘 这样就不需要生成条件FP树 由于不需要遍历结点的父结点 故树的结点中不需要parent link域 在时间和空间上面可以优化算法我们以例1 1进行说明 14 算法改进 对项I5 我们得到长度为1的项集 I5 由于在FP 树中的项都是频繁的 在以后的讨论中将忽略频繁一项集 对项I4 建PSF I4 因为项I5在相对于项I4下的支持计数为0 故 I4 I5 是非频繁的 对项I3 建PSF I3 项I4 I5在相对于项I3下的计数为0 故I4 I5与I3的组合都是非频繁的 不需要再考虑 对项I1 建PSF I1 项I3 I4 I5在相对于项I1下的计数分别是4 1 2 故 I1 I3 I1 I5 是频繁模式 由于项集 I1 I4 是非频繁的 故没有必要进一步挖掘 建PSF I1 I3 由于在 I1 I3 下项I5的支持计数是1 小于最小支持度阀值 不需要继续挖掘 对项I2 建PSF I2 项I2相对于项I1 I3 I4 I5