本文已收录到:机器学习笔记 专题
- 机器学习的学习顺序、书籍和一些体会
- 朴素贝叶斯 – 根据男性特征分析女性是否嫁的问题
- 感知机 – 一种二分类线性分类模型,划分红豆和绿豆
- 逻辑斯谛回归 – 不那么生硬的划分红豆和绿豆
- 支持向量机:线性可分支持向量机与硬间隔最大化
- 支持向量机:线性可分支持向量机与软间隔最大化
- 利用集成方法提高基分类器分类性能
- 集成方法之Bagging装袋法:三个臭皮匠投票、少数服从多数
- 集成方法之Boosting提升方法:更像现实中实际学习的模型
- 决策树不仅可以做分类,还可以回归:回归树
- K-均值聚类算法,对无标签数据进行分组汇聚
- Apriori算法进行关联分析
- 使用FP-growth算法高效的挖掘海量数据中的频繁项集
- 维度是什么?数据降维方法,降维的用途
- 最广泛的降维算法:主成分分析(PCA)【原理讲解+代码】
- 人工神经网络(ANN)及BP算法原理
- 深度学习常用数据集、发展脉络和工具框架介绍
- 自编码器 – 经典的无监督学习神经网络、领会它的思想
- 卷积神经网络:卷积就是特征提取器,就是CBAPD
- 循环神经网络(RecurrentNN):有记忆的神经网络
为什么使用FP-growth?
FP是频繁模式的缩写。Apriori算法需要多次扫描数据,I/O是很大的瓶颈。为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。
FP树
什么是FP树?
FP(Frequent Pattern),即频繁模式的缩写。所以FP树又叫做频繁模式树。
FP-growth算法是一种将数据存储在FP树这种数据结构的算法,并可以直接从该数据结构中提取出频繁项集。
一棵FP树的结构如下图所示:
FP树的特点介绍:
- 空集作为跟结点。
- 每个结点由一个字母(这个字母是项名称):一个数字表示,数字表示项的频数。
- 一条路径(实线)表示的是一个事务,路径不同代表事物不同,所以一棵树中允许出现多个同名项。
- 如果事务完全一致,则路径可以重合。
- 相似项之间的链接(虚线)为节点链接(link),主要是用来快速发现相似项的位置。
为了快速访问树中的相同项,还需要维护一个连接相同项的节点的指针列表(headTable),每个列表元素(headTable的列)包括:数据项、该项的全局最小支持度、指向FP树中该项链表的表头的指针。
算法步骤
题目来源书P161页。
下表中的TID表示订单号,商品ID是商品的唯一标识。
题目告知我们最小支持度为2。
第一步:扫描每个商品项出现的次数。
对题目中每一项进行扫描,统计在所有订单中出现的总次数。
对于小于最小支持度的项(<2),去除。本题中没有小于最小支持度的项。
第二步:写出F-List;排序;重新构建表格
写出F-List:
排序:
次数多的排在前面。
因为有些项因为不满足最小支持度,会被删除掉。接下来还需要更新原始表格。
在本题中,没有项被删除,所以表格与原始表格相同,我们照抄下来。
铅笔是排序后的结果,根据每个项出现的频数降序排序。
eg:T100订单,I2的频数7>I1的频数6>I5的频数2。
第三步:画FP树
画出Head Table:
第一列式项名,第二类是出现的频数,第三类头结点。
… …以此类推
最后用虚线把相同的项连接起来:
现在FP树就构造完成了。
第四步:列出表格,从FP树中抽取频繁项集
频繁项集表一共有4列。分别是项、条件模式集、条件频数和频繁项集。
- 项:Head Table item列第一个不要,剩下的倒叙写。
- 条件模式基。
方法:以I5项为例,在FP树中找到I5项,I5出现了两次,所以是有两个路径的,顺着路径往上找,有多个路径的算多个条件模式基。最后倒着写。I2, I1:1后面的数字代表的意思是这条路径走了1次。 - 由条件模式基写条件FP:
方法:以I5项的条件模式基为例,第一个模式基I2出现了1次,I1出现1次;第二个模式基I2、I1、I3分别出现1次。共计I2出现2次,I1出现2次,I3出现1次。小于最小支持度的I3被舍丢弃。所以条件FP树为<I1:2, I1:2>。剩下的项以此类推… … - 频繁项集:
方法:由项和条件FP树组合得到频繁项集。
例如第一个项I5与条件FP树<I2:2, I1:2>,I5可与I2、I5与I1,I5与I2和I1组合;
I4只能与自己的频繁FP树<I2:2>组合得到{I4, I2:2};
I3可与I2、I3与I1、I3与I2和I1;
I1与I2;
编码实现
源代码:FP-growth算法
参考文献:
https://www.bilibili.com/video/BV1fX4y1A75f