FP-Growth Algorithm in Data Mining

Finding every frequent itemset in a transaction database — the same underlying task covered in the lesson on market basket analysis — gets computationally expensive fast with the Apriori algorithm's approach, because Apriori has to repeatedly rescan the entire database and generate a large number of candidate itemsets at every step, most of which turn out not to be frequent at all. FP-Growth (Frequent Pattern Growth), introduced by Han, Pei, and Yin, solves the same problem with a fundamentally different strategy: compress the database into a compact tree structure once, then mine frequent patterns directly out of that tree without ever generating a single candidate itemset.

The FP-Tree: A Compressed Representation of the Whole Database

An FP-tree represents every transaction as a path from a root node, with transactions that share a common prefix of items sharing the same path through the tree — which is exactly what makes the structure compact. Each node tracks an item name and a count of how many transactions passed through it, and a separate header table lists every frequent item along with a link connecting all the tree nodes representing that same item, which is what lets the mining step efficiently find every occurrence of a given item without re-scanning the whole tree.

Building an FP-Tree, Fully Worked

Rather than describe the construction steps abstractly, working through one small database end to end makes every step concrete. Take six transactions over four items, with a minimum support count of 3 (out of 6 transactions):

T1: A, B, D
T2: B, C, D
T3: A, B, C, D
T4: B, C
T5: A, B, C, D
T6: A, C

Step 1 — count and prune. Counting each item across all transactions: A=4, B=5, C=5, D=4. All four meet the minimum support of 3 (in a database also containing an item that appeared only once, that item would simply be dropped entirely at this step — FP-Growth never builds tree nodes for infrequent items in the first place).

Step 2 — fix a global item order by descending frequency (ties broken alphabetically here): B(5), C(5), A(4), D(4). Every transaction gets its items reordered to match this sequence before insertion — this consistent ordering is exactly what maximizes prefix sharing between transactions.

Step 3 — insert each reordered transaction, incrementing shared node counts:

T1 -> [B, A, D]
T2 -> [B, C, D]
T3 -> [B, C, A, D]
T4 -> [B, C]
T5 -> [B, C, A, D]
T6 -> [C, A]

Building the tree transaction by transaction produces:

root
├── B:5
│    ├── A:1
│    │    └── D:1
│    └── C:4
│         ├── D:1
│         └── A:2
│              └── D:2
└── C:1
     └── A:1

It's worth verifying this tree is actually correct before trusting it: summing every node labeled with a given item should reproduce the original global counts. B: one node, 5 — matches. C: 4 + 1 = 5 — matches. A: 1 + 2 + 1 = 4 — matches. D: 1 + 1 + 2 = 4 — matches. Every check confirms the tree faithfully represents all six transactions in a fraction of the space six separate lists would take, because T3 and T5 — identical transactions — collapse onto exactly the same path.

Mining the Tree: Working Out Every Itemset Containing D

Mining proceeds from the least frequent items upward, so D (tied for least frequent) is a natural place to start. D appears in the tree three times, and each occurrence contributes a conditional pattern base entry — the path leading to it, weighted by D's count at that specific node:

D:1 at root->B->A->D  ->  pattern base entry {B, A} : 1
D:1 at root->B->C->D  ->  pattern base entry {B, C} : 1
D:2 at root->B->C->A->D -> pattern base entry {B, C, A} : 2

Summing each item's weighted count across these entries: B = 1+1+2 = 4, C = 1+2 = 3, A = 1+2 = 3. All three clear the minimum support of 3, so all three survive into D's conditional FP-tree — a smaller tree built purely from these weighted prefix paths, exactly the same way the main tree was built, just restricted to transactions that contained D.

The support of each itemset combining D with these items falls directly out of that conditional structure, without any further database scanning:

{B, D}:    support 4   (frequent)
{C, D}:    support 3   (frequent)
{A, D}:    support 3   (frequent)
{B, C, D}: support 3   (frequent)
{A, B, D}: support 3   (frequent)
{A, C, D}: support 2   (NOT frequent — falls below the threshold of 3)

That last line matters as much as the frequent ones: A and C never co-occur with D outside of the single path that also includes B (contributing count 2), so {A, C, D} is correctly excluded — the algorithm doesn't need to construct this itemset and then check it against the database, its support is simply never reachable in the conditional tree in the first place. Repeating this exact process — build a conditional pattern base, build a conditional tree, read off the supports — for A, C, and finally B (each working only with the items that precede it in the frequency order) is what completes the full frequent-itemset enumeration for the whole database.

Why This Beats Rescanning the Database Repeatedly

The entire mining process above — for every itemset involving D — required zero additional passes over the original six transactions. Everything came from the tree built during the two scans required to construct it (one scan to count item frequencies, one scan to insert the reordered transactions). Apriori, by contrast, has to rescan the full transaction database once for every itemset size it checks — a much heavier cost as the database grows. This is FP-Growth's central advantage, and it comes with real trade-offs worth stating plainly: the tree itself is more complex to construct and reason about than Apriori's straightforward candidate lists, and its actual size depends heavily on the data. In the best case, transactions share long common prefixes and the tree stays compact — even collapsing toward a single dominant branch, as T3 and T5 did above. In the worst case, transactions share almost nothing, the tree grows a separate branch for nearly every transaction, and it can end up occupying more memory than the raw data it was meant to compress.

Key Advantages

• Only two database scans are required, regardless of how many itemset sizes are ultimately mined.
• No candidate itemsets are generated or tested — patterns are read directly out of the tree structure.
• The compact FP-tree representation scales well to large transaction databases when the data has meaningful shared structure across transactions.