The Apriori Algorithm

Apriori (Agrawal and Srikant, 1994) is the classic algorithm for mining frequent itemsets and generating association rules. It solves the combinatorial explosion problem with a single powerful observation.

The Apriori Property (Downward Closure)

   "All non-empty SUBSETS of a frequent itemset must also be frequent."

   Equivalently (the contrapositive, which is what makes it useful):

   "If an itemset is INFREQUENT, then ALL of its supersets are also infrequent."

Why this works: support is anti-monotonic — adding an item to an itemset can never increase its support, because a transaction containing {A,B,C} necessarily contains {A,B}.

The payoff: if {Milk, Beer} is infrequent, we can prune {Milk, Beer, Bread}, {Milk, Beer, Diaper}, and every other superset without ever counting them. This prunes an exponential search space into something tractable.

In the lattice above, if {B,C} (red) is found infrequent, then {A,B,C} (grey) is pruned immediately — it can never be frequent.

The Algorithm

INPUT:  transaction database D, minimum support threshold min_sup

1. Scan D once; count the support of every individual item
   ->  L₁ = set of frequent 1-itemsets (those with support ≥ min_sup)

2. FOR k = 2, 3, 4, … WHILE L(k−1) is not empty:

   a) JOIN step:      generate candidate k-itemsets Cₖ by joining L(k−1)
                      with itself (join two (k−1)-itemsets that share their
                      first k−2 items)

   b) PRUNE step:     remove any candidate that has a (k−1)-subset NOT in
                      L(k−1)   <- this is the Apriori property at work

   c) COUNT step:     scan D to count the support of the surviving candidates

   d) SELECT step:    Lₖ = candidates in Cₖ with support ≥ min_sup

3. Frequent itemsets = L₁ ∪ L₂ ∪ … ∪ Lₖ

4. Generate association rules from each frequent itemset and keep those
   with confidence ≥ min_confidence

Complete Worked Example

Transaction database (min_support = 2 transactions = 40%):

Iteration 1 — Find L₁

C₁ (candidate 1-itemsets) with counts:

L₁ = { {I1}, {I2}, {I3}, {I4}, {I5} } — all five survive.

Iteration 2 — Find L₂

C₂ = all pairs from L₁ (C(5,2) = 10 candidates):

L₂ = { {I1,I2}, {I1,I3}, {I1,I5}, {I2,I3}, {I2,I4}, {I2,I5} }

Iteration 3 — Find L₃

Join step — join pairs in L₂ sharing their first item:

   {I1,I2} ⋈ {I1,I3}  ->  {I1,I2,I3}
   {I1,I2} ⋈ {I1,I5}  ->  {I1,I2,I5}
   {I1,I3} ⋈ {I1,I5}  ->  {I1,I3,I5}
   {I2,I3} ⋈ {I2,I4}  ->  {I2,I3,I4}
   {I2,I3} ⋈ {I2,I5}  ->  {I2,I3,I5}
   {I2,I4} ⋈ {I2,I5}  ->  {I2,I4,I5}

Prune step — check that every 2-subset is in L₂:

This is the whole value of Apriori — four of six candidates are eliminated without a single database scan.

Count step — only two candidates need counting:

L₃ = { {I1,I2,I3}, {I1,I2,I5} }

Iteration 4 — Find L₄

Join:  {I1,I2,I3} ⋈ {I1,I2,I5}  ->  {I1,I2,I3,I5}
Prune: subset {I1,I3,I5} is NOT in L₃  ->  PRUNED

C₄ is empty  ->  L₄ is empty  ->  ALGORITHM TERMINATES

Rule Generation from {I1, I2, I5} (support = 2/9 = 0.222)

For each non-empty proper subset as antecedent (2³ − 2 = 6 rules):

Strong rules (confidence ≥ 70%): {I1,I5}→{I2}, {I2,I5}→{I1}, {I5}→{I1,I2}

Notice all three high-confidence rules involve I5 as (part of) the antecedent — I5 is rare (appears twice) but always appears alongside I1 and I2.

Python

import pandas as pd
from itertools import combinations

transactions = [
    ["I1","I2","I5"], ["I2","I4"], ["I2","I3"],
    ["I1","I2","I4"], ["I1","I3"], ["I2","I3"],
    ["I1","I3"], ["I1","I2","I3","I5"], ["I1","I2","I3"],
]
min_support_count = 2
n = len(transactions)
tsets = [set(t) for t in transactions]

def support_count(itemset):
    return sum(1 for t in tsets if itemset.issubset(t))

def apriori_manual(min_sup_count):
    items = sorted({i for t in transactions for i in t})
    # L1
    L = {frozenset([i]): support_count({i}) for i in items}
    L = {k: v for k, v in L.items() if v >= min_sup_count}
    all_frequent = dict(L)
    k = 2
    while L:
        prev = list(L.keys())
        # JOIN
        candidates = set()
        for a, b in combinations(prev, 2):
            union = a | b
            if len(union) == k:
                candidates.add(union)
        # PRUNE using the Apriori property
        pruned = {c for c in candidates
                  if all(frozenset(sub) in L for sub in combinations(c, k - 1))}
        print(f"k={k}: {len(candidates)} candidates after join, "
              f"{len(pruned)} survive pruning")
        # COUNT + SELECT
        L = {c: support_count(set(c)) for c in pruned}
        L = {c: s for c, s in L.items() if s >= min_sup_count}
        all_frequent.update(L)
        k += 1
    return all_frequent

frequent = apriori_manual(min_support_count)
print("\nFrequent itemsets:")
for itemset, count in sorted(frequent.items(), key=lambda x: (len(x[0]), -x[1])):
    print(f"  {set(itemset)}: count={count}, support={count/n:.3f}")

# Generate rules from the frequent itemsets
def generate_rules(frequent, min_conf=0.7):
    rules = []
    for itemset, sup_count in frequent.items():
        if len(itemset) < 2:
            continue
        for r in range(1, len(itemset)):
            for ante in combinations(itemset, r):
                ante = frozenset(ante)
                cons = itemset - ante
                conf = sup_count / frequent[ante]
                lift = conf / (frequent[frozenset(cons)] / n) if frozenset(cons) in frequent else None
                if conf >= min_conf:
                    rules.append({
                        "rule": f"{set(ante)} -> {set(cons)}",
                        "support": round(sup_count / n, 3),
                        "confidence": round(conf, 3),
                        "lift": round(lift, 3) if lift else None,
                    })
    return pd.DataFrame(rules).sort_values("lift", ascending=False)

print(generate_rules(frequent, min_conf=0.7).to_string(index=False))

# Using mlxtend — the production-standard implementation
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules, fpgrowth

te = TransactionEncoder()
df = pd.DataFrame(te.fit(transactions).transform(transactions), columns=te.columns_)

frequent_itemsets = apriori(df, min_support=2/9, use_colnames=True)
frequent_itemsets["length"] = frequent_itemsets["itemsets"].apply(len)
print(frequent_itemsets.sort_values(["length", "support"], ascending=[True, False]))

rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)
print("\nStrong rules:")
print(rules[["antecedents", "consequents", "support", "confidence", "lift"]]
      .sort_values("lift", ascending=False).round(3).to_string(index=False))

# Apriori vs FP-Growth on a larger dataset
import numpy as np, time

np.random.seed(42)
products = [f"P{i}" for i in range(30)]
big = [list(np.random.choice(products, np.random.randint(2, 8), replace=False))
       for _ in range(3000)]

te = TransactionEncoder()
df_big = pd.DataFrame(te.fit(big).transform(big), columns=te.columns_)

t0 = time.time(); fi_ap = apriori(df_big, min_support=0.01, use_colnames=True); t_ap = time.time() - t0
t0 = time.time(); fi_fp = fpgrowth(df_big, min_support=0.01, use_colnames=True); t_fp = time.time() - t0

print(f"Apriori  : {len(fi_ap)} itemsets in {t_ap:.3f}s")
print(f"FP-Growth: {len(fi_fp)} itemsets in {t_fp:.3f}s")
print("Same results:", len(fi_ap) == len(fi_fp))
# FP-Growth finds identical itemsets, typically several times faster.

Apriori vs FP-Growth

Other alternatives: ECLAT (vertical data format, uses set intersection of TID-lists) and Partition/Sampling algorithms for very large databases.

Improving Apriori's Efficiency

Advantages and Disadvantages

That completes Unit 3. You can now build predictive models (classification, regression) and descriptive models (clustering, association rules). Unit 4 turns to the tools — the Python analytics stack — and to what happens when data outgrows a single machine.