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 条评论
登录 后参与评论

相关文章

来自专栏余林丰

MyBatis之级联——鉴别器

鉴别器(discriminator)是MyBatis为我们提供的第三个级联也是最后一个。基于之前两篇级联中的场景,现增加学生们去体检,但男女体检项目不一样,我们...

2367
来自专栏斑斓

使用Python Pandas处理亿级数据

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,Hado...

5544
来自专栏我是攻城师

如何使用neo4j存储树形无限级菜单

3836
来自专栏PPV课数据科学社区

【学习】在Python中利用Pandas库处理大数据的简单介绍

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,...

3447
来自专栏吉浦迅科技

DAY58:阅读Launch Bounds

As discussed in detail in Multiprocessor Level, the fewer registers a kernel use...

401
来自专栏owent

2018年的新通用伪随机数算法(xoshiro / xoroshiro)的C++(head only)实现

前段时间看到说Lua 5.4用了一种新的通用随机数算法,替换掉本来内部使用的CRT的随机数引擎。我看了一下大致的实现,CPU和空间复杂度任然保持了一个较低的水平...

502
来自专栏深度学习入门与实践

【原】Learning Spark (Python版) 学习笔记(四)----Spark Sreaming与MLlib机器学习

本来这篇是准备5.15更的,但是上周一直在忙签证和工作的事,没时间就推迟了,现在终于有时间来写写Learning Spark最后一部分内容了。   第10-1...

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

Day3晚笔记

DEV C++扩展栈空间 ? -Wl,--stack=64000000000 带权二分图匹配 建一个超级源点S,超级汇点T 把左边的点的点权作为权值,连一条S到...

2904
来自专栏数据之美

Hive 中的 LEFT SEMI JOIN 与 JOIN ON 的前世今生

hive 的 join 类型有好几种,其实都是把 MR 中的几种方式都封装实现了,其中 join on、left semi join 算是里边具有代表性,且使...

2368
来自专栏智能算法

挖掘关联规则之Apriori算法

1. Apriori算法的目的: 主要是用来挖掘关联规则,即从一个事务数据集中发现频繁项集并推出关联规则,其名字是因为算法基于先验知识(prior knowle...

2626

扫码关注云+社区