FP-Growth Algorithm
Source: Unit 4 §9
Apriori pays for its candidates: it generates them, then scans the database again to test them. FP-Growth never generates a candidate at all.
Why FP-Growth?
| Apriori | FP-Growth | |
|---|---|---|
| Approach | Generate-and-test with candidates | No candidate generation |
| Cost | candidate generation is expensive; multiple DB scans (I/O); subset checking | compresses the DB into a tree; only 2 passes |
| Data structure | hash tree | FP-tree (compressed) |
FP-Growth uses a compressed representation (the FP-tree) and a recursive divide-and-conquer approach.
- Build the FP-tree - 2 passes over the data.
- Extract frequent itemsets directly from the FP-tree by traversal.
Step 1: building the FP-tree
- Pass 1: count item frequencies, then order the items by descending frequency. That ordering is the header table.
- Pass 2: for each transaction, sort its items into the header order, insert it down the tree incrementing the counts of any shared prefix nodes, and maintain node-link pointers between nodes of the same item (the dotted lists).
The more the paths overlap, the higher the compression, and putting the most frequent items nearest the root is what maximises overlap. A well compressed FP-tree may fit in memory, which is what removes the repeated database scans. Node-link (chain) pointers then let you find all the paths containing a given item quickly.
Worked example
10 transactions. Pass 1 gives the header table, in descending frequency:
| Item | Count |
|---|---|
| B | 8 |
| A | 7 |
| C | 7 |
| D | 5 |
| E | 3 |
Each transaction is re-sorted into the order B, A, C, D, E before it is inserted. The ten transactions after reordering:
Inserting the first two of them shows the mechanic:
Carrying on for all ten gives the full FP-tree, with its node-link pointers:
The slides draw only the first two insertions and then say "continue for all 10 transactions". The tree above was built from the notes' own reordered transaction list, and it checks out against their numbers twice over: the per-item node counts sum to B:8, A:7, C:7, D:5, E:3, exactly the header table, and the conditional pattern base for suffix E recounts to A:2, C:2, D:2 with B at 1 and therefore dropped, exactly as the notes state.
Step 2: mining via conditional FP-trees
Mine bottom-up from the least frequent item, using it as the suffix. For each suffix, build a conditional FP-tree: the tree of itemsets ending in that suffix.
- Find all paths containing the focus item - this is the conditional pattern base.
- Re-count item frequencies along those paths and build a new header. The item order can change, and items below min support are dropped.
- Re-insert the paths in the new order, truncating the suffix.
- Base of the recursion: when the tree is a single path, output all of its subsets plus the suffix.
- Take the paths ending in E and recount them:
A:2, C:2, D:2, while B has support 1, which is below minsup 2, so B is dropped. - Recurse on suffix DE - a base case - giving FI: DE, ADE.
- Recurse on suffix CE, giving FI: CE.
- Recurse on suffix AE, giving FI: AE.
Each conditional FP-tree gets its own header, recounted from its own pattern base. Items can change order, and items that were frequent globally can fall below minsup locally and be dropped - B does exactly this under suffix E.
Final frequent itemsets
All of these were found without generating a single candidate.
Recompute it and you get more than three itemsets. D's conditional pattern base
is the five prefixes {B,C}, {A,C}, {A}, {B,A,C}, {B,A}, in which
A appears 4 times, B 3 times and C 3 times - all at or above the minimum
support of 2. So AD (4), BD (3) and ABD (2) are frequent too, alongside
the CD, BCD and ACD the slides list. The list above is reproduced as the
notes have it; if a question asks you to derive the suffix-D itemsets yourself,
derive all six.