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

相关文章

来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2830
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

8498
来自专栏魂祭心

原 canvas绘制clock

5074
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4214
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

5218
来自专栏杨龙飞前端

scrollto 到指定位置

2934
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5747
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.4K7
来自专栏c#开发者

为什么nhibernate 不能保存on-to-many的结构

下面是主类文件 Code namespace EasyTalk.Module {     /// <summary>     /// SiteAddre...

2565
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2742

扫码关注云+社区