Association Rule Mining in Python: Apriori Math, Support, Confidence, and Lift Explained

Association Rule Mining is an unsupervised data mining technique designed to discover interesting 'if-then' relationships and co-occurrence patterns among items in massive transactional databases. Unlike supervised models that predict a specific target column, association rule mining requires no labeled outcomes; it scans unlabeled baskets to determine which items naturally gravitate together — unlocking the foundational science behind retail recommendation engines and Market Basket Analysis.

1. Key Concepts & Metric Glossary

Every association rule is expressed in the form $A \Rightarrow B$, where $A$ is the antecedent (the item bought first) and $B$ is the consequent (the item added as a result). Here are the primary statistical metrics used to evaluate rule quality:

2. Mathematical Foundations & The Downward Closure Property

Let a transactional database $D = \{T_1, T_2, \dots, T_N\}$ consist of $N$ transactions, where each transaction $T_i$ is a subset of the master item catalog $I$. An association rule is an implication of the form:

$$A \Rightarrow B \quad \text{where } A \subset I, \; B \subset I, \; \text{and } A \cap B = \emptyset$$

The Directional Asymmetry of Confidence

Confidence represents conditional probability: $\text{confidence}(A \Rightarrow B) = P(B \mid A)$. Crucially, confidence is directionally asymmetric:

$$\text{confidence}(A \Rightarrow B) = \frac{\text{support}(A \cup B)}{\text{support}(A)} \neq \frac{\text{support}(A \cup B)}{\text{support}(B)} = \text{confidence}(B \Rightarrow A)$$

For instance, if nearly everyone who buys printer toner also buys printer paper, $\text{confidence}(\text{Toner} \Rightarrow \text{Paper})$ might be $95\%$. However, millions of people buy paper without buying toner, meaning $\text{confidence}(\text{Paper} \Rightarrow \text{Toner})$ could be as low as $5\%$. Direction dictates shelf placement!

Lift: Correcting for Consequent Popularity

Confidence can be deceiving if the consequent item $B$ is universally popular. Lift controls for baseline frequency by dividing confidence by the independent support of $B$:

$$\text{lift}(A \Rightarrow B) = \frac{\text{confidence}(A \Rightarrow B)}{\text{support}(B)} = \frac{\text{support}(A \cup B)}{\text{support}(A) \times \text{support}(B)}$$

Notice that unlike confidence, Lift is mathematically symmetric: $\text{lift}(A \Rightarrow B) = \text{lift}(B \Rightarrow A)$. It measures the strength of the mutual association rather than direction.

The Anti-Monotonicity Principle (Apriori Pruning Property)

For a catalog of $d$ unique items, there exist $2^d - 1$ possible candidate itemsets. If a supermarket stocks just 100 items, searching all combinations would require evaluating $2^{100} - 1 \approx 1.26 \times 10^{30}$ itemsets — a computational impossibility.

The Apriori Algorithm overcomes this combinatorial explosion through the Downward Closure Property (Anti-Monotonicity):

$$\forall A, B \quad \text{if } A \subseteq B \implies \text{support}(B) \le \text{support}(A)$$

3. Step-by-Step Worked Numerical Trace

Let us trace the Apriori algorithm step by step on a real 8-basket supermarket dataset with $\text{min\_support} = 0.50$ (must appear in at least $4$ out of $8$ transactions):

• $T_1$: {Bread, Milk}
• $T_2$: {Bread, Diapers, Beer, Eggs}
• $T_3$: {Milk, Diapers, Beer, Cola}
• $T_4$: {Bread, Milk, Diapers, Beer}
• $T_5$: {Bread, Milk, Diapers, Cola}
• $T_6$: {Bread, Milk, Diapers, Beer}
• $T_7$: {Milk, Diapers, Beer}
• $T_8$: {Bread, Milk, Diapers}

Pass 1: Frequent 1-Itemsets ($L_1$)

Count the occurrence of every individual item across all 8 transactions:

• Milk: $7/8 = 0.875$ (Survives)
• Diapers: $7/8 = 0.875$ (Survives)
• Bread: $6/8 = 0.750$ (Survives)
• Beer: $5/8 = 0.625$ (Survives)
• Cola: $2/8 = 0.250$ (Pruned: below 0.50)
• Eggs: $1/8 = 0.125$ (Pruned: below 0.50)

Pass 2: Frequent 2-Itemsets ($L_2$)

Form candidate pairs exclusively from surviving items {Milk, Diapers, Bread, Beer}:

• {Milk, Diapers}: $6/8 = 0.750$ (Survives)
• {Diapers, Beer}: $5/8 = 0.625$ (Survives)
• {Milk, Bread}: $5/8 = 0.625$ (Survives)
• {Bread, Diapers}: $5/8 = 0.625$ (Survives)
• {Milk, Beer}: $4/8 = 0.500$ (Survives)
• {Bread, Beer}: $3/8 = 0.375$ (Pruned: below 0.50)

Pass 3: Frequent 3-Itemsets ($L_3$)

Generate 3-item combinations from pairs. Before counting, prune candidate {Bread, Diapers, Beer} because its subset {Bread, Beer} was already pruned! The surviving 3-itemsets are:

• {Milk, Bread, Diapers}: $4/8 = 0.500$ (Survives)
• {Milk, Diapers, Beer}: $4/8 = 0.500$ (Survives)

4. The Milk & Bread Trap: Why Lift Is Non-Negotiable

Now examine two rules generated with minimum confidence $\text{min\_confidence} = 0.70$ ($70\%$):

• Rule A: {Diapers} $\Rightarrow$ {Beer}
  $$\text{confidence} = \frac{0.625}{0.875} \approx 0.714 \quad (71.4\%), \quad \text{lift} = \frac{0.714}{0.625} \approx 1.143$$
  Because $\text{lift} = 1.143 > 1$, buying diapers provides a genuine $+14.3\%$ uplift in the probability of purchasing beer.
• Rule B: {Bread} $\Rightarrow$ {Milk}
  $$\text{confidence} = \frac{0.625}{0.750} \approx 0.833 \quad (83.3\%), \quad \text{lift} = \frac{0.833}{0.875} \approx 0.952$$
  Notice that confidence is an impressive $83.3\%$. But look at lift: $0.952 < 1.0$!

5. From-Scratch Python Implementation

Here is the complete from-scratch implementation of the Apriori algorithm and rule generation in pure Python using only standard library utilities:

from itertools import combinations, chain

def compute_support(itemset, transactions):
    """Calculates the fraction of transactions containing the itemset."""
    itemset_set = set(itemset)
    count = sum(1 for t in transactions if itemset_set.issubset(t))
    return count / len(transactions)

def get_frequent_itemsets(candidates, transactions, min_support):
    """Filters candidate itemsets against the minimum support threshold."""
    frequent = {}
    for candidate in candidates:
        sup = compute_support(candidate, transactions)
        if sup >= min_support:
            frequent[frozenset(candidate)] = sup
    return frequent

def generate_candidates(prev_frequent, k):
    """
    Self-joins frequent (k-1)-itemsets and applies Apriori pruning:
    a candidate k-itemset is only kept if ALL its (k-1) subsets are frequent.
    """
    items = sorted(prev_frequent.keys(), key=lambda x: sorted(x))
    candidates = set()
    n = len(items)

    for i in range(n):
        for j in range(i + 1, n):
            union = items[i] | items[j]
            if len(union) == k:
                # Downward closure check: all (k-1) subsets must be in prev_frequent
                subsets_valid = all(
                    frozenset(sub) in prev_frequent
                    for sub in combinations(union, k - 1)
                )
                if subsets_valid:
                    candidates.add(frozenset(union))
    return candidates

def apriori_from_scratch(transactions, min_support=0.5):
    """Full Apriori algorithm returning all frequent itemsets."""
    all_unique_items = set(chain.from_iterable(transactions))
    candidates_1 = [{item} for item in all_unique_items]
    current_frequent = get_frequent_itemsets(candidates_1, transactions, min_support)
    all_frequent = dict(current_frequent)

    k = 2
    while current_frequent:
        candidates_k = generate_candidates(current_frequent, k)
        current_frequent = get_frequent_itemsets(candidates_k, transactions, min_support)
        all_frequent.update(current_frequent)
        k += 1

    return all_frequent

def generate_association_rules(frequent_itemsets, transactions, min_confidence=0.7):
    """Generates A => B rules and calculates Support, Confidence, and Lift."""
    rules = []
    n_transactions = len(transactions)

    for itemset, itemset_support in frequent_itemsets.items():
        if len(itemset) < 2:
            continue
        items_list = list(itemset)

        for r in range(1, len(items_list)):
            for ant_tuple in combinations(items_list, r):
                antecedent = frozenset(ant_tuple)
                consequent = itemset - antecedent

                ant_support = frequent_itemsets.get(antecedent) or compute_support(antecedent, transactions)
                confidence = itemset_support / ant_support

                if confidence >= min_confidence:
                    cons_support = frequent_itemsets.get(consequent) or compute_support(consequent, transactions)
                    lift = confidence / cons_support
                    leverage = itemset_support - (ant_support * cons_support)
                    conviction = (1.0 - cons_support) / (1.0 - confidence) if confidence < 1.0 else float("inf")

                    rules.append({
                        "antecedent": set(antecedent),
                        "consequent": set(consequent),
                        "support": itemset_support,
                        "confidence": confidence,
                        "lift": lift,
                        "leverage": leverage,
                        "conviction": conviction
                    })
    return rules

# Verification test on 8 grocery baskets
if __name__ == "__main__":
    transactions = [
        {"Bread", "Milk"},
        {"Bread", "Diapers", "Beer", "Eggs"},
        {"Milk", "Diapers", "Beer", "Cola"},
        {"Bread", "Milk", "Diapers", "Beer"},
        {"Bread", "Milk", "Diapers", "Cola"},
        {"Bread", "Milk", "Diapers", "Beer"},
        {"Milk", "Diapers", "Beer"},
        {"Bread", "Milk", "Diapers"},
    ]

    frequent = apriori_from_scratch(transactions, min_support=0.5)
    print(f"Total frequent itemsets found: {len(frequent)}")

    rules = generate_association_rules(frequent, transactions, min_confidence=0.7)
    print(f"Total rules meeting 70% confidence: {len(rules)}\n")
    for r in sorted(rules, key=lambda x: -x["lift"]):
        ant = " + ".join(sorted(r["antecedent"]))
        cons = " + ".join(sorted(r["consequent"]))
        print(f"{{{ant}}} => {{{cons}}}")
        print(f"  Support: {r['support']:.3f} | Conf: {r['confidence']:.3f} | Lift: {r['lift']:.3f} | Leverage: {r['leverage']:.3f}\n")

6. Production Implementation via mlxtend

In production workflows, Python developers use the highly optimized mlxtend library to run Market Basket Analysis on tabular DataFrames:

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules

# 1. Input Transactions (8 retail baskets)
transactions = [
    ["Bread", "Milk"],
    ["Bread", "Diapers", "Beer", "Eggs"],
    ["Milk", "Diapers", "Beer", "Cola"],
    ["Bread", "Milk", "Diapers", "Beer"],
    ["Bread", "Milk", "Diapers", "Cola"],
    ["Bread", "Milk", "Diapers", "Beer"],
    ["Milk", "Diapers", "Beer"],
    ["Bread", "Milk", "Diapers"],
]

# 2. One-hot encode transactions into a Boolean DataFrame
te = TransactionEncoder()
te_array = te.fit(transactions).transform(transactions)
df = pd.DataFrame(te_array, columns=te.columns_)

# 3. Mine frequent itemsets with min_support = 50%
frequent_itemsets = apriori(df, min_support=0.5, use_colnames=True)
frequent_itemsets["length"] = frequent_itemsets["itemsets"].apply(lambda x: len(x))

print("=== Frequent Itemsets (min_support = 0.5) ===")
print(frequent_itemsets.sort_values(by="support", ascending=False).to_string(index=False))

# 4. Generate association rules evaluated on Confidence and Lift
rules = association_rules(
    frequent_itemsets,
    metric="confidence",
    min_threshold=0.7,
    num_itemsets=len(frequent_itemsets)
)

# Format for clean display
rules["antecedents"] = rules["antecedents"].apply(lambda x: ", ".join(list(x)))
rules["consequents"] = rules["consequents"].apply(lambda x: ", ".join(list(x)))

cols_to_show = ["antecedents", "consequents", "support", "confidence", "lift", "leverage", "conviction"]
print("\n=== Discovered Association Rules (min_confidence = 0.7) ===")
print(rules[cols_to_show].sort_values(by="lift", ascending=False).to_string(index=False))

7. Advanced Metrics: Leverage & Conviction

Beyond Lift, production recommendation pipelines rely on Leverage and Conviction to filter out spurious correlations:

• Leverage: $\text{leverage}(A \Rightarrow B) = \text{support}(A \cup B) - \text{support}(A) \times \text{support}(B)$. Unlike Lift (which is a ratio), Leverage measures the absolute surplus probability above independence in units of customer volume. $\text{leverage} = 0$ indicates independence.
• Conviction: $\text{conviction}(A \Rightarrow B) = \frac{1 - \text{support}(B)}{1 - \text{confidence}(A \Rightarrow B)}$. Measures the expected error rate under independence divided by the observed error rate. A conviction of $\infty$ means the rule is an absolute law (confidence is $100\%$; $A$ is never seen without $B$).

8. Apriori vs. FP-Growth: Algorithmic Comparison

9. Top 5 Pitfalls & Common Mistakes

1. Trusting Confidence Without Checking Lift: Blindly reporting high-confidence rules where consequent items are staples (Milk, Bananas) leads to promoting items that shoppers would have bought anyway.
2. The Rare Item Problem: High-value items (televisions, laptops) have low support ($0.001\%$), so uniform minimum support thresholds discard them while retaining low-margin groceries.
3. Conflating Association with Causation: Discovering $A \Rightarrow B$ does not mean purchasing $A$ causes someone to purchase $B$; an unobserved third factor (like a rainy day) could cause purchases of both umbrellas and hot coffee.
4. Ignoring Directional Asymmetry: Placing beer next to diapers boosts beer sales, but placing diapers next to beer does not necessarily boost diaper sales.
5. Memory Exhaustion on Low Support: Lowering min_support too far on catalogs with thousands of items causes exponential candidate explosion, crashing server memory.

10. Summary & Key Takeaways

• Market Basket Analysis: Uncovers co-occurrence patterns in transaction records without requiring labeled outcomes.
• Support, Confidence, and Lift: Support measures overall frequency; Confidence measures directional probability; Lift measures true association over chance.
• The Downward Closure Property: All subsets of a frequent itemset must also be frequent, enabling Apriori to prune unpromising candidates.
• Always Verify Lift > 1: Rules with Lift $< 1.0$ indicate independence or negative association, even when confidence approaches $90\%$.
• Use FP-Growth for Scale: For enterprise catalogs, transition from Apriori's $k$ database scans to FP-Growth's tree-based mining.