分析FP-Growth机制

同步更新公众号：海涛技术漫谈

高频项挖掘主要用于发现相关物品。其中最著名的是电商企业通过收集并分析客户的购买记录,识别出常被一起采购的商品,并以提供个性化建议的方式进行推荐。

本文主要阐述了频繁项挖掘技术的演进过程,经历了从暴力求解到Apriori算法的发展阶段.接着,本文通过一个具体案例对FP-Growth的工作原理进行了深入分析.随后介绍了并行化处理的具体方法,并详细描述了如何利用三次map-reduce实现这一功能.最终通过对 spark mlib 包中 PFP-Growth 核心实现代码的深入分析与研究,在一定程度上加深了对该算法的理解.

假设我们的Transaction数据库包含5条交易数据。如表所示，在表中列出了abcde五个商品。假设设定参数minSupport为0.4，则表示该参数要求至少共同出现两次。

id	购买的商品
1	a b d
2	b c d
3	a b e
4	a b c
5	b c d

表1：交易数据

一：频繁项挖掘的技术演进

1.1 暴力求解

在这一部分中：

1. 每个SKU都有一个唯一的条目。
2. 通过暴力枚举所有可能性来计算所有的商品组合数。
3. 遍历整个交易数据库并统计每组的购买频率。
4. 检查其是否达到预设的支持阈值level。