FP-Growth (频繁模式增长)
- 提出者
- Jiawei Han, Jian Pei & Yiwen Yin
- 年份
- 2000
- 类型
- Frequent-itemset mining algorithm
- 类别
- Pattern mining
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
FP-Growth 由 Jiawei Han、Jian Pei 和 Yiwen Yin 于 2000 年提出,它在不生成候选集的情况下从事务数据中挖掘频繁项集,而生成候选集是拖慢经典 Apriori 算法的耗时步骤。它通过两次扫描将数据库压缩成频繁模式树(FP-tree),然后从该结构中递归地增长频繁模式,这使得它在大型、密集型数据集上的速度远超 Apriori。
方法背后的直觉
Apriori 通过反复生成和测试候选组合来查找频繁项集——这是一个昂贵且扫描密集的过程,在密集数据上会导致爆炸性增长。FP-Growth 采取了不同的路线:它将整个事务数据库压缩到一个紧凑的树中,共享的前缀只存储一次,因此公共模式会重叠和压缩。然后,它不生成候选集,而是通过沿着通向每个项的路径直接从树中读取频繁模式,并递归地挖掘更小的“条件”树。两次遍历数据和一种巧妙的数据结构取代了 Apriori 的多次遍历和组合候选集爆炸。
历史学
Han、Pei 和 Yin 在 2000 年的 SIGMOD 会议上提出了 FP-Growth,作为 Apriori 的一种无候选集生成的替代方案,并在他们 2004 年的《数据挖掘与知识发现》文章中进行了扩展阐述。频繁模式树的思想——将事务压缩成共享前缀结构并递归挖掘——成为模式挖掘中的一项基础技术,与 Apriori(基于候选集)和 ECLAT(垂直格式)并列。它仍然是数据挖掘库中一种标准的、高性能的项集挖掘器。
何时使用
使用 FP-Growth 从事务数据中挖掘频繁项集(以及下游的关联规则)——市场篮子分析、Web 使用和点击流挖掘、推荐系统以及生物信息学共现——尤其是在 Apriori 的候选集生成太慢的大型或密集型数据集上。它只需要两次数据库扫描,通常性能远超 Apriori。其成本:FP-tree 必须能放入内存(对于非常大或极其稀疏的数据,树压缩效果差,这是一个限制),递归实现可能很复杂,并且像所有基于支持度的挖掘一样,它对最小支持度阈值敏感(太低会导致输出爆炸,太高会错过模式)。ECLAT(垂直项集交集)是一个替代方案;对于规则本身,请结合关联规则生成。
局限与注意事项
- FP-tree 必须能放入内存;非常大的数据集可能无法满足。
- 在稀疏数据上,树的压缩效果差,会削弱优势。
- 递归条件树构建实现起来相对复杂。
- 对最小支持度阈值敏感,如同所有频繁项集挖掘。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 无候选集生成——在大型/密集型数据上比 Apriori 快得多。
- 仅两次数据库扫描,与模式长度无关。
- FP-tree 压缩共享结构,在密集数据上节省内存和时间。
- 可扩展到压倒候选集方法的长频繁模式。
应用
- 市场篮子分析和零售关联挖掘。
- Web 使用和点击流模式挖掘。
- 通过频繁共现项进行推荐。
- 生物信息学共现和基序发现。
- 任何 Apriori 太慢的大规模频繁项集任务。
使用方式
使用方式
第一次数据库扫描计算每个项的支持度,并丢弃低于最小支持度阈值的项。剩余的频繁项按降序频率排序——这种排序允许事务共享树前缀并保持 FP-tree 的紧凑性。
公式
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}第二次扫描将每个事务(按排序顺序的频繁项)插入 FP-tree,增加共享前缀路径上的计数,并在需要时添加新分支。头部表链接每个项的所有出现,因此树紧凑地表示了整个数据集的频繁结构。
公式
\text{second scan: insert each transaction's frequent items into the FP-tree}对于每个频繁项(按频率从低到高处理),算法收集其条件模式基——树中与该项共现的前缀路径集,每条路径都按其计数加权。这捕获了该项频繁出现的上下文。
公式
\text{for each item: collect its conditional pattern base (prefix paths)}从每个条件模式基构建一个更小的条件 FP-tree 并递归挖掘,通过将项附加到在其条件树中找到的模式上来增长更长的频繁项集。递归在单路径树处达到基线,其项集组合直接枚举——产生所有频繁项集,无需候选集生成。
公式
\text{build conditional FP-trees recursively to grow frequent patterns}常见陷阱
- 设置的最小支持度过低,导致项集爆炸。
- 假设它总是优于 Apriori——在小型或稀疏数据上,收益很小。
- 忘记频繁项集不是规则;规则生成是单独的步骤。
- 在 FP-tree 无法装入 RAM 时,忽略内存限制。
常见问题
FP-Growth 比 Apriori 快的原因是什么?
Apriori 反复生成和测试候选项集,多次扫描数据库。FP-Growth 完全避免了候选集生成:它在两次扫描中将数据压缩成 FP-tree,并从中递归地挖掘模式。这消除了组合候选集爆炸,在大密度数据上实现了巨大的速度提升。
什么是 FP-tree?
数据库频繁项的压缩前缀树。共享前缀的事务共享一条路径,节点计数记录支持度,头部表链接每个项的出现。它紧凑地存储数据集的频繁结构,以便无需重新扫描数据即可读取模式。
FP-Growth 与 ECLAT 和关联规则的关系是什么?
FP-Growth、ECLAT 和 Apriori 都用于查找频繁项集;ECLAT 使用垂直项集交集方法而不是树。查找频繁项集只是第一阶段——关联规则(带有置信度/提升度)是从这些项集中在单独的步骤中生成的。
相关方法
参考文献
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
打开 DOI 文献已复制。Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.
打开 DOI 文献已复制。