文档章节

数据挖掘算法之关联规则挖掘(二)FPGrowth算法

Dragon_
 Dragon_
发布于 2015/04/24 15:20
字数 866
阅读 167
收藏 0

之前介绍的apriori算法中因为存在许多的缺陷,例如进行大量的全表扫描和计算量巨大的自然连接,所以现在几乎已经不再使用

在mahout的算法库中使用的是PFP算法,该算法是FPGrowth算法的分布式运行方式,其内部的算法结构和FPGrowth算法相差并不是十分巨大

所以这里首先介绍在单机内存中运行的FPGrowth算法


还是使用apriori算法的购物车数据作为例子,如下图所示:


TID为购物车项的编号,i1-i5为商品的编号

FPGrowth算法的基本思想是,首先扫描整个购物车数据表,计算每个商品的支持度,并从大到小从上往下排序,得到如下表所示


从底部最小支持度开始,逐一构建FP树

构建过程如下图:


最终构建出的FP树如下图


将这个FP树和支持度表关联起来如下图:

支持度表中的每一项都有一个存放指向FP树中对应节点的指针,例如第一行指向i2:7;第二行指向i1:4,因为i1节点还出现在FP树中的其他位置,所谓i1:4节点中还存放着指向i1:2节点的指针

通过少数的全表扫描构建好的FP树将购物车没有规律的数据变成了一个有迹可循的树形结构,并且省去了进行巨大的自然连接的运算



通过FP树挖掘出关联规则:

通过上图的FP树,我们可以根据每个商品得到该商品对应的条件模式基,条件FP树和产生的频繁模式

例如i5

在FP树中可以看到,从根节点到i5:1的路径有两条:

i2:7-->i1:4-->i5:1

i2:7-->i14-->i3:2-->i5:1

i2:7-->i1:4和i2:7-->i14-->i3:2就是i5的条件模式基,因为最终到达的节点肯定是i5,所以将i5省略

记为{i2,i1:1}{i2,i1,i3:1},为什么每个条件模式基的计数为1呢?虽然i2和i1的计数都很大,但是由于i5的计数为1,最终到达i5的重复次数也只能为1。所以条件模式基的计数是根据路径中节点的最小计数来决定的

根据条件模式基,我们可以得到该商品的条件FP树,例如i5:


根据条件FP树,我们可以进行全排列组合,得到挖掘出来的频繁模式(这里要将商品本身,如i5也算进去,每个商品挖掘出来的频繁模式必然包括这商品本身)

根据FP树得到的全表如下:


至此,FPGrowth算法输出的结果就是产生的频繁模式,FPGrowth算法使用的是分而治之的方式,将一颗可能十分巨大的树形结构通过构构建条件FP子树的方式分别处理

但是在商品数据十分巨大的情况下,FPGrowth算法所构建的FP树可能会大到计算机内存都无法加载,这时就要使用分布式的FPGrowth,PFP算法来进行计算

本文参考书:《数据挖掘概念与技术》

本文转载自:http://blog.csdn.net/qq1010885678/article/details/45244829

Dragon_
粉丝 1
博文 16
码字总数 0
作品 0
闵行
程序员
私信 提问
Spark数据挖掘-FPGrowth算法

Spark数据挖掘-FPGrowth算法 主要内容 什么是关联规则挖掘? 关联规则有哪些术语? 什么是FP-Growth算法? 1.1 FPGrowth算法 1.1.1 基本概念 关联规则挖掘的一个典型例子是购物篮分析。关联规...

clebeg
2015/11/03
695
0
推荐系统(一):频繁模式挖掘的FPGrowth实现

算法说明:FPGrowth算法是用来做购物车分析,说白了就是分析下什么商品和什么商品会被一同购买,还有一同购买的频次是多少,经常被一同购买的商品就可以放到一起做推荐了。 频繁模式挖掘关键...

阿拉德大陆的魔法师
2016/04/08
339
0
【spark】41.Spark Mlib:FPGrowth算法

简介 FP-Growth算法是韩嘉炜等人在2000年提出的关联分析算法,它采取如下分治策略:将提供频繁项集的数据库压缩到一棵频繁模式树(FP-tree),但仍保留项集关联信息。 在算法中使用了一种称为...

Areya
02/21
26
0
Spark MLlib 机器学习算法与源码解析(网络课程—第一期)

《Spark MLlib 机器学习算法与源码解析》 spark是一个开源集群运算框架,最初是由加州大学柏克利分校AMPLab所开发。Spark使用了内存内运算技术,在内存上的运算速度比Hadoop MapReduce的运算...

sunbow0
2016/05/11
0
0
【数据挖掘】关联规则和Apriori算法

一.数据挖掘概念 1.1什么是数据挖掘? 数据挖掘就是从海量的数据源中,如数据库、文本、图片、万维网、视频等资源中寻找有用的模式,这些模式是有用的、有潜在价值的、可以被理解的。 1.2从数...

yaopan007
2015/11/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Experts say the weaker pound is drawing investors to the UK tech sector

UK tech companies secured a record £5.5bn in foreign investment in the first seven months of this year, research shows. This was more than the amount invested per capita in th......

wowloop
13分钟前
3
0
Add support for Android 9-patch images in BorderImage

The 9-patch image implementation in Qt Quick Controls 1 is an internal implementation detail of the Android style. It cannot handle .9.png image files out of the box, but takes ......

shzwork
17分钟前
4
0
c/c++日期时间处理函数小结

日期时间处理函数: 日期时间转为字符串 strftime/std::put_time 字符串解析成日期时间 strptime/std::get_time 时间结构转换:time_t->tm localtime:time_t->tm 时间结构转换:tm->time_t ...

chuqq
22分钟前
4
0
Apache Flink 进阶入门(二):Time 深度解析

前言 Flink 的 API 大体上可以划分为三个层次:处于最底层的 ProcessFunction、中间一层的 DataStream API 和最上层的 SQL/Table API,这三层中的每一层都非常依赖于时间属性。时间属性是流处...

大涛学长
23分钟前
3
0
创龙基于Xilinx Artix-7系列FPGA处理器

SOM-TLA7是一款由广州创龙基于Xilinx Artix-7系列FPGA自主研发的核心板,可配套广州创龙Artix-7开发板使用。核心板尺寸仅70mm*50mm,采用沉金无铅工艺的10层板设计,专业的PCB Layout保证信号...

Tronlong创龙
29分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部