FP-Growth (Frequent Pattern Growth)
Also known as: frequent pattern growth, FP-tree mining, FP-Growth algorithm, sık örüntü büyütme
FP-Growth, introduced by Jiawei Han, Jian Pei, and Yiwen Yin in 2000, mines frequent itemsets from transaction data without generating candidate sets, the costly step that slows the classic Apriori algorithm. It compresses the database into a frequent-pattern tree (FP-tree) in two scans, then grows frequent patterns recursively from that structure, making it dramatically faster than Apriori on large, dense datasets.
Key highlights
- No candidate generation — far faster than Apriori on large/dense data.
- Only two database scans, regardless of pattern length.
- The FP-tree compresses shared structure, saving memory and time on dense data.
- Scales to long frequent patterns that overwhelm candidate-based methods.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use FP-Growth to mine frequent itemsets (and, downstream, association rules) from transactional data — market-basket analysis, web-usage and clickstream mining, recommendation, and bioinformatics co-occurrence — especially on large or dense datasets where Apriori's candidate generation is too slow. It needs only two database scans and typically far outperforms Apriori. Its costs: the FP-tree must fit in memory (a limitation for very large or extremely sparse data, where the tree compresses poorly), the recursion can be intricate to implement, and like all support-based mining it is sensitive to the minimum-support threshold (too low explodes the output, too high misses patterns). ECLAT (vertical tidset intersection) is an alternative; for the rules themselves, pair with association-rule generation.
Strengths & limitations
- No candidate generation — far faster than Apriori on large/dense data.
- Only two database scans, regardless of pattern length.
- The FP-tree compresses shared structure, saving memory and time on dense data.
- Scales to long frequent patterns that overwhelm candidate-based methods.
- The FP-tree must fit in memory; very large datasets may not.
- On sparse data the tree compresses poorly, eroding the advantage.
- Recursive conditional-tree construction is comparatively complex to implement.
- Sensitive to the minimum-support threshold, like all frequent-itemset mining.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How is FP-Growth faster than Apriori?
Apriori repeatedly generates and tests candidate itemsets, scanning the database many times. FP-Growth avoids candidate generation entirely: it compresses the data into an FP-tree in two scans and mines patterns recursively from it. This removes the combinatorial candidate blow-up, giving large speedups on dense data.
What is the FP-tree?
A compressed prefix tree of the database's frequent items. Transactions sharing a prefix share a path, with node counts recording support, and a header table links each item's occurrences. It stores the dataset's frequent structure compactly so patterns can be read off without rescanning the data.
How does FP-Growth relate to ECLAT and association rules?
FP-Growth, ECLAT, and Apriori all find frequent itemsets; ECLAT uses a vertical tidset-intersection approach instead of a tree. Finding frequent itemsets is only the first stage — association rules (with confidence/lift) are generated from those itemsets in a separate step.
Sources
- 1.Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
- 2.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.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 2). FP-Growth. ScholarGate. https://scholargate.app/machine-learning/fp-growth