机器学习实战 - 读书笔记(12) - 使用FP-growth算法来高效发现频繁项集

前言

最近在看Peter Harrington写的“机器学习实战”,这是我的学习心得,这次是第12章 - 使用FP-growth算法来高效发现频繁项集。

基本概念

  • FP-growth算法 FP-growth算法的性能很好,只需要扫描两次数据集,就能生成频繁项集。但不能用于发现关联规则。 我想应该可以使用Apriori算法发现关联规则。 FP代表频繁模式(Frequent Pattern)。
  • 条件模式基(conditional pattern base)。 条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径(prefix path)。 一条前缀路径是介于所查找元素项与树根节点之间的所有内容。

FP-growth算法 - 用途

  • 快速生成频繁项集
  • 在一批有共性的文章中找到经常出现的匹配词汇(共现词),并进一步发现关联规则。可以用于输入自动补全功能。
  • 发现数据中的共性。比如,可以找到,哪类用户喜欢哪些文章。

核心算法解释

FP-growth算法:生成频繁项集

FP-growth算法 - Step 1:生成FP树

  • 输入
    • 数据集[数据,出现次数] 注:出现次数默认为1。在第二步的时候,会再次用到这个方法,这是出现次数就用其用途了。
    • 最小支持度
  • 输出
    • FP树:FPTree

    FPTree的根节点为项名为null的节点。

    • 头指针表: headerTable
  • Tree Node 的数据结构
    • name : 项名
    • count : 其路径在数据集中出现的频率
    • nodeLink : 指向在FP树下一个同项名的项。
    • parent : 父节点
    • children : 子节点
  • Header Table Item 的数据结构
    • name : 项名
    • count : 在数据集中出现的频率
    • nodeLink : 指向在FP树第一个同项名的项。
  • 逻辑过程
    • 输入
      • sample 数据集

事务ID

事务中的项集

1

'a', 's', 'w', 'x'

2

'a', 'd', 's'

3

'a', 'w'

4

'a', 'x'

5

'a', 'd', 'w'

6

'a', 'e', 's'

    • 最小支持度为3
  • Step 1: 生成Header Table。
遍历数据集,获得每个元素项的出现频率
去掉不满足最小支持度的元素项。

结果如下:

元素项

出现频率

a

6

s

3

w

3

注: 项d,e,x被去掉了,由于它们的出现频率小于最小支持率3。

    • Step 2: 生成FP Tree。
遍历数据集,
    对当前项集,去掉不在Header Table中的项。
    对当前项集,按照在Header Table中出现频率从大到小排序。
    加入到FP Tree(), 并且对每项,更新Header Table Item或者Tree Node的NodeLink属性。

去掉不在Header Table中的项的结果:

事务ID

事务中的项集

过滤并排序后的项集

1

'a', 's', 'w', 'x'

'a', 's', 'w'

2

'a', 'd', 's'

'a', 's'

3

'a', 'w'

'a', 'w'

4

'a', 'x'

'a'

5

'a', 'd', 'w'

'a', 'w'

6

'a', 'e', 's'

'a'

把处理过的项集加入 FP Tree 的过程:

按照路径找,如果有count++,如果没有增加一个节点,count=1
对新增加的节点,连接到上一个同项集或者header Table的项集的NodeLinker上。

示意图如下:

最终的结果如下:(输出的FP树和头指针表)

FP-growth算法 - Step 2:生成频繁项集

  • 输入
    • FP树:PF Tree
    • 头指针表: header Table
    • 最小支持度
    • 前缀项集: 初始值为Empty List (输出)
    • 频繁项集List: 初始值为Empty List (输出)
  • 输出 无
  • 逻辑过程
对Header Table的项,按照count从小到大排序
对Header Table的每一元素项:
    把当前元素项加入到频繁项集List中。(Header Table中的每个项都是满足最小支持度的)
    前缀项集 = 前缀项集 + 当前元素项。
    找到已当前元素项的结尾的条件模式基(到根节点的所有路径以及路径的count)。
    将条件模式基看成一个数据集(每个数据有一个count数),用生成FP Tree的方法,生成新的FP Tree和Header Table。
    注:上一步过滤掉了不满足最小支持度的子项集。(比如:对于元素项w,过滤掉了{s,a})
    如果新的Header Table有数据:
        使用生成频繁项集的方法(也就是递归调用本方法)继续生成(有n+1个元素项的)频繁项集。
    • 每个元素项的条件模式基

元素项

条件模式基

a

{}:6

s

{a}:3

w

{s,a}:1, {a}:2

    • 元素项w的FP树和Header Table 注:元素项s和节点s实际上都不存在,因为不满足最小支持度。

参考

  • Machine Learning in Action by Peter Harrington

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1265. [NOIP2012] 同余方程

1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

3396
来自专栏数据结构与算法

P1789 【Mc生存】插火把

题目背景 初一党应该都知道...... 题目描述 话说有一天linyorson在Mc开了一个超平坦世界,他把这个世界看成一个n*n的方阵,现在他有m个火把和k个...

3525
来自专栏乐沙弥的世界

SQL, PL/SQL 之NUMBER数据类型

    NUMBER数据类型在Oracle中使用的较为广泛,可以存储零值,正负数,以及定长数,对于这个数据类型有个几个概念要搞清,否则容易搞混,下面给出具体描述...

842
来自专栏数据处理

proc-tabulate

1132
来自专栏tkokof 的技术,小趣及杂念

HGE系列之五 管中窥豹(基础类别)

继上次我们编写了那个小程序之后,想必大家对于HGE的认识都有了进一步的提高,那么现在,我想则是时候来一番“管中窥豹”,睹一睹HGE的源码实现了 :)而相应的源...

951
来自专栏tkokof 的技术,小趣及杂念

数学小记

结果为 2n + 1, 考虑到任一奇数都可以表示成这种形式,所以使用以下构造方法即可立即得到上述的b和c:

1223
来自专栏禹都一只猫博客

Python科学计算:在Numpy的边缘试探(入门学习)

2118
来自专栏数据结构与算法

agc027D - Modulo Matrix(构造 黑白染色)

构造一个$n * n$的矩阵,要求任意相邻的两个数$a,b$,使得$max(a,b) % min(a,b) \not = 0$

863
来自专栏有趣的Python

算法与数据结构(八) 图论:带权图&最小生成树

带权图 Weighted Graph ? 带权图 边上都有自己的权值的带权图。 ? 邻接矩阵 把原来的1/0变成权值。 邻接表的改造 ? 邻接表 邻接...

4456
来自专栏小樱的经验随笔

浅谈String模块ascii_letters和digits

本文介绍string模块ascii_letters和digits方法,其中ascii_letters是生成所有字母,从a-z和A-Z,digits是生成所有数字...

3997

扫码关注云+社区