---
title: Association Rule Mining in Python: Apriori Math, Support, Confidence, and Lift Explained
source: https://app.sythra.ai/learn/machine-learning/association-rule-mining-apriori-support-confidence-lift-python
topic: Machine Learning
updated: 2026-09-09
publisher: Sythra (https://app.sythra.ai)
---

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

Association Rule Mining is an unsupervised machine learning technique used in Market Basket Analysis to uncover actionable 'if-then' item relationships across transactions. The Apriori Algorithm uses the anti-monotonicity property (all subsets of a frequent itemset must also be frequent) to prune search space exponentially, filtering rules with Support (frequency), Confidence (conditional probability), and Lift (correlation over independence).

_Source: [https://app.sythra.ai/learn/machine-learning/association-rule-mining-apriori-support-confidence-lift-python](https://app.sythra.ai/learn/machine-learning/association-rule-mining-apriori-support-confidence-lift-python) — free to read on Sythra._

## Key points

- Explains Market Basket Analysis through the intuitive shoebox grocery receipts analogy.
- Derives the exact mathematical formulas for Support, Confidence, Lift, Leverage, and Conviction.
- Proves the Downward Closure (Anti-Monotonicity) property that makes candidate pruning tractable.
- Reveals the subtle 'Milk & Bread' trap where high confidence conceals negative association (Lift < 1.0).
- Implements pure Python Apriori from scratch and production pipelines using mlxtend.

**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**.

> **THE SHOEBOX RECEIPT ANALOGY:** Imagine a veteran neighborhood shopkeeper who keeps every paper checkout slip from the past decade in a large shoebox. After years behind the register, they notice subtle purchasing habits: _'Almost every customer who buys charcoal also picks up lighter fluid and ground beef.'_ The **Apriori Algorithm** is the automated, mathematically rigorous version of that observant shopkeeper. Instead of relying on gut feelings, it sifts through millions of digital shopping carts to compute exact statistical metrics for how frequent (**Support**), how dependable (**Confidence**), and how genuinely surprising (**Lift**) each relationship really is.

## 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:

| Metric / Term | Mathematical Formula | Plain-English Meaning | Target / Range |
| --- | --- | --- | --- |
| **Itemset ($I$)** | A collection of items: $\{i_1, i_2, \dots, i_k\}$ | Any group of products found inside a customer's basket. | Size $k \ge 1$ |
| **Support** | $\text{support}(A) = \frac{\text{count}(A)}{N}$ | How common is this itemset across all $N$ total transactions? | $[0, 1]$ (Higher = more universal) |
| **Rule Support** | $\text{support}(A \Rightarrow B) = \text{support}(A \cup B)$ | How frequently are both $A$ and $B$ purchased together? | $[0, 1]$ (Filters out rare noise) |
| **Confidence** | $\text{confidence}(A \Rightarrow B) = \frac{\text{support}(A \cup B)}{\text{support}(A)}$ | When a customer buys $A$, what percentage also buys $B$? | $[0, 1]$ (Directional certainty) |
| **Lift** | $\text{lift}(A \Rightarrow B) = \frac{\text{confidence}(A \Rightarrow B)}{\text{support}(B)}$ | How much does buying $A$ increase the odds of buying $B$ over chance? | $>1$: Positive, $=1$: Independent, $<1$: Negative |
| **Leverage** | $\text{leverage} = \text{support}(A \cup B) - \text{support}(A)\text{support}(B)$ | Difference between observed joint frequency and expected frequency under independence. | $[-0.25, +0.25]$ (0 = independent) |
| **Conviction** | $\text{conviction} = \frac{1 - \text{support}(B)}{1 - \text{confidence}(A \Rightarrow B)}$ | Ratio of expected frequency of $A$ without $B$ to observed incorrect predictions. | $[0, \infty)$ (1 = independent, $\infty$ = perfect rule) |

## 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)$$

> **MATHEMATICAL PROOF: APRIORI PRUNING:** Any transaction that contains superset $B$ must, by definition, contain subset $A$. Therefore, $B$ can never appear in more transactions than $A$ ($|T_B| \le |T_A|$).
$$\text{If } \text{support}(A) < \text{min\_support}, \quad \text{then } \text{support}(B) < \text{min\_support} \quad \forall B \supseteq A$$
If an itemset is infrequent, **all of its supersets are guaranteed to be infrequent**. The algorithm can immediately prune every superset from the candidate lattice without ever counting transactions.

## 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$**!

> **CRITICAL DATA SCIENCE INSIGHT:** Why is the lift for {Bread} $\Rightarrow$ {Milk} less than 1.0? Because Milk has a baseline probability of $87.5\%$ across all shoppers. If a customer is picked at random, there is an $87.5\%$ chance they buy Milk. But if they put Bread in their cart, their probability of buying Milk actually **drops to $83.3\%$**! High confidence was a statistical illusion driven entirely by Milk's baseline popularity. Lift exposes that Bread and Milk have a slight negative association in this store.

## 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:

```python
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:

```python
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

| Feature | Apriori Algorithm | FP-Growth (Frequent Pattern Tree) |
| --- | --- | --- |
| **Database Passes** | $k$ passes (one full scan per itemset length) | Exactly 2 database scans |
| **Candidate Generation** | Explicit self-join ($C_k$) with subset testing | Zero candidate generation (mines tree recursively) |
| **Data Structure** | Array of transaction sets or hash trees | Compact prefix tree (FP-Tree) in memory |
| **Execution Speed** | Slow on dense data and low support | Up to $10\times$ to $100\times$ faster than Apriori |
| **Best Use Case** | Educational intuition and small catalogs | Enterprise e-commerce and large transaction databases |

## 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.

## FAQ

### What is the primary difference between Support, Confidence, and Lift?

Support measures how often items appear together across all transactions (frequency). Confidence measures how often item B is bought when item A is purchased (conditional certainty). Lift measures how much more likely item B is purchased when item A is present compared to B's baseline popularity (association strength).

### What is the Apriori property (anti-monotonicity)?

The Apriori property states that all subsets of a frequent itemset must also be frequent. Conversely, if an itemset is infrequent, none of its supersets can ever be frequent. This allows the algorithm to prune vast combinatorial branches without counting transactions.

### Why is Lift symmetric while Confidence is asymmetric?

Confidence divides joint support by the antecedent support (P(B|A)), which changes depending on which item is the antecedent. Lift divides joint support by the product of both individual supports (P(A and B) / (P(A) * P(B))), which produces identical values regardless of direction.

### What does a Lift value of less than 1.0 mean?

A Lift below 1.0 indicates a negative association or substitution effect. It means purchasing item A actually decreases the probability that the customer will purchase item B compared to random chance, even if the rule has a seemingly high confidence score.

### When should you use FP-Growth instead of the Apriori algorithm?

FP-Growth should be used on large production datasets, dense transaction logs, or when minimum support is set low. While Apriori generates millions of candidate pairs and scans the database repeatedly, FP-Growth builds a compact prefix tree and mines frequent patterns in just two database passes.

## Related

- [K-Means Clustering From Scratch in Python](https://app.sythra.ai/learn/machine-learning/k-means-clustering-from-scratch-python-math) — Master centroid-based unsupervised grouping and distance metrics in Python.
- [Supervised vs Unsupervised Learning: The Math and Code](https://app.sythra.ai/learn/machine-learning/supervised-vs-unsupervised) — Understand how unsupervised pattern discovery differs from supervised target prediction.
- [Exploratory Data Analysis in Python: Complete Walkthrough](https://app.sythra.ai/learn/machine-learning/exploratory-data-analysis) — Learn transaction frequency distributions, item co-occurrences, and data prep.
- [Handling Imbalanced Datasets: SMOTE and Class Weighting](https://app.sythra.ai/learn/machine-learning/handling-imbalanced-datasets-smote-class-weighting-python) — Discover how class frequency skews model perception in classification problems.

---

Written by Sythra — Learn machine learning by building. Practice this topic with Sythra's AI tutor: https://app.sythra.ai/pricing