专栏首页编程Python基础原理:FP-growth算法的构建

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基础原理:FP-growth算法的构建

    和Apriori算法相比,FP-growth算法只需要对数据库进行两次遍历,从而高效发现频繁项集。对于搜索引擎公司而言,他们需要通过查看互联网上的用词,来找出经...

    企鹅号小编
  • java 用httpclient访问https时经常返回403的原因

    纠结了一天的问题终于落下了帷幕!先听一首歌吧 今天使用了一些httpclient包进行https网页数据的访问,但是一直返回403的问题,一开始以为网站做了限制...

    企鹅号小编
  • 都知道网站404 可你知道为啥是404吗?

    每当浏览网页出现“404错误”时,我们都知道这表示该网页出现了访问错误,也就是页面丢失。其实,这早已是人尽皆知的常识。作为一种标准的HTTP返回代码,404被用...

    企鹅号小编
  • Python基础原理:FP-growth算法的构建

    和Apriori算法相比,FP-growth算法只需要对数据库进行两次遍历,从而高效发现频繁项集。对于搜索引擎公司而言,他们需要通过查看互联网上的用词,来找出经...

    企鹅号小编
  • Python爬虫之豆瓣音乐及糗事百科

    專 欄 ❈ 罗罗攀,Python中文社区专栏作者 专栏地址: http://www.jianshu.com/u/9104ebf5e177 ❈ 一、豆瓣音乐t...

    Python中文社区
  • Linux debug问题

    命令行解决方法:go build -tags nopkcs11 LiteIDE解决办法:编译环境-》自定义-》BUILDARGS:-i -tags nopkc...

    用户2187945
  • 深度学习的JavaScript基础:从callbacks到sync/await

    这篇文章就谈一谈JavaScript中的异步编程。文章参考了网上的一些资料,主要示例代码来自Async JavaScript: From Callbacks, ...

    云水木石
  • 快讯 | 137亿美元买下全食超市,亚马逊又增一处AI练兵场

    作者 | 胡永波 近日,媒体盛传亚马逊要花90亿美元收购商业聊天应用Slack,没想到能让亚马逊下重手却是生鲜超市——全食(Whole Foods),以137亿...

    AI科技大本营
  • Promise, Generator, async/await的渐进理解

         作为前端开发者的伙伴们,肯定对Promise,Generator,async/await非常熟悉不过了。Promise绝对是烂记于心,而async/a...

    sam dragon
  • gcc的-fstack-protector

    /lib/i386-linux-gnu/libc.so.6(gsignal+0x4f) [0xb2b751df]

    随心助手

扫码关注云+社区

领取腾讯云代金券