How does Apriori's downward-closure property prune candidate itemsets during mining?

## The property An itemset's support is **anti-monotone** with respect to adding items: ``` X subset of Y => support(Y) <= support(X) ``` A basket that contains all of Y necessarily contains all of X, so the count for Y can only be smaller or equal. Turned around, this is the **downward-closure** property: if X is frequent, every subset of X is frequent, and therefore if X is *not* frequent, no superset of X can be. That single implication is what makes mining feasible on a real catalogue. ## Why the search space needs it With `n` distinct items there are `2^n - 1` non-empty itemsets. A pharmacy chain carrying 40,000 SKUs has about 800 million possible pairs alone (40,000 * 39,999 / 2), and the number of triples runs to the order of 10 trillion. Enumerating and counting even the pairs is out of reach, and the triples are hopeless. Downward closure lets the algorithm decide most of that space is empty without ever touching it. ## The level-wise algorithm Apriori builds frequent itemsets one length at a time. Write `L_k` for the frequent itemsets of size k and `C_k` for the candidates of size k. 1. **Scan 1.** Count every item. Keep those at or above the minimum support - that is `L_1`. In the pharmacy case, most of the 40,000 SKUs die here; perhaps a few thousand survive. 2. **Generate.** Build `C_2` by joining pairs of items from `L_1`. 3. **Prune.** Drop any candidate that has a subset of size k-1 not present in `L_{k-1}`. At k=2 this does nothing; from k=3 upward it does most of the work. 4. **Scan.** Pass over the transactions counting only the surviving candidates; those meeting the threshold form `L_k`. 5. Repeat with k+1 until no candidates survive. The **join** is usually done on a canonical ordering: two frequent (k-1)-itemsets sharing their first k-2 items are merged into a k-candidate. The **prune** then checks all k subsets of size k-1. A triple `{A, B, C}` is discarded before counting if any of `{A,B}`, `{A,C}`, `{B,C}` failed - and because most pairs fail, most triples never get counted. This is exactly where length-3 candidate generation would otherwise explode. ## What it costs Apriori's cost profile is easy to state: **one pass over the whole transaction log per itemset length**, plus the memory to hold the current candidate set and its counters. If the longest frequent itemset has 6 items, that is 6 or 7 passes. On disk-resident data those passes dominate the runtime; the candidate set is what dominates memory. The minimum support threshold controls both. Lower it and more singletons survive level 1, which quadratically inflates the pair candidates, which inflates the triples, and the run can go from minutes to never finishing. Small changes in the threshold produce very non-linear changes in runtime, which is why practitioners start high and walk down. ## From frequent itemsets to rules Support pruning produces frequent *itemsets*, not rules. Rule generation is a second phase: for each frequent itemset Y, consider every way of splitting it into a non-empty antecedent X and consequent `Y \ X`, and keep the splits whose confidence clears the minimum. Confidence has its own monotonicity within a single itemset. Since `confidence(X -> Y \ X) = support(Y) / support(X)` and `support(Y)` is fixed, shrinking the antecedent raises its support and therefore *lowers* confidence. So if `{A, B} -> {C}` fails the confidence threshold, `{A} -> {B, C}` must fail too, and that half of the rule lattice can be pruned as well. Note the direction carefully - it is the opposite bookkeeping from support pruning, and it is a favourite follow-up. ## Closed and maximal itemsets The frequent itemset collection is highly redundant: every subset of a frequent itemset is reported too. Two compressions are standard. A **maximal** frequent itemset has no frequent superset; keeping only these gives the smallest description of *which* itemsets are frequent but loses the support values of subsets. A **closed** frequent itemset has no superset with the same support; keeping only these preserves every support count exactly while still collapsing most of the redundancy. Closed itemsets are usually what you want if rules and their metrics will be computed afterwards. ## When Apriori is still the right choice It is simple, its memory footprint is predictable, the level-wise structure parallelises cleanly by partitioning the transactions and merging counts, and on data with a high support threshold the frequent set is small enough that a handful of passes is nothing. It becomes a bad choice when the threshold is low, the frequent itemsets are long, or a pass over the data is expensive - which is the case the alternatives were built for.