How does FP-growth mine frequent itemsets without generating candidates?

## The idea Apriori pays for its simplicity twice: it enumerates candidate itemsets, and it re-reads the transaction log once per itemset length. FP-growth removes both costs by first squeezing the log into an in-memory structure that preserves exactly the information support counting needs, then mining that structure recursively. ## Building the tree - two scans **Scan one.** Count every item. Discard everything below the minimum support - by downward closure, no itemset containing a dropped item can be frequent, so removing them now is lossless. Sort the survivors by descending frequency; call this the item order. **Scan two.** For each basket, keep only the frequent items and sort them into the global item order. Insert that sequence as a path from the root of the tree, creating nodes where needed and incrementing a count on every node reused. Sorting by descending frequency is deliberate: the most common items sit near the root, so the maximum number of baskets share the same prefix nodes, which is where the compression comes from. Alongside the tree, a **header table** holds one entry per frequent item with its total count and the head of a linked list threading every node for that item, wherever it sits in the tree. Over ten million supermarket baskets drawn from a catalogue where a few hundred items dominate, this collapses dramatically: millions of baskets funnel through the same handful of top-level nodes. The tree, not the log, is what the rest of the algorithm reads. ## Mining - conditional pattern bases Mining proceeds item by item, starting from the *least* frequent item in the header table and working up. 1. Follow the item's node chain. For each node, walk up to the root to read the prefix path, and tag that path with the node's count. The collection of these counted paths is the item's **conditional pattern base** - literally, the baskets that contained this item, projected onto the items that come before it in the ordering. 2. Treat the conditional pattern base as a small transaction database of its own, drop items in it that now fall below the threshold, and build a **conditional FP-tree** from it. 3. Recurse on that conditional tree, accumulating the item into the growing pattern prefix. Each recursion works on strictly fewer items over strictly smaller data, and every itemset it emits is frequent by construction. Nothing is ever proposed and then tested, which is the sense in which the method is candidate-free: it grows patterns out of the data rather than generating them from the previous level. ## Cost profile against level-wise mining - **Data scans.** Two, versus roughly one per itemset length. When the log is large and disk-resident, or long frequent itemsets exist, this is the dominant win. - **Candidate enumeration.** None, versus a join-and-prune step per level whose candidate set can be enormous at low thresholds. - **Memory.** The whole compressed tree, plus a stack of conditional trees during recursion, must fit. Level-wise mining only needs the current candidate set and its counters. The memory point is the real failure mode. Compression depends on baskets sharing prefixes. Data that is wide and sparse - many items, short baskets, little overlap in what people buy - produces a tree with almost as many nodes as there are item occurrences, plus per-node overhead, and it can be *larger* than the input. Very low support thresholds have the same effect, because few items get filtered out in scan one and the ordering has less mass at the top. When the tree will not fit, the usual answers are to partition the transactions, mine each partition and merge, or to raise the threshold. ## What it does not change FP-growth is a different route to the same destination: the set of frequent itemsets at a given minimum support, with exact counts. It does not alter which itemsets are frequent, does not produce different support values, and does not generate rules - rule generation from frequent itemsets, with its own confidence threshold, is a separate phase either way. Nor does it remove the redundancy in the output; closed or maximal representations are still the answer when the itemset list itself is too large. ## In an interview The expected shape of the answer is: compress into a prefix tree in two scans, exploit shared prefixes, mine recursively via conditional pattern bases, no candidates. The differentiating sentence is the caveat - the compression is data-dependent, and on sparse data with a low threshold the tree can blow memory, which is precisely when the level-wise alternative, slow but predictable in memory, is preferable.