Skip to content
Tutorials Center
My learning

Topics

Lesson 72 of 111 ยท Unsupervised Learning

Association Rule Mining and the Apriori Algorithm

Find items bought together: itemsets, support, confidence and lift, with the Apriori algorithm written from scratch in plain Python on a basket dataset.

A supermarket has millions of receipts and no labels. Nobody has marked which receipts are "good" or "bad", so there is nothing to predict. But there is still something to learn: which items tend to appear in the same basket? Knowing that customers who buy pasta often buy tomato sauce helps with shelf layout, bundles, coupons and "frequently bought together" boxes. Finding such patterns is called association rule mining, or market basket analysis, and it is a classic unsupervised technique.

This lesson defines the three numbers that matter (support, confidence and lift), then writes the Apriori algorithm from scratch in plain Python on a small basket dataset, so every step is visible. The same idea works for any "set of things that occur together": pages visited in one session, symptoms in one patient, tags on one article. For recommenders that use ratings instead, see Recommender Basics.

scikit-learn has no association rule module. The usual Python library is mlxtend (with apriori, fpgrowth and association_rules), but it is not installed in the in-browser runner, so we write the algorithm ourselves. Its code is shown read-only near the end of this lesson.

Transactions, itemsets and support

The data is a list of transactions: each one is a set of items bought together. A set of items is an itemset; {bread, butter} is an itemset of size 2.

The support of an itemset is the fraction of transactions that contain all of its items:

support(X) = (transactions containing X) / (all transactions)

If 3 of 10 baskets contain both bread and butter, then support({bread, butter}) = 0.3. Support tells you how common a pattern is. Rare patterns are usually not worth acting on, so you choose a minimum support and call every itemset above it frequent.

Rules: confidence and lift

A rule X โ†’ Y says "baskets with X tend to contain Y". Two numbers describe it:

  • Confidence = support(X โˆช Y) / support(X): among baskets with X, the share that also contain Y. It is the conditional probability P(Y | X), the same quantity from Bayes' rule.
  • Lift = confidence / support(Y): how much more often Y appears with X than you would expect if X and Y were unrelated.

Confidence alone is misleading. If 90% of all baskets contain bags, then "chewing gum โ†’ bags" has 90% confidence without gum having anything to do with it. Lift fixes that: a lift of 1 means no association, above 1 means the items appear together more than chance, and below 1 means they avoid each other.

Three numbers per rule

Support How common is the pattern?
Confidence How often does Y follow X?
Lift Is that more than chance?
1 / 2

The search problem and the Apriori trick

With 1,000 products there are about 10ยณโฐโฐ possible itemsets, so you cannot count them all. Apriori avoids almost all of them using one observation: if an itemset is frequent, every subset of it must be frequent too. If {bread, butter, jam} appears in 30% of baskets, then {bread, butter} appears in at least 30%. Turn that around: if {bread, jam} is not frequent, then no larger itemset containing it can be, so it is never worth counting.

The algorithm works level by level:

  1. Count single items and keep those with enough support.
  2. Build candidate pairs from the surviving items, count them, keep the frequent ones.
  3. Build candidate triples only from pairs whose subsets all survived, count, keep.
  4. Stop when a level produces no frequent itemsets.
flowchart LR
    A["Count single items"] --> B["Keep items with support >= min"]
    B --> C["Join survivors into larger candidates"]
    C --> D["Prune candidates with an infrequent subset"]
    D --> E["Count remaining candidates"]
    E --> F{"Any frequent left?"}
    F -- yes --> C
    F -- no --> G["Generate rules from frequent itemsets"]

Apriori grows itemsets one item at a time and prunes using the "every subset must be frequent" property.

Apriori from scratch

The code below keeps transactions as Python frozensets (immutable sets, so they can be dictionary keys). apriori returns a dictionary from frequent itemset to support. Notice the prune step: before counting a candidate of size k, it checks that every subset of size k-1 was frequent.

Python Apriori on a small basket dataset

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 brute-force check passes: Apriori found exactly the same itemsets as counting all 2โต โˆ’ 1 = 31 possible ones. With five items brute force is fine; the point of Apriori is that with hundreds of items it still only counts a small fraction of the candidates. Because support rescans every transaction, this version is slow on big data. Real implementations use bitmaps or the FP-Growth algorithm, which builds a compact tree of the transactions and never generates candidates at all.

From itemsets to rules

For every frequent itemset with two or more items, split it into an antecedent X and a consequent Y in every possible way, compute confidence and lift, and keep the rules that pass your thresholds. We never need to scan the data again: supports of every subset are already known, because all subsets of a frequent itemset are frequent.

Python Generating rules and reading lift

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.

Read the table from the top: rules are sorted by lift. jam -> bread and cereal -> milk both have confidence 1.0 (every basket with jam also has bread) and the highest lift, 1.43. On a tiny data set like this, nothing is dramatic; on real receipts you would look for lifts of 2, 5 or more. Rules at the bottom show the other side of the scale: bread & butter -> milk has 60% confidence but a lift of 0.86, below 1, so those baskets are less likely than average to contain milk.

The last lines show why confidence alone misleads. Bread is in 70% of all baskets, so even a perfect confidence for jam -> bread raises the chance of bread by only a factor of 1.43. Nobody would build a promotion around that alone; look for rules whose lift is large and whose support is high enough to matter.

Tune three thresholds together: min support (how common), min confidence (how reliable) and min lift (how surprising). Start with a fairly high support, then lower it if you get too few rules. Too low a support on a big catalog produces millions of rules that are mostly noise.

With mlxtend (read-only)

On a real data set you would use a library. This is what the same analysis looks like with mlxtend; it needs the transactions as a one-hot table (one column per item, True if the basket contains it). It is not available in the browser runner, so treat it as a reference.

Python
# Read-only: mlxtend is not installed in the browser runner.
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, fpgrowth, association_rules

encoder = TransactionEncoder()
onehot = pd.DataFrame(encoder.fit(transactions).transform(transactions),
                      columns=encoder.columns_)

frequent = fpgrowth(onehot, min_support=0.3, use_colnames=True)
rules = association_rules(frequent, metric="lift", min_threshold=1.0)
print(rules[["antecedents", "consequents", "support", "confidence", "lift"]])

ECLAT and FP-Growth compared with Apriori

Apriori has two weak spots. It generates candidates (itemsets that might be frequent) and it rescans every transaction for every level. Two other classic algorithms attack these costs in different ways, and all three return exactly the same frequent itemsets.

  • ECLAT changes the data layout from horizontal (a list of items per transaction) to vertical: for every item, store the set of transaction ids (its tidset) that contain it. The support of an itemset is then just the size of the intersection of its items' tidsets, so no transaction is ever rescanned. ECLAT grows itemsets depth-first and intersects as it goes, which is very fast on dense data that fits in memory.
  • FP-Growth compresses the transactions into an FP-tree (frequent-pattern tree): items are sorted by global frequency and shared prefixes of transactions are merged into one path with a count. To mine it, take each item in turn, collect the paths that lead to it (its conditional pattern base), build a smaller tree from those, and recurse. It never generates candidates, and it scans the data only twice.
Apriori ECLAT FP-Growth
Data layout Horizontal lists Vertical tidsets Compressed prefix tree
Search Breadth-first, level by level Depth-first Divide and conquer on the tree
Candidates Generated and pruned Implicit (intersections) None
Scans of the data One per level One Two
Weak point Many scans, many candidates Big tidsets when data is dense and huge Tree can be large; harder to code

The program implements all three in plain Python on 1,495 generated baskets (a few popular items, a long tail and one planted association between item00 and item01), checks that their results are identical, and times them.

Python Apriori, ECLAT and FP-Growth side by side

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.

All three find the same 324 frequent itemsets with the same counts, including the planted pair (404 baskets) and the biggest triple {item00, item01, item02}. The timings depend on your machine, but the ranking is typical: Apriori is the slowest by a large factor because of its repeated scans, and the vertical ECLAT and tree-based FP-Growth are many times faster. In this short pure-Python version ECLAT beats FP-Growth, because the data set is small and tree building has overhead. In production libraries FP-Growth is usually the default choice, since it scales better to large, sparse transaction tables, while ECLAT is attractive when the data is dense. Whichever algorithm you use, the choice changes the speed, never the answer, so the rest of the workflow (confidence, lift, rule filtering) stays the same.

Limits and cautions

  • Association is not causation. Diapers and beer in one basket does not mean one causes the other. Rules suggest experiments (a coupon test), not conclusions.
  • Popular items dominate support-based rankings; use lift (or leverage) to find the surprising combinations.
  • Rare but valuable patterns, such as a luxury item, fall below any sensible minimum support, so they need a separate approach.
  • Time and sequence are ignored: baskets are sets. If the order matters (page sequences), you need sequential pattern mining.
  • Test your rules. A rule found on last year's data is a hypothesis; check that it holds on a held-out month before acting.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In 10 baskets, 4 contain bread and butter together. What is support({bread, butter})?

    Support is the fraction of all transactions that contain the whole itemset: 4 out of 10 = 0.4.
  2. 2. What property lets Apriori skip most candidate itemsets?

    If any subset of a candidate is infrequent, the candidate itself cannot reach the minimum support, so it is never counted.
  3. 3. A rule has confidence 0.9 and lift 1.0. What does that tell you?

    A lift of 1 means the items appear together exactly as often as independence predicts. The 0.9 confidence is just the base rate of the consequent.
  4. 4. Why is mlxtend not used in the runnable examples of this lesson?

    scikit-learn has no association rule module and mlxtend is not available in the in-browser runner, which is why the lesson implements Apriori itself.

Summary

  • Association rule mining finds items that occur together in transactions, with no labels needed.
  • Support measures how common an itemset is; confidence is P(Y | X); lift compares confidence with the base rate of Y (1 means unrelated).
  • Apriori counts itemsets level by level and prunes candidates with any infrequent subset; FP-Growth avoids candidate generation.
  • Always check lift, not just confidence, and tune min support, confidence and lift together.
  • Rules are hypotheses about association, not causation; test them before acting.
  • mlxtend is the usual library but is not available in the browser runner; the from-scratch version is enough to understand it.

Next, a very different kind of learning with no labeled answers: Reinforcement Learning Basics.