Association Rule Mining: Foundations

Source: Unit 4 §5

Given a set of transactions, association rule mining finds rules that predict the occurrence of an item based on the occurrences of other items.

The market-basket problem

TID	Items
1	Bread, Milk
2	Bread, Diaper, Beer, Eggs
3	Milk, Diaper, Beer, Coke
4	Bread, Milk, Diaper, Beer
5	Bread, Milk, Diaper, Coke

Example rules read off this basket: {Diaper} → {Beer}, {Milk, Bread} → {Eggs, Coke}, {Beer, Bread} → {Milk}.

⚠GotchaThe arrow is not a causal arrow

Implication here means CO-OCCURRENCE, not causality. {Diaper} → {Beer} says the two appear together often enough to clear the thresholds; it says nothing about one causing the other.

Key definitions

Term	Definition
Itemset	a collection of one or more items, e.g. {Milk, Bread, Diaper}
k-itemset	an itemset with k items
Support count σ	frequency: the number of transactions containing the itemset. σ({Milk,Bread,Diaper}) = 2
Support s	fraction of transactions containing the itemset. s = 2/5 = 0.4
Frequent itemset	an itemset whose support ≥ minsup threshold
Association Rule	an implication X → Y, where X and Y are itemsets

Rule evaluation metrics: support and confidence

For a rule X → Y:

$$\text{Support}(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{|T|} \qquad \text{Confidence}(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{\sigma(X)}$$

Support is the fraction of transactions containing both X and Y. Confidence is how often Y appears among the transactions that already contain X.

→StepsWorked example: `{Milk, Diaper} → {Beer}`

1. Support. $\sigma(\text{Milk, Diaper, Beer}) = 2$ (transactions 3 and 4), so $s = 2/5 = \mathbf{0.4}$.
2. Confidence. $\sigma(\text{Milk, Diaper}) = 3$ (transactions 3, 4 and 5), so $c = 2/3 = \mathbf{0.67}$.

≡FactsLift, the third metric that usually rides along

Confidence alone rewards a rule whose right-hand side is simply common. Lift divides it out: $\text{Lift}(X \rightarrow Y) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)}$. For {Milk, Diaper} → {Beer}, Beer has support $3/5 = 0.6$, so lift $= 0.67 / 0.6 = 1.11$: barely above 1, meaning the association is only slightly stronger than chance. Lift $> 1$ is positive association, $= 1$ is independence, $< 1$ is negative association.

The mining task, and why brute force fails

Goal: find all rules with support ≥ minsup AND confidence ≥ minconf.

• Brute force: list every rule, compute support and confidence for each, and prune the ones below the thresholds. This is computationally prohibitive.
• Key observation: rules from the same itemset - for example all the binary partitions of {Milk, Diaper, Beer} - have identical support but different confidence. So support and confidence can be decoupled and handled in separate phases.

The two-step approach

Support and confidence are decoupled on purpose: step 1 pays the exponential cost once, step 2 is cheap partitioning of what survived.

→StepsThe two phases

1. Frequent itemset generation - generate all itemsets with support ≥ minsup. This is the computationally expensive step.
2. Rule generation - generate high-confidence rules from each frequent itemset, where each rule is a binary partition of that itemset.

#NumbersWhy step 1 is the expensive one

Given d items there are $2^d$ possible candidate itemsets (the itemset lattice), so brute-force support counting costs $O(N \cdot M \cdot w)$ with $M = 2^d$, where N is the number of transactions and w the transaction width.