Python基础原理:FP-growth算法的构建

和Apriori算法相比,FP-growth算法只需要对数据库进行两次遍历,从而高效发现频繁项集。对于搜索引擎公司而言,他们需要通过查看互联网上的用词,来找出经常在一块出现的词。因此就需要能够高效的发现频繁项集的方法,FP-growth算法就可以完成此重任。

FP-growth算法是基于Apriori原理的,通过将数据集存储在FP(Frequent Pattern)树上发现频繁项集。

FP-growth算法只需要对数据库进行两次扫描,而Apriori算法在求每个潜在的频繁项集时都需要扫描一次数据集,所以说FP-growth算法是高效的。

FP算法发现频繁项集的过程是:

(1)构建FP树;

(2)从FP树中挖掘频繁项集

FP表示的是频繁模式,其通过链接来连接相似元素,被连起来的元素可看成是一个链表

将事务数据表中的各个事务对应的数据项,按照支持度排序后,把每个事务中的数据项按降序依次插入到一棵以 NULL为根节点的树中,同时在每个结点处记录该结点出现的支持度。

假设存在的一个事务数据样例为,构建FP树的步骤如下:

结合Apriori算法中最小支持度的阈值,在此将最小支持度定义为3,结合上表中的数据,那些不满足最小支持度要求的将不会出现在最后的FP树中。

据此构建FP树,并采用一个头指针表来指向给定类型的第一个实例,快速访问FP树中的所有元素,构建的带头指针的FP树如图:

结合绘制的带头指针表的FP树,对表中数据进行过滤,排序如下:

在对数据项过滤排序了之后,就可以构建FP树了,从NULL开始,向其中不断添加过滤排序后的频繁项集。过程可表示为:

这样,FP树对应的数据结构就建好了,现在就可以构建FP树了,FP树的构建函数参见Python源代码。

在运行上例之前还需要一个真正的数据集,结合之前的数据自定义数据集。这样就构建了FP树,接下来就是使用它来进行频繁项集的挖掘。

本文来自企鹅号 - 中科院计算所职业学校媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

python中的时间处理大总结

北京 上海巡回站 | NVIDIA DLI深度学习培训 2018年1月26/1月12日 ? NVIDIA 深度学习学院 带你快速进入火热的DL领域 正文共485...

18410
来自专栏飞雪无情的博客

编写高效的Android代码

毫无疑问,基于Android平台的设备一定是嵌入式设备。现代的手持设备不仅仅是一部电话那么简单,它还是一个小型的手持电脑,但是,即使是最快的最高端的手持设备也远...

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

【Python环境】如何使用正确的姿势进行高效Python函数式编程?

关于函数式编程 有哪些函数式语言? 其实函数是语言很早就出现了,上世纪30年代出现的Lambda和50年代的LISP,比面向过程和对象的语言出现的更早,现代的C...

19910
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(五)No.55

Hello哈,又好久没聊大数据相关的东西了,是不是又忘记了吖?这次聊聊B-树的升级版,B+树。前面的内容小伙伴可以回顾一下。 大数据计数原理1+0=1这你都不...

1839
来自专栏cmazxiaoma的架构师之路

一个Java小白的面试之旅总结

1673
来自专栏大数据和云计算技术

索引技术简介

2.索引技术 索引是关系型数据库里的重要概念。总的来说,索引就是拿空间换时间。数据库技术和大数据技术会有一个融合的过程,除了前面讲到的B数索引、Hash索引等,...

4228
来自专栏机器学习算法与Python学习

机器学习(31)之频繁集挖掘FP Tree详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 明早7:22推送第2期免费送书活动 ...

3636
来自专栏猿人谷

[你必须知道的.NET] 第四回:后来居上:class和struct

本文将介绍以下内容: • 面向对象基本概念 • 类和结构体简介 • 引用类型和值类型区别 1. 引言 提起class和struct,我们首先的感觉是语法几乎相...

18210
来自专栏后端之路

单元测试JMockit使用

背景 由于目前dubbo等外部依赖越来越多 现在小伙伴关于测试经常跑不通 比如 ? 之前也提供了stub方案,但是目前使用的人几乎没有junit测试之第三方组件...

2385
来自专栏人工智能LeadAI

python中的时间处理大总结

python中处理时间的模块有三个,datetime, time,calendar,融汇贯通三个模块,才能随心所欲地用python处理时间。本文就是为此而写,文...

3645

扫码关注云+社区