Association Rule Mining

Association rule mining discovers interesting relationships, correlations, or frequent co-occurrence patterns among items in large transactional datasets. Its most famous application is market basket analysis — "customers who buy X also buy Y".

   Rule form:      A  ->  B          read as "if A then B"

   A = antecedent (LHS)     B = consequent (RHS)
   A and B are disjoint itemsets:  A ∩ B = ∅

   Example:  {Bread, Butter} -> {Milk}

Important: an association rule expresses co-occurrence, not causation and not implication in the logical sense. It says these items appear together often — not that buying bread causes buying milk.

Terminology

The Three Key Metrics

1. SUPPORT — how frequently the itemset appears in the whole database

                        Number of transactions containing (A ∪ B)
   Support(A -> B) = ────────────────────────────────────────────────
                          Total number of transactions

   Measures: usefulness / popularity of the rule
   Range: 0 to 1


2. CONFIDENCE — how often the rule is correct when A is present

                            Support(A ∪ B)
   Confidence(A -> B) = ─────────────────────  =  P(B | A)
                              Support(A)

   Measures: reliability / strength of the rule
   Range: 0 to 1


3. LIFT — how much more likely B is when A is present, vs B on its own

                       Confidence(A -> B)          Support(A ∪ B)
   Lift(A -> B) = ───────────────────────── = ───────────────────────────
                          Support(B)            Support(A) × Support(B)

   Lift > 1  ->  POSITIVE correlation — A and B appear together more than by chance
   Lift = 1  ->  INDEPENDENT — A tells you nothing about B
   Lift < 1  ->  NEGATIVE correlation — A and B substitute for each other

Additional Measures

   Leverage(A -> B)  = Support(A ∪ B) − Support(A) × Support(B)
                       (0 means independence; measures the raw excess co-occurrence)

                          1 − Support(B)
   Conviction(A -> B) = ─────────────────────
                        1 − Confidence(A -> B)
                       (∞ means the rule never fails; 1 means independence)

Worked Example

Transaction database (5 transactions):

Evaluate the rule {Diaper} → {Beer}:

Total transactions = 5

Transactions containing Diaper       : T2, T3, T4, T5  ->  σ(Diaper) = 4
Transactions containing Beer         : T2, T3, T4      ->  σ(Beer) = 3
Transactions containing BOTH         : T2, T3, T4      ->  σ(Diaper, Beer) = 3

Support(Diaper)         = 4/5 = 0.8
Support(Beer)           = 3/5 = 0.6
Support(Diaper -> Beer) = 3/5 = 0.6            ->  60% of ALL transactions

Confidence(Diaper -> Beer) = Support(Diaper ∪ Beer) / Support(Diaper)
                           = 0.6 / 0.8 = 0.75   ->  75% of diaper buyers also buy beer

Lift(Diaper -> Beer) = Confidence / Support(Beer)
                     = 0.75 / 0.6 = 1.25        ->  LIFT > 1: positive association

Interpretation: diaper buyers are 25% more likely to buy beer than a random customer. Retail action: place beer near diapers, or bundle them.

Now check the reverse rule {Beer} → {Diaper}:

Support(Beer -> Diaper)    = 3/5 = 0.6              (SAME — support is symmetric)
Confidence(Beer -> Diaper) = 0.6 / 0.6 = 1.00       (DIFFERENT — 100%!)
Lift(Beer -> Diaper)       = 1.00 / 0.8 = 1.25      (SAME — lift is symmetric)

Key insight: support and lift are symmetric; confidence is NOT. Every beer buyer bought diapers (confidence 100%), but only 75% of diaper buyers bought beer. Direction matters when acting on a rule.

Why Confidence Alone Misleads

Suppose 80% of all customers buy milk. A rule {Bread} → {Milk} with 80% confidence sounds strong — but milk is bought by 80% of everyone anyway, so bread tells us nothing:

   Lift = 0.80 / 0.80 = 1.0   ->  completely INDEPENDENT

Always check lift before acting on a high-confidence rule.

The Rule-Mining Process

Step 1 is the computationally hard part — with n distinct items there are 2ⁿ − 1 possible itemsets. For just 100 products that is more itemsets than atoms in a small planet. The Apriori algorithm (next lesson) makes this tractable.

Generating Rules from a Frequent Itemset

For a frequent k-itemset, there are 2ᵏ − 2 possible rules (every non-empty proper subset as the antecedent):

Frequent 3-itemset {Bread, Milk, Diaper} generates 2³ − 2 = 6 rules:

   {Bread}         -> {Milk, Diaper}
   {Milk}          -> {Bread, Diaper}
   {Diaper}        -> {Bread, Milk}
   {Bread, Milk}   -> {Diaper}
   {Bread, Diaper} -> {Milk}
   {Milk, Diaper}  -> {Bread}

All six share the SAME support (that of the full itemset) but have
DIFFERENT confidences.

Python

import pandas as pd
from itertools import combinations

transactions = [
    ["Bread", "Milk"],
    ["Bread", "Diaper", "Beer", "Eggs"],
    ["Milk", "Diaper", "Beer", "Cola"],
    ["Bread", "Milk", "Diaper", "Beer"],
    ["Bread", "Milk", "Diaper", "Cola"],
]
n = len(transactions)

def support(items):
    items = set(items)
    return sum(1 for t in transactions if items.issubset(set(t))) / n

def rule_metrics(antecedent, consequent):
    s_both = support(set(antecedent) | set(consequent))
    s_ante = support(antecedent)
    s_cons = support(consequent)
    conf = s_both / s_ante if s_ante else 0
    lift = conf / s_cons if s_cons else 0
    leverage = s_both - s_ante * s_cons
    return {"support": round(s_both, 3), "confidence": round(conf, 3),
            "lift": round(lift, 3), "leverage": round(leverage, 3)}

print("{Diaper} -> {Beer}:", rule_metrics(["Diaper"], ["Beer"]))
# {'support': 0.6, 'confidence': 0.75, 'lift': 1.25, 'leverage': 0.12}

print("{Beer} -> {Diaper}:", rule_metrics(["Beer"], ["Diaper"]))
# {'support': 0.6, 'confidence': 1.0, 'lift': 1.25, 'leverage': 0.12}

# Enumerate every 2-item rule and rank by lift
items = sorted({i for t in transactions for i in t})
rows = []
for a, b in combinations(items, 2):
    for ante, cons in [([a], [b]), ([b], [a])]:
        m = rule_metrics(ante, cons)
        if m["support"] >= 0.4 and m["confidence"] >= 0.6:
            rows.append({"rule": f"{{{ante[0]}}} -> {{{cons[0]}}}", **m})

rules_df = pd.DataFrame(rows).sort_values("lift", ascending=False)
print(rules_df.to_string(index=False))

# Using mlxtend — the standard library for this task
# pip install mlxtend
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules

te = TransactionEncoder()
te_array = te.fit(transactions).transform(transactions)
df_encoded = pd.DataFrame(te_array, columns=te.columns_)
print(df_encoded.astype(int))
#    Beer  Bread  Cola  Diaper  Eggs  Milk
# 0     0      1     0       0     0     1
# 1     1      1     0       1     1     0
# 2     1      0     1       1     0     1
# 3     1      1     0       1     0     1
# 4     0      1     1       1     0     1

frequent = apriori(df_encoded, min_support=0.4, use_colnames=True)
print("\nFrequent itemsets:\n", frequent.sort_values("support", ascending=False))

rules = association_rules(frequent, metric="confidence", min_threshold=0.6)
rules = rules[["antecedents", "consequents", "support", "confidence", "lift", "leverage"]]
print("\nRules sorted by lift:")
print(rules.sort_values("lift", ascending=False).round(3).to_string(index=False))

Choosing Thresholds

Typical starting points: support 0.01–0.05 for retail (thousands of products), confidence 0.5–0.8, and lift > 1.2.

Applications Beyond Retail

Limitations

1. Combinatorial explosion — the number of candidate itemsets grows exponentially with the number of items
2. Spurious rules — with enough items, some co-occurrences are pure chance
3. Rare item problem — genuinely valuable niche patterns fall below min_support (e.g. luxury goods)
4. No causation — correlational only
5. Static — standard algorithms ignore time order and seasonality
6. Rule overload — thousands of rules can be generated, most of them uninteresting

The next lesson presents Apriori — the algorithm that makes finding frequent itemsets computationally feasible.