Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 39 ยท Association Rules

Frequent Itemsets and Market Basket Analysis

Learn market basket analysis from scratch: transactions, itemsets, support, confidence, lift, and how rules like bread implies butter are formed, with Python code.

Why do supermarkets put diapers near beer, or an online shop say "customers who bought this also bought..."? Behind these features is association rule mining: finding items that occur together often enough, and expressing it as "if the basket has A, it probably has B". The classic use is market basket analysis, but the same method applies to web pages visited in a session, symptoms in patient records, courses a student takes together, or features used in one app session.

Transactions and itemsets

The input is a list of transactions (baskets). Each one is a set of items. An itemset is any set of items; a k-itemset has k items. There is no order and no quantity here, only presence.

Transaction Items
T1 bread, milk
T2 bread, diaper, beer, eggs
T3 milk, diaper, beer, cola
T4 bread, milk, diaper, beer
T5 bread, milk, diaper, cola

The number of possible itemsets explodes: with d items there are 2^d - 1 non-empty itemsets. For 100 items that is more than 10^30. We cannot test them all, which is why clever algorithms (Apriori, FP-Growth) exist.

Support: how common is it?

The support of an itemset is the share of transactions that contain it:

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

An itemset is frequent if its support is at least a chosen minimum support min_sup. Support filters out coincidences and rare combinations that are not worth acting on. The support count is the raw number of transactions.

Python Support of 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.

Rules, confidence and lift

A rule A -> B says: baskets containing the antecedent A often also contain the consequent B. A and B are disjoint itemsets. Its quality is measured by:

  • Support of the rule: support(A union B), how often both appear.
  • Confidence: support(A union B) / support(A), the conditional probability of B given A.
  • Lift: confidence / support(B), how much more often B appears with A than expected if they were independent. Lift above 1 means a positive association, 1 means independence, below 1 means they avoid each other.

Confidence alone can mislead. If 90 percent of all baskets contain bread, the rule milk -> bread may have high confidence simply because bread is everywhere. Lift corrects for that.

Python Confidence and lift for a rule

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.

Notice that diaper -> beer and beer -> diaper have the same support and lift but different confidence: rules are not symmetric. Beer baskets always have diapers here (confidence 1.0), while diaper baskets only sometimes include beer.

The two-step recipe

Every algorithm in this chapter follows the same plan:

Mining association rules

Find frequent itemsets Support at least min_sup. The hard, expensive part.
Generate rules Split each itemset, keep confidence at least min_conf.

Step 1 dominates the cost.

1 / 2

A frequent itemset {diaper, beer, milk} can be split in every way into A and B: {diaper, beer} -> {milk}, -> {diaper, beer}, and so on. Rules from the same itemset share the same support but differ in confidence, so there is no need to scan the data again.

Python Brute-force: all itemsets, then rules

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.

This works for 6 items; for 10,000 items it is hopeless, because it checks every combination. The key observation that fixes this is the Apriori property: if an itemset is frequent, all its subsets are frequent. Equivalently, if {beer, cola} is rare, any larger set containing it is rare too, so we never need to count it. The next lesson builds on that.

Data formats

Real transaction data arrives in two layouts:

  • Long format: one row per (transaction id, item).
  • Wide (one-hot) format: one row per transaction, one boolean column per item.
Python From long format to a boolean basket matrix

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 boolean matrix lets you compute support of any itemset with a vectorized all(axis=1) and mean().

Choosing thresholds

  • Too high min_sup: you only find obvious rules (everyone buys bread). Too low: millions of rules and noise.
  • Retail data is sparse, so supports are often small (0.1 to 1 percent).
  • Look at confidence and lift together, then check usefulness with a human: does a rule suggest an action?
  • Rules between very frequent and very rare items need special care; some systems use different thresholds per item.

Beyond shopping

Association rules appear wherever "co-occurrence in a group" makes sense: pages per web session, courses per student, diagnoses per patient, alarm codes per hour in a network, code changes per commit. Remember they describe correlation, not causation: diapers do not cause beer purchases.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In 10 transactions, bread and milk appear together in 3. The support of {bread, milk} is:

    Support is the fraction of transactions containing the itemset: 3/10.
  2. 2. Confidence of the rule A -> B is:

    It is the conditional probability of B given A.
  3. 3. A lift of 1 means:

    Lift 1: B appears with A exactly as often as expected if they were unrelated.
  4. 4. Why is testing all itemsets impractical?

    The number of possible itemsets grows exponentially with the number of items.
  5. 5. Rules from the same frequent itemset share which measure?

    They all have support(A union B) of the whole itemset; confidence and lift depend on the split.

Summary

  • Input: transactions of items; output: frequent itemsets and rules A -> B.
  • Support = how common; confidence = P(B | A); lift = confidence / support(B).
  • Two steps: find frequent itemsets (expensive), then generate rules above min_conf.
  • The Apriori property (subsets of frequent sets are frequent) makes search feasible.
  • Rules are directional and describe correlation, not cause.

Next: The Apriori Algorithm