Association Rule Mining
Support counts how often items appear together, confidence measures how reliably one predicts another, and lift checks whether that beats pure chance.
Why Does This Exist?
A grocery chain sits on millions of receipts and wants to know what gets bought together. Not one target column to predict, the way a classifier wants. The whole question is which combinations show up more than chance would put there, so the merchandising team can place items near each other or bundle a promotion.
That is the job association rule mining was built for. And it carries one trap that looks harmless until it costs money: the most frequent rule is often not the most meaningful one. Confuse the two and you bundle items that were never related.
This page covers the counting itself: support, confidence, lift, and the search trick that keeps it affordable. Turning those patterns into per-shopper picks is the next step, in collaborative filtering. The other unsupervised route into co-occurrence data, filling in missing entries instead of counting sets, is matrix factorization.
Think of It Like This
Popcorn, movies, and the restroom line
Nearly everyone who sees a movie also uses the restroom that evening. Nearly everyone who sees a movie also buys popcorn. Check either behavior against movie night and both look like strong, reliable associations.
But people use restrooms on every outing, movie or not. That pairing tells you nothing specific about movies. Popcorn is different: people rarely buy it on days they skip the film, so popcorn genuinely tracks movie night. Confidence alone cannot tell these two apart, because both behaviors follow a movie visit at a high rate. You have to ask whether that rate beats each behavior's own baseline, movie or not. That ratio is lift.
Where it stops: real baskets are noisier than movie night, and twelve receipts never settle anything. Lift also stays silent on cause. Popcorn tracks movies, but the film does not reach into your wallet.
How It Actually Works
Three numbers, each answering a different question
Call one set of items (bread) and another (butter). An itemset is any group of items, and is the total receipt count. Support of an itemset is the share of all receipts holding it. The support of a rule is the share holding both at once. Rules built on a handful of coincidental receipts sit near zero support, which is why rules need a minimum support bar before anyone trusts them.
Confidence of is the share of receipts that also hold , written and read as the chance of given . High confidence sounds like a strong rule, but it cannot spot an item everyone buys regardless of the trigger.
Lift asks the question confidence skips: it divides confidence by 's own baseline rate, . A lift of exactly 1 says buyers take at precisely the population rate, meaning no association at all. Above 1 means genuinely raises the chance of . Below 1 means buyers take less than average, a negative link confidence would never show on its own.
Worked example
Twelve receipts, small enough to count by hand:
- T1 to T3: bread, butter
- T4: bread, butter, milk
- T5 to T7: bread, milk
- T8: bread
- T9 to T10: milk
- T11: eggs
- T12: cheese
Bread fills 8 of the 12 receipts. Butter fills 4 (T1 to T4). Milk fills 6 (T4 to T7, T9, T10). Support counts each pair over all 12:
Confidence divides by the 8 bread receipts:
Same support, same confidence. Now divide each by its own baseline. Butter's baseline is and milk's is :
Bread buyers grab butter at 1.5 times the base rate: a genuine link worth acting on. They grab milk at exactly the population rate: no association at all, despite the tied confidence. That split is the picture at the top of the page.
Why counting everything fails
Past a small catalog, listing every possible itemset is hopeless: a 10,000-item store has more candidate sets than anyone can count. Apriori prunes with one structural fact: adding items can only make a set rarer, never more common. So if an itemset misses the minimum support bar, every larger set holding it misses too, and whole branches die the moment a smaller set fails. The algorithm climbs level by level, keeping only what clears the bar.
FP-Growth skips Apriori's repeated full-database scans by compressing the receipts into a tree once, then mining patterns straight from that tree. Heavier upfront structure, far fewer passes over raw data: the standard pick once transaction counts get large.
Code
The point is the check, not the formula: count the same twelve baskets and watch the tie in confidence break apart in lift.
baskets: list[set[str]] = [ {"bread", "butter"}, {"bread", "butter"}, {"bread", "butter"}, {"bread", "butter", "milk"}, {"bread", "milk"}, {"bread", "milk"}, {"bread", "milk"}, {"bread"}, {"milk"}, {"milk"}, {"eggs"}, {"cheese"},]
n: int = len(baskets)
def support(items: set[str]) -> float: return sum(1 for b in baskets if items <= b) / n
def confidence(antecedent: set[str], consequent: set[str]) -> float: return support(antecedent | consequent) / support(antecedent)
def lift(antecedent: set[str], consequent: set[str]) -> float: return confidence(antecedent, consequent) / support(consequent)
bread: set[str] = {"bread"}butter: set[str] = {"butter"}milk: set[str] = {"milk"}
print(f"bread -> butter: support={support(bread | butter):.2f} confidence={confidence(bread, butter):.2f} lift={lift(bread, butter):.2f}") # -> bread -> butter: support=0.33 confidence=0.50 lift=1.50print(f"bread -> milk: support={support(bread | milk):.2f} confidence={confidence(bread, milk):.2f} lift={lift(bread, milk):.2f}") # -> bread -> milk: support=0.33 confidence=0.50 lift=1.00The printout matches the hand count above: both rules at 0.33 support and 0.50 confidence, then lift splits them into 1.50 and 1.00.
Watch Out For
Ranking rules by confidence alone
Confidence loves popular items. Milk lands in half of all twelve receipts, so almost any trigger predicts it at a decent rate, and a leaderboard sorted by confidence fills up with the store's greatest hits whether or not any real link exists. Our two rules tie at 0.50, and only lift shows milk sitting on the chance rate.
Symptom: every top rule shares the same popular consequent. Fix: demand lift clearly above 1 next to every confidence you report, and never ship a rule on confidence alone.
Reading lift as proof of cause
A lift of 1.50 says bread buyers grab butter more often, not that bread makes anyone buy butter. Maybe Saturday shoppers buy both, or the store shelved them side by side. Treating lift as cause means bundling items whose link vanishes the moment you move them.
Symptom: a promotion built on a high-lift rule flops outside the aisle it was mined in. Fix: treat lift as a lead for an experiment, not a verdict. The full line between association and cause is drawn in correlation vs causation.
The Quick Version
- Support is the share of all receipts holding an itemset; both pairs here sit at 0.33.
- Confidence is the share of trigger receipts holding both items; both rules tie at 0.50.
- Lift divides confidence by the consequent's own baseline, and only it breaks the tie: 1.50 for butter against 1.00 for milk.
- A lift of 1 means the trigger changes nothing, so confidence without lift promotes popular items into fake rules.
- Apriori climbs level by level, dropping every branch whose smaller set misses the support bar, while FP-Growth compresses receipts into a tree first and suits large transaction counts.