【机器学习实战】第12章 使用FP-growth算法来高效发现频繁项集

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

前言

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

FP-growth 算法简介

  • 一种非常好的发现频繁项集算法。
  • 基于Apriori算法构建,但是数据结构不同,使用叫做 FP树 的数据结构结构来存储集合。下面我们会介绍这种数据结构。

FP-growth 算法步骤

  • 基于数据构建FP树
  • 从FP树种挖掘频繁项集

FP树 介绍

  • FP树的节点结构如下:
class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue     # 节点名称
        self.count = numOccur     # 节点出现次数
        self.nodeLink = None      # 不同项集的相同项通过nodeLink连接在一起
        # needs to be updated
        self.parent = parentNode  # 指向父节点
        self.children = {}        # 存储叶子节点

FP-growth 原理

基于数据构建FP树

步骤1:

  1. 遍历所有的数据集合,计算所有项的支持度。
  2. 丢弃非频繁的项。
  3. 基于 支持度 降序排序所有的项。 
  1. 所有数据集合按照得到的顺序重新整理。
  2. 重新整理完成后,丢弃每个集合末尾非频繁的项。 

步骤2: 6. 读取每个集合插入FP树中,同时用一个头部链表数据结构维护不同集合的相同项。

最终得到下面这样一棵FP树 

从FP树中挖掘出频繁项集

步骤3:

  1. 对头部链表进行降序排序
  2. 对头部链表节点从小到大遍历,得到条件模式基,同时获得一个频繁项集。 

如上图,从头部链表 t 节点开始遍历,t 节点加入到频繁项集。找到以 t 节点为结尾的路径如下: 

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

  1. 条件模式基继续构造条件 FP树, 得到频繁项集,和之前的频繁项组合起来,这是一个递归遍历头部链表生成FP树的过程,递归截止条件是生成的FP树的头部链表为空。 根据步骤 2 得到的条件模式基 [z,x,y,s,t]:2,[z,x,y,r,t]:1 作为数据集继续构造出一棵FP树,计算支持度,去除非频繁项,集合按照支持度降序排序,重复上面构造FP树的步骤。最后得到下面 t-条件FP树 : 

 然后根据 t-条件FP树 的头部链表进行遍历,从 y 开始。得到频繁项集 ty 。然后又得到 y 的条件模式基,构造出 ty的条件FP树,即 ty-条件FP树。继续遍历ty-条件FP树的头部链表,得到频繁项集 tyx,然后又得到频繁项集 tyxz. 然后得到构造tyxz-条件FP树的头部链表是空的,终止遍历。我们得到的频繁项集有 t->ty->tyz->tyzx,这只是一小部分。

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

FP-growth 算法优缺点:

* 优点: 1. 因为 FP-growth 算法只需要对数据集遍历两次,所以速度更快。
        2. FP树将集合按照支持度降序排序,不同路径如果有相同前缀路径共用存储空间,使得数据得到了压缩。
        3. 不需要生成候选集。
        4. 比Apriori更快。
* 缺点: 1. FP-Tree第二次遍历会存储很多中间过程的值,会占用很多内存。
        2. 构建FP-Tree是比较昂贵的。
* 适用数据类型:标称型数据(离散型数据)。

FP-growth 代码讲解

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

main 方法大致步骤:

if __name__ == "__main__":
    simpDat = loadSimpDat()                       #加载数据集。
    initSet = createInitSet(simpDat)              #对数据集进行整理,相同集合进行合并。
    myFPtree, myHeaderTab = createTree(initSet, 3)#创建FP树。
    freqItemList = []
    mineTree(myFPtree, myHeaderTab, 3, set([]), freqItemList) #递归的从FP树中挖掘出频繁项集。
    print freqItemList

大家看懂原理,再仔细跟踪一下代码。基本就没有问题了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python3

习题5:更多的变量和打印

字符串是非常好用的东西,所以在这个练习中你将学会如何创建包含变量内容的字符串,并使用专门的格式化(format string)和语法把变量的内容放到字符串里,相...

6120
来自专栏数据科学与人工智能

【Python环境】Python面试题汇总(一)

拿网络上关于Python的面试题汇总了,给出了自认为合理的答案,有些题目不错,可以从中学到点什么,答案如不妥,请指正...... +++++++++++++++...

36760
来自专栏布尔

阅读Ext 学习Javascript(一)Core/Ext.js

从Library的角度去看,Ext(喜欢中文的朋友可以到它的中文站看看)和Prototype JQuery YUI没有太大区别,但它有它的优点,完整的OO支持、...

22270
来自专栏用户2442861的专栏

《Effective Modern C++》读书笔记

Note:为避免各种侵权问题,本文并没有复制原书任意文字(代码除外,作者已经声明代码可以被使用)。需要原书完整中文翻译的读者请等待官方译本的发布。

69520
来自专栏信安之路

【作者投稿】奇葩webshell技巧

前段时间看XDCTF的一道web题,发现了一种很奇特的构造webshell的方法。

14200
来自专栏Java技术栈

10 道关于 Java 泛型的面试题

这是在各种Java泛型面试中,一开场你就会被问到的问题中的一个,主要集中在初级和中级面试中。那些拥有Java1.4或更早版本的开发背景的人都知道,在集合中存储对...

13220
来自专栏向治洪

Java 8新特性

编者注:Java 8已经公布有一段时间了,种种迹象表明Java 8是一个有重大改变的发行版。 在Java Code Geeks上已经有大量的关于Java 8 的...

39760
来自专栏Java Web

《编写高质量代码》学习笔记(2)

写着写着发现简书提醒我文章接近字数极限,建议我换一篇写了。 ---- 建议52:推荐使用String直接量赋值 一般对象都是通过new关键字生成的,但是Str...

37340
来自专栏好好学java的技术栈

一文看透java8新特性

毫无疑问,Java 8发行版是自Java 5(发行于2004,已经过了相当一段时间了)以来最具革命性的版本。Java 8 为Java语言、编译器、类库、开发工具...

13820
来自专栏黑泽君的专栏

java基础学习_IO流03_字符流、IO流小结、案例_day21总结

10220

扫码关注云+社区

领取腾讯云代金券