第12章 使用FP-growth算法来高效发现频繁项集

    在 第11章 时我们已经介绍了用 算法发现 频繁项集 与 。
    本章将继续关注发现 频繁项集 这一任务，并使用 算法更有效的挖掘 频繁项集。

    FP-growth 算法简介

    • 一种非常好的发现频繁项集算法。
    • 基于数据构建FP树
    • 从FP树种挖掘频繁项集

    FP树 介绍

    • FP树的节点结构如下:

    基于数据构建FP树

    步骤1:

    1. 遍历所有的数据集合，计算所有项的支持度。
    2. 丢弃非频繁的项。
    3. 基于 支持度 降序排序所有的项。
    4. 所有数据集合按照得到的顺序重新整理。
    1. 读取每个集合插入FP树中，同时用一个头部链表数据结构维护不同集合的相同项。
      第12章 使用FP-growth算法来高效发现频繁项集 - 图4
      最终得到下面这样一棵FP树

    从FP树中挖掘出频繁项集

    步骤3:

    1. 对头部链表进行降序排序

    2. 对头部链表节点从小到大遍历，得到条件模式基，同时获得一个频繁项集。
      第12章 使用FP-growth算法来高效发现频繁项集 - 图6
      如上图，从头部链表 t 节点开始遍历，t 节点加入到频繁项集。找到以 t 节点为结尾的路径如下:

      去掉FP树中的t节点，得到条件模式基<左边路径,左边是值>[z,x,y,s,t]:2，[z,x,y,r,t]:1 。条件模式基的值取决于末尾节点 t ，因为 t 的出现次数最小，一个频繁项集的支持度由支持度最小的项决定。所以 t 节点的条件模式基的值可以理解为对于以 t 节点为末尾的前缀路径出现次数。

    • 条件模式基:头部链表中的某一点的前缀路径组合就是条件模式基，条件模式基的值取决于末尾节点的值。
    • 条件FP树:以条件模式基为数据集构造的FP树叫做条件FP树。

    FP-growth 算法优缺点:

    FP-growth 代码讲解

    完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/12.FrequentPattemTree/fpGrowth.py

    main 方法大致步骤:

    • 作者：
    • 版权声明：欢迎转载学习 => 请标注信息来源于 ApacheCN