Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 39 ยท Association Rules

The Apriori Algorithm

Understand and implement the Apriori algorithm: level-wise candidate generation, the pruning property, rule generation and optimizations, with complete runnable Python.

Apriori is the classic algorithm for finding frequent itemsets. It was published in 1994 and is still the best way to learn the idea. Its trick is to search level by level: find frequent single items, use them to build candidate pairs, count the pairs, keep the frequent ones, then build triples from those, and so on. The Apriori property prunes the search so that most of the exponentially many itemsets are never even counted.

The Apriori property

If an itemset is frequent, all of its subsets are frequent. Equivalently, if an itemset is infrequent, every superset of it is infrequent.

Why? Any transaction containing {A, B, C} also contains {A, B}, so support({A, B}) >= support({A, B, C}). Support can only shrink as itemsets grow (it is anti-monotone). So when {A, B} fails min_sup, we can skip {A, B, C}, {A, B, D} and every other superset without looking at the data.

flowchart TD
    A["1-itemsets: count, keep frequent L1"] --> B["Join L1 with itself: candidates C2"]
    B --> C["Prune candidates with an infrequent subset"]
    C --> D["Scan data: count C2, keep frequent L2"]
    D --> E["Join L2: candidates C3 ..."]
    E --> F["Stop when no candidates remain"]

One level in detail

  1. Join: combine two frequent (k-1)-itemsets that share their first k-2 items to make a candidate k-itemset. ({A, B} and {A, C} give {A, B, C}.)
  2. Prune: drop a candidate if any of its (k-1)-subsets is not frequent.
  3. Count: scan the transactions once, count each surviving candidate.
  4. Filter: keep candidates with support at least min_sup. These form L_k.

A complete implementation

Python Apriori from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed lines show the pruning at work: the number of candidates at each level is much smaller than the count of all possible combinations.

Generating rules

From each frequent itemset with at least two items, try every split A -> B and keep those with confidence at least min_conf. Rule confidence has a helpful property too: moving items from the antecedent to the consequent can only lower confidence, so one can prune rule search the same way.

Python Rules from the frequent itemsets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Apriori on a larger synthetic data set

Here we plant a real pattern in random noise and check that Apriori finds it. This also shows the run time dropping as min_sup rises.

Python Finding a planted pattern

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The set {i1, i2, i3} appears at every threshold up to 0.15 because it occurs in about 20 percent of baskets. Random pairs of items only co-occur in about 0.08 * 0.08 = 0.64 percent of baskets, far below the thresholds, so they are pruned.

Cost and improvements

Apriori's weaknesses are:

  • Many scans: one pass over the data per level.
  • Large candidate sets: when many 1-itemsets are frequent, C2 has about |L1|^2 / 2 candidates.
  • Counting cost: checking each candidate against each transaction.

Standard improvements:

  • Hash-based itemset counting: while counting 1-itemsets, hash pairs into buckets; buckets under the threshold eliminate candidate pairs early.
  • Transaction reduction: a transaction with no frequent k-itemset cannot contain a frequent (k+1)-itemset, so drop it from later scans.
  • Partitioning: split data, find locally frequent itemsets, then verify globally (any globally frequent itemset must be frequent in at least one partition).
  • Sampling: mine a sample with a lowered threshold, then verify.
  • Dynamic itemset counting and, best of all, avoiding candidate generation entirely, as FP-Growth does.

When to use it

Use Apriori to learn, for small or sparse data, and when you need to explain exactly how itemsets were found. For big data use FP-Growth, Eclat or a library. The measures used to judge the rules are discussed in Association Rule Types and Measures.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. The Apriori property states that:

    Subsets of a frequent itemset must also be frequent, so infrequent subsets prune candidates.
  2. 2. In the prune step, a candidate k-itemset is removed if:

    By the Apriori property, such a candidate cannot be frequent, so it need not be counted.
  3. 3. How many passes over the data does basic Apriori need?

    Each level counts its candidates with a scan of the transactions.
  4. 4. Which is an Apriori optimization?

    Transactions with no frequent k-itemset can be skipped in later scans.
  5. 5. Why is support anti-monotone?

    A transaction containing a bigger itemset also contains each of its subsets.

Summary

  • Apriori finds frequent itemsets level by level: join, prune, count, filter.
  • The anti-monotone property of support lets it discard huge parts of the search space.
  • Rules are generated from frequent itemsets by splitting them and checking confidence.
  • Costs: repeated scans and many candidates; improvements include hashing, transaction reduction, partitioning and sampling.
  • FP-Growth removes candidate generation altogether.

Next: The FP-Growth Algorithm