There's a famous retail story. Someone digs through supermarket receipts and finds that late in the evening, shoppers who buy diapers often grab beer too. New dad sent out for nappies, rewards himself on the way to the till. Whether or not the story is literally true, it's the perfect picture of what association rule mining does: nobody labelled anything, nobody wrote a rule, the pattern just fell out of the receipts.
Day 28 of MachineLearningFromZero builds that miner from nothing, and you can play with it here:
https://dev48v.infy.uk/ml/day28-apriori.html
Toggle items in the baskets, drag the support and confidence sliders, and watch the frequent itemsets grow level by level while the losing candidates get struck out. Here's what's actually happening underneath.
Three numbers
Everything rides on three quantities, and getting them straight is most of the battle.
Support of an itemset is just how often it shows up: the fraction of baskets that contain all of its items. {beer, diapers} in 6 of 10 baskets means support 0.6. That's popularity, nothing more.
Confidence of a rule X to Y is support(X and Y) divided by support(X). It's the conditional probability of Y given you already have X. {diapers} -> {beer} with confidence 1.0 means every single basket with diapers also had beer.
Lift is the one people forget, and it's the one that matters. Lift is confidence divided by support(Y). It asks: does X actually make Y more likely than Y already is? Lift above 1 is a real positive association. Lift of 1 means X tells you nothing. Lift below 1 means X actually pushes Y away.
Why you can't just rank by confidence
Say bread is in 80% of your baskets. Then {anything} -> {bread} scores about 0.8 confidence automatically. Not because your antecedent predicts bread, but because bread is everywhere. That's the base-rate trap, and it's why a naive "sort by confidence" recommender keeps suggesting the most popular item to everyone.
Lift fixes it. Divide that 0.8 confidence by bread's 0.8 support and you get a lift of 1.0: no signal at all. The demo colours lift green above 1, red below, and sorts the rules table by it. Rank by lift, never by confidence alone.
The blowup, and the trick that saves you
Finding frequent itemsets sounds easy: score every possible combination, keep the common ones. The problem is that d items have 2^d possible subsets. Ten items is a thousand combinations, fine. A hundred items is more than a trillion trillion. A real supermarket has tens of thousands of products. Brute force is dead on arrival.
Apriori's escape is one clean observation, the downward-closure principle: if an itemset is rare, every larger set containing it must be at least as rare. Adding a requirement to a basket can only match fewer baskets, never more. So the moment {bread, chips} turns out to be infrequent, you know {bread, chips, milk}, {bread, chips, beer} and every other superset is infrequent too, and you throw all of them away without counting a single one.
Flip that around and you get the working rule: every subset of a frequent itemset is itself frequent.
How the algorithm actually loops
Apriori climbs one level at a time.
- Count single items, keep the ones above minimum support. That's L1.
- Join the survivors into pairs, but only pairs whose sub-items are all still in the game.
- Prune: before counting a candidate, check that all of its smaller subsets were frequent. If even one wasn't, kill the candidate now. This is downward closure doing the heavy lifting.
- Scan the database to count only the survivors. That's L2.
- Repeat for triples, quadruples, until nothing new survives.
In the live demo you can watch step 3 fire. With the default baskets, {milk, bread, chips} gets generated by the join, but {bread, chips} was never frequent, so the triple is crossed out and never counted. That single cull is the whole reason the algorithm scales.
From itemsets to rules
Frequent itemsets are the raw material. To make rules, take each itemset of size two or more and split it every possible way into an antecedent and a consequent, then check confidence and lift. Notice that {diapers} -> {beer} and {beer} -> {diapers} share the same support but can have different confidence, because they divide by different things.
Where it goes next
Apriori is the clearest way to understand this, but it rescans the data at every level. FP-Growth compresses the transactions into a tree and mines patterns straight off it with no candidate generation, usually much faster. Same frequent itemsets, same rules, smarter engine. In practice you learn Apriori and then reach for mlxtend's apriori and association_rules, or fpgrowth when the data gets big.
Open the page, drop the support slider, and watch the rules multiply. It's the most direct way I know to feel why the base-rate trap is real.
Top comments (0)