Association rules and market basket analysis

The big idea

A supermarket has millions of receipts. Which items tend to be bought together? If people who buy pasta usually buy tomato sauce, you can shelve them near each other, bundle them, or suggest one at checkout when the other is in the basket.

Association rule miningFinding rules of the form 'if a basket contains X, it tends to contain Y' from many transactions, measured by support, confidence and lift. finds these patterns without any labels. Each receipt is a transactionOne record in association rule mining, such as a shopping basket, viewed as a set of items., a set of items, and the goal is rules of the form X -> Y: "baskets with X often also have Y".

The trouble is how many candidate rules there are. With just 100 products there are about 10^30 possible itemsets. You cannot count them all. The Apriori algorithm avoids nearly all of that work with one observation, the same one a detective uses: if nobody saw the suspect in the city, nobody saw him on a particular street of that city.

How it works

Take 10 baskets from the code: {bread, milk}, {bread, butter, milk}, {bread, butter}, {beer, chips}, {bread, butter, jam}, {milk, chips}, {beer, chips, bread}, {bread, butter, milk}, {beer, chips} and {milk}.

Step 1: Support, how common an itemset is

The supportThe fraction of all transactions that contain every item in an itemset. of an itemset is the share of baskets that contain all of its items. Bread is in 6 of 10 baskets, so support(bread) = 0.6. Bread and butter appear together in 4, so support(bread, butter) = 0.4. You set a minimum support, here 0.3, and call itemsets above it frequent itemsetsAn itemset whose support is at least the chosen minimum support.. Rare combinations are ignored: they are too few to trust and too rare to act on.

Step 2: Confidence, how often the rule holds

The confidenceFor a rule X -> Y, the share of baskets containing X that also contain Y: support(X and Y) / support(X). of X -> Y is the share of baskets with X that also contain Y. It is the conditional probability P(Y | X):

butter -> bread has confidence 0.4 / 0.4 = 1.00: every basket with butter has bread. bread -> butter has 0.4 / 0.6 = 0.67. Rules are not symmetric.

Step 3: Lift, better than chance?

Confidence alone can mislead. Bread is in 60 percent of all baskets, so almost any rule ending in bread looks confident. LiftFor a rule X -> Y, confidence divided by the support of Y. Above 1 means X and Y co-occur more than if they were independent; 1 means no association; below 1 means they co-occur less. compares the rule to what you would see if the items were independent:

beer -> chips: confidence 1.00, and chips are in 40 percent of baskets, so lift = 1.00 / 0.4 = 2.5. Beer buyers are 2.5 times as likely as an average shopper to buy chips. bread -> milk has confidence 0.50 and milk is in 50 percent of baskets: lift 1.00, no association at all, even though half of bread buyers take milk.

Step 4: Apriori, prune before you count

The AprioriAn algorithm for frequent itemsets that grows them one item at a time and discards any candidate with an infrequent subset, because a superset can never be more frequent than its subsets. principle: every subset of a frequent itemset must also be frequent. A basket containing {bread, butter, milk} also contains {butter, milk}, so the triple can never be more common than the pair. Turned around: if a set is infrequent, every superset is too, and you never need to count them.

The algorithm works level by level:

1. Count single items; keep the frequent ones (jam, in 1 basket, is dropped).
2. Build candidate pairs only from frequent items (10 candidates from 5 items), count them, keep the frequent ones (3 survive).
3. Build candidate triples from frequent pairs, and throw out any whose subsets are not all frequent. Here the only triple is pruned before counting, so the search stops.
4. From each frequent itemset, form rules and keep those above a minimum confidence, then rank by lift.

Going deeper

Code: Apriori from scratch

from itertools import combinations

# 10 shopping baskets
baskets = [
    {"bread", "milk"}, {"bread", "butter", "milk"}, {"bread", "butter"},
    {"beer", "chips"}, {"bread", "butter", "jam"}, {"milk", "chips"},
    {"beer", "chips", "bread"}, {"bread", "butter", "milk"}, {"beer", "chips"},
    {"milk"},
]
n = len(baskets)
support = lambda items: sum(items <= b for b in baskets) / n  # share of baskets containing all items

# Apriori: grow itemsets one item at a time, keeping only frequent ones
min_support = 0.3
frequent = {}
level = [frozenset([i]) for i in sorted(set().union(*baskets))]
k = 1
while level:
    kept = [s for s in level if support(s) >= min_support]
    print(f"size {k}: {len(level)} candidates, {len(kept)} frequent")
    frequent.update({s: support(s) for s in kept})
    # next candidates: unions of kept sets, but only if EVERY subset is frequent (the Apriori prune)
    k += 1
    level = {a | b for a in kept for b in kept if len(a | b) == k}
    level = [c for c in sorted(level, key=sorted) if all(frozenset(s) in frequent for s in combinations(c, k - 1))]

print()
for s, sup in sorted(frequent.items(), key=lambda t: (-len(t[0]), -t[1], sorted(t[0]))):
    print(f"{'{' + ', '.join(sorted(s)) + '}':<24} support {sup:.1f}")

# Rules X -> Y from frequent pairs
print()
for s in sorted((s for s in frequent if len(s) == 2), key=lambda s: (-frequent[s], sorted(s))):
    for x in sorted(s):
        X, Y = frozenset([x]), s - {x}
        conf = frequent[s] / frequent[X]
        lift = conf / support(Y)
        print(f"{x:>6} -> {next(iter(Y)):<7} support {frequent[s]:.1f}  confidence {conf:.2f}  lift {lift:.2f}")

size 1: 6 candidates, 5 frequent
size 2: 10 candidates, 3 frequent

{bread, butter}          support 0.4
{beer, chips}            support 0.3
{bread, milk}            support 0.3
{bread}                  support 0.6
{milk}                   support 0.5
{butter}                 support 0.4
{chips}                  support 0.4
{beer}                   support 0.3

 bread -> butter  support 0.4  confidence 0.67  lift 1.67
butter -> bread   support 0.4  confidence 1.00  lift 1.67
  beer -> chips   support 0.3  confidence 1.00  lift 2.50
 chips -> beer    support 0.3  confidence 0.75  lift 2.50
 bread -> milk    support 0.3  confidence 0.50  lift 1.00
  milk -> bread   support 0.3  confidence 0.60  lift 1.00

Note the asymmetry in the output: butter -> bread has confidence 1.00 while bread -> butter has 0.67, yet both have the same lift, 1.67, because lift is symmetric in X and Y. Libraries such as mlxtend implement Apriori and the faster FP-GrowthFrequent Pattern Growth: an algorithm that compresses transactions into a prefix tree and mines frequent itemsets without generating candidates level by level., which compresses transactions into a tree and avoids repeated scans of the data.

Choosing thresholds and reading results

Minimum support too high, and you only rediscover that everyone buys bread and milk. Too low, and you drown in rules from a handful of baskets, many of them coincidences. Common practice: a support threshold that corresponds to a meaningful number of baskets, a moderate confidence threshold, then sort by lift and read the top rules. Lift below 1 is also useful: items that are rarely bought together may be substitutes, like two brands of the same coffee.

Association is not causation. Beer and chips may both rise because of a football match, not because one causes the other. And a rule with high lift but support of 0.001 may not be worth a shelf change.

Trade-offs

Common mistakes

• Ranking rules by confidence alone, which favours rules that end in very popular items.
• Setting minimum support so low that rules come from a handful of baskets.
• Reading a high-lift rule as a causal effect and acting on it without a test.
• Forgetting that X -> Y and Y -> X have different confidence.

In the wild

Market basket analysis is a classic of retail analytics: placing complementary products near each other, designing bundles and promotions, and "frequently bought together" suggestions in online shops. The same counting applies far beyond shopping: symptoms and diagnoses that occur together in medical records, web pages visited in the same session, or software modules that change together in commits, which can point to hidden coupling. Personalized recommendation today mostly uses collaborative filtering and learned models ( Recommender fundamentals ), but association rules remain a fast, explainable first look at co-occurrence.

Check yourself

Recap