Definition
FP-Growth (frequent-pattern growth) finds every itemset that appears in at least transactions. It reads the database twice to build an FP-tree, a prefix tree in which baskets that start with the same items share nodes, and then mines that tree recursively. For each item it builds a smaller conditional tree of what co-occurs with it. It never generates candidate itemsets and counts them, which is the step that makes Apriori slow.
At a glance
- Task
- Unsupervised frequent-itemset mining (the first half of association-rule learning)
- Input → output
- a list of transactions (sets of items) and a minimum support → every itemset with , plus its count
- Learns
- nothing parametric: it builds a compressed index of the data (the FP-tree) and lists patterns from it
- Training cost
- 2 database scans, , to build the tree; mining costs roughly the number of frequent itemsets times the size of the conditional trees
- Prediction cost
- none by itself; rules derived from the itemsets are applied by lookup,
- Hyperparameters
- min support (the big one), optional max itemset length; min confidence / lift come later, when rules are generated
- Assumes
- binary presence/absence of items (quantities ignored), and an FP-tree small enough to fit in memory
The problem
Frequent-itemset mining asks which groups of items keep showing up together, for example bread and butter or eggs and milk. With distinct items there are possible itemsets, so nobody enumerates them all. Apriori (see the Apriori article for support, confidence, lift and rule generation) prunes the search with the rule that every subset of a frequent itemset is frequent. It still works generate and test though: at level it builds every candidate -itemset whose subsets are all frequent, then scans the whole database to count them.
That costs two things. Scans: Apriori reads the database once per level, so a frequent 10-itemset needs about 10 passes. Candidates: with frequent single items, level 2 alone has about candidate pairs, and each one has to be stored and counted. Han, Pei and Yin (2000) asked whether the itemsets could be found without generating candidates at all. Their answer was to compress the database into a tree once, then grow patterns from it, with each step working on a smaller and smaller projected database.
The idea
Step 1: compress. Count every item and throw away the infrequent ones, since by downward closure no frequent itemset can contain them. Rewrite each basket as its frequent items sorted from most to least frequent, then insert these sorted lists into a prefix tree (a trie). Baskets that start the same way share a path, and each node stores how many baskets passed through it. Because popular items come first, they sit near the root and get shared most often.
Step 2: divide and conquer. Split the itemsets by their least frequent item. To find every frequent itemset that ends in butter, you only need the baskets that contain butter, and of those only the part above butter in the sorted order. In the tree that part is the path from each butter node up to the root. Collect those paths (the conditional pattern base), build a small FP-tree from them, and repeat. Each recursive call fixes one more item (the suffix) and works on a strictly smaller tree.
Vocabulary
- Transaction / basket
- one set of items , e.g. one shopping receipt; the database is a list of them
- Itemset
- any set of items ; a -itemset has items
- Support
- , the number (or fraction) of transactions containing all of
- Frequent itemset
- one with , the minimum support
- F-list
- the frequent single items sorted by descending support; it fixes the order of items along every path of the tree
- FP-tree
- a prefix tree with a null root; each node holds an item, a count, a parent pointer and a link to the next node with the same item
- Header table
- one row per frequent item: its support and the head of its node-link chain
- Node-link
- the chain through every tree node that carries the same item, so all occurrences of an item can be visited without searching the tree
- Prefix path
- the items on the path from the root down to (but not including) a node, weighted by that node's count
- Conditional pattern base
- the multiset of prefix paths of all nodes of item , a small database of everything that co-occurs with
- Conditional FP-tree
- the FP-tree built from a conditional pattern base, after dropping items that are infrequent within it
- Suffix (pattern)
- the items fixed so far in the recursion; every itemset emitted at that level ends with them
The math
- the database, a list of transactions (each a set of items)
- the set of all distinct items
- an itemset
- the minimum support, as a count (min_support × |D| when given as a fraction)
- the output: all frequent itemsets
Downward closure. If then every transaction containing also contains , so . An item with support below therefore belongs to no frequent itemset and can be deleted from every transaction before anything else happens. That deletion is scan 1.
- the F-list order: more frequent items come first
- the frequent single items
- the sorted frequent part of transaction t, which is inserted as one root-to-node path
What a node count means. Inserting adds 1 to every node along it, so a node whose root path is has count = the number of transactions whose sorted frequent part starts with . Each transaction contains an item at most once, so it passes through exactly one -node. Summing the counts along 's node-link therefore gives its support:
- all tree nodes labelled , reached through the header table's node-link chain
- number of transactions whose sorted path passes through node n
The pattern-growth lemma. Take a set of items that all come before in the order. A transaction contains exactly when its path goes through some -node and lies on the path above . Items before can only appear above in the path, never below it. Group the transactions by the -node they pass through and add up:
- the items on the path from the root down to 's parent
- the conditional pattern base of : each as a transaction with weight
- weighted support of inside that small database
This identity is the whole algorithm. Mining every frequent itemset whose least frequent item is is the same as mining with the same threshold and attaching to every result. is again a list of weighted transactions, so we build an FP-tree from it and recurse. Each itemset has exactly one least frequent item, so processing the header items from the bottom up finds every frequent itemset exactly once, with no duplicates and no candidates.
- the current suffix
- counts along the path, non-increasing ()
Single-path shortcut. When a conditional tree is one chain, the recursion can stop. All combinations of the chain's items are frequent (every after pruning), and each one's support is its deepest node's count. This is where FP-Growth saves the most on dense data.
How acts. Lowering (i) keeps more items in the F-list, so the tree gets more nodes, and (ii) keeps more items alive in every conditional base, so the recursion goes deeper. The output can grow exponentially: on the worked example it goes from 2 itemsets at to 9 at and 23 at . The tree size is bounded by , the number of frequent item occurrences, and reaches that bound only when no two baskets share a first item. Sorting by descending support is a heuristic that maximizes prefix sharing. It is usually good but not guaranteed optimal.
Worked example: 10 grocery baskets
Ten baskets, six products, and minimum support baskets (30%). Scan 1 counts the items: bread 8, milk 7, eggs 6, butter 4, coffee 1, jam 1. Coffee and jam fall below 3 and are dropped, and the F-list is bread ≻ milk ≻ eggs ≻ butter.
| Basket | Items | Sorted frequent items |
|---|---|---|
| T1 | bread, milk, eggs | bread, milk, eggs |
| T2 | bread, butter | bread, butter |
| T3 | bread, milk, butter | bread, milk, butter |
| T4 | milk, eggs | milk, eggs |
| T5 | bread, milk, eggs, butter | bread, milk, eggs, butter |
| T6 | bread, eggs | bread, eggs |
| T7 | milk, eggs, jam | milk, eggs |
| T8 | bread, milk | bread, milk |
| T9 | bread, milk, eggs | bread, milk, eggs |
| T10 | coffee, bread, butter | bread, butter |
Scan 2: building the FP-tree
- 1T1 bread, milk, eggs: the tree is empty, so it creates the path bread:1 → milk:1 → eggs:1.
- 2T2 bread, butter: shares bread (now 2) and adds a new child butter:1 under bread.
- 3T3 bread, milk, butter: bread 3, milk 2, then a new butter:1 under milk.
- 4T4 milk, eggs: the root has no milk child, so it starts a second branch milk:1 → eggs:1. There are now two milk nodes, joined by the milk node-link.
- 5T5 to T10 continue the same way. T7 loses jam, T10 loses coffee, and T8 and T9 only increment existing counts.
- 6Result: 25 frequent item occurrences stored in 9 nodes: bread:8 → {milk:5 → {eggs:3 → butter:1, butter:1}, butter:2, eggs:1}, and milk:2 → eggs:2. Check: the butter nodes sum to 2 + 1 + 1 = 4 = sup(butter).
Mining, least frequent item first
- 1butter (support 4, three nodes). Prefix paths: bread:2, bread→milk:1, bread→milk→eggs:1. Inside this base bread has 4, milk 2 and eggs 1, so milk and eggs are pruned and the conditional tree is just bread:4. Emit and .
- 2eggs (support 6, nodes 3 + 1 + 2). Prefix paths: bread→milk:3, bread:1, milk:2. Local counts are milk 5 and bread 4, so both survive and the conditional tree is milk:5 → bread:3 plus a separate bread:1. It has two branches, so we recurse: bread's base is milk:3, giving and ; milk then gives . Together with that is four itemsets.
- 3milk (support 7, nodes 5 + 2). Prefix paths: bread:5, plus the root-level milk:2, whose prefix is empty. Emit and .
- 4bread (support 8). Its only node hangs off the root, so the base is empty. Emit .
- 5Total: 9 frequent itemsets from 2 database scans. Apriori would scan 3 times and count 6 + 6 + 1 = 13 candidates to reach the same answer.
| Item | Node-link counts | Conditional pattern base | Conditional FP-tree | Itemsets emitted |
|---|---|---|---|---|
| butter | 2 + 1 + 1 = 4 | bread:2 · bread→milk:1 · bread→milk→eggs:1 | bread:4 | {butter}:4, {bread, butter}:4 |
| eggs | 3 + 1 + 2 = 6 | bread→milk:3 · bread:1 · milk:2 | milk:5 → bread:3; bread:1 | {eggs}:6, {bread, eggs}:4, {bread, milk, eggs}:3, {milk, eggs}:5 |
| milk | 5 + 2 = 7 | bread:5 · (empty):2 | bread:5 | {milk}:7, {bread, milk}:5 |
| bread | 8 | (empty):8 | — | {bread}:8 |
Using the result. Rules come from the itemset counts with no further scans. has confidence and lift , and has confidence and lift . So a new customer who puts eggs in the cart gets milk recommended: 5 of the 6 egg baskets also had milk, 19% more often than milk's 70% base rate. If the cart already holds bread and eggs, has confidence and lift only 1.07.
- 1fpgrowth(D, minsup, suffix=∅):
- 2 scan 1: count supports, drop < minsup
- 3 sort each basket by support (desc)
- 4 scan 2: for t in D: insert t
- 5 shared prefix → count+1, else new node
- 6 for a in header, least frequent first:
- 7 emit {a} ∪ suffix
- 8 base ← prefix paths of a's nodes
- 9 Tₐ ← FP-tree of base (minsup)
- 10 fpgrowth(Tₐ, minsup, {a} ∪ suffix)
- 11 return all emitted itemsets
Scan 1 counts every item over the 10 baskets: bread 8, milk 7, eggs 6, butter 4, coffee 1, jam 1. coffee and jam fall below minsup 3 and are dropped for good.
The algorithm, step by step
FP-Growth(D, σ)
- 1Scan 1. Count the support of every item. Keep items with support and sort them by descending support (fix a deterministic tie-break). This is the F-list.
- 2Scan 2. For each transaction, keep its frequent items, sort them by the F-list, and insert them from the root: follow an existing child if there is one (count += weight), otherwise create a node and append it to that item's node-link chain.
- 3Mine(tree, suffix). For each header item , from least to most frequent: emit suffix with support along 's node-link.
- 4Project. Walk up from every -node to the root to get its prefix path, weighted by that node's count. These paths form the conditional pattern base .
- 5Recurse. Build an FP-tree from , dropping items whose support within is below . If it is a single path, emit every combination directly. Otherwise call Mine(conditional tree, suffix).
Complexity
- Scans of D
- exactly 2, whatever the length of the longest pattern (Apriori needs one per level)
- Tree build
- plus sorting each transaction, ; child lookup via a hash map per node
- Tree size
- at most nodes; often far fewer when frequent prefixes are shared
- Mining
- one conditional tree per frequent itemset that gets extended; the work is output-sensitive, roughly proportional to the number of frequent itemsets times the size of their conditional trees
- Memory
- the whole tree must fit in RAM, and conditional trees add to that along the recursion stack. This is the main limit on sparse data where little is shared
Variants and tuning
| Setting / variant | What it does | Guidance |
|---|---|---|
| min_support σ | Prunes items and itemsets below σ; controls tree size and output size | Start high (1–5%) and lower it until the number of itemsets stops being useful. Output can explode by orders of magnitude |
| max_len | Stops the recursion once the suffix has that many items | Cap it at 3–4 for recommendation rules; long itemsets are rarely actionable |
| Tie-break in the F-list | Fixes the order of equally frequent items | Does not change the result, only the tree shape. Keep it deterministic so runs are reproducible |
| FP-Max / FPClose | Output only maximal or closed itemsets | Far smaller output with the same information (closed) or only the frontier (maximal) |
| PFP (parallel FP-Growth) | Shards items into groups, builds per-group conditional databases on workers | Spark MLlib's FPGrowth, for databases that do not fit on one machine |
| Eclat | Vertical layout: an id-list per item, support from intersections | Often faster when data is sparse and id-lists are short. See the Eclat article |
In code
1import numpy as np2from collections import defaultdict34T = [["bread","milk","eggs"], ["bread","butter"], ["bread","milk","butter"],5 ["milk","eggs"], ["bread","milk","eggs","butter"], ["bread","eggs"],6 ["milk","eggs","jam"], ["bread","milk"], ["bread","milk","eggs"],7 ["coffee","bread","butter"]]89class Node:10 def __init__(self, item, parent):11 self.item, self.parent, self.count, self.children = item, parent, 0, {}1213def build_tree(weighted, min_count):14 """weighted: list of (items, count). Returns root, header{item: [nodes]}, order, supports."""15 items = sorted({i for t, _ in weighted for i in t})16 idx = {it: k for k, it in enumerate(items)}17 # one-hot matrix -> item supports in one vectorised pass (scan 1)18 X = np.zeros((len(weighted), len(items)), dtype=int)19 w = np.array([c for _, c in weighted])20 for r, (t, _) in enumerate(weighted):21 X[r, [idx[i] for i in t]] = 122 sup = w @ X23 keep = [it for it in items if sup[idx[it]] >= min_count]24 order = sorted(keep, key=lambda it: (-sup[idx[it]], it)) # descending support, ties alphabetical25 rank = {it: k for k, it in enumerate(order)}26 root, header = Node(None, None), defaultdict(list)27 for t, c in weighted: # scan 2: insert sorted frequent items28 node = root29 for it in sorted((i for i in t if i in rank), key=rank.get):30 if it not in node.children:31 node.children[it] = Node(it, node)32 header[it].append(node.children[it]) # node-link33 node = node.children[it]34 node.count += c35 return root, header, order, {it: int(sup[idx[it]]) for it in order}3637def fp_growth(weighted, min_count, suffix=()):38 root, header, order, sup = build_tree(weighted, min_count)39 out = {}40 for it in reversed(order): # least frequent first41 new = (it,) + suffix42 out[frozenset(new)] = sup[it]43 base = [] # conditional pattern base44 for node in header[it]:45 path, p = [], node.parent46 while p.item is not None:47 path.append(p.item); p = p.parent48 if path:49 base.append((path[::-1], node.count))50 out.update(fp_growth(base, min_count, new))51 return out5253result = fp_growth([(t, 1) for t in T], min_count=3)54for s, n in sorted(result.items(), key=lambda kv: (-kv[1], sorted(kv[0]))):55 print(f"{n} {{{', '.join(sorted(s))}}}")56print(len(result), "frequent itemsets")57# 8 {bread} | 7 {milk} | 6 {eggs} | 5 {bread, milk} | 5 {eggs, milk}58# 4 {bread, butter} | 4 {bread, eggs} | 4 {butter} | 3 {bread, eggs, milk}59# 9 frequent itemsets1import pandas as pd2from mlxtend.preprocessing import TransactionEncoder3from mlxtend.frequent_patterns import fpgrowth, association_rules45T = [["bread","milk","eggs"], ["bread","butter"], ["bread","milk","butter"],6 ["milk","eggs"], ["bread","milk","eggs","butter"], ["bread","eggs"],7 ["milk","eggs","jam"], ["bread","milk"], ["bread","milk","eggs"],8 ["coffee","bread","butter"]]910te = TransactionEncoder()11df = pd.DataFrame(te.fit(T).transform(T), columns=te.columns_)12freq = fpgrowth(df, min_support=0.3, use_colnames=True) # 3 of 10 transactions13print(freq.sort_values("support", ascending=False).to_string(index=False))1415rules = association_rules(freq, metric="confidence", min_threshold=0.8)16print(rules[["antecedents", "consequents", "support", "confidence", "lift"]].round(3).to_string(index=False))17# 9 itemsets: bread 0.8, milk 0.7, eggs 0.6, {milk,bread} 0.5, {eggs,milk} 0.5,18# butter 0.4, {eggs,bread} 0.4, {butter,bread} 0.4, {eggs,milk,bread} 0.319# antecedents consequents support confidence lift20# (eggs) (milk) 0.5 0.833 1.1921# (butter) (bread) 0.4 1.000 1.25Use when
- +Data is dense, with a few very frequent items, so prefixes are shared and the tree compresses well.
- +Frequent patterns are long, where Apriori's level-by-level scans and candidate sets explode.
- +Rereading the database is expensive (large files, remote storage): FP-Growth needs exactly 2 passes.
- +You need exact counts for every frequent itemset as input to rule mining.
Avoid when
- −The FP-tree does not fit in memory (very sparse, huge catalogues). Use PFP, Eclat, or partitioning.
- −You need incremental updates: new transactions can change the F-list order, forcing a rebuild.
- −Items carry quantities, prices or timestamps that matter: plain FP-Growth only sees presence. Use sequential or utility pattern mining.
- −The threshold must be very low on wide data: no algorithm saves you from an exponential output, so mine closed or maximal itemsets instead.
Where it's used
Market-basket analysis
Which products sell together, for shelf placement, bundles and "frequently bought together" widgets.
Recommendation candidates
High-confidence rules give cheap, explainable item-to-item recommendations, or features for a ranking model.
Log and alarm mining
Sets of error codes or events that fire together in the same session point to a shared root cause.
Web usage and clinical data
Pages visited in the same session, or diagnoses and prescriptions recorded together in patient histories.
Check yourself
In the worked example's FP-tree, what is the conditional pattern base of butter?
Check yourself
How many full passes over the transaction database does FP-Growth make, regardless of the longest frequent itemset?
Check yourself
A conditional FP-tree for suffix {x} is the single path a:5 → b:4 → c:3, with σ = 3. How many itemsets containing x does it emit (not counting {x} itself), and what is the support of {a, c, x}?
Check yourself
Why are items inserted in descending order of support?
Remember
- ✓FP-Growth finds the same frequent itemsets as Apriori, but with 2 database scans and no candidate generation.
- ✓Scan 1 builds the F-list (frequent items by descending support). Scan 2 inserts each basket's sorted frequent items into a prefix tree whose node counts record how many baskets share each prefix.
- ✓Key identity: equals the support of in 's conditional pattern base, the prefix paths of 's nodes weighted by those nodes' counts.
- ✓Mine items from least to most frequent, recurse on each conditional FP-tree, and on a single path emit all combinations directly. Each itemset is found exactly once.
- ✓The tree is bounded by the number of frequent occurrences, but the output can still be exponential: control it with min support, max_len, or closed and maximal itemsets.