FP-Growth 算法

定义

FP-Growth(Frequent Pattern Growth)由韩家炜(Jiawei Han)等人于 2000 年提出,是针对 Apriori 算法反复扫描数据库、候选集爆炸两大缺陷设计的频繁项集挖掘算法。

原理

算法只需扫描数据库两次:第一次统计各项的支持度并按频率排序;第二次将每条交易按序插入一棵称为 FP-tree 的前缀树,公共前缀共享节点,从而把整个数据库压缩进紧凑的内存结构,并以项头表串联相同项的节点。挖掘阶段对每个项自底向上抽取其条件模式基,递归构造条件 FP-tree,通过"模式增长"直接产出频繁项集,全程不生成候选集。

优缺点

在稠密数据上通常比 Apriori 快一个数量级以上;但 FP-tree 可能占用大量内存,且递归实现较复杂。

应用

Spark MLlib 提供其并行实现(PFP),广泛用于大规模购物篮分析与日志模式挖掘。