Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 76 ยท Modelling

Association Rules and Market Basket Analysis

Find items that are bought together: build a basket table, compute support, confidence and lift in pandas, write a small Apriori from scratch, and avoid misleading rules.

"Customers who bought this also bought..." Every online shop shows such suggestions, and supermarkets use the same idea to decide which products to place near each other or to bundle in promotions. The technique behind it is market basket analysis, and its output is a set of association rules such as:

If a basket contains bread and butter, it often contains jam too.

Unlike most models in this course, there is no target column to predict. Association rule mining is unsupervised: it searches a large table of past transactions for item combinations that occur together more often than you would expect by chance. This lesson builds the three key measures by hand with pandas, writes a small Apriori algorithm from scratch, and explains how to avoid being fooled by rules that look impressive but say nothing.

Transactions and baskets

The raw data is a list of transactions. Each transaction is one basket: the set of items bought together. The order of the items and the quantity do not matter; only presence does.

For counting, convert the list into a table with one row per basket, one column per item, and True when the item is in the basket. pandas can do this with explode and crosstab (or get_dummies):

Python From a list of baskets to a True/False table

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 mean of a True/False column is the share of baskets that contain the item. That number is called the item's support, and it is the first of three measures.

Support, confidence and lift

Consider a rule A โ†’ B ("if A is in the basket, B tends to be too"). Three numbers describe it:

  • Support of a set of items is the share of all baskets that contain the whole set: support(A and B) = baskets with A and B / all baskets. It tells you how common the combination is. A rule with tiny support might be luck.
  • Confidence of A โ†’ B is the share of baskets with A that also contain B: confidence = support(A and B) / support(A). It estimates P(B | A), the chance of B given A. But it can be high simply because B is very popular.
  • Lift corrects for that: lift = confidence / support(B) = support(A and B) / (support(A) * support(B)). It compares what we see with what we would see if A and B were independent.
    • Lift = 1: A and B are unrelated.
    • Lift above 1: bought together more often than chance (positive association).
    • Lift below 1: bought together less often (A tends to replace B).
flowchart LR
    S["Support(A and B)<br/>how common"] --> C["Confidence(A -> B)<br/>how reliable"]
    C --> L["Lift(A -> B)<br/>better than chance?"]
    P["Support(B)<br/>popularity of B"] --> L

Support says how often, confidence says how reliably, lift says whether it beats coincidence.

Python Compute the three measures for one 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.

In this tiny data set, 50 percent of baskets contain both bread and butter, and 71 percent of bread baskets also contain butter. But butter is itself popular (70 percent of baskets), so the lift is only about 1.02: bread buyers are hardly more likely to buy butter than anybody else, and the rule is no real discovery. The milk and jam pair has a lift of 0.5, below 1: they appear together less often than chance would predict.

Frequent itemsets and the Apriori idea

With 1,000 items there are about half a million pairs and 166 million triples. Counting every possible combination is hopeless, so rule mining uses a minimum support threshold and a clever trick, the Apriori principle:

If an itemset is infrequent, every larger itemset that contains it must also be infrequent.

If "caviar" appears in only two baskets out of a million, then "caviar and bread" and "caviar, bread and butter" cannot appear in more than two. So once an itemset fails the threshold, you never need to examine its supersets. The algorithm proceeds level by level:

  1. Count single items; keep those with support at least min_support.
  2. Build candidate pairs only from the survivors; count them; keep the frequent pairs.
  3. Build triples from frequent pairs; count; keep. Repeat until nothing survives.
  4. From each frequent itemset, generate rules and keep those with enough confidence (and lift above 1).

Here is the whole algorithm in about twenty lines:

Python Apriori from scratch, 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.

The printed rules are the survivors: frequent enough, reliable enough, and (just) better than chance. Their lifts are barely above 1, which is honest: ten baskets cannot reveal strong associations, and in real data you would look for lifts well above 1. The pruning step all(... in frequent ...) is the Apriori principle in code. On real data you would use a library implementation (for instance mlxtend.frequent_patterns with apriori or the faster fpgrowth, and association_rules; both are read-only here), which works on the same one-hot table you built above.

Faster miners: Eclat and FP-growth

Apriori rereads the data once per itemset size and generates many candidates. Two other algorithms find the same frequent itemsets with less work.

Eclat flips the table. Instead of "basket, then its items" it stores, for every item, the set of baskets that contain it, called a tid-list (transaction-id list). The support of a bigger itemset is the size of the intersection of the tid-lists: the baskets with bread and butter are tids["bread"] & tids["butter"]. Eclat then walks depth first, extending one itemset at a time and stopping as soon as an intersection is smaller than the threshold. It is short to write and fast when the data fits in memory.

Python Eclat with tid-lists

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 nine itemsets are exactly what the Apriori example finds at the same support of 0.3, only found by intersecting sets instead of rescanning baskets.

FP-growth compresses the whole data set into an FP-tree (frequent-pattern tree) and never generates candidates. Steps:

  1. Count single items once and drop the infrequent ones.
  2. Sort the items of each basket from most to least frequent, so common prefixes line up.
  3. Insert every sorted basket into a prefix tree; shared prefixes share nodes and just increase a counter. A header table links every node that holds the same item.
  4. For each item, starting with the rarest, read its conditional pattern base: the paths from the root down to that item, each with the item's count there. Mine those small paths recursively for the patterns that end in the item.
Python FP-growth: building the FP-tree

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 tree as "7 baskets contain bread; 5 of them also butter; 2 of those also milk". The line jam [(['bread', 'butter'], 1), ...] says: jam occurs in four places in the tree, below bread and butter once, below bread, butter and milk once, below bread alone once and below butter alone once. Counting how often bread and butter appear together with jam over those paths gives the support of each combination without touching the baskets again. In practice use mlxtend.frequent_patterns.fpgrowth (read-only here); it returns the same itemsets as apriori and is usually much faster on large data.

Kinds of association rules

The rules you have seen are the simplest kind: single-level, boolean ("item present"), on one table. Variations extend them.

  • Multilevel / generalized rules use a hierarchy (cola, then soft drinks, then beverages). A rule such as "bread, then dairy" may be strong at the category level even when no single product pair reaches the support threshold.
  • Quantitative rules involve numeric attributes after binning them: age in 30-39 and income high, then buys sports car.
  • Multidimensional rules use several attributes of different kinds (age, city, product) instead of only "what is in the basket".
  • Multi-relational rules span several tables (customers, orders, products) and need joins before mining.
  • Sequential rules add order: "after buying a phone, buys a case within a week".

Associative classification

Associative classification uses association rules for prediction. Mine rules whose right side is the class label (income=high, then insured=yes, a class association rule), rank them by confidence, then support, then shortness, keep the best, and classify a new row with the first rule that matches (with a default class when none does). This is the idea behind the CBA algorithm. The rules are readable (an advantage over many models) and often accurate on categorical data, but the number of candidate rules explodes with many attributes, so you must set support and confidence thresholds carefully.

Python Associative classification: class association 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.

Not every row needs to match a rule; the default class covers the rest. Always judge such a classifier on rows it has not seen (see Train, Test and Validation); the perfect accuracy above is on the training table.

Loss-leader analysis

Retailers also use basket data to decide loss leaders: items sold at or below cost to bring people into the shop. The analysis asks which item has a high-lift rule towards profitable items (milk, then snacks). Discount the antecedent when its customers reliably add the consequent, and the discount pays for itself. Check with an experiment, because discounts can also attract shoppers who buy only the cheap item.

Reading rules the right way

Rules are easy to compute and easy to misread. Keep these warnings in mind.

Lift above 1 is the point, confidence alone misleads. A rule "anything โ†’ milk" can have high confidence because milk is in 90 percent of baskets. Check lift.

Small support means unreliable. A rule seen in three baskets with lift 8 is probably noise. Keep a minimum count (for example at least 30 baskets), and think of a rule's support as a sample size.

Thousands of rules, a few are accidents. With many items you test huge numbers of combinations, so some will look interesting by chance. Keep a hold-out set of baskets and check that good rules still hold there, just as you validate any model (see Train, Test and Validation).

Association is not causation. "Nappies and beer" is the legendary example: the rule does not mean that nappies cause beer purchases (shoppers on a weekend errand buy both). Moving the products next to each other is an experiment to test, ideally with an A/B test as in A/B Testing.

Rules are not directional. Support and lift are symmetric (the lift of A โ†’ B equals that of B โ†’ A); only confidence differs.

Obvious rules are useless. "Burger bun โ†’ burger patty" is true and known. Filter by lift, then look for rules that surprise a domain expert, or rules that connect different categories.

Think about the basket definition. A basket might be a purchase, a customer's month, a user's session, or a patient's visit. The same method finds symptoms that occur together, web pages visited together, or features in code reviews. Choose the unit that matches your question.

Beyond baskets: where else it is used

  • Recommendations: "Frequently bought together" boxes, playlist suggestions, "people also search for".
  • Store layout and promotions: place complements close together or bundle them.
  • Medicine and science: diagnoses or genes that occur together.
  • Security and operations: log events that usually precede a failure.

For personalised recommendations at larger scale, collaborative filtering and matrix factorisation (see Linear Algebra for Data Science) take over, but association rules remain the simplest, most explainable starting point.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In 200 baskets, 50 contain item A. What is the support of A?

    Support is a share of all baskets: 50 / 200 = 0.25.
  2. 2. Rule A -> B has confidence 0.8, and B appears in 80% of all baskets. What is its lift?

    Lift = confidence / support(B) = 0.8 / 0.8 = 1. The rule is no better than chance, even though its confidence looks high.
  3. 3. What does the Apriori principle let the algorithm skip?

    If an itemset is infrequent, every superset is infrequent too, so those candidates never need to be counted.
  4. 4. A rule has lift 6 but appears in only 3 of 50,000 baskets. What should you conclude?

    A very small support means very few observations. Impressive lift on tiny counts is often chance.
  5. 5. Is association rule mining supervised?

    There is no target. The algorithm looks for item combinations that occur together unusually often.

Summary

  • Market basket analysis finds items that occur together in transactions; the data is a True/False basket-by-item table.
  • Support is how common an itemset is; confidence is P(B | A); lift compares confidence with the popularity of B (1 means independent).
  • Apriori counts level by level and prunes any candidate that has an infrequent subset.
  • Keep rules with enough support, reasonable confidence and lift above 1, and validate them on held-out baskets.
  • Association is not causation; test business changes with experiments.
  • The same method works on any "set of events", not just shopping.

Next: Clustering and Segmentation continues unsupervised learning, grouping customers instead of items.