Walk into any grocery store's data warehouse and you'll find millions of transactions — each one a list of items bought together. Association rule mining is the technique for finding patterns hidden in that pile of baskets: which items tend to appear together often enough to be useful.

The classic example, apocryphal but illustrative, is "customers who buy diapers also buy beer." Whether or not that specific rule is real, the underlying idea is everywhere: Amazon's "frequently bought together," grocery store shelf placement, and cross-sell recommendations in e-commerce all trace back to this family of algorithms.

Support, confidence, and lift

Association rules take the form {A} → {B}: if a transaction contains itemset A, it's likely to also contain itemset B. Three metrics decide whether a rule is worth keeping.

Support — how often the itemset appears across all transactions. support({A, B}) = (transactions containing A and B) / (total transactions). Low support means the pattern is too rare to matter commercially.

Confidence — given that A is in the basket, how often is B also there? confidence(A → B) = support({A, B}) / support({A}). This is conditional probability: P(B | A).

Lift — does A actually increase the chance of B, or would B have shown up anyway? lift(A → B) = confidence(A → B) / support(B). Lift of 1 means A and B are independent — no real association. Lift above 1 means a positive association; below 1 means buying A makes B less likely.

Note

A rule can have high confidence purely because B is popular overall, not because A has any causal or correlational relationship with it. If 90% of all shoppers buy bread, then almost any rule {A} → {bread} will have high confidence — it looks like a strong rule but says nothing special about A. Lift corrects for this by comparing against B's baseline frequency, which is why serious analyses always report lift alongside confidence.

The combinatorial explosion problem

With n distinct products, there are 2^n possible itemsets. A modest grocery store with 10,000 SKUs has far more possible itemsets than atoms in the universe. Checking every combination for support is computationally impossible — you need a smarter search strategy. That's exactly what the Apriori algorithm provides.

The Apriori algorithm

Apriori exploits one simple, powerful fact: if an itemset is frequent, all of its subsets must also be frequent. Equivalently, if any subset is infrequent, the superset cannot possibly be frequent either (adding more items to a basket condition can only keep or reduce how often it occurs). This is called the downward closure property, and it lets Apriori prune the search space aggressively instead of checking every combination.

The algorithm proceeds level by level:

1. Count single items. Find all individual items with support above a minimum threshold — these are the frequent 1-itemsets (L1).
2. Generate candidates. Combine frequent itemsets from the previous level to build candidate itemsets one size larger.
3. Prune. Discard any candidate that contains an infrequent subset — it cannot be frequent by the downward closure property.
4. Count and filter. Scan the transactions to compute support for the surviving candidates; keep those above the threshold.
5. Repeat until no new frequent itemsets are found.

Once you have all frequent itemsets, generating rules is straightforward: for each frequent itemset, split it into an antecedent and consequent, and keep the split if confidence and lift clear your thresholds.

python

Apriori vs. brute-force itemset search

Property	Brute force (check all 2^n subsets)	Apriori
Search space	Exponential, every possible itemset	Pruned using downward closure
Scalability	Infeasible beyond a few dozen items	Practical for thousands of SKUs
Database scans	One giant pass over all subsets	One pass per itemset size (level-wise)
Implementation	Rarely done in practice	mlxtend, R's arules, Spark MLlib FP-Growth

Note

Apriori still requires repeated database scans and can generate enormous candidate sets at low support thresholds. For very large catalogs, the FP-Growth algorithm is usually preferred — it compresses transactions into a tree structure (an FP-tree) and mines frequent itemsets without generating explicit candidates, making it considerably faster at scale while producing identical results.

Real-world applications

Market basket analysis — the original use case: which products to place near each other, which items to bundle into promotions, which cross-sells to surface at checkout.

Web usage mining — "pages visited together" patterns inform site navigation and content recommendations.

Medical diagnosis — association rules between symptoms, test results, and conditions can surface patterns worth investigating (though causality must still be verified separately).

Fraud detection — unusual combinations of transactions or account actions that rarely co-occur legitimately can flag suspicious activity.

What's next

Association rule mining finds relationships between items based on co-occurrence. Collaborative Filtering for Recommender Systems takes a related but distinct approach: instead of mining item-to-item co-occurrence directly, it learns from the full pattern of user-item interactions to predict what a specific person will like next.

I build these systems professionally.

Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.

Work With Me →

Need production AI or MarTech expertise? I build custom LLM workflows, server-side GTM tagging, and analytics infrastructures professionally.

Need custom AI or MarTech setup? Let's build together.

Let's talk →