Data Science & Machine Learning — Article 32

Apriori Algorithm: A Comprehensive Guide

Explore detailed Apriori Algorithm

Data Science & Machine Learning — Article 32

Introduction

How do you find the frequent itemsets in the first place?

With 40 items there are over a trillion subsets, and counting them individually is not an option.

Apriori was the 1994 answer, and it remains the clearest. It works level by level, generating candidates of size k only from confirmed frequent itemsets of size k-1, so entire regions of the search space are never visited.

Table of Contents

• Introduction
• Table of Contents
• What is Apriori Algorithm
• Core Components of Apriori Algorithm
• Mathematical Foundation
• Types of Apriori Algorithm
• Evaluation Metrics
• Selecting Evaluation Metrics
• Assumptions and Practical Considerations

What is Apriori Algorithm

Definition

Apriori is a level-wise algorithm for mining frequent item sets, which at each level generates candidate k-item sets by joining frequent (k-1)-item sets, discards candidates having any infrequent subset, and counts the survivors in a single database scan.

Why it is needed

• The itemset space is 2ⁿ — 1, so exhaustive counting is impossible beyond trivial n.
• Downward closure, proven in Article 32, gives a sound basis for skipping candidates without counting them.
• Level-wise structure means each level needs exactly one database scan, so the number of scans equals the size of the largest frequent itemset.
• It is the conceptual foundation the alternatives in Articles 34 and 35 are measured against.

Where it is used

Real world analogy

Consider searching a library for books that mention both a rare author and a rare topic. Rather than checking every book, you first find the shelf list for the author, then check only those books for the topic. If the author appears in no book at all, you skip the topic search entirely.

Apriori formalizes that: never look for a larger pattern when a smaller part of it is already known to be absent.

Key characteristics

• Level-wise, or breadth-first, processing all k-itemsets before any (k+1)-itemsets.
• Candidate generate-and-test, which is its defining structure and its main weakness.
• Horizontal data layout, meaning one row per transaction.
• One database scan per level, so the scan count equals the longest frequent itemset.
• Complete and correct. It finds every frequent itemset, with no approximation.

The two pruning mechanisms, which are distinct

These are frequently described as one thing. They are not, and Section 5.6 measures how much each contributes. The result is not what most treatments imply.

Core Components of Apriori Algorithm

Candidate Itemsets

• Purpose: the sets whose support might need counting at the current level.
• Function: denoted Cₖ, produced by joining then pruning.
• Relationship: the algorithm’s cost is driven almost entirely by ∣ Cₖ∣, so both pruning mechanisms exist to shrink it.
• Practical example: 6 candidate pairs generated from 4 frequent items.

Frequent Itemsets

• Purpose: the output, and the input to the next level.
• Function: denoted Fₖ or Lₖ, the candidates whose support met the threshold.
• Relationship: Fₖ is the only source of Cₖ₊₁, which is what makes the algorithm level-wise.
• Practical example: 6 frequent pairs surviving from 6 candidates.

The Join Step

• Purpose: generates candidates without duplicates.
• Function: combines two (k-1)-itemsets when their sorted forms share the first k-2 items and differ in the last.
• Relationship: the shared-prefix condition is itself a pruning mechanism, not merely a bookkeeping device, and Section 5.6 shows it doing more work than expected.
• Practical example: beer, bread joins beer, diaper to give beer, bread, diaper.

The Prune Step

• Purpose: removes candidates that cannot possibly be frequent.
• Function: checks that every (k-1)-subset of a candidate is in Fₖ₋₁.
• Relationship: applies the contrapositive of downward closure from Article 32 Section 5.4.
• Practical example: discarding beer, cola, eggs because cola, eggs is infrequent.

Support Counting

• Purpose: determines which candidates are frequent.
• Function: one pass over the database, testing every candidate against every transaction.
• Relationship: the dominant runtime cost, which is why avoiding candidates matters more than counting them faster.
• Practical example: counting 6 candidates in one scan of 10 transactions.

Minimum Support Threshold

• Purpose: controls the output size and the search cost.
• Function: the count or fraction an itemset must reach.
• Relationship: lowering it increases both the frequent itemset count and the candidate count superlinearly.
• Practical example: min_support = 0.3 giving 12 frequent itemsets, 0.1 giving 35.

Hash Tree or Trie

• Purpose: accelerates the subset test during counting.
• Function: stores candidates in a structure so that finding which candidates a transaction contains does not require testing all of them.
• Relationship: an implementation optimization that does not change which itemsets are found.

• Practical example: hashing candidate prefixes so a transaction only probes relevant branches.

Mathematical Foundation

Variables

Formula

Support, as in Article 32:

Downward closure, the foundation:

The contrapositive, which is the usable form:

The join step:

where itemsets are stored in sorted order and pᵢ denotes the ith item.

The prune step:

Database scans required:

Worst-case candidate count at level 2, when every item is frequent:

Mathematical Intuition

Five ideas explain the algorithm:

• The whole method rests on one monotonicity property. Support decreases as itemsets grow, so infrequency propagates upward. Without that, no pruning would be sound and the search would be exhaustive.
• The join uses a sorted-prefix condition to avoid duplicates. Generating a, b, c from a, b+a, c only, rather than also from a, c+b, c and a, b+b, c, means each candidate is produced exactly once. Requiring pₖ₋₁ < qₖ₋₁ enforces that.
• The join is a stronger filter than it appears. A candidate can only form if two of its (k-1)-subsets are frequent and share a prefix. Section 5.6 measures the consequence, which is surprising.
• The prune step catches the remainder. The join guarantees two subsets are frequent; the prune checks the other k-2. Both steps are needed for completeness of the filtering, though not for correctness of the result.
• Cost is dominated by candidate count, not by counting speed. Each level scans the whole database once, so the useful lever is generating fewer candidates rather than testing them faster.

Step by Step Derivation

Two things deserve deriving: why the join is complete, and the scan count.

Join completeness

Step 1: Suppose Y is a frequent k-itemset, written in sorted order as y₁ < y₂ < ⋯ < yₖ. We must show the join generates it, or the algorithm would miss it.

Step 2: Consider the two (k-1)-subsets obtained by dropping the last and second-to-last items:

Step 3: Both are subsets of Y, and Y is frequent, so by downward closure both are frequent. Hence P, Q ∈ Fₖ₋₁.

Step 4: They share their first k-2 items by construction, and their last items satisfy yₖ₋₁ < yₖ.

Step 5: So the join condition is met exactly, and P ∪ yₖ = Y is generated.

Step 6: Note what this proves. The join is complete, meaning it never misses a frequent itemset. It is not sound, meaning it generates candidates that turn out infrequent. That is why the prune and count steps follow.

Prune soundness

Step 7: The prune step discards c when some (k-1)-subset S ⊂ c has S ∉ Fₖ₋₁, meaning supp(S) < s.

Step 8: By downward closure, S ⊂ c implies supp(c) ≤ supp(S) < s.

Step 9: So c is infrequent and discarding it loses nothing.

Scan count

Step 10: Level 1 requires one scan to count all single items. Each subsequent level k with a non-empty candidate set requires one more.

Step 11: The algorithm terminates when Fₖ is empty, or earlier when Cₖ is empty by generation. So:

Step 12: In the best case this is ℓ, the size of the largest frequent itemset, since generation may produce nothing at level ℓ+1. Section 5.5 shows exactly that: 3 scans for a largest frequent itemset of size 3.

Which Pruning Mechanism Actually Works?

The closure prune step never fired. At levels 2 and 3 it discarded nothing. Every candidate the join produced was counted. And at level 4 the candidate was eliminated by the join failing, not by the prune.

So on this dataset at s = 0.3, the prefix-join condition did all the filtering. The famous downward-closure prune contributed zero.

Why? Because every frequent pair was frequent. When F₂ contains all C(∣F₁∣, 2) pairs, every triple’s subsets are automatically available, so nothing can fail the subset check.

The prune step only earns its place when the frequent itemsets are sparse within their level.

Lowering the threshold makes it fire. At s = 0.1, so σ = 1, the rare items cola and eggs survive level 1 and the picture changes:

Now the prune step avoids 9 support counts. Examples of what it caught:

Each of these has a subset with support zero, and the prune step eliminated them without a single database access.

The honest summary. Both mechanisms matter, but their relative contribution depends on the data and threshold:

• At high support, few items survive level 1, most surviving pairs are frequent, and the join does the filtering.
• At low support, many items survive, frequent itemsets become sparse within each level, and the closure prune becomes essential.

Reporting “Apriori works by downward closure pruning” is true in general and can be false for your specific run. It is worth instrumenting both counters rather than assuming.

Why Apriori Struggles

Three costs are structural rather than implementation artifacts.

Repeated database scans. One per level means ℓ scans for a largest frequent itemset of size ℓ.

When the database exceeds memory, each scan is disk I/O, so a pattern of length 10 means 10 full passes. FP-Growth in Article 35 reduces this to exactly 2.

Candidate explosion at level 2. Level 2 has no prior level to prune against beyond F₁, so:

With 10,000 frequent items that is roughly 5×1⁰⁷ candidate pairs, and every one must be counted. This is Apriori’s worst bottleneck, and it is unavoidable within the level-wise framework.

Subset testing cost. Counting requires testing each candidate against each transaction. Naively that is ∣ Cₖ∣ × N subset tests per level. Hash trees reduce the constant but not the structure.

The alternatives in the next two articles attack different parts of this. Eclat removes the repeated scans by transposing the data. FP-Growth removes candidate generation entirely.

Types of Apriori Algorithm

Classic Apriori

• Definition: the original 1994 algorithm as described above.
• Working principle: level-wise join, prune, and count.
• Advantages: simple, provably complete, and easy to reason about.
• Disadvantages: one scan per level, and the level-2 candidate explosion.
• Applications: teaching, and moderate data that fits in memory.

Apriori TID

• Definition: replaces database scans with a shrinking encoding of the transactions.
• Working principle: after level k, stores for each transaction only the candidate IDs it contains, then counts level k+1 against that instead of the original data.
• Advantages: the encoded set shrinks as k grows, so later levels become cheap.
• Disadvantages: the encoding at level 2 can be larger than the original database, so early levels get worse.
• Applications: as the second half of a hybrid, once the encoding has shrunk.

Apriori Hybrid

• Definition: classic Apriori for early levels, switching to Apriori TID later.
• Working principle: estimates when the encoded set will fit in memory and switches at that point.
• Advantages: captures the best of both, and was the practical recommendation in the original paper.
• Disadvantages: the switch heuristic is data dependent.
• Applications: large databases with deep frequent itemsets.

Partition-Based Apriori

• Definition: divides the database into memory-sized partitions.
• Working principle: finds locally frequent itemsets in each partition, unions them as global candidates, then verifies with one final scan. Any globally frequent itemset must be locally frequent in at least one partition.
• Advantages: exactly two database scans regardless of itemset depth.
• Disadvantages: the candidate union can be much larger than the true frequent set, so verification is expensive.
• Applications: databases far exceeding memory.

Sampling-Based Apriori

• Definition: mines a random sample, then verifies on the full database.
• Working principle: uses a lowered threshold on the sample to reduce false negatives, then one full scan to confirm and catch misses.
• Advantages: very fast, with probabilistic bounds on completeness.
• Disadvantages: not guaranteed complete, unlike every other variant here.
• Applications: exploratory analysis where approximate results suffice.

Dynamic Itemset Counting

• Definition: adds candidates mid-scan rather than only between scans.
• Working principle: starts counting an itemset as soon as all its subsets are known frequent, even part-way through a pass.
• Advantages: fewer total scans than classic Apriori.
• Disadvantages: more complex bookkeeping, and performance is sensitive to transaction order.
• Applications: when scan cost dominates strongly.

Evaluation Metrics

Apriori’s output is exact, so evaluation concerns cost rather than quality.

Number of Database Scans

• Interpretation: the dominant cost when the database exceeds memory.
• When to use: always, and it is the primary basis for comparing against FP-Growth.
• Limitations: irrelevant when the data fits comfortably in memory.

Section 5.5 measured 3 scans for a largest frequent itemset of size 3.

Candidates Generated

• Interpretation: how much work the join created.
• When to use: diagnosing the level-2 bottleneck.
• Limitations: counts generation, not the more expensive counting step.

Support Counts Performed

• Interpretation: how many itemsets actually had their support computed, which is the real cost.
• When to use: the fairest single measure of Apriori’s work.
• Limitations: ignores the per-count cost, which varies with itemset size.

Section 5.5 measured 16 counts against 63 for brute force, a 74.6 percent saving.

Pruning Effectiveness, Split by Mechanism

• Interpretation: how much each mechanism contributes separately.
• When to use: when tuning, and to avoid the misattribution Section 5.6 documents.
• Limitations: requires instrumenting the implementation.

Report both. Section 5.6 found closure pruning contributing exactly zero at s = 0.3 and nine avoided counts at s = 0.1 on identical data.

Frequent Itemset Count

• Interpretation: the output size, and a direct indicator of whether the threshold is sensible.
• When to use: always, first.
• Limitations: not a quality measure. More itemsets is not better.

Section 5.6 showed 12 itemsets at s = 0.3 and 35 at s = 0.1, from a threefold threshold reduction.

Maximum Frequent Itemset Size

• Interpretation: determines the scan count, so it predicts cost directly.
• When to use: capacity planning before a run.
• Limitations: unknown until the run completes.

Wall Clock Time and Peak Memory

• Interpretation: the practical measures.
• When to use: comparing implementations rather than algorithms.
• Limitations: implementation and hardware dependent, so not portable between studies.

Selecting Evaluation Metrics

Business considerations

• The threshold choice is a business decision with a computational consequence. Halving it can multiply both runtime and output size severalfold, as the 12-to-35 jump in Section 5.6 illustrates on a tiny dataset.
• Report the threshold with any result. Frequent itemset counts are meaningless without it.
• Apriori's output is exact, so there is no accuracy to trade away. The only trade is time against threshold.

Dataset characteristics

• Many frequent single items is the danger sign. Level 2 generates C(∣F₁∣, 2) candidates unconditionally, so 10,000 frequent items means roughly 5×10⁷ pairs.
• Long transactions produce deep frequent itemsets, hence many scans. Retail baskets are short and shallow; clickstreams and gene sets are not.
• Dense data means most itemsets are frequent, which defeats pruning and favours closed itemset mining instead.
• Very low thresholds cause combinatorial explosion regardless of algorithm.

Common mistakes

• Attributing all pruning to downward closure without measuring. Section 5.6 found it contributing zero on a real run.
• Setting the threshold low and being surprised by the runtime, when the relationship is superlinear.
• Using Apriori on data with tens of thousands of frequent items, where the level-2 explosion dominates.
• Not reporting the threshold alongside results.
• Assuming more frequent itemsets means a better analysis.
• Ignoring that each level costs a full database scan when data exceeds memory.
• Using the sampling variant and reporting the result as complete.

Assumptions and Practical Considerations

Transactions Are Sets

• Requirement: each transaction is a set of items, with no order and no quantity.
• Why: the subset test X ⊆ T is the only operation the algorithm performs on data.
• Check: confirm duplicates within a transaction are collapsed.
• Fix: sequential pattern mining if order matters, as noted in Article 32.

Items Are Consistently Encoded

• Requirement: each distinct item has exactly one identifier.
• Why: the same product under two labels splits its support and can drop both below the threshold.
• Check: count distinct items and look for near-duplicates.
• Fix: normalize identifiers before mining.

Item sets Can Be Totally Ordered

• Requirement: a fixed ordering on items, used by the join step.
• Why: the shared-prefix condition in Step 4 of the derivation requires sorted item sets. Without a consistent order, candidates are generated multiple times or missed.
• Check: confirm the implementation sorts item sets on creation.
• Fix: sort by any consistent criterion. Lexicographic works; frequency order matters for FP-Growth but not here.

The Threshold Is Set Before Mining

• Requirement: min_support chosen in advance.
• Why: the algorithm prunes irreversibly, so lowering the threshold afterwards requires a complete rerun.
• Check: confirm the threshold is a deliberate choice, not a default.
• Fix: run at several thresholds if unsure, budgeting for the superlinear cost.

Level 2 Is Computationally Feasible

• Requirement: C(∣F₁∣, 2) candidates can be held and counted.
• Why: Section 5.7 identifies this as the structural bottleneck. It cannot be pruned, because there is nothing above F₁ to prune against.
• Check: count items above the threshold, then compute the pair count before proceeding.