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.

All itemsets of Bread, Milk, Diapers and Beer drawn as a lattice with single items on top and the 4-item set at the bottom. Ten sets are frequent and green. The pair Milk, Beer has count 2 and is red. Every set below it that contains Milk and Beer is dashed: it is never counted. Bread, Milk, Diapers is counted and has count 2.
One pair that is not frequent, {Milk, Beer}, removes every larger set that contains it before any counting.

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.

Four boxes in a row for level 3. Join: two frequent pairs that share an item make a 3-item candidate, 3 candidates. Prune: drop a candidate with a pair inside that is not frequent, 2 left. Count: read every basket once and add 1 for each candidate it holds, counts 2 and 3. Filter: keep candidates with count at least min support, 1 frequent. An arrow loops back from filter to join for the next level.
Level 3 on the page: 5 frequent pairs go in, 3 candidates are joined, 1 is pruned, 2 are counted and 1 is frequent.
  1. 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.
  2. Prune. Check every (k−1)-item subset of the candidate. If one is missing from Lk−1, drop the candidate.
  3. Count. Read every basket once. Add 1 to each candidate the basket holds.
  4. 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%)JoinedPrunedCountedFrequent
1: single items6065 (Eggs has count 2)
2: pairs100105
3: triples3121: {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 supportLevelsItemsets countedFrequent itemsetsRules
20% (2 baskets)4261954
30% (3 baskets)3181116
40% (4 baskets)21252
50% (5 baskets)2720

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:

MeasureFormulaIt answers
supportcount(X and Y) / all basketshow often does the rule apply at all?
confidencecount(X and Y) / count(X)of the baskets with X, what share also hold Y?
liftconfidence / 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.

Two panels. Left, Milk to Bread: 8 of all 10 baskets hold Bread, support 80 percent; 3 of the 4 baskets with Milk hold Bread, confidence 75 percent; lift 0.94, below 1. Right, Milk to Diapers: 5 of 10 baskets hold Diapers, support 50 percent; 3 of the 4 Milk baskets hold Diapers, confidence 75 percent; lift 1.50, above 1.
Two rules with the same confidence, 75%: compared with all baskets, one is worse than a guess and the other is 1.5 times better.

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.

On the mind map

Open the Machine Learning mind mapMachine LearningLearning setup: what feedback, how to scoreLearning setupLinear models: weighted sum w·x + bLinear modelsOther classic models: trees, margins, neighboursOther classic modelsUnsupervised: find structure without labelsUnsupervisedTraining: loss, gradient, small stepTrainingNeural networks: layers of σ(W·a + b)Neural networksArchitectures: how layers share informationArchitecturesLanguage models: predict the next tokenLanguage modelsLLM speed and tuning: cheaper to run, safer to useLLM speed and tuningRetrieval and agents: give the model data and toolsRetrieval and agentsK-meansK-meansassign to nearest centroid, move centroidK-Medoids and SilhouetteK-Medoids and SilhouetteReal points as centres; pick k by avg sApriori RulesSubset not frequent → skip the supersetDBSCANDBSCANgrow clusters from dense core pointsPCA vs t-SNEPCA vs t-SNEPCA keeps variance, t-SNE keeps neighboursk-means vs GMMk-means vs GMMhard circles vs soft covariance ellipsesEM algorithmEM algorithmE: soft labels, M: refit; ℓ never dropsHierarchical clusteringHierarchical clusteringMerge closest pair; cut the dendrogramMatrix factorization recsMatrix factorization recsRatings ≈ user vectors · item vectorsCollaborative FilteringCollaborative FilteringSimilar users' ratings fill the empty cellOpen the Machine Learning mind mapMachine Learningfind structure without labelsUnsupervisedK-meansK-meansassign to nearest centroid, move centroidK-Medoids and SilhouetteK-Medoids and SilhouetteReal points as centres; pick k by avg sApriori RulesSubset not frequent → skip the supersetDBSCANDBSCANgrow clusters from dense core pointsPCA vs t-SNEPCA vs t-SNEPCA keeps variance, t-SNE keeps neighboursk-means vs GMMk-means vs GMMhard circles vs soft covariance ellipsesEM algorithmEM algorithmE: soft labels, M: refit; ℓ never dropsHierarchical clusteringHierarchical clusteringMerge closest pair; cut the dendrogramMatrix factorization recsMatrix factorization recsRatings ≈ user vectors · item vectorsCollaborative FilteringCollaborative FilteringSimilar users' ratings fill the empty cell
This page on the Machine Learning mind map · 81 pages in 10 branches · open it to see the whole map and test yourself in recall mode.