Association Rules

Association rules find patterns of the form “if a transaction contains X, it probably also contains Y.” Instead of predicting a single target column like classification or regression, they search the whole dataset for if-then relationships between items. The classic application is market basket analysis: discovering that customers who buy bread and milk often buy butter too.

The task has two steps. First, find all itemsets whose support exceeds a minimum threshold — the frequent itemsets. Second, from each frequent itemset, generate rules whose confidence exceeds another threshold, and rank them by lift.

Support, confidence, and lift

For a rule $X \Rightarrow Y$ over a database of $N$ transactions:

$$\text{support}(X \Rightarrow Y) = P(X \cup Y) = \frac{\#\text{transactions containing both } X \text{ and } Y}{N}$$ $$\text{confidence}(X \Rightarrow Y) = P(Y \mid X) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}$$ $$\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X)\,\text{support}(Y)}$$

Support measures how often the pattern occurs at all. Confidence measures how reliable the rule’s prediction is. Lift is the ratio of the observed support to what you would expect if $X$ and $Y$ were independent: lift $> 1$ means the items co-occur more than chance, lift $< 1$ means they actually repel each other, and lift $= 1$ means the rule tells you nothing.

The Apriori principle

Enumerating every itemset is exponential in the number of items, so all practical algorithms prune the search. The key observation behind the Apriori algorithm is:

Apriori works level by level: it counts 1-itemsets, keeps the frequent ones, joins them to form candidate 2-itemsets, deletes any candidate with an infrequent subset, counts the survivors against the database, and repeats. Earlier algorithms made similar scans less efficiently — AIS generated candidates on-the-fly from each transaction (producing far too many), SETM deferred counting to the end of each pass at the cost of storing transaction IDs with every candidate, and AprioriTid replaced later database scans with a compact in-memory structure $C'$ listing which frequent itemsets each transaction contains. Modern implementations (Apriori, FP-Growth) are descendants of this idea.

Worked example: a five-transaction basket

The legacy example database has five transactions over items $\{A, B, C, D, E\}$:

Transaction	Items
T1	A, B, C
T2	A, C, D
T3	B, C, D
T4	A, D, E
T5	B, C, E

Set the minimum support to 40% (at least 2 of 5 transactions).

Pass 1 — frequent 1-itemsets. Counts: A = 3, B = 3, C = 4, D = 3, E = 2. All five items are frequent.

Pass 2 — frequent 2-itemsets. Counting all pairs gives AC = 2, AD = 2, BC = 3, BE = 2, CD = 2, CE = 2 as frequent; AB = 1, AE = 1, BD = 1, DE = 1 are infrequent.

Pass 3 — candidate 3-itemsets. Joining the frequent pairs produces ACD and BCE as candidates (ABC and ABD are never generated, because AB and BD are infrequent — that is the Apriori principle doing its work). Counting shows ACD = 1 and BCE = 1, so there are no frequent 3-itemsets and the search stops.

Now generate rules from the frequent itemsets and score them:

Rule	Support	Confidence	Lift
$A \Rightarrow D$	$2/5$	$2/3$	$10/9$
$C \Rightarrow A$	$2/5$	$2/4$	$5/6$
$A \Rightarrow C$	$2/5$	$2/3$	$5/6$
$B, C \Rightarrow D$	$1/5$	$1/3$	$5/9$

Check the first row: $A$ appears in 3 transactions (T1, T2, T4), $D$ in 3 (T2, T3, T4), and $\{A, D\}$ together in 2 (T2, T4). So support $= 2/5$, confidence $= (2/5)/(3/5) = 2/3$, and lift $= (2/3)/(3/5) = 10/9 \approx 1.11$ — buying $A$ raises the chance of buying $D$ slightly. Contrast $C \Rightarrow A$: its confidence is a respectable $1/2$, but lift $= 5/6 < 1$ because $A$ is already more common overall than among $C$-buyers. Confidence alone would have called this a useful rule; lift exposes it as worse than guessing $A$ at random.

In practice

Nobody writes Apriori by hand anymore. In Python, mlxtend.frequent_patterns.apriori and mlxtend.frequent_patterns.association_rules mine rules from a one-hot-encoded DataFrame in a few lines, and pyspark.ml.fpm.FPGrowth scales the same task across a cluster. The one-hot encoding step matters: each transaction becomes a row of boolean columns, one per item — the same trick as encoding categorical variables. For real retail data with thousands of SKUs, FP-Growth’s compressed prefix-tree representation is usually far faster than Apriori’s candidate generation.

Common pitfalls

• Trusting confidence without lift. A rule into a very popular item always looks confident; lift corrects for the item’s baseline popularity.
• Setting minimum support too low. You get a flood of spurious rules that occur a handful of times by chance.
• Setting it too high. Rare but valuable patterns (expensive item pairs, fraud signatures) are pruned before you ever see them.
• Treating rules as causal. Diapers $\Rightarrow$ beer is a stocking and marketing hint, not a mechanism.
• Ignoring rule direction. $X \Rightarrow Y$ and $Y \Rightarrow X$ have different confidences and different lifts.

Summary

Association rules mine co-occurrence patterns from transaction data, scored by support (how common), confidence (how reliable), and lift (how much better than independence). The Apriori principle — every subset of a frequent itemset is frequent — makes the search tractable by pruning huge parts of the itemset lattice without counting them. The five-transaction example shows the full pipeline: count, prune, generate rules, and let lift separate real associations from popularity artifacts.