# FP-Growth

> Compress the transactions into a prefix tree and mine frequent itemsets from it recursively — no candidate generation.

Source: https://www.mlfoundry.in/learn/fp-growth  
Section: ML Algorithms › Unsupervised · Association Rule Learning  
Level: core · 16 min read · updated 2026-10-07

**FP-Growth (frequent-pattern growth):** finds every itemset that appears in at least $\sigma$ 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.

- **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 $\sigma$ → every itemset $X$ with $\text{sup}(X)\ge\sigma$, 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, $O(\sum_t |t|)$, 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, $O(\#\text{rules})$
- **Hyperparameters:** min support $\sigma$ (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 $m$ distinct items there are $2^m-1$ 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 $k$ it builds every candidate $k$-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 $10^4$ frequent single items, level 2 alone has about $5\times10^7$ 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 $t\subseteq I$, e.g. one shopping receipt; the database $D$ is a list of them
- **Itemset:** any set of items $X\subseteq I$; a $k$-itemset has $k$ items
- **Support:** $\text{sup}(X)$, the number (or fraction) of transactions containing all of $X$
- **Frequent itemset:** one with $\text{sup}(X)\ge\sigma$, 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$, a small database of everything that co-occurs with $a$
- **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

$$
\text{sup}_D(X)=\big|\{\,t\in D : X\subseteq t\,\}\big|,\qquad F_\sigma=\{X\subseteq I:\ \text{sup}_D(X)\ge\sigma\}
$$

- $D$: the database, a list of transactions $t$ (each a set of items)
- $I$: the set of all distinct items
- $X$: an itemset
- $\sigma$: the minimum support, as a count (min_support × |D| when given as a fraction)
- $F_\sigma$: the output: all frequent itemsets

**Downward closure.** If $X\subseteq Y$ then every transaction containing $Y$ also contains $X$, so $\text{sup}(X)\ge\text{sup}(Y)$. An item with support below $\sigma$ therefore belongs to no frequent itemset and can be deleted from every transaction before anything else happens. That deletion is scan 1.

$$
a\prec b \iff \text{sup}(a)>\text{sup}(b)\ \ (\text{ties broken by a fixed rule}),\qquad \text{path}(t)=\text{sort}_\prec\big(t\cap F_1\big)
$$

- $\prec$: the F-list order: more frequent items come first
- $F_1$: the frequent single items
- $\text{path}(t)$: the sorted frequent part of transaction t, which is inserted as one root-to-node path

**What a node count means.** Inserting $\text{path}(t)$ adds 1 to every node along it, so a node $n$ whose root path is $p_1\prec\dots\prec p_k$ has count = the number of transactions whose sorted frequent part **starts with** $p_1\ldots p_k$. Each transaction contains an item $a$ at most once, so it passes through exactly one $a$-node. Summing the counts along $a$'s node-link therefore gives its support:

$$
\text{sup}_D(a)=\sum_{n\,\in\,\text{links}(a)}\text{count}(n)
$$

- $\text{links}(a)$: all tree nodes labelled $a$, reached through the header table's node-link chain
- $\text{count}(n)$: number of transactions whose sorted path passes through node n

**The pattern-growth lemma.** Take a set $\beta$ of items that all come *before* $a$ in the order. A transaction contains $\beta\cup\{a\}$ exactly when its path goes through some $a$-node $n$ and $\beta$ lies on the path above $n$. Items before $a$ can only appear above $a$ in the path, never below it. Group the transactions by the $a$-node they pass through and add up:

$$
\text{sup}_D(\beta\cup\{a\})=\sum_{n\in\text{links}(a)}\text{count}(n)\cdot\mathbb 1\big[\beta\subseteq\text{prefix}(n)\big]=\text{sup}_{B_a}(\beta)
$$

- $\text{prefix}(n)$: the items on the path from the root down to $n$'s parent
- $B_a$: the conditional pattern base of $a$: each $\text{prefix}(n)$ as a transaction with weight $\text{count}(n)$
- $\text{sup}_{B_a}(\beta)$: weighted support of $\beta$ inside that small database

This identity is the whole algorithm. Mining every frequent itemset whose least frequent item is $a$ is the same as mining $B_a$ with the same threshold $\sigma$ and attaching $a$ to every result. $B_a$ 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.

$$
\text{if } T \text{ is a single path } p_1\!:\!c_1\to\dots\to p_k\!:\!c_k,\quad \text{sup}(S\cup\alpha)=\min_{p_i\in S}c_i\ \ \text{for every } \varnothing\ne S\subseteq\{p_1,\dots,p_k\}
$$

- $\alpha$: the current suffix
- $c_i$: counts along the path, non-increasing ($c_1\ge c_2\ge\dots$)

**Single-path shortcut.** When a conditional tree is one chain, the recursion can stop. All $2^k-1$ combinations of the chain's items are frequent (every $c_i\ge\sigma$ 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 $\sigma$ acts.** Lowering $\sigma$ (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 $\sigma=7$ to 9 at $\sigma=3$ and 23 at $\sigma=1$. The tree size is bounded by $\sum_t|t\cap F_1|$, 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 $\sigma=3$ 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**.

The database, and each basket rewritten as its frequent items in F-list order (what actually gets inserted into the tree). Highlighted: the four baskets containing 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**

1. **T1** bread, milk, eggs: the tree is empty, so it creates the path bread:1 → milk:1 → eggs:1.
2. **T2** bread, butter: shares *bread* (now 2) and adds a new child butter:1 under bread.
3. **T3** bread, milk, butter: bread 3, milk 2, then a new butter:1 under milk.
4. **T4** 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.
5. **T5** to **T10** continue the same way. T7 loses *jam*, T10 loses *coffee*, and T8 and T9 only increment existing counts.
6. **Result**: 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**

1. **butter** (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 $\{\text{butter}\}:4$ and $\{\text{bread},\text{butter}\}:4$.
2. **eggs** (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 $\{\text{bread},\text{eggs}\}:4$ and $\{\text{bread},\text{milk},\text{eggs}\}:3$; milk then gives $\{\text{milk},\text{eggs}\}:5$. Together with $\{\text{eggs}\}:6$ that is four itemsets.
3. **milk** (support 7, nodes 5 + 2). Prefix paths: bread:5, plus the root-level milk:2, whose prefix is empty. Emit $\{\text{milk}\}:7$ and $\{\text{bread},\text{milk}\}:5$.
4. **bread** (support 8). Its only node hangs off the root, so the base is empty. Emit $\{\text{bread}\}:8$.
5. **Total: 9 frequent itemsets** from 2 database scans. Apriori would scan 3 times and count 6 + 6 + 1 = 13 candidates to reach the same answer.

Conditional pattern bases and what each one contributes (σ = 3).

| 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. $\text{eggs}\Rightarrow\text{milk}$ has confidence $5/6=0.833$ and lift $0.833/0.7=1.19$, and $\text{butter}\Rightarrow\text{bread}$ has confidence $4/4=1.0$ and lift $1.0/0.8=1.25$. 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, $\{\text{bread},\text{eggs}\}\Rightarrow\text{milk}$ has confidence $3/4=0.75$ and lift only 1.07.

> Figure: FP-Growth on the 10 baskets. Scan 1 counts items and crosses out coffee and jam (support 1). Scan 2 inserts the sorted baskets one by one: shared prefixes light up and gain +1, new nodes appear, and dashed node-links chain nodes of the same item. Mining then takes butter, eggs, milk, bread in turn, highlights each item's prefix paths, lists its conditional pattern base and draws its conditional FP-tree. At min support 3 the tree has 9 nodes and 9 itemsets are found. Change min support to see the tree and the output change: 11 nodes and 23 itemsets at 1, 6 nodes and 5 itemsets at 5.

> **The tree is a lossless index of the frequent part of the data:** Together with the node-links, the FP-tree holds every fact needed to count any itemset over frequent items, since the lemma above recovers all supports from it. That is why the original database is never read again after scan 2. Compression comes from shared prefixes: here 25 occurrences fit into 9 nodes, and on dense real data such as census or retail logs with a few dominant items the ratio is often much larger.

## The algorithm, step by step

**FP-Growth(D, σ)**

1. **Scan 1.** Count the support of every item. Keep items with support $\ge\sigma$ and sort them by descending support (fix a deterministic tie-break). This is the F-list.
2. **Scan 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.
3. **Mine(tree, suffix).** For each header item $a$, from least to most frequent: emit $\{a\}\cup$ suffix with support $\sum\text{count}$ along $a$'s node-link.
4. **Project.** Walk up from every $a$-node to the root to get its prefix path, weighted by that node's count. These paths form the conditional pattern base $B_a$.
5. **Recurse.** Build an FP-tree from $B_a$, dropping items whose support *within* $B_a$ is below $\sigma$. If it is a single path, emit every combination directly. Otherwise call Mine(conditional tree, $\{a\}\cup$ suffix).

**Complexity**

- **Scans of D:** exactly 2, whatever the length of the longest pattern (Apriori needs one per level)
- **Tree build:** $O\big(\sum_t |t|\big)$ plus sorting each transaction, $O(|t|\log|t|)$; child lookup via a hash map per node
- **Tree size:** at most $\sum_t|t\cap F_1|$ 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

Knobs and variants you will meet in practice.

| 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 |

> **A low support threshold can blow up the output, not the tree:** People expect FP-Growth to be safe at any $\sigma$ because it avoids candidates. The tree is bounded, but the **output** is not: a single path of 30 frequent items yields $2^{30}-1\approx10^9$ itemsets. Use max_len, mine closed or maximal itemsets, or raise $\sigma$. Lowering $\sigma$ from 3 to 1 on this 10-basket example already takes the output from 9 to 23 itemsets.

> **Sparse data defeats the compression:** When baskets rarely share a prefix (e.g. a catalogue of millions of products, each bought a few times), the FP-tree has about one node per occurrence plus pointer overhead, so it can be **larger** than the raw data. Eclat or a sampled or partitioned approach often wins there.

## In code

```python
import numpy as np
from collections import defaultdict

T = [["bread","milk","eggs"], ["bread","butter"], ["bread","milk","butter"],
     ["milk","eggs"], ["bread","milk","eggs","butter"], ["bread","eggs"],
     ["milk","eggs","jam"], ["bread","milk"], ["bread","milk","eggs"],
     ["coffee","bread","butter"]]

class Node:
    def __init__(self, item, parent):
        self.item, self.parent, self.count, self.children = item, parent, 0, {}

def build_tree(weighted, min_count):
    """weighted: list of (items, count). Returns root, header{item: [nodes]}, order, supports."""
    items = sorted({i for t, _ in weighted for i in t})
    idx = {it: k for k, it in enumerate(items)}
    # one-hot matrix -> item supports in one vectorised pass (scan 1)
    X = np.zeros((len(weighted), len(items)), dtype=int)
    w = np.array([c for _, c in weighted])
    for r, (t, _) in enumerate(weighted):
        X[r, [idx[i] for i in t]] = 1
    sup = w @ X
    keep = [it for it in items if sup[idx[it]] >= min_count]
    order = sorted(keep, key=lambda it: (-sup[idx[it]], it))   # descending support, ties alphabetical
    rank = {it: k for k, it in enumerate(order)}
    root, header = Node(None, None), defaultdict(list)
    for t, c in weighted:                                       # scan 2: insert sorted frequent items
        node = root
        for it in sorted((i for i in t if i in rank), key=rank.get):
            if it not in node.children:
                node.children[it] = Node(it, node)
                header[it].append(node.children[it])            # node-link
            node = node.children[it]
            node.count += c
    return root, header, order, {it: int(sup[idx[it]]) for it in order}

def fp_growth(weighted, min_count, suffix=()):
    root, header, order, sup = build_tree(weighted, min_count)
    out = {}
    for it in reversed(order):                                  # least frequent first
        new = (it,) + suffix
        out[frozenset(new)] = sup[it]
        base = []                                               # conditional pattern base
        for node in header[it]:
            path, p = [], node.parent
            while p.item is not None:
                path.append(p.item); p = p.parent
            if path:
                base.append((path[::-1], node.count))
        out.update(fp_growth(base, min_count, new))
    return out

result = fp_growth([(t, 1) for t in T], min_count=3)
for s, n in sorted(result.items(), key=lambda kv: (-kv[1], sorted(kv[0]))):
    print(f"{n}  {{{', '.join(sorted(s))}}}")
print(len(result), "frequent itemsets")
# 8 {bread} | 7 {milk} | 6 {eggs} | 5 {bread, milk} | 5 {eggs, milk}
# 4 {bread, butter} | 4 {bread, eggs} | 4 {butter} | 3 {bread, eggs, milk}
# 9 frequent itemsets
```

From scratch: FP-tree with node-links, conditional pattern bases and recursive mining (NumPy one-hot for the support count). Prints the 9 itemsets above.

```python
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth, association_rules

T = [["bread","milk","eggs"], ["bread","butter"], ["bread","milk","butter"],
     ["milk","eggs"], ["bread","milk","eggs","butter"], ["bread","eggs"],
     ["milk","eggs","jam"], ["bread","milk"], ["bread","milk","eggs"],
     ["coffee","bread","butter"]]

te = TransactionEncoder()
df = pd.DataFrame(te.fit(T).transform(T), columns=te.columns_)
freq = fpgrowth(df, min_support=0.3, use_colnames=True)       # 3 of 10 transactions
print(freq.sort_values("support", ascending=False).to_string(index=False))

rules = association_rules(freq, metric="confidence", min_threshold=0.8)
print(rules[["antecedents", "consequents", "support", "confidence", "lift"]].round(3).to_string(index=False))
# 9 itemsets: bread 0.8, milk 0.7, eggs 0.6, {milk,bread} 0.5, {eggs,milk} 0.5,
#             butter 0.4, {eggs,bread} 0.4, {butter,bread} 0.4, {eggs,milk,bread} 0.3
# antecedents consequents  support  confidence  lift
#      (eggs)      (milk)      0.5       0.833  1.19
#    (butter)     (bread)      0.4       1.000  1.25
```

Library version with mlxtend: same 9 itemsets, then the two rules with confidence ≥ 0.8.

> **At scale:** In PySpark, `FPGrowth(itemsCol="items", minSupport=0.3, minConfidence=0.8).fit(df)` runs the parallel PFP variant and exposes `freqItemsets` and `associationRules`. mlxtend's `fpgrowth` and `apriori` return identical tables, so you can switch between them without changing anything downstream.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

**Question:** In the worked example's FP-tree, what is the conditional pattern base of butter?

- A. {bread, milk, eggs}:4
- B. bread:2, bread→milk:1, bread→milk→eggs:1
- C. bread:8, milk:5, eggs:3
- D. bread:4, milk:2, eggs:1

**Answer:** B. bread:2, bread→milk:1, bread→milk→eggs:1 — Walk up from each of the three butter nodes. Each prefix path carries the count of the **butter** node it starts from (2, 1 and 1), not the counts of the nodes on the path. Option D is the item support *within* the base, which is the next step.

**Question:** How many full passes over the transaction database does FP-Growth make, regardless of the longest frequent itemset?

- A. 1
- B. 2
- C. One per itemset length
- D. One per frequent item

**Answer:** B. 2 — Scan 1 counts items to build the F-list, and scan 2 inserts the sorted transactions into the FP-tree. All mining afterwards uses only the tree and its conditional trees.

**Question:** 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}?

- A. 3 itemsets; 5
- B. 6 itemsets; 4
- C. 7 itemsets; 3
- D. 8 itemsets; 3

**Answer:** C. 7 itemsets; 3 — Every non-empty subset of {a, b, c} is frequent, giving $2^3-1=7$ itemsets. The support of a combination is the count of its deepest node, here c:3, so $\text{sup}(\{a,c,x\})=3$.

**Question:** Why are items inserted in descending order of support?

- A. It is required for correctness: other orders miss itemsets
- B. Frequent items near the root are shared by more baskets, so the tree has fewer nodes
- C. So the most frequent itemset is found first
- D. It makes confidence values larger

**Answer:** B. Frequent items near the root are shared by more baskets, so the tree has fewer nodes — Any fixed order gives correct results. Descending support is a compression heuristic: the items most baskets have in common become shared prefixes, which keeps the tree, and every conditional tree, small.

**Key points**

- 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: $\text{sup}(\beta\cup\{a\})$ equals the support of $\beta$ in $a$'s conditional pattern base, the prefix paths of $a$'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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
