The idea: count small sets first, and skip what cannot be frequent
A shop keeps one basket (a transaction) per sale: the set of items bought together. An itemset is any set of items, and its support is the share of baskets that hold all of them. An itemset is frequent when its support reaches a chosen min support. Apriori finds every frequent itemset without counting every possible one. It works by size: single items first, then pairs, then triples. A larger set is counted only if all its smaller parts were frequent.
The page uses 10 baskets and 6 items. With min support 30%, an itemset must be in at least 3 baskets. The left panel is the basket table, the middle panel holds the candidates of the current level (later the rules), and the right panel collects the frequent itemsets.
Downward closure
If a basket holds {Bread, Milk, Beer}, it also holds {Milk, Beer}. So a set can never be in more baskets than any of its subsets. This gives the rule Apriori is built on, called downward closure (or the Apriori property):
- every subset of a frequent itemset is frequent;
- so if one subset is not frequent, the larger set cannot be frequent, and there is no need to count it.
On the page {Milk, Beer} is in only 2 baskets. That is enough to drop {Bread, Milk, Beer} without reading a single basket. (Demo 2: level 3, one candidate pruned without counting)
One level: join, prune, count, filter
Level k turns the frequent (k−1)-itemsets, written Lk−1, into the frequent k-itemsets Lk. The candidates Ck are the sets that might be frequent.
- Join. Keep the items of every set in one fixed order. Two frequent (k−1)-itemsets that agree on their first k−2 items make one candidate: {Bread, Milk} and {Bread, Diapers} give {Bread, Milk, Diapers}. At level 2 this is every pair of frequent items.
- Prune. Check every (k−1)-item subset of the candidate. If one is missing from Lk−1, drop the candidate.
- Count. Read every basket once. Add 1 to each candidate the basket holds.
- Filter. Keep the candidates whose count reaches min support. They are Lk.
The loop stops when a level has no frequent itemset, or when no two sets can be joined. (Demo 1: frequent itemsets, level by level)
| Level (min support 30%) | Joined | Pruned | Counted | Frequent |
|---|---|---|---|---|
| 1: single items | 6 | 0 | 6 | 5 (Eggs has count 2) |
| 2: pairs | 10 | 0 | 10 | 5 |
| 3: triples | 3 | 1 | 2 | 1: {Bread, Diapers, Beer} |
Apriori counts 6 + 10 + 2 = 18 itemsets. Brute force would count all 26 − 1 = 63. With thousands of items the gap is what makes the search possible at all.
Choosing min support
Min support decides how much work there is and how much comes out.
| Min support | Levels | Itemsets counted | Frequent itemsets | Rules |
|---|---|---|---|---|
| 20% (2 baskets) | 4 | 26 | 19 | 54 |
| 30% (3 baskets) | 3 | 18 | 11 | 16 |
| 40% (4 baskets) | 2 | 12 | 5 | 2 |
| 50% (5 baskets) | 2 | 7 | 2 | 0 |
Set it too high and nothing is left: at 50% only Bread and Diapers are frequent, their pair is in 3 baskets, and mining stops with no rule at all. (Demo 3: min support 50%, mining stops at pairs) Set it too low and the number of candidates and rules grows fast, and many of the rules rest on two or three baskets. The page offers 30%, 40% and 50%.
From itemsets to rules
An association rule X → Y says: baskets that hold X tend to hold Y too. Every frequent itemset with 2 or more items is split into X and Y in every way. A pair gives 2 rules, a triple gives 6. Three numbers describe a rule:
| Measure | Formula | It answers |
|---|---|---|
| support | count(X and Y) / all baskets | how often does the rule apply at all? |
| confidence | count(X and Y) / count(X) | of the baskets with X, what share also hold Y? |
| lift | confidence / support(Y) | how much more likely is Y with X than in general? |
No new pass over the baskets is needed: every count in these formulas was stored while mining, because X, Y and X ∪ Y are all frequent. A rule passes when its confidence reaches min confidence. At 30% support and 70% confidence, 8 of the 16 rules pass. (Demo 4: rules with support, confidence and lift)
Confidence is the conditional probability P(Y | X). See Bayes' Theorem for why P(Y | X) and P(X | Y) differ. Here Beer → Bread has confidence 4/4 = 100%, but Bread → Beer has only 4/8 = 50%: every Beer basket holds Bread, yet half the Bread baskets hold no Beer. (Demo 6: confidence has a direction, 100% vs 50%) Lift is the same in both directions.
High confidence can mislead: look at lift
Milk → Bread has confidence 3/4 = 75%, so it passes min confidence 70%. But Bread is in 8 of the 10 baskets. A random basket holds Bread 80% of the time, and a Milk basket only 75% of the time. Knowing that a customer bought Milk makes Bread slightly less likely. The rule looks strong only because Bread is popular.
Lift makes that comparison: lift = confidence / support(Y) = 75% / 80% = 0.94.
- lift above 1: Y is more likely with X than in general. Milk → Diapers has the same confidence, 75%, but Diapers is in only half the baskets, so its lift is 1.50.
- lift about 1: X and Y look independent; the rule tells nothing.
- lift below 1: X makes Y less likely.
(Demo 5: misleading rule, 75% confidence but lift 0.94) The page marks a rule that passes min confidence with lift not above 1 in yellow. With real data, a chi-square test can tell whether a lift near 1 is just noise. Even a high lift only shows that items are bought together, not that one causes the other; see correlation.
Related ideas
Apriori is unsupervised, like K-Means clustering: there is no label to predict, only patterns to find. A decision tree also produces if-then rules, but for one chosen target column. Baskets are sets, and MinHash and LSH find similar sets when comparing them one by one is too slow. The number of itemsets of each size is a row of Pascal's triangle: 6, 15, 20, 15, 6, 1 for six items.
What the page leaves out
Real data has thousands of items and millions of baskets. Then the counting pass is the cost, and Apriori stores the candidates in a hash tree or a trie so each basket is matched quickly. FP-Growth and Eclat find the same frequent itemsets without making candidates. Rule generation can also be pruned: if a rule from an itemset fails min confidence, rules that move more items to the right side fail too. Other measures (leverage, conviction), closed and maximal itemsets, and item hierarchies are not shown. Min support 20% is left out of the menu because its 54 rules do not fit the table.