Association Rule Mining

Why Does This Exist?

A grocery chain has millions of transactions and wants to know which items tend to get bought together — not to predict a single target the way a classifier would, but to surface rules like "customers who buy bread also buy butter" that a merchandising team can act on directly, by placing items near each other or bundling a promotion. There's no label column here at all; the entire question is which combinations of items co-occur more than chance would predict.

Association rule mining is built specifically for that question, and it comes with a trap that looks harmless until you check it: the most frequent rule and the most meaningful rule are often not the same rule, and mistaking one for the other is how a merchandising team ends up bundling two items that were never actually related.

Think of It Like This

How It Actually Works

Three numbers, each answering a different question

Support for an itemset is simply how often it appears across all transactions — the share of receipts containing both bread and butter, say. It's a frequency, nothing more, and rules built on very low support are usually just noise from a handful of coincidental transactions.

Confidence of a rule "if bread, then butter" is the share of bread-buying transactions that also included butter — a conditional frequency, $P(\text{butter} \mid \text{bread})$. High confidence sounds like a strong rule, but confidence alone can't distinguish a real association from an item that's simply bought by nearly everyone regardless of what else is in the basket, the milk-and-restroom problem from the analogy above.

Lift answers the question confidence can't: it divides that conditional frequency by how often butter appears on its own, $P(\text{butter} \mid \text{bread}) / P(\text{butter})$. A lift of exactly 1 means bread buyers buy butter at precisely the rate everyone else does — no real association, whatever confidence said. A lift meaningfully above 1 means bread genuinely raises the chance of butter beyond its own baseline popularity; a lift below 1 means bread buyers actually buy butter less than average, a negative association confidence would never reveal on its own.

Why the naive approach doesn't scale

Checking every possible combination of items for support, confidence, and lift is combinatorially hopeless past a small catalog — a 10,000-item store has more possible itemsets than atoms worth counting. Apriori exploits one structural fact to prune the search: if an itemset doesn't meet a minimum support threshold, no larger itemset containing it can meet that threshold either, since adding items can only make a set rarer, never more common. That lets the algorithm build up frequent itemsets level by level, discarding entire branches of the search the moment a smaller itemset fails the threshold. FP-Growth avoids Apriori's repeated full-database scans by compressing the transaction data into a tree structure once and mining frequent patterns directly from that tree, trading a heavier upfront structure for far fewer passes over the raw data — the standard choice once the transaction count gets large.

Show Me the Code

Two rules with nearly identical confidence, separated cleanly by lift.

1import numpy as np2
3rng = np.random.default_rng(9)4n = 50005bread = rng.random(n) < 0.46butter = np.where(bread, rng.random(n) < 0.8, rng.random(n) < 0.2)  # butter co-occurs with bread7milk = rng.random(n) < 0.85  # milk is just common, bought regardless of bread8
9def support(mask: np.ndarray) -> float:10    return float(mask.mean())11
12def confidence(antecedent: np.ndarray, consequent: np.ndarray) -> float:13    return float((antecedent & consequent).sum() / antecedent.sum())14
15def lift(antecedent: np.ndarray, consequent: np.ndarray) -> float:16    return confidence(antecedent, consequent) / support(consequent)17
18print(f"bread -> butter: support={support(bread & butter):.2f}  confidence={confidence(bread, butter):.2f}  lift={lift(bread, butter):.2f}")19print(f"bread -> milk:   support={support(bread & milk):.2f}  confidence={confidence(bread, milk):.2f}  lift={lift(bread, milk):.2f}")20# -> bread -> butter: support=0.32  confidence=0.80  lift=1.8121# -> bread -> milk:   support=0.33  confidence=0.85  lift=1.00

Bread-to-milk actually has higher confidence than bread-to-butter — 0.85 against 0.80 — which would rank it as the stronger rule by confidence alone. Lift tells the true story: milk's lift of exactly 1.00 means bread buyers buy milk at precisely the population rate, no real association at all, while butter's lift of 1.81 reflects a genuine link a merchandising team could actually act on.

Watch Out For

The Quick Version

• Support measures how often an itemset occurs; confidence measures how reliably one item predicts another; lift checks whether that reliability beats the consequent's own baseline popularity.
• A rule can have high confidence purely because its consequent is popular overall, with no real association at all — lift is what separates that case from a genuine link.
• Apriori prunes the search using the fact that no itemset can be more frequent than any of its subsets, building frequent itemsets level by level.
• FP-Growth compresses transactions into a tree once, avoiding Apriori's repeated full-database scans, and is the standard choice at scale.
• A minimum support threshold set purely for runtime convenience can systematically exclude rare but strategically valuable item associations.

What to Read Next

• Classification Metrics covers the same precision-versus-baseline-rate reasoning that motivates lift over confidence alone.
• K-Means is a different way of finding structure in transaction-like data, grouping customers rather than finding item co-occurrence rules.
• Matrix Factorization is the latent-factor alternative to explicit rule mining for recommendation-style problems.
• Definitions worth a look: Class Imbalance and Standardization.