How Apriori finds patterns in everyday transactions
Apriori is a foundational algorithm for association-rule discovery. It searches a transaction database for groups of items that occur together often enough to matter under a minimum support threshold. In market-basket analysis, a transaction might represent one supermarket visit, while an itemset might contain tea, milk and biscuits. Apriori ignores purchase order and reports co-occurrence rather than causation, leaving domain experts to judge whether a pattern is useful.
Understanding the Apriori algorithm means understanding three linked ideas: support, candidate generation and the downward closure of frequent itemsets. A worked example uses six baskets from a Melbourne grocer, and a Python implementation builds the algorithm from scratch. Privacy and consumer-law duties shape how Australian retailers may use the output, while comparisons with denser algorithms and sequence models show where the assumptions matter. The result is a practical mental model for baskets, clickstreams, inventory and course-choice data.
Why frequent itemset mining matters for Australian retail
Australian supermarkets such as Coles and Woolworths, together with independent grocers, create datasets shaped by local habits. A weekly shop may combine pantry staples, fresh produce, household goods and an impulse purchase; shoppers may also divide spending between a large supermarket and a neighbourhood store. In Sydney, Melbourne and Brisbane, the same products can appear across many baskets, while store layout, stock and promotions influence what is actually bought.
Market-basket analysis uses frequent itemsets to expose stable combinations and then evaluates rules with confidence and lift. A rule such as tea to milk states that milk appears in a given share of tea baskets; lift compares that share with milk’s overall frequency. If the objective is instead to group shoppers by continuous features such as spend and visit frequency, soft clustering with Gaussian mixture models answers a different question more directly.
Frequent itemset analysis can answer several kinds of practical questions:
- Repeat demand: Which products consistently appear in the same transaction?
- Complementary pairs: Which items could support a relevant cross-promotion?
- Unexpected combinations: Which pairs exceed what the marginal frequencies would suggest?
- Stable segments: Which patterns persist across stores, suburbs or seasons?
- Testable hypotheses: Which findings deserve controlled trials rather than immediate deployment?
The Apriori principle and candidate pruning
Each transaction is treated as a set, so duplicate units of one product do not change its support. For an itemset (A), support is the number of transactions containing every member of (A), divided by the total number of transactions. The threshold should reflect both statistical rarity and business value: 0.01 may reveal a meaningful wholesale pattern, whereas 0.01 in a small grocery sample may reflect only two baskets.
The Apriori principle is anti-monotonicity. If an itemset is infrequent, every larger itemset containing it must also be infrequent, because adding items cannot increase the number of matching transactions. Consequently, the algorithm generates candidates by joining frequent itemsets from the previous level, counts them against the database, and prunes those below the threshold. Only survivors are extended, preventing an enormous tree of mostly impossible patterns.
F1 = itemsets of size 1 with support >= min_support
F = F1
while Fk contains frequent itemsets:
Ck+1 = join candidates from Fk
Fk+1 = candidates with support >= min_support
F = F union Fk+1
Each pass creates a larger level of itemsets and ends when no candidate survives. The number of possible itemsets is (2^m - 1) for (m) distinct products, so threshold choice and pruning are central to performance. Sparse baskets usually limit candidate growth, while dense data can make repeated database scans expensive. Keeping support counts in integer form and using sparse data structures helps memory use without changing the result.
A worked example from a Melbourne grocer
Consider six anonymised baskets from a Melbourne grocer. Five contain coffee, four contain tea, four contain milk, and one contains biscuits. Basket one contains coffee, tea and milk; basket two contains coffee and tea; basket three contains coffee and biscuits; basket four contains tea and milk; basket five again contains coffee, tea and milk; basket six contains coffee and milk. Repetition here represents repeated shopping patterns, not repeated visits by the same person.
With a minimum support of 0.50, coffee, tea and milk survive as singletons. Coffee and tea occur together in three baskets, as do coffee and milk and tea and milk, so all three pairs also reach 0.50 support. The triple coffee, tea and milk occurs in only two baskets, giving support 0.33, and is pruned. Biscuit pairs fall below the threshold and are discarded. This is the Apriori pruning rule operating on a tiny database.
Rules are derived after the frequent itemsets are known. For tea to milk, confidence is 0.50 divided by 0.67, or 0.75, so milk appears in 75% of tea baskets. Lift is 0.75 divided by milk’s 0.67 baseline, approximately 1.13, indicating a modest positive association. That does not prove tea causes milk purchases; price, discounts and the grocer’s layout may explain it. For many Australian retailers, loyalty information is also governed by the Privacy Act 1988 and Australian Privacy Principles. De-identifying records reduces risk but does not remove every duty, while claims attached to a promotion must still comply with the Australian Consumer Law.
Implementing Apriori in Python
A compact implementation can use Python sets for transactions and frozensets for frequent itemsets. This choice is deliberate: the Python data model explains how equality and hashing determine whether an object can serve as a dictionary key. The code below generates each next level, counts candidate containment and returns every surviving itemset with its support.
from collections import Counter
from itertools import combinations
def apriori(transactions, min_support):
rows = [set(row) for row in transactions]
if not rows:
return {}
n = len(rows)
counts = Counter(item for row in rows for item in row)
frequent = {
frozenset([item]): count / n
for item, count in counts.items()
if count / n >= min_support
}
level = set(frequent)
while level:
candidates = set()
ordered = sorted(level, key=lambda s: tuple(sorted(s)))
for left, right in combinations(ordered, 2):
merged = left | right
if len(merged) == len(left) + 1:
candidates.add(merged)
counts = Counter()
for row in rows:
for candidate in candidates:
if candidate <= row:
counts[candidate] += 1
next_level = {
candidate: count / n
for candidate, count in counts.items()
if count / n >= min_support
}
frequent.update(next_level)
level = set(next_level)
return frequent
After calling apriori with the sample baskets and a threshold of 0.50, the result contains the three singletons and three frequent pairs, but not the triple. A production version should validate the threshold, remove empty transactions where appropriate and check that item identifiers are consistent across files. It should also return counts, not only proportions, so analysts can distinguish a pattern supported by two rows from one supported by millions.
Testing matters because implementation details can hide subtle errors. Use a small transaction set whose counts can be checked by hand, then compare results with an independent counter for one-item and two-item sets. Measure runtime and memory as the vocabulary and basket density grow. Analysing recent data can also reveal seasonal shifts that would make a rule from an older sample misleading.
Extending and validating the analysis
Apriori has clear boundaries. It is order-blind, struggles with very sparse items and can generate many candidates when a catalogue contains many frequently purchased products. A high-support rule may also be profitable to ignore, while a less frequent pair may matter more to a particular category manager. The appropriate threshold therefore comes from domain costs and validation data, not from a default percentage copied from a tutorial.
Other algorithms answer specialised versions of the question. FP-growth encodes transactions into a compact tree and can avoid some repeated scans, while Eclat uses item and itemset intersections. For order-sensitive data, such as products added during a Sydney train journey, recurrent models such as LSTM networks can learn temporal dependencies, though they predict sequences rather than merely enumerate co-occurrences. A constrained miner can also enforce limits such as a minimum basket value or an excluded product combination.
Several extensions preserve the core logic while addressing practical requirements:
- Sequence mining: Preserve event order when timing changes the meaning of a basket.
- Constrained mining: Require revenue, margin or category limits during candidate generation.
- Frequent-pattern variants: Compare Apriori with FP-growth or Eclat on the same transaction set.
- Customer segmentation: Combine basket summaries with behavioural or demographic features.
- Drift monitoring: Re-estimate support as prices, seasons and customer habits change.
The lasting value of Apriori is its transparent logic: count what occurs, extend surviving patterns and prune the rest. That simplicity makes it a strong baseline for teaching, prototyping and small-to-medium transaction datasets, while its assumptions clearly show where denser algorithms, constrained mining or temporal models are needed.