- Year not given
FP-Growth and Apriori disadvantage
Short answer
FP-growth builds an FP-tree from two database scans, then recursively mines conditional FP-trees without candidate generation. Overcomes Apriori by: no candidate generation, only two scans, counts stored in tree, compresses data via shared prefixes, divide-and-conquer for long patterns. Much faster, especially at low support.
Define FP-Growth algorithm for frequent item set generation. Explain how FP growth approach overcomes the disadvantage of Apriori algorithm.
FP-growth (Frequent Pattern growth, Han, Pei and Yin) finds frequent itemsets without candidate generation. It compresses the database into a compact prefix tree, the FP-tree, and then mines the tree recursively by a divide-and-conquer pattern-growth method.
Algorithm
- Scan 1: find the support count of each item; delete infrequent items; sort the frequent items in descending order of count (the F-list).
- Build the FP-tree: scan 2: for each transaction, sort its frequent items by the F-list order and insert it as a path from the root. Shared prefixes share nodes (count is increased); a header table links all nodes of the same item (node-links).
- Mine the tree, for each item from the least frequent upward:
- take its conditional pattern base (prefix paths leading to the item, with the item's counts);
- build a conditional FP-tree from it (drop items below min_sup);
- recursively mine it, appending the item as the suffix.
- Union of all patterns is the set of frequent itemsets.
How it overcomes the disadvantages of Apriori
| Apriori problem | FP-growth solution |
|---|---|
| Generates huge numbers of candidate itemsets | No candidate generation; patterns grow from frequent items in the tree |
| Scans the database many times (k scans) | Only two scans of the database |
| Counts candidates against every transaction | Counts are kept in the tree; mining works on the compact tree in memory |
| Large memory/time with dense data or low support | The tree compresses the data (shared prefixes), so mining is much faster |
| Level-wise search for long patterns is costly | Divide-and-conquer decomposes the problem into smaller conditional databases |
Experiments show FP-growth is about an order of magnitude faster than Apriori for low min_sup.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- FP-Growth advantages and disadvantages · Data Mining, chapter 4
- FP-tree on HotDogs data · Data Mining, chapter 4
- FP-tree on t1-t5 data · Data Mining, chapter 4
- Apriori on 8 transactions, 25% support · Data Mining, chapter 4
- Apriori on HotDogs data with rules · Data Mining, chapter 4
- Association analysis and Apriori pruning · Data Mining, chapter 4 · asked 2×
- Advantages and disadvantages of DTMF set · Telecommunications, chapter 1
- Variational approach for one-dimensional heat conduction · Finite Element Method, chapter 5
- Importance of growth function; Theta, O, Omega · Data Structure and Algorithm, chapter 9
- Fit y = a b^x (growth data) · Numerical Method, chapter 4