Association Rule Mining: Definition, Support, Confidence & Correlation Extension

Definition with Example

Association Rule Mining discovers interesting relationships (rules) between items that frequently co-occur in a transactional dataset. A rule has the form:

$$A \Rightarrow B \quad [\text{support } s,\ \text{confidence } c]$$

Example: In supermarket transaction data, the rule
$$\{\text{Bread, Butter}\} \Rightarrow \{\text{Milk}\} \quad [s=20\%, c=75\%]$$
means: 20% of all transactions contain Bread, Butter, and Milk together, and 75% of the transactions that contain Bread and Butter also contain Milk.

Support and Confidence

Support — the fraction of transactions in the database that contain the itemset:
$$support(A \Rightarrow B) = P(A \cup B) = \frac{\text{transactions containing } A \cup B}{\text{total transactions}}$$
It measures how frequently the rule applies — i.e., its statistical significance.

Confidence — the conditional probability that a transaction containing A also contains B:
$$confidence(A \Rightarrow B) = P(B \mid A) = \frac{support(A \cup B)}{support(A)}$$
It measures the strength/reliability of the rule.

A rule is called strong if it satisfies both a minimum support threshold and a minimum confidence threshold.

Extending to Correlation Analysis

Support and confidence alone can be misleading — a rule can have high confidence purely because the consequent B is very common overall, even if A and B have no real relationship (the classic "coffee ⇒ tea" trap when both are individually popular). To check whether A and B are genuinely related, we compute lift:

$$lift(A, B) = \frac{P(A \cup B)}{P(A) \cdot P(B)} = \frac{confidence(A \Rightarrow B)}{support(B)}$$

• lift = 1 → A and B are statistically independent — the "association" is coincidental.
• lift > 1 → A and B are positively correlated (occur together more than expected by chance) — a genuinely useful rule.
• lift < 1 → A and B are negatively correlated (occurrence of A discourages B).

Worked Example

Suppose in 5000 transactions: 3000 contain "computer games", 3750 contain "videos", and 2000 contain both.

• $support(\text{games} \Rightarrow \text{videos}) = 2000/5000 = 40\%$
• $confidence(\text{games} \Rightarrow \text{videos}) = 2000/3000 = 66.7\%$ (looks "strong")
• $lift = \dfrac{2000/5000}{(3000/5000)(3750/5000)} = \dfrac{0.4}{0.6 \times 0.75} = \dfrac{0.4}{0.45} \approx 0.89$

Since lift < 1, buying games actually negatively correlates with buying videos — the high confidence was misleading because videos are popular on their own (75% of all customers buy them anyway). This shows why correlation analysis (lift) is essential beyond raw support/confidence.

Support/Confidence  ──▶  "Looks like a strong rule" (66.7% confidence)
        +
     Lift check      ──▶  Reveals TRUE relationship (lift=0.89 < 1 → negatively correlated!)