Association Rule Learning

Association rule learning mines frequent co-occurrence patterns in transactional data: "customers who bought X also bought Y". It's the backbone of market basket analysis, recommendation systems, and cross-selling strategies.

ItemsetAny subset of items. E.g., {bread, butter, milk}.

TransactionOne purchase/session. E.g., the set of items a customer bought in a single visit.

Rule$X \Rightarrow Y$: if $X$ appears in a transaction, $Y$ tends to also appear.

The Three Core Metrics

Support, Confidence, Lift$$\text{Support}(X) = \frac{|\{t : X\subseteq t\}|}{|T|} \qquad \text{Confidence}(X\Rightarrow Y) = \frac{\text{Support}(X\cup Y)}{\text{Support}(X)}$$$$\text{Lift}(X\Rightarrow Y) = \frac{\text{Confidence}(X\Rightarrow Y)}{\text{Support}(Y)}$$Lift > 1: $X$ and $Y$ co-occur more than by chance. Lift = 1: independent. Lift < 1: anti-correlated.

SupportHow often does the itemset appear? Low support → ignore (too rare to be actionable).

ConfidenceGiven $X$, how often is $Y$ also present? High confidence but low lift → $Y$ is just popular (a useless rule).

LiftThe most important metric. Measures how much more likely $Y$ is given $X$, compared to its base rate. Always use lift, not just confidence.

The Apriori Algorithm

Apriori exploits the Apriori property: if an itemset is infrequent, all its supersets are also infrequent. This prunes the exponential search space drastically.

Find all frequent 1-itemsets (items with support ≥ min_support).
Generate candidate 2-itemsets from frequent 1-itemsets; prune those with infrequent subsets.
Count support of surviving candidates; keep frequent ones.
Repeat until no new frequent itemsets are found.
Generate rules from all frequent itemsets; filter by min_confidence and min_lift.

Python

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

# Simulated grocery transactions
dataset = [
    ["milk",  "bread",  "butter", "eggs"],
    ["milk",  "bread",  "diapers","beer", "cola"],
    ["milk",  "bread",  "butter"],
    ["eggs",  "diapers","beer",   "cola"],
    ["bread", "butter", "eggs",   "milk"],
    ["beer",  "cola",   "diapers"],
    ["milk",  "bread",  "butter", "diapers"],
    ["bread", "eggs",   "milk"],
    ["diapers","beer",  "cola",   "bread"],
    ["milk",  "eggs",   "bread"],
]

# Encode to one-hot
te = TransactionEncoder()
X  = pd.DataFrame(te.fit_transform(dataset), columns=te.columns_)
print("One-hot encoded transactions:")
print(X.astype(int).to_string()); print()

# Mine frequent itemsets
frequent = apriori(X, min_support=0.3, use_colnames=True)
frequent["length"] = frequent["itemsets"].apply(len)
print(f"Found {len(frequent)} frequent itemsets (min_support=0.30)")
print(frequent.sort_values("support", ascending=False).head(10))

# Generate association rules
rules = association_rules(frequent, metric="lift", min_threshold=1.0)
rules = rules.sort_values("lift", ascending=False)
print(f"
Total rules (lift ≥ 1.0): {len(rules)}")
print(rules[["antecedents","consequents","support","confidence","lift"]].head(8).to_string())

ECLAT Algorithm

ECLAT (Equivalence CLAss Transformation) uses a vertical data format — for each item, store the set of transaction IDs (tidset) containing it. Support is computed by set intersection size, which is faster than scanning the database repeatedly.

Apriori

Horizontal format: scan database at each pass.
Easy to understand and implement.
Multiple database scans (one per itemset size).
Better when database is very large but items are few.

ECLAT

Vertical format: tidsets per item.
Support = intersection of tidsets. Fewer database scans.
Faster for dense datasets.
High memory usage (stores all tidsets).

Python

def eclat(transactions, min_support=0.3):
    n = len(transactions)
    # Build vertical representation: item -> set of transaction IDs
    tidsets = {}
    for tid, trans in enumerate(transactions):
        for item in trans:
            tidsets.setdefault(frozenset([item]), set()).add(tid)

    # Filter by min_support
    frequent = {k: v for k, v in tidsets.items()
                if len(v)/n >= min_support}

    result = dict(frequent)

    # Generate 2-itemsets and beyond
    items = list(frequent.keys())
    for i, item1 in enumerate(items):
        for item2 in items[i+1:]:
            candidate = item1 | item2
            if len(candidate) > len(item1):    # avoid duplicates
                tidset = frequent[item1] & tidsets.get(frozenset([list(item2)[0]]), set())
                if len(tidset)/n >= min_support:
                    result[candidate] = tidset
                    frequent[candidate] = tidset

    return {frozenset(k): len(v)/n for k, v in result.items()}

eclat_results = eclat(dataset, min_support=0.3)
for itemset, support in sorted(eclat_results.items(), key=lambda x: -x[1])[:8]:
    print(f"  {set(itemset)!s:40s} support={support:.2f}")

Real-World Applications

RetailMarket basket analysis → cross-selling, store layout optimisation, product bundling.

E-commerce"Customers also bought…" recommendations. Pairs well with collaborative filtering.

MedicineDrug co-prescription patterns, symptom co-occurrence, adverse event mining.

Web analyticsPage navigation patterns, click-stream analysis, content recommendations.

🌿

Practical tuning guide: Start with min_support=0.05–0.1 for retail data (most items are rare). Filter rules by lift > 1.2 as a minimum, and confidence > 0.5. Too many rules → raise thresholds. No rules → lower them. Always inspect the top 20 rules by lift with a domain expert before deployment.

Summary

Support: frequency of an itemset. Confidence: conditional probability $P(Y|X)$. Lift: how much more than chance — always report lift.
Apriori: horizontal format, prunes using Apriori property. Classic and easy.
ECLAT: vertical format, set intersection for support. Faster for dense datasets.
Lift > 1 = useful rule. Lift = 1 = independence. Lift < 1 = anti-association.