Apriori Algorithm
Apriori is a classic algorithm for frequent itemset mining. It looks through transaction-style data and finds groups of items that occur together often enough to pass a minimum-support threshold.
Apriori in one sentence
Keep frequent combinations, discard infrequent combinations, and use that pruning to avoid checking many impossible larger combinations.
Apriori in Simple Words
Read Baskets
See which items appear in each transaction.
Count
Measure support for candidate itemsets.
Prune
Remove itemsets below minimum support.
Grow
Use surviving itemsets to build larger candidates.
Tiny supermarket example
| Transaction | Items |
|---|---|
| T1 | Bread, Milk |
| T2 | Bread, Butter |
| T3 | Milk, Butter |
| T4 | Bread, Milk, Butter |
| T5 | Bread, Milk |
Suppose minimum support is 50%. Apriori asks: which single items are frequent, which pairs are frequent, and can any larger combination still be frequent?
Frequent itemsets can later be used to create association rules for market-basket analysis, cross-selling ideas, web-usage patterns, and other co-occurrence analysis. Apriori itself is mainly the frequent-itemset mining stage; confidence and lift are used when evaluating rules generated from those itemsets.
The Apriori Property: Why Pruning Works
If an itemset is frequent, every subset of that itemset must also be frequent.
The downward-closure / Apriori property
The most useful way to apply this idea is its pruning form:
If {Bread, Butter} is infrequent...
{Bread, Milk, Butter} cannot be frequent.
So Apriori can prune the larger candidate instead of wasting work counting it.
Why is the property true?
Every transaction that contains {Bread, Milk, Butter} must also contain {Bread, Butter}. Therefore, a larger itemset can never occur more often than one of its subsets.
Key Terminologies
Item
One entity, such as Bread, Milk, Butter, a webpage, or a product ID.
Itemset
A set of one or more items, such as {Bread, Milk}.
Frequent Itemset
An itemset whose support is at least the chosen minimum-support threshold.
Candidate Itemset
A combination Apriori considers before deciding whether it is frequent.
Support
Support tells us what fraction of transactions contain an itemset.
Support(X) = Transactions containing X / Total transactions
Worked example: {Bread, Milk}
It appears in T1, T4 and T5 → 3 transactions.
Support = 3 / 5 = 0.60 = 60%
Minimum Support
Minimum support is the threshold that decides which itemsets are frequent. A high threshold can remove rare but potentially useful patterns; a very low threshold can create a large number of candidates. It is therefore a modeling/business choice rather than a universal constant.
After Apriori: Confidence and Lift
Apriori first returns frequent itemsets. If we then generate a rule such as Bread → Milk, metrics such as confidence and lift help evaluate that rule.
Confidence
Confidence(X → Y) = Support(X ∪ Y) / Support(X)
Bread support = 4/5 = 0.8
Bread + Milk support = 3/5 = 0.6
0.6 / 0.8 = 0.75
Lift
Lift(X → Y) = Confidence(X → Y) / Support(Y)
Confidence(Bread → Milk) = 0.75
Support(Milk) = 0.8
0.75 / 0.8 = 0.9375
Important interpretation
Confidence is 75%, but lift is below 1 because Milk is already very common in this tiny dataset. This is why a high-looking confidence value alone does not prove a useful positive association.
Apriori Step by Step
Complete Worked Example
Use the five transactions from the opening example and set minimum support = 50%.
Step 1 — Count 1-itemsets
Bread: 4 / 5 = 0.80 ✓
Milk: 4 / 5 = 0.80 ✓
Butter: 3 / 5 = 0.60 ✓
All three pass 0.50, so all three can participate in candidate pairs.
Step 2 — Generate and count candidate 2-itemsets
{Bread, Milk}: 3 / 5 = 0.60 ✓
{Bread, Butter}: 2 / 5 = 0.40 ✗
{Milk, Butter}: 2 / 5 = 0.40 ✗
Step 3 — Apply the Apriori property before counting a 3-itemset
Consider candidate {Bread, Milk, Butter}.
Two of its 2-item subsets — {Bread, Butter} and {Milk, Butter} — are already known to be infrequent.
Therefore the triple can be pruned without another support count.
Step 4 — Final frequent itemsets at 50% support
{Bread}, {Milk}, {Butter}, {Bread, Milk}
Why This Saves Work
With n distinct items there are 2n − 1 possible non-empty itemsets in the full search space. Apriori does not blindly enumerate all of them: minimum-support filtering and downward-closure pruning can remove large parts of the search space. The amount of work still depends strongly on the number of items, transaction density, and support threshold.
Python Implementation with mlxtend
A transaction list is first converted into a one-hot Boolean table. Apriori then returns frequent itemsets with their support values. Association rules are a separate next step.
Python Code: Apriori using mlxtend
# pip install pandas mlxtend
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules
# 1. Raw transactions
transactions = [
['Bread', 'Milk'],
['Bread', 'Butter'],
['Milk', 'Butter'],
['Bread', 'Milk', 'Butter'],
['Bread', 'Milk']
]
# 2. Convert baskets to a Boolean one-hot table
te = TransactionEncoder()
encoded = te.fit(transactions).transform(transactions)
df = pd.DataFrame(encoded, columns=te.columns_)
# 3. Mine frequent itemsets
frequent_itemsets = apriori(
df,
min_support=0.40,
use_colnames=True
)
# Make item names easy to read and output deterministic
display_itemsets = frequent_itemsets.copy()
display_itemsets['items'] = display_itemsets['itemsets'].apply(
lambda x: ', '.join(sorted(x))
)
print(
display_itemsets[['support', 'items']]
.sort_values(['support', 'items'], ascending=[False, True])
.to_string(index=False)
)
# 4. Generate rules AFTER frequent-itemset mining
rules = association_rules(
frequent_itemsets,
metric='confidence',
min_threshold=0.70,
num_itemsets=len(df)
)
rules['antecedent'] = rules['antecedents'].apply(
lambda x: ', '.join(sorted(x))
)
rules['consequent'] = rules['consequents'].apply(
lambda x: ', '.join(sorted(x))
)
print(
rules[['antecedent', 'consequent', 'support', 'confidence', 'lift']]
.sort_values(['antecedent', 'consequent'])
.round(3)
.to_string(index=False)
)Expected frequent itemsets
support items
0.8 Bread
0.8 Milk
0.6 Bread, Milk
0.6 Butter
0.4 Bread, Butter
0.4 Butter, MilkRules with confidence ≥ 0.70
antecedent consequent support confidence lift
Bread Milk 0.6 0.75 0.938
Milk Bread 0.6 0.75 0.938Why min_support = 0.40 in the code but 0.50 in the manual example?
The manual 50% example is designed to make Apriori pruning obvious. The code lowers support to 40% so the pair itemsets containing Butter remain available and learners can see more frequent-itemset output. Changing the threshold changes what Apriori returns.
Apriori vs FP-Growth
| Idea | Apriori | FP-Growth |
|---|---|---|
| Frequent-itemset strategy | Generate candidate itemsets, then prune | Compress transactions into FP-tree structures and avoid explicit candidate generation |
| Repeated passes | Classical Apriori makes repeated passes as itemset size grows | Designed to reduce repeated candidate-counting work |
| Which is faster? | Depends on dataset size, density, support threshold and implementation. FP-Growth often avoids Apriori's candidate explosion, but do not treat one method as universally faster in every situation. | |
Advantages
- Simple, interpretable frequent-itemset logic.
- The Apriori property provides intuitive and effective pruning.
- Useful for teaching association mining and for manageable transaction datasets.
- Support thresholds give direct control over what counts as frequent.
Limitations
- Low support thresholds can create very large candidate sets.
- Dense transaction data can make combinatorial growth severe.
- Classical Apriori may require repeated scans/counting passes.
- Frequent co-occurrence does not imply causation or business value.
Where Apriori-Style Analysis Can Help
Market Basket Analysis
Find products that frequently co-occur in baskets.
Cross-Sell Exploration
Generate candidate product combinations for later validation.
Web Usage Mining
Find pages or actions that often occur in the same sessions.
Operational Pattern Mining
Explore recurring combinations of events or categorical conditions.
Common Mistakes
Counting a candidate that should already be pruned
If any required subset is infrequent, use the Apriori property and discard the larger candidate.
Thinking Apriori itself is the association rule
Apriori mines frequent itemsets. Rules and metrics such as confidence/lift come afterwards.
Assuming high confidence means a strong positive association
Always compare against the consequent baseline; lift can reveal that a high confidence is unsurprising.
Choosing minimum support mechanically
Threshold choice changes both computation and which patterns can be discovered.
Treating a rule as causal
Bread → Milk is a co-occurrence pattern, not proof that Bread causes Milk purchases.
Quick Recap
If {A, B} is infrequent, should Apriori test {A, B, C} as a frequent candidate?
No. Because {A, B} is a subset of {A, B, C}, the larger itemset cannot be frequent.
What does minimum support control?
It controls the minimum transaction frequency required for an itemset to be considered frequent.
Does Apriori directly prove that one product causes another purchase?
No. It discovers frequent co-occurrence patterns. Association is not causation.
Final Summary
Apriori mines frequent itemsets by repeatedly generating candidates, measuring support and pruning combinations that cannot satisfy the minimum-support requirement.
Its key insight is the downward-closure property: if a smaller itemset is infrequent, every larger itemset containing it must also be infrequent. This turns a potentially huge combination search into a more manageable pruning process when the data and support threshold allow it.
Remember
Apriori answers: “Which item combinations occur frequently enough to keep exploring?” Association-rule metrics answer the next question: “Which of the resulting rules are interesting enough to examine?”
Related lesson
Association Rules → Support, Confidence and Lift