Definition
Apriori finds every frequent itemset in a database of transactions — every set of items that appears together in at least a fraction of the baskets — by searching level by level: frequent 1-itemsets, then 2-itemsets built from them, then 3-itemsets, and so on. It then turns frequent itemsets into association rules such as {Bread, Jam} ⇒ {Butter}, kept when their confidence is high enough.
At a glance
- Task
- Unsupervised pattern mining: frequent itemsets and association rules
- Input → output
- a list of transactions (sets of items) → all itemsets with support , plus rules with confidence
- Learns
- no parameters — it enumerates patterns; the "model" is the list of itemsets and rules with their support, confidence and lift
- Training cost
- one database scan per level; total work subset tests — exponential in the worst case, practical when keeps small
- Prediction cost
- look up rules whose antecedent is contained in a basket: subset checks, or a hash lookup
- Hyperparameters
- minimum support , minimum confidence , maximum itemset length; ranking metric (lift, leverage, conviction)
- Assumes
- items are binary (present / absent) — no quantities, no order; patterns worth knowing are frequent
The problem
A shop logs millions of baskets and wants to know which products are bought together — to place them on the same shelf, bundle them, or recommend one when the other is in the cart. With products there are possible itemsets. Counting all of them is hopeless: for that is about sets, and even the pairs alone for a 10,000-product catalogue number 49,995,000 — each one needing a pass over the data to count.
Supervised methods do not help: there is no label to predict, and we want every strong co-occurrence, not one decision function. What we need is an exact way to skip the overwhelming majority of itemsets without counting them — while still guaranteeing that every frequent one is found.
The idea
If {Bread, Jam, Milk} appears in at least 3 baskets, then {Jam, Milk} certainly appears in at least those same 3 baskets — a basket that contains the bigger set contains every part of it. Turned around: if {Jam, Milk} is rare, every set that contains it is at least as rare. So once we learn that one small itemset is infrequent, we can delete its entire family of supersets from the search, unseen.
Apriori exploits this level by level. Count single items; keep the frequent ones. Build 2-item candidates only from frequent items; count them; keep the frequent ones. Build 3-item candidates only from frequent pairs — and before counting, throw away any candidate that has an infrequent pair inside it. Repeat until no candidates remain. Each level needs one scan of the database, and the name says it all: knowledge from the previous level is used a priori to prune the next.
Vocabulary
- Item
- one product / event / token, e.g. Bread
- Transaction (basket)
- one set of items bought together, ; the database is a list of of them
- Itemset, k-itemset
- any set of items ; a -itemset has exactly items
- Support count
- = number of transactions that contain all of
- Support
- , the fraction of baskets containing
- Frequent itemset
- an itemset with the minimum support; = all frequent -itemsets
- Candidate set
- = the -itemsets Apriori will actually count at level
- Downward closure (Apriori property)
- every subset of a frequent itemset is frequent; equivalently, every superset of an infrequent itemset is infrequent
- Rule A ⇒ C
- antecedent and consequent , disjoint itemsets: baskets with tend to contain
- Lattice
- all itemsets arranged by size, with an edge from each set to its supersets one item bigger
The math
Let be the transactions over item set . The support of an itemset counts the transactions that cover it:
- an itemset
- support count: number of transactions containing every item of X
- number of transactions
- below: the set of transactions covering (its tidset)
Deriving the Apriori property. Take . Any transaction that contains contains every item of , hence every item of . So the covering sets are nested, and their sizes follow:
- set of transactions covering an itemset
- support is anti-monotone: adding items can never raise it
The contrapositive is the pruning rule: if then for every . Hence a -itemset can only be frequent if all of its -subsets are in , and the candidates at level can be restricted to:
- the first k−2 items of p, with items kept in one fixed (e.g. alphabetical) order
- join: two frequent (k−1)-sets with the same prefix give one k-set
- prune: drop candidates that have an infrequent (k−1)-subset
The join is complete: any frequent -itemset has the two frequent subsets and , which share their first items — so it is always generated. And it never generates the same candidate twice, because the shared prefix and the two last items determine the pair.
Rules. From a frequent itemset and a non-empty proper subset , form with . Its strength is measured by:
- fraction of baskets with A that also contain C — an estimate of P(C | A)
- how much more often A and C co-occur than if they were independent; 1 = independent, > 1 = positive association
- baseline rate of the consequent
- leverage: excess co-occurrence over independence, in absolute support units
- conviction: how much more often the rule would be wrong if A and C were independent; ∞ for a rule that is never wrong
Rule generation has its own anti-monotone property. For a fixed itemset , . Moving an item from the antecedent to the consequent makes the antecedent smaller, so its support grows (Apriori property) and the confidence can only fall. If fails the confidence threshold, so do and — consequents can be grown level by level too.
What the two thresholds do
- Minimum support σ
- sets the pruning power. Lowering it can only add frequent itemsets (the set grows as falls), and the number of candidates — and runtime — grows roughly exponentially as patterns get longer. Raising it removes rare but possibly interesting combinations.
- Minimum confidence γ
- only filters rules after mining; it costs nothing at the expensive itemset stage. High keeps reliable rules, but confidence ignores the base rate , so it must be read together with lift.
- Maximum length
- stops the level loop at ; caps the worst case at candidates.
Worked example: ten breakfast baskets
Five items — Bread, bUtter, Jam, Milk, Eggs — in ten baskets. Minimum support is 30% (a count of 3), minimum confidence 0.7. Items are kept in the fixed order B < U < J < M < E for the join.
| Basket | Items | Letters |
|---|---|---|
| T1 | Bread, Butter, Jam | B U J |
| T2 | Bread, Butter, Jam | B U J |
| T3 | Bread, Butter, Jam, Eggs | B U J E |
| T4 | Bread, Butter, Milk | B U M |
| T5 | Bread, Butter, Milk | B U M |
| T6 | Bread, Milk | B M |
| T7 | Butter, Milk, Eggs | U M E |
| T8 | Jam, Milk | J M |
| T9 | Bread, Milk | B M |
| T10 | Butter, Jam | U J |
Apriori by hand (minimum support count 3)
- 1Scan 1, count items. B 7, U 7, J 5, M 6, E 2. Eggs falls below 3, so — and the 15 larger itemsets containing E are dead without being looked at.
- 2Join . Every pair of frequent items: — 6 candidates instead of the 10 possible pairs. At the prune step removes nothing (both 1-subsets are in by construction).
- 3Scan 2, count pairs. BU 5, BJ 3, BM 4, UJ 4, UM 3, JM 1. So ; only Jam + Milk is rare.
- 4Join (same first item): BU+BJ → BUJ, BU+BM → BUM, BJ+BM → BJM, UJ+UM → UJM.
- 5Prune. BJM contains JM and UJM contains JM — not in , so both are deleted without counting. .
- 6Scan 3. BUJ 3 (T1, T2, T3), BUM 2 (T4, T5). .
- 7Join . A single itemset has no partner, so and the search stops after 3 scans. In total 13 itemsets were counted out of 31, and 10 are frequent.
| Level k | Joined | Pruned | Counted (support) | Frequent Lₖ |
|---|---|---|---|---|
| 1 | 5 | 0 | B 7 · U 7 · J 5 · M 6 · E 2 | B, U, J, M |
| 2 | 6 | 0 | BU 5 · BJ 3 · BM 4 · UJ 4 · UM 3 · JM 1 | BU, BJ, BM, UJ, UM |
| 3 | 4 | 2 (BJM, UJM) | BUJ 3 · BUM 2 | BUJ |
| 4 | 0 | — | — | ∅ → stop |
Rules. Each frequent itemset of size yields candidate rules. From BUJ (support 3): has confidence ; ; and ; and . From the pairs: , and , everything else below 0.7. Five rules pass:
| Rule | Support | Confidence | Lift | Leverage | Conviction |
|---|---|---|---|---|---|
| {Bread, Jam} ⇒ {Butter} | 0.30 | 1.000 | 1.429 | 0.09 | ∞ |
| {Jam} ⇒ {Butter} | 0.40 | 0.800 | 1.143 | 0.05 | 1.50 |
| {Butter, Jam} ⇒ {Bread} | 0.30 | 0.750 | 1.071 | 0.02 | 1.20 |
| {Bread} ⇒ {Butter} | 0.50 | 0.714 | 1.020 | 0.01 | 1.05 |
| {Butter} ⇒ {Bread} | 0.50 | 0.714 | 1.020 | 0.01 | 1.05 |
A new basket. A customer has {Bread, Jam} in the cart. The applicable rules are those whose antecedent is inside the cart and whose consequent is not: (confidence 1.00, lift 1.43) is the strongest, so we recommend Butter. Note the bottom two rows: Bread ⇒ Butter has 71% confidence, which sounds strong, but its lift is 1.02 — Butter is in 70% of all baskets anyway, so knowing Bread is there tells us almost nothing.
- 1L₁ ← items with count ≥ minsup
- 2for k = 2, 3, … while Lₖ₋₁ ≠ ∅:
- 3 Cₖ ← join pairs of Lₖ₋₁ that
- 4 share their first k−2 items
- 5 drop c ∈ Cₖ with an infrequent
- 6 (k−1)-subset
- 7 scan: count(c) for every c ∈ Cₖ
- 8 Lₖ ← { c : count(c) ≥ minsup }
- 9for each frequent X and A ⊂ X:
- 10 keep A → X∖A if s(X)/s(A) ≥ minconf
10 baskets over 5 items, so there are 2⁵ − 1 = 31 possible itemsets. Minimum support = 3 baskets (30%); minimum confidence = 0.7.
The algorithm, step by step
Apriori(D, σ, γ)
- 1Level 1. One scan of counts every item; = items with count .
- 2Join. For : sort each itemset in by a fixed item order; merge every pair that agrees on its first items into a -itemset.
- 3Prune. Delete any candidate with a -subset not in (store in a hash set, so each check is lookups).
- 4Count. One scan of : for every transaction, increment every candidate it contains (a hash tree or trie over finds them without testing all candidates).
- 5Filter. . Stop when (or ) is empty.
- 6Rules. For each frequent with and each non-empty , output if . All supports are already known — no more scans.
Complexity
- Database scans
- at most, where is the length of the longest frequent itemset
- Counting
- level costs about subset tests, = average basket width; this dominates
- Candidate generation
- for the join, hash lookups for the prune
- Memory
- all of with counters must fit in memory; is usually the peak
- Worst case
- a frequent itemset of length forces all of its proper subsets to be frequent — e.g. for — so long patterns are inherently expensive
Variants and practical tuning
| Variant | Change | Helps when |
|---|---|---|
| AprioriTid | after scan 1, replace each transaction by the candidates it contains | later levels: the encoded database shrinks fast |
| DHP (hash-based) | while counting items, hash all pairs into buckets; a pair in a light bucket can't be frequent | C₂ is huge — the usual bottleneck |
| Transaction reduction | drop baskets that contain no frequent k-itemset from later scans | many short baskets |
| Partitioning | mine each chunk locally; any globally frequent set is frequent in some chunk; one verification scan | data does not fit in memory; 2 scans total |
| Sampling (Toivonen) | mine a sample at a lowered threshold, then verify on the full data | approximate answers are fine, scans are costly |
| FP-Growth / Eclat | no level-wise candidate generation at all | low support, dense data, long patterns |
Tuning in practice
- Start high, lower slowly
- begin with a support that yields a few hundred itemsets (e.g. 1–5% of baskets for retail) and halve it while runtime and output size stay manageable
- Rank by lift, not confidence
- filter by a modest confidence, then sort by lift or leverage; drop rules with lift ≤ 1
- Cap the length
max_len=3or 4 is often enough for actionable rules, and caps the worst case- Aggregate items
- rare SKUs never reach support; mining at the category level (all jams → Jam) finds patterns hidden at product level
- Check stability
- re-mine on a different month or a bootstrap sample; rules that vanish were noise
In code
1import numpy as np2from itertools import combinations34def apriori(X, items, min_support):5 """X: boolean (n_transactions, n_items). Returns {itemset (tuple of col idx): support count}."""6 n = X.shape[0]7 min_count = int(np.ceil(min_support * n))8 counts = X.sum(axis=0)9 L = {(j,): int(c) for j, c in enumerate(counts) if c >= min_count}10 frequent, k, counted = dict(L), 2, X.shape[1]11 while L:12 prev = sorted(L)13 # join: two (k-1)-itemsets sharing their first k-2 items14 cands = [a + (b[-1],) for a, b in combinations(prev, 2) if a[:-1] == b[:-1]]15 # prune: every (k-1)-subset must be frequent16 prevset = set(prev)17 cands = [c for c in cands if all(s in prevset for s in combinations(c, k - 1))]18 counted += len(cands)19 # count: a transaction contains c iff all its columns are 120 L = {}21 for c in cands:22 s = int(X[:, list(c)].all(axis=1).sum())23 if s >= min_count:24 L[c] = s25 frequent.update(L)26 k += 127 return frequent, counted2829def rules(frequent, n, min_conf):30 out = []31 for iset, s in frequent.items():32 for r in range(1, len(iset)):33 for A in combinations(iset, r):34 C = tuple(i for i in iset if i not in A)35 conf = s / frequent[A]36 if conf >= min_conf:37 lift = conf / (frequent[C] / n)38 out.append((A, C, s / n, conf, lift))39 return out4041items = ["Bread", "Butter", "Jam", "Milk", "Eggs"]42baskets = ["BUJ", "BUJ", "BUJE", "BUM", "BUM", "BM", "UME", "JM", "BM", "UJ"]43code = {"B": 0, "U": 1, "J": 2, "M": 3, "E": 4}44X = np.zeros((len(baskets), len(items)), dtype=bool)45for i, b in enumerate(baskets):46 X[i, [code[ch] for ch in b]] = True4748freq, counted = apriori(X, items, min_support=0.3)49print("candidates counted:", counted, "of", 2 ** len(items) - 1) # 13 of 3150for iset, s in sorted(freq.items(), key=lambda kv: (len(kv[0]), kv[0])):51 print([items[j] for j in iset], s) # ... ['Bread', 'Butter', 'Jam'] 352for A, C, sup, conf, lift in rules(freq, len(baskets), 0.7):53 print([items[j] for j in A], "->", [items[j] for j in C], f"sup={sup:.2f} conf={conf:.3f} lift={lift:.3f}")54# ['Bread', 'Jam'] -> ['Butter'] sup=0.30 conf=1.000 lift=1.429 (and 4 more)1import pandas as pd2from mlxtend.preprocessing import TransactionEncoder3from mlxtend.frequent_patterns import apriori, association_rules45baskets = [6 ["Bread", "Butter", "Jam"], ["Bread", "Butter", "Jam"], ["Bread", "Butter", "Jam", "Eggs"],7 ["Bread", "Butter", "Milk"], ["Bread", "Butter", "Milk"], ["Bread", "Milk"],8 ["Butter", "Milk", "Eggs"], ["Jam", "Milk"], ["Bread", "Milk"], ["Butter", "Jam"],9]10te = TransactionEncoder()11X = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_) # one-hot booleans1213freq = apriori(X, min_support=0.3, use_colnames=True) # optionally max_len=314print(freq.sort_values("support", ascending=False).to_string(index=False))1516rules = association_rules(freq, metric="confidence", min_threshold=0.7)17print(rules[["antecedents", "consequents", "support", "confidence", "lift", "leverage", "conviction"]]18 .sort_values("lift", ascending=False).round(3).to_string(index=False))19# antecedents consequents support confidence lift leverage conviction20# (Jam, Bread) (Butter) 0.3 1.000 1.429 0.09 inf21# (Jam) (Butter) 0.4 0.800 1.143 0.05 1.5022# (Jam, Butter) (Bread) 0.3 0.750 1.071 0.02 1.2023# (Bread) (Butter) 0.5 0.714 1.020 0.01 1.0524# (Butter) (Bread) 0.5 0.714 1.020 0.01 1.05Use when
- +You need every frequent itemset exactly, with an easy-to-explain algorithm and output ("bought together in 30% of baskets").
- +Support is moderately high and patterns are short — sparse retail baskets, click sets, symptom lists.
- +Data lives in a database where one scan per level is cheap (SQL GROUP BY per level works).
- +You want the candidate counts and supports themselves, e.g. to compute any rule metric afterwards.
Avoid when
- −Minimum support must be very low (rare but valuable items) — candidate sets explode.
- −Data is dense or patterns are long: all 2^m − 2 subsets of a long pattern must be generated and counted.
- −The database is huge and each scan is expensive — FP-Growth needs two scans, Eclat one.
- −Items have quantities, order or time — use sequential pattern mining or a supervised model instead.
Where it's used
Market-basket analysis
Shelf placement, bundles and "frequently bought together" in retail and e-commerce.
Recommendation seeds
Rules with high lift give cheap, explainable item-to-item recommendations.
Medical and pharmacovigilance data
Co-occurring diagnoses, or drug combinations that appear with adverse events more than expected.
Web usage and log mining
Pages visited in one session, or alarm codes that fire together in system logs.
Check yourself
In some database, {A, C} has support 0.3, {A} 0.4 and {C} 0.5. What are the confidence and lift of A ⇒ C?
Check yourself
L₂ = {AB, AC, AD, BC, CD} (items ordered A < B < C < D). Which candidates survive the join and prune into C₃?
Check yourself
Apriori finds that {Jam, Milk} appears in only 1 of 10 baskets (min count 3). What can it conclude about {Bread, Jam, Milk} without scanning?
Check yourself
{Bread, Jam} ⇒ {Butter} has confidence 1.0. Without any counting, what do we know about {Jam} ⇒ {Bread, Butter}?
Remember
- ✓Support is anti-monotone: . Every superset of an infrequent itemset is infrequent.
- ✓Apriori is level-wise: join frequent -itemsets sharing items, prune any candidate with an infrequent subset, then count the survivors in one scan.
- ✓On the 10-basket example it counts 13 of 31 itemsets in 3 scans and finds 10 frequent ones; BJM and UJM are pruned without counting.
- ✓Rules come from frequent itemsets for free: confidence = s(A∪C)/s(A). Always check lift, because confidence ignores how common the consequent already is.
- ✓Minimum support controls the cost; low support or long patterns blow up candidate sets — then use FP-Growth or Eclat.