Association Rules: Support, Confidence & Lift

Association-rule mining starts from transactions—sets of items, events, or properties—and asks which item combinations recur. A rule $A\Rightarrow B$ says that transactions containing itemset $A$ often also contain disjoint itemset $B$. The arrow records a directional conditional frequency: it is not logical implication, temporal order, causation, or a recommendation policy.

The method separates a computational problem from an interpretive one. First find frequent itemsets without enumerating the full power set; then decide which rules are surprising, stable, and useful enough to act on.

From transactions to rules #

Let $I=\{i_1,\ldots,i_m\}$ be the item universe and $D=\{T_1,\ldots,T_N\}$ a transaction database, where each $T_j\subseteq I$. A transaction contains itemset $X$ when $X\subseteq T_j$. Define its count as

$$n(X)=\left\lvert\{T_j\in D:X\subseteq T_j\}\right\rvert.$$

An association rule is $A\Rightarrow B$ with $A,B\subseteq I$ and $A\cap B=\varnothing$. Requiring disjoint sides avoids restating an item already assumed in the antecedent. The same framework works for shopping baskets, diagnoses recorded during one encounter, pages within one session, or alarms within one incident—but the definition of a transaction changes what co-occurrence means.

Support, confidence, and lift #

Support is the fraction of transactions containing an itemset. For a rule it is the support of the union:

$$\mathop{\mathrm{supp}}(A\Rightarrow B) =\mathop{\mathrm{supp}}(A\cup B) =\frac{n(A\cup B)}{N}.$$

Confidence asks what fraction of antecedent transactions also contain the consequent:

$$\mathop{\mathrm{conf}}(A\Rightarrow B) =\frac{\mathop{\mathrm{supp}}(A\cup B)}{\mathop{\mathrm{supp}}(A)} =P(B\mid A).$$

Lift divides that conditional rate by the baseline prevalence of $B$:

$$\mathop{\mathrm{lift}}(A\Rightarrow B) =\frac{P(B\mid A)}{P(B)}.$$

Lift 1 is the value expected under independence in the observed sample; above 1 means positive association and below 1 negative association. Support and lift are symmetric in $A$ and $B$, but confidence is not, because reversing a rule changes the denominator.

Basket example #

Among 100 baskets, 40 contain bread, 30 butter, and 24 both. Then

$$\mathop{\mathrm{supp}}(bread\cup butter)=0.24,$$

$$\mathop{\mathrm{conf}}(bread\Rightarrow butter)=24/40=0.60,$$

and lift is $0.60/0.30=2$. Butter is twice as common in bread baskets as overall. The reverse confidence is $24/30=0.80$, while lift remains 2. Confidence is directional because denominators differ; lift is symmetric for the pair even though the displayed rule arrow is not causal.

Now consider 1,000 baskets in which 100 contain tea, 800 contain a bag, and 80 contain both. The rule $tea\Rightarrow bag$ has confidence $80/100=0.80$, which sounds strong, but lift is $0.80/0.80=1$. Tea adds no information about a bag: the consequent is simply common. Conversely, a rule observed twice can have spectacular lift and almost no evidential or operational value.

Apriori controls combinatorial search #

With $m$ items there are $2^m$ itemsets. Apriori uses anti-monotonicity:

If an itemset is infrequent, every superset is infrequent.

It first finds frequent single items, joins them to propose candidate pairs, prunes any candidate whose subsets are not all frequent, scans support, and repeats for larger sets. This removes entire branches of the itemset lattice. After frequent itemsets are known, candidate rules are generated and filtered by confidence or other criteria.

For each frequent itemset $L$ and each non-empty proper subset $A\subset L$, the remaining items form $B=L\setminus A$. The rule survives a confidence threshold when

$$\frac{\mathop{\mathrm{supp}}(L)}{\mathop{\mathrm{supp}}(A)}\geq \mathop{\mathrm{minconf}}.$$

This two-stage decomposition matters: minimum support prunes itemsets during the expensive search, while minimum confidence filters directions after their counts exist. Low minimum support can still produce an explosion of candidates; high support can erase rare but important combinations. FP-growth and related methods avoid explicit candidate generation by compressing transactions, but a faster search does not make the resulting rules statistically valid.

Generalized rules use an item taxonomy #

Leaf-level identifiers are often too sparse. Individual green-tea and black-tea products may each miss minimum support even though the broader category tea has a stable relationship with bakery. A generalized, hierarchical, or multilevel association rule allows either side to contain nodes from any level of an is-a taxonomy.

flowchart TD
  Beverage --> Tea
  Beverage --> Coffee
  Beverage --> Soda
  Tea --> Green["Green tea"]
  Tea --> Black["Black tea"]
  Bakery --> Cookies
  Bakery --> Bread

Arrows in the diagram run from category to child: green tea is-a tea, and tea is-a beverage. The taxonomy may be a tree or a directed acyclic graph when an item participates in more than one classification. A transaction supports category $x$ when it contains $x$ itself or any descendant of $x$. The simplest implementation forms an extended transaction by adding every observed item's ancestors and removing duplicates, then runs an ordinary frequent-itemset miner.

Consider these eight baskets:

After ancestor expansion, Beverage is present in baskets 1–7, so its support is $7/8$. Bakery is present in baskets 1–4 and 6–8, also $7/8$. Their intersection contains baskets 1–4, 6, and 7, giving

$$\mathop{\mathrm{supp}}(Beverage\Rightarrow Bakery)=\frac{6}{8},$$

$$\mathop{\mathrm{conf}}(Beverage\Rightarrow Bakery)=\frac{6}{7}, \qquad \mathop{\mathrm{lift}}=\frac{6/7}{7/8}=\frac{48}{49}\approx0.98.$$

The generalized rule has high coverage and confidence but essentially no positive association. More importantly, basket 7 contains both green tea and coffee yet contributes only once to Beverage support. Category support is therefore not the sum of child supports: overlapping descendants would double-count transactions.

Generalization also creates structural redundancy:

• $green\ tea\Rightarrow Tea$ is true by taxonomy, not discovered behavior, so rules whose consequent is an ancestor of an antecedent item must be rejected.
• An itemset containing both green tea and Tea has the same support as the itemset without the ancestor; it adds no constraint.
• A specialized rule is uninformative when its support and confidence are no more surprising than those predicted by its closest ancestor rule.
• Very broad categories gain support but can wash out a strong leaf-level association. Search and report the abstraction level at which the effect changes, not only the broadest rule that clears a threshold.

Taxonomy-aware miners exploit these relations without materializing every ancestor in every transaction. The historical Cumulate and EstMerge algorithms precompute relevant ancestors, avoid candidates containing an item and its ancestor, and use hierarchy-aware pruning or sampling. Those optimizations change runtime, not the definitions above.

What makes a rule actionable #

Evaluate rules on later or held-out transactions. Attach counts and uncertainty, not only ratios. Check whether association persists across stores, periods, customer segments, taxonomy revisions, and exposure conditions. Compare with a popularity baseline and with the cost of the proposed action.

For a fixed rule, the four counts $A\cap B$, $A\cap\neg B$, $\neg A\cap B$, and $\neg A\cap\neg B$ form a $2\times2$ contingency table. An independence test can quantify whether the observed departure from lift 1 is compatible with sampling noise, but mining first and testing the selected winner invalidates an ordinary single-test interpretation. Searching millions of candidates almost guarantees extreme-looking lift by chance. Stability filters, false-discovery control, shrinkage, minimum counts, and a confirmatory holdout reduce this risk; see goodness-of-fit and independence tests.

If a rule will drive a recommendation, promotion, or alert, test that policy itself. Deployment changes exposure: recommending $B$ to people with $A$ alters later confidence, and a profitable intervention depends on incremental effect, margin, and opportunity cost—not historical co-occurrence alone.

Diagnostic checklist #

Other common failures include duplicated or bot transactions, inconsistent item identifiers, and treating a basket as a sequence. Promotions, layout, season, or customer type can cause both sides of a rule; next-event claims require ordered event data and a sequential-pattern method.

Association rules are compact exploratory summaries. Their role is to surface hypotheses and candidate policies; causal impact requires an experiment or a design that addresses confounding and exposure.