SyntaxPilot
Courses/Machine Learning/Lesson 47
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Machine Learning · Lesson 47 of 90

Association rules

market basket analysistransaction dataitemsetfrequent itemsetssupportconfidenceliftApriori algorithmFP-growth

Machine Learning Full Course · Episode 47. Every code sample below was run with Python 3.13, NumPy 2.5.3, pandas 3.0.5 and mlxtend 0.25.0; the output shown is the real output (two programs print timings, which change from run to run and machine to machine). Riya's 5,000 shop baskets are made up for teaching. Because we made the data ourselves, we secretly know the four buying habits hidden inside it, which lets us check whether the method finds them.

The big idea: a shop wants "frequently bought together" offers. Each bill is a transaction (a basket), a list of baskets is transaction data, and any set of items is an itemset. The support of an itemset is the share of baskets that contain all of its items. A rule "if A, then B" has a confidence: of the baskets with A, the share that also have B, the conditional probability P(B | A). Ranking by confidence alone fools you: soap → milk has confidence 0.62, only because milk is in 61% of all baskets anyway. Lift = confidence ÷ support(B) compares the rule with that base rate: soap → milk 1.02 (unrelated), butter → bread 3.34 (a real habit). Counting every itemset is hopeless (20 items give 1,048,575 itemsets, 1,000 items about 10^301), so the Apriori principle helps: a set can only be frequent if all its subsets are. Our Apriori from scratch counted 392 candidate itemsets instead of 1,048,575 and found 115 frequent itemsets; mlxtend's apriori and fpgrowth find the same 115. FP-growth squeezes the data into a prefix tree (the FP-tree) and reads itemsets off it with no candidates at all. Finally, 30 of the 56 rules with confidence ≥ 0.5 have lift below 1.1: without lift, half of Riya's offers would be useless.

Sources: R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules in Large Databases", VLDB 1994, pp. 487-499 (vldb.org); J. Han, J. Pei and Y. Yin, "Mining frequent patterns without candidate generation", SIGMOD Record 29(2), 2000, doi:10.1145/335191.335372 (scholars.duke.edu); the installed mlxtend 0.25.0: TransactionEncoder, apriori, fpgrowth (min_support must be in the interval (0, 1]) and association_rules.

Words you need first

  • Unsupervised learning (Episode 1): learning from data that has no answer column (no labels). Clustering (Episodes 43 to 45) was one kind; today is another: finding patterns of items that appear together.
  • Probability and conditional probability (Episode 9): P(B) is how often B happens; P(B | A), "B given A", is how often B happens among the cases where A happened. Example: P(umbrella | rain) is much higher than P(umbrella).
  • Base rate (Episode 9): how common something is anyway, before you know anything else. Example: if India wins 60% of its matches, a tip "India will win" is right 60% of the time with no skill at all.
  • Set (Python set): an unordered collection with no repeats, like {"bread", "butter"}. A <= B means "every item of A is also in B" (A is a subset of B). A | B is the union: everything in A or B. A frozenset is a set that can never change, so it can be used as a dictionary key.
  • itertools: Python's toolbox for combinations. itertools.chain(*baskets) glues all baskets into one long stream of items; itertools.combinations(items, 3) gives every group of 3 different items (order does not matter); itertools.permutations(items, 2) gives every ordered pair (bread → butter and butter → bread both appear).
  • pandas Series and DataFrame: a labelled column and a table. value_counts() counts how often each value appears.
  • Random generator: np.random.default_rng(3) makes the same "random" numbers every run, so you get exactly the outputs printed here.

The real-life hook: what goes with what?

Riya runs a grocery store. She has 5,000 bills from last month; each bill is just a list of items: bread, butter, milk. She wants combo offers like "buy bread, get butter at 10% off", but only for items that people really buy together. There is nothing to predict and no labels: we are mining patterns from the baskets. This is market basket analysis: studying which items show up in the same baskets.

These lines create the data; every program below starts with them (we call them HDR):

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
  • p gives each of the 20 items its own chance of being in a basket: milk 0.6 (60%), butter only 0.04.
  • r.random() < q is true with probability q, so b is a basket where every item was "bought" independently, like 20 coin flips with different coins.
  • habits hides four buying habits: if a basket has bread, butter is added with chance 0.55; tea → sugar 0.7; onion → tomato 0.6; chips → soda 0.5. These are what a good method should find.
  • sorted(...) stores each basket as an alphabetical list. Baskets have different lengths.

Transactions, itemsets and support

  • Transaction: one basket (one bill). Example: ['potato', 'sugar', 'tea'].
  • Transaction data: a list of baskets. It is not a table with fixed columns: each basket has a different number of items.
  • Itemset: any set of items, for example {bread, butter}. An itemset with k items is a k-itemset.
  • Support of an itemset X:
support(X) = (number of baskets that contain ALL items of X) ÷ (number of baskets)

Example: if {bread, butter} is in 750 of 5,000 baskets, its support is 0.15. Support is a share (between 0 and 1), not a count.

  • Minimum support (min_support): a threshold you choose, such as 0.05 (5% of baskets).
  • Frequent itemset: an itemset whose support is at least the minimum support. Rare itemsets are ignored: an offer that touches 3 baskets a month is not worth printing.

Q1: look at the baskets

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
print("baskets:", len(baskets), "   items:", len(set(itertools.chain(*baskets))))
for b in baskets[:3]: print("  ", b)
count = pd.Series(list(itertools.chain(*baskets))).value_counts()
print("support (share of baskets):"); print((count / len(baskets)).round(2).head(6).to_string())

Output:

baskets: 5000    items: 20
   ['biscuits', 'bread', 'butter', 'dal', 'milk', 'potato']
   ['potato', 'sugar', 'tea']
   ['atta', 'biscuits']
support (share of baskets):
milk      0.61
onion     0.34
potato    0.31
rice      0.30
tomato    0.29
dal       0.26
  • 5,000 baskets, 20 different items. Baskets have different sizes: the third has only 2 items.
  • value_counts() counts how many baskets have each item (an item appears at most once per basket), and dividing by 5,000 gives the support of every 1-itemset.
  • Milk is in 61% of all baskets. Remember that number. Tomato is at 0.29 although its own chance was only 0.1: the onion → tomato habit added the rest.

Rules: antecedent, consequent and confidence

An association rule A → B says: "if a basket has A, it probably also has B". Example: bread → butter.

  • Antecedent: the "if" part, A (bread). It can be one item or an itemset.
  • Consequent: the "then" part, B (butter).
  • A and B never share items.

Three numbers describe a rule:

support(A → B)    = support(A and B together)
confidence(A → B) = support(A and B) ÷ support(A)
  • Support of the rule: how often A and B appear together; it says how many baskets the rule touches.
  • Confidence: of all baskets with A, the share that also have B. That is the conditional probability P(B | A) from Episode 9. Example: 200 baskets have tea, 150 of them also have sugar: confidence(tea → sugar) = 150 / 200 = 0.75.
  • Confidence has a direction: confidence(A → B) and confidence(B → A) are usually different, because they divide by different supports.

Q2: every one-item rule, sorted by confidence (the obvious attempt)

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
n = len(baskets); sets = [set(b) for b in baskets]
def support(items): return sum(items <= s for s in sets) / n             # share of baskets containing ALL the items
items = sorted(set(itertools.chain(*baskets))); sup1 = {i: support({i}) for i in items}
rules = []
for a, b in itertools.permutations(items, 2):                            # rule: a -> b
    s_ab = support({a, b})
    rules.append((a, b, s_ab, s_ab / sup1[a], s_ab / sup1[a] / sup1[b]))  # support, confidence, lift
R = pd.DataFrame(rules, columns=["if", "then", "support", "confidence", "lift"]).round(2)
print(R.sort_values("confidence", ascending=False).head(8).to_string(index=False))

Output:

    if   then  support  confidence  lift
butter  bread     0.15        0.84  3.34
tomato  onion     0.22        0.76  2.24
   tea  sugar     0.15        0.73  3.40
 sugar    tea     0.15        0.68  3.40
 onion tomato     0.22        0.65  2.24
  curd   milk     0.12        0.62  1.01
  soap   milk     0.07        0.62  1.02
   dal   milk     0.16        0.62  1.01
  • items <= s is True when every item of the itemset is in basket s; sum(...) counts the Trues (True counts as 1), and / n turns the count into a share.
  • itertools.permutations(items, 2): all 20 × 19 = 380 ordered pairs, so 380 one-item rules.
  • The last column, lift, is explained in the next section.

Read the top: butter → bread 0.84, tomato → onion, tea → sugar. Those look like real habits. But then come curd → milk, soap → milk, dal → milk, all 0.62. A combo offer "buy soap, get milk"? Wait: 61% of all baskets have milk anyway. Buying soap raises the chance of milk from 0.61 to 0.62, which is nothing.

Why confidence misleads: confidence only looks at baskets with A. If B is very popular, almost any A gets a high confidence towards B. Confidence never asks "is this more than B's base rate?"

Lift: better than chance?

lift(A → B) = confidence(A → B) ÷ support(B)
            = support(A and B) ÷ (support(A) × support(B))
  • support(B) is B's base rate: the chance of B in a random basket.
  • Lift says how many times A raises the chance of B. Like a cricket tip: if India wins 60% of its matches anyway, a tip "India will win" is only worth something if it is right more than 60% of the time.
  • Lift ≈ 1: A and B are unrelated (independent). soap → milk 1.02, curd → milk 1.01, dal → milk 1.01.
  • Lift > 1: bought together more than chance. butter → bread 3.34: more than three times the base rate.
  • Lift < 1: bought together less than chance (Practice 2 looks at such rules).
  • Lift is symmetric: lift(A → B) = lift(B → A). In Q2, tea → sugar and sugar → tea both have lift 3.40, while their confidences differ (0.73 vs 0.68).

Plotting all 380 rules (confidence against lift) shows it clearly: the "anything → milk" rules sit at confidence around 0.6 but lift right at 1, while the four hidden habits (in both directions) stand out with high lift. Confidence alone would have recommended milk to everyone.

Bigger itemsets: why counting everything explodes

Offers can be bigger: "if tea and milk, then sugar". Why not count the support of every possible itemset? With n items, each item is either in or out of an itemset: 2 × 2 × ... = 2^n ways, minus the empty set, so 2^n − 1 itemsets. This blow-up of combinations is called a combinatorial explosion.

Q3: time the triples, estimate the rest

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
from math import comb
n = len(baskets); sets = [set(b) for b in baskets]
def support(items): return sum(items <= s for s in sets) / n
items = sorted(set(itertools.chain(*baskets)))
t = time.time(); triples = [support(set(c)) for c in itertools.combinations(items, 3)]
per = (time.time() - t) / len(triples)                                   # seconds to count one itemset
print(f"all {len(triples)} triples: {time.time() - t:.1f} s")
for k in (20, 100, 1000):                                                # every itemset of k items: 2^k - 1
    print(f"{k:4} items -> {2 ** k - 1:.3g} itemsets, about {(2 ** k - 1) * per / 3600:.3g} hours")
print("pairs alone among 1,000 items:", comb(1000, 2))

Output (one run; the seconds and hours depend on the machine and change every run, the itemset counts do not):

all 1140 triples: 0.4 s
  20 items -> 1.05e+06 itemsets, about 0.0956 hours
 100 items -> 1.27e+30 itemsets, about 1.16e+23 hours
1000 items -> 1.07e+301 itemsets, about 9.77e+293 hours
pairs alone among 1,000 items: 499500
  • time.time() reads the clock in seconds; per is the average time to count one itemset over all 5,000 baskets.
  • :.3g prints 3 significant digits; 1.05e+06 means 1.05 × 10^6 (about a million).
  • comb(1000, 2) is "1,000 choose 2", the number of pairs: 1000 × 999 / 2 = 499,500.
  • 20 items: 2^20 − 1 = 1,048,575 itemsets, a few minutes here (0.0956 hours in this run).
  • A real store has thousands of items. 100 items: 1.27 × 10^30 itemsets. 1,000 items: 1.07 × 10^301. Even the pairs alone among 1,000 items are about half a million. Counting everything is hopeless.

The Apriori principle

Common sense first. If only 3 students in a school take Sanskrit, then at most 3 can take Sanskrit and music. Adding an item to a set can only make it rarer, never more common:

X ⊆ Y  (X is a subset of Y)   ⇒   support(Y) ≤ support(X)

This property is called anti-monotone (or downward closed): as the set grows, support can only stay the same or go down. Example: if support({bread}) were 0.25, support({bread, butter, milk}) could be at most 0.25.

Turned around, that is the Apriori principle, from Agrawal and Srikant (VLDB 1994):

  • If an itemset is rare (below the minimum support), every bigger set containing it is rare too: never count them.
  • A set can only be frequent if all its subsets are frequent.

The Apriori algorithm

A candidate is an itemset we have to count to know whether it is frequent. Apriori works level by level (size 1, then 2, then 3, ...):

  1. Count all single items; keep the frequent ones.
  2. Join: combine frequent sets of size k into candidates of size k + 1. Example: {bread, butter} and {bread, milk} join into {bread, butter, milk}.
  3. Prune: before counting, drop any candidate that has a subset of size k that was not frequent. Example: if {butter, milk} was rare, {bread, butter, milk} is dropped without being counted.
  4. Count the survivors in the baskets, keep the frequent ones, and go back to step 2. Stop when no candidate survives.

Q4: Apriori from scratch

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
n = len(baskets); sets = [frozenset(b) for b in baskets]
def apriori(min_support):
    level = [frozenset([i]) for i in sorted(set(itertools.chain(*baskets)))]   # size-1 candidates
    frequent = {}
    while level:
        sup = {c: sum(c <= s for s in sets) / n for c in level}          # count only the candidates
        keep = {c: v for c, v in sup.items() if v >= min_support}
        print(f"size {len(level[0])}: {len(level):4} candidates counted, {len(keep):3} frequent")
        frequent.update(keep)
        size = len(level[0]) + 1                                         # join frequent sets into bigger ones ...
        joined = {a | b for a in keep for b in keep if len(a | b) == size}
        level = [c for c in joined                                       # ... and prune: every smaller subset
                 if all(frozenset(sub) in keep for sub in itertools.combinations(c, size - 1))]   # must be frequent
    return frequent
t = time.time(); F = apriori(0.05)
print(f"{len(F)} frequent itemsets in {time.time() - t:.2f} s")

Output (the seconds change from run to run):

size 1:   20 candidates counted,  20 frequent
size 2:  190 candidates counted,  77 frequent
size 3:  180 candidates counted,  18 frequent
size 4:    2 candidates counted,   0 frequent
115 frequent itemsets in 0.13 s
  • frozenset instead of set, because the itemsets are used as dictionary keys in keep.
  • Join: a | b for every two frequent sets; keep the unions that are exactly one item bigger.
  • Prune: itertools.combinations(c, size - 1) lists every subset one item smaller; all(... in keep ...) keeps the candidate only if all of them were frequent.
  • frequent collects every frequent itemset with its support.

Read the output:

  • Size 1: all 20 items are frequent (every item is in at least 5% of baskets).
  • Size 2: so all 20 × 19 / 2 = 190 pairs are candidates; 77 are frequent.
  • Size 3: only 180 candidates instead of all 1,140 triples (the prune removed the rest); 18 frequent.
  • Size 4: just 2 candidates instead of 4,845 possible 4-itemsets; none frequent, so the loop stops.
  • 115 frequent itemsets, and we counted 20 + 190 + 180 + 2 = 392 sets instead of 1,048,575. The bigger the sets, the more the pruning saves (on a log-scale chart, the gap between "all itemsets of size k" and "counted by Apriori" grows with every level).

You just invented the Apriori algorithm.

The library: TransactionEncoder, apriori, fpgrowth, association_rules

mlxtend is a Python library with machine-learning extras; its frequent_patterns module has Apriori and FP-growth. They do not take a list of baskets: they want a one-hot table (a True/False table): one row per basket, one column per item, True if the basket has that item. "One-hot" means each item gets its own on/off column. Example:

bread butter milk
basket 1 True True True
basket 2 False False True

TransactionEncoder builds that table: fit learns the list of all items (columns_), transform turns each basket into a row of True/False.

Q5: same 115 itemsets, then rules

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, fpgrowth, association_rules
te = TransactionEncoder(); df = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)
print("one-hot table:", df.shape, "  True/False per item")
for f in (apriori, fpgrowth):                                            # same answer, two algorithms
    F = f(df, min_support=0.05, use_colnames=True); print(f"{f.__name__:9} {len(F)} frequent itemsets")
rules = association_rules(F, metric="confidence", min_threshold=0.5)    # rules with confidence >= 0.5
rules["rule"] = rules.antecedents.map(sorted).str.join(", ") + " -> " + rules.consequents.map(sorted).str.join(", ")
top = rules.sort_values("lift", ascending=False)[["rule", "support", "confidence", "lift"]].round(2)
print(top.head(7).to_string(index=False))
print("rules kept:", len(rules), "  with lift < 1.1:", (rules.lift < 1.1).sum())

Output:

one-hot table: (5000, 20)   True/False per item
apriori   115 frequent itemsets
fpgrowth  115 frequent itemsets
                   rule  support  confidence  lift
          soda -> chips     0.08        0.59  3.86
     milk, sugar -> tea     0.09        0.69  3.48
butter, potato -> bread     0.05        0.86  3.45
bread, potato -> butter     0.05        0.60  3.42
           tea -> sugar     0.15        0.73  3.40
           sugar -> tea     0.15        0.68  3.40
     milk, tea -> sugar     0.09        0.73  3.40
rules kept: 56   with lift < 1.1: 30
  • df.shape is (5000, 20): 5,000 baskets × 20 items.
  • apriori(df, min_support=0.05, use_colnames=True) returns a table with a support column and an itemsets column; use_colnames=True writes item names instead of column numbers.
  • Both algorithms find the same 115 frequent itemsets as our scratch version. Both are exact: only the method differs, not the answer.
  • association_rules(F, metric="confidence", min_threshold=0.5) builds every rule from the frequent itemsets and keeps those with confidence ≥ 0.5. Its antecedents and consequents columns hold frozensets; .map(sorted).str.join(", ") only turns them into readable text.
  • Top by lift: soda → chips 3.86 (the chips → soda habit, seen from the other side), then bigger rules such as milk, sugar → tea (3.48): the tea-sugar habit with milk along for the ride.
  • The last line: 56 rules have confidence ≥ 0.5, and 30 of them have lift below 1.1. Without lift, more than half of Riya's offers would be "popular, not related".

FP-growth: no candidates at all

Apriori still guesses candidates and scans all the baskets again for every level. FP-growth (frequent-pattern growth), from Han, Pei and Yin (2000), avoids candidate generation completely. Its two steps:

  1. Build the FP-tree. Count every item once and drop the rare ones. Sort each basket's frequent items by popularity (most common first), then insert the basket into a prefix tree: a tree where baskets that start the same share a branch, and every node keeps a count. Like phone contacts that start with the same letters share the first steps of a search. Example: the baskets milk, bread, butter and milk, bread share the branch milk → bread, so the tree has milk 2 → bread 2 → butter 1, not two separate copies.
  2. Mine the tree. For each item, collect the paths that lead to it (its conditional pattern base), count the items on those paths, and grow frequent itemsets from them, branch by branch. No candidate is ever guessed and checked.

The FP-tree ("frequent-pattern tree") is the whole dataset squeezed small: common starts are stored once. FP-growth shines on big data with long baskets, where Apriori's candidate lists explode. Practice 5 builds a small FP-tree by hand and in code.

Two errors you will meet

Q6

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
from mlxtend.preprocessing import TransactionEncoder; from mlxtend.frequent_patterns import apriori; import textwrap
def show(e): print(*textwrap.wrap(type(e).__name__ + ": " + str(e), 62), sep="\n")
raw = pd.DataFrame(baskets[:5])                                          # MISTAKE: item NAMES in columns
try: apriori(raw, min_support=0.05)
except Exception as e: show(e)
te = TransactionEncoder(); df = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)
try: apriori(df, min_support=50)                                         # MISTAKE: a count instead of a share
except Exception as e: show(e)
print("min_support=50/5000 works:", len(apriori(df, min_support=50 / 5000)), "itemsets")

Output on the screen (standard output):

ValueError: NaN values are not permitted in the DataFrame when
null_values=False.
ValueError: `min_support` must be a positive number within the
interval `(0, 1]`. Got 50.
min_support=50/5000 works: 967 itemsets

And on the error stream (standard error, printed before the first error), exactly as this install wrote it, missing spaces included:

/usr/local/lib/python3.13/site-packages/mlxtend/frequent_patterns/fpcommon.py:175: DeprecationWarning: DataFrames with non-bool types result in worse computationalperformance and their support might be discontinued in the future.Please use a DataFrame with bool type
  warnings.warn(
  • textwrap.wrap(text, 62) only splits a long message into lines of at most 62 characters so it fits the screen; type(e).__name__ is the error's class name.
  • Mistake 1: the raw baskets. pd.DataFrame(baskets[:5]) puts item names in columns 0, 1, 2, ... and fills short baskets with NaN ("not a number", pandas' mark for an empty cell). First a DeprecationWarning (a warning that something still works but may stop working in a future version): the table is not True/False (bool). Then ValueError: NaN values are not permitted in the DataFrame when null_values=False. (null_values is an option of the function that is off by default.) Fix: TransactionEncoder.
  • Mistake 2: a count instead of a share. ValueError: `min_support` must be a positive number within the interval `(0, 1]`. Got 50. The interval (0, 1] means "above 0, up to and including 1". Support is a share: 50 baskets out of 5,000 is 50 / 5000 = 0.01.
  • That works, but look: at 0.01 there are 967 frequent itemsets, compared with 115 at 0.05. Many of them are rare coincidences. Too low a minimum support floods you with rules about noise.

From rules to decisions

How does Riya use the rules?

  • Filters: a minimum support (the rule must cover enough baskets to matter) and a minimum confidence; then sort by lift (or keep only lift clearly above 1).
  • Decisions: combo offers ("buy tea, get sugar at 10% off"), putting chips and soda on nearby shelves, or an "add to cart" suggestion in the shop's app.
  • Correlation is not causation. A rule says items are bought together (they are correlated), not that one causes the other. Chips do not make people buy soda; maybe both come from a match-night party.
  • A/B test: before rolling out an offer everywhere, try it in some stores (group A) and compare their sales with stores without it (group B). Only that comparison shows whether the offer itself changes what people buy.

Common mistakes

Mistake Exact message / symptom Why Fix
Rank rules by confidence soap → milk confidence 0.62, lift 1.02 (≈ 1) Milk is in 61% of baskets anyway Use lift (well above 1)
Count every itemset 2^20 − 1 = 1,048,575 itemsets; 1.07e+301 for 1,000 items Combinatorial explosion Apriori or FP-growth
Item names as columns ValueError: NaN values are not permitted in the DataFrame when null_values=False. (after a DeprecationWarning about non-bool types) Needs a one-hot True/False table TransactionEncoder
Support as a count ValueError: `min_support` must be a positive number within the interval `(0, 1]`. Got 50. Support is a share, not a count 50 / 5000
min_support too low 967 itemsets at 0.01 (115 at 0.05) Rules for rare noise Raise it, check lift
Treat a rule as a cause "chips make people buy soda" Together ≠ cause A/B test the offer

Mini project: Riya's offer list

Find the frequent itemsets with FP-growth, keep confident rules (≥ 0.5) that beat chance (lift ≥ 1.5) with one item to put on offer, pick the best rule for each offered item, and check that the four hidden habits were found.

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth, association_rules
te = TransactionEncoder(); df = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)
F = fpgrowth(df, min_support=0.05, use_colnames=True)                    # 1) frequent itemsets
rules = association_rules(F, metric="confidence", min_threshold=0.5)    # 2) confident rules ...
rules = rules[(rules.lift >= 1.5) & (rules.consequents.map(len) == 1)]   # ... that beat chance, one item to offer
print("candidate offers:", len(rules))
best = {}                                                                # 3) one offer per item on sale
for _, row in rules.sort_values("lift", ascending=False).iterrows():
    get = next(iter(row.consequents))
    if get not in best: best[get] = row
for get, row in best.items():
    buy = " + ".join(sorted(row.antecedents))
    print(f"buy {buy:17} get {get:7} 10% off   baskets {row.support * len(baskets):4.0f}"
          f"   confidence {row.confidence:.2f}   lift {row.lift:.2f}")
habits = {("bread", "butter"), ("sugar", "tea"), ("onion", "tomato"), ("chips", "soda")}   # sorted pairs
found = {tuple(sorted(r.antecedents | r.consequents)) for _, r in rules.iterrows() if len(r.antecedents) == 1}
print("hidden habits found as one-item rules:", sorted(habits & found), " missed:", sorted(habits - found))

Output:

candidate offers: 25
buy soda              get chips   10% off   baskets  383   confidence 0.59   lift 3.86
buy milk + sugar      get tea     10% off   baskets  446   confidence 0.69   lift 3.48
buy butter + potato   get bread   10% off   baskets  253   confidence 0.86   lift 3.45
buy bread + potato    get butter  10% off   baskets  253   confidence 0.60   lift 3.42
buy tea               get sugar   10% off   baskets  726   confidence 0.73   lift 3.40
buy biscuits + tomato get onion   10% off   baskets  289   confidence 0.81   lift 2.37
buy onion + rice      get tomato  10% off   baskets  368   confidence 0.68   lift 2.34
hidden habits found as one-item rules: [('bread', 'butter'), ('chips', 'soda'), ('onion', 'tomato'), ('sugar', 'tea')]  missed: []
  • rules.consequents.map(len) == 1 keeps rules with exactly one item in the "then" part. next(iter(...)) takes the one item out of the frozenset.
  • iterrows() walks through the table row by row; sorted by lift, the first rule seen for each item is its best.
  • 25 rules pass the filters; one offer per item leaves 7. baskets = support × 5,000: "tea → sugar" touches 726 baskets, "butter + potato → bread" only 253.
  • All four hidden habits are found as one-item rules. Notice "butter + potato → bread": potato is probably just along for the ride (lift 3.45 is close to butter → bread's 3.34). A simpler rule with almost the same lift is usually the better offer.
  • Before printing posters, Riya should A/B test the top offers in a few stores.

Practice

1. Run the scratch Apriori with min_support 0.02. How many candidates and frequent itemsets per level?

Solution

The Q4 program with apriori(0.02) and two extra prints:

import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
n = len(baskets); sets = [frozenset(b) for b in baskets]
def apriori(min_support):
    level = [frozenset([i]) for i in sorted(set(itertools.chain(*baskets)))]
    frequent = {}
    while level:
        sup = {c: sum(c <= s for s in sets) / n for c in level}
        keep = {c: v for c, v in sup.items() if v >= min_support}
        print(f"size {len(level[0])}: {len(level):4} candidates counted, {len(keep):3} frequent")
        frequent.update(keep)
        size = len(level[0]) + 1
        joined = {a | b for a in keep for b in keep if len(a | b) == size}
        level = [c for c in joined
                 if all(frozenset(sub) in keep for sub in itertools.combinations(c, size - 1))]
    return frequent
F = apriori(0.02)
print(len(F), "frequent itemsets; biggest:", max(len(c) for c in F), "items")
print("example of size 4:", sorted(sorted(c) for c in F if len(c) == 4)[0])

Output:

size 1:   20 candidates counted,  20 frequent
size 2:  190 candidates counted, 161 frequent
size 3:  775 candidates counted, 185 frequent
size 4:  100 candidates counted,  31 frequent
size 5:    2 candidates counted,   0 frequent
397 frequent itemsets; biggest: 4 items
example of size 4: ['atta', 'milk', 'onion', 'tomato']

A lower minimum support lets more pairs through (161 instead of 77), so the join makes far more size-3 candidates (775 instead of 180) and the algorithm goes one level deeper. 397 frequent itemsets, and still only 20 + 190 + 775 + 100 + 2 = 1,087 sets counted. Itemsets like {atta, milk, onion, tomato} are mostly popular items meeting by chance plus one habit (onion, tomato).

2. List the rules with lift below 1. What do they mean?

Solution
import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth, association_rules
te = TransactionEncoder(); df = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)
F = fpgrowth(df, min_support=0.05, use_colnames=True)
rules = association_rules(F, metric="lift", min_threshold=0)                # every rule from the frequent itemsets
low = rules[rules.lift < 1].copy()
low["rule"] = low.antecedents.map(sorted).str.join(", ") + " -> " + low.consequents.map(sorted).str.join(", ")
print("all rules:", len(rules), "  lift < 1:", len(low), "  lowest lift:", round(low.lift.min(), 3))
print(low.sort_values("lift")[["rule", "support", "confidence", "lift"]].round(3).head(4).to_string(index=False))

Output:

all rules: 262   lift < 1: 78   lowest lift: 0.931
          rule  support  confidence  lift
 rice -> sugar    0.061       0.199 0.931
 sugar -> rice    0.061       0.283 0.931
milk -> paneer    0.057       0.095 0.934
paneer -> milk    0.057       0.567 0.934

Lift below 1 means "together less often than chance". Here the lowest is 0.931, very close to 1: in our made-up data no items avoid each other on purpose, so these are just random wobbles around 1. Note paneer → milk: confidence 0.567 looks good, yet it is below milk's base rate of 0.61, so knowing "paneer" makes milk slightly less likely. In real data a clearly low lift can point to substitutes (two brands of the same thing, where buying one replaces the other).

3. Plant a new habit (rice → dal, chance 0.4). Can lift find it?

Solution
import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
r2 = np.random.default_rng(5)                                             # plant a new habit: rice -> dal (made up)
baskets2 = [sorted(set(b) | ({"dal"} if "rice" in b and r2.random() < .4 else set())) for b in baskets]
for name, B in [("before", baskets), ("after", baskets2)]:
    sets = [set(b) for b in B]; n = len(sets)
    s = lambda X: sum(X <= t for t in sets) / n
    conf = s({"rice", "dal"}) / s({"rice"})
    print(f"{name:6} support(dal) {s({'dal'}):.3f}   confidence(rice -> dal) {conf:.3f}   lift {conf / s({'dal'}):.2f}")

Output:

before support(dal) 0.265   confidence(rice -> dal) 0.267   lift 1.01
after  support(dal) 0.357   confidence(rice -> dal) 0.569   lift 1.59

Before: lift 1.01, rice and dal unrelated. After planting the habit, confidence jumps to 0.569 and lift to 1.59: found. The lift is lower than the other habits' (3+) because dal is common (0.357 base rate): a popular consequent leaves less room to "beat chance".

4. Use metric="lift" in association_rules (keep lift ≥ 1.5). What do you lose?

Solution
import numpy as np, pandas as pd, itertools, time
r = np.random.default_rng(3); baskets = []                               # 5,000 baskets at Riya's store (made up)
p = dict(milk=.6, bread=.25, eggs=.2, rice=.3, dal=.25, atta=.2, onion=.35, potato=.3, chips=.15, biscuits=.25,
         tea=.2, curd=.2, paneer=.1, soap=.1, noodles=.15, ghee=.08, butter=.04, sugar=.08, tomato=.1, soda=.06)
habits = [("bread", "butter", .55), ("tea", "sugar", .7), ("onion", "tomato", .6), ("chips", "soda", .5)]
for _ in range(5000):
    b = {i for i, q in p.items() if r.random() < q}                     # each item by its own chance ...
    baskets.append(sorted(b | {c for a, c, q in habits if a in b and r.random() < q}))   # ... plus hidden habits
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules
te = TransactionEncoder(); df = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)
F = apriori(df, min_support=0.05, use_colnames=True)
rules = association_rules(F, metric="lift", min_threshold=1.5)            # keep rules with lift >= 1.5
rules["rule"] = rules.antecedents.map(sorted).str.join(", ") + " -> " + rules.consequents.map(sorted).str.join(", ")
print("rules with lift >= 1.5:", len(rules), "  lowest confidence among them:", round(rules.confidence.min(), 2))
print(rules.sort_values("confidence")[["rule", "support", "confidence", "lift"]].round(2).head(4).to_string(index=False))

Output:

rules with lift >= 1.5: 44   lowest confidence among them: 0.16
                     rule  support  confidence  lift
   onion -> bread, tomato     0.05        0.16  2.20
onion -> biscuits, tomato     0.06        0.17  2.37
     onion -> dal, tomato     0.06        0.18  2.26
   tomato -> bread, onion     0.05        0.19  2.23

44 rules pass, but some have confidence as low as 0.16: "onion → bread, tomato" has lift 2.20 only because the onion-tomato habit is inside it, and it is right for just 16% of onion buyers. Lift alone ignores how often the rule is actually right; confidence alone ignores the base rate. Use both: a minimum confidence, then sort by lift.

5. Draw the FP-tree by hand for 5 tiny baskets (minimum support 0.4, that is 2 of 5): {milk, bread, butter}, {milk, bread}, {milk, tea, sugar}, {bread, butter}, {milk, tea}. Then check with code.

Solution

By hand:

  1. Count: milk 4, bread 3, butter 2, tea 2, sugar 1. Sugar is below 2: drop it.
  2. Order by popularity: milk, bread, butter, tea (ties in alphabetical order).
  3. Insert each basket's kept items in that order. Baskets 1 and 2 share milk → bread; basket 3 and 5 share milk → tea; basket 4 starts a new branch at bread.
root
  milk 4
    bread 2
      butter 1
    tea 2
  bread 1
    butter 1
  1. Mine butter: the paths leading to butter are (milk, bread) once and (bread) once. On those paths bread appears 2 times, milk 1 time, so {bread, butter} is frequent (2) and {milk, butter} is not (1). Likewise tea gives {milk, tea} (2), and bread gives {milk, bread} (2). With the four single items that makes 7 frequent itemsets, found without guessing a single candidate.
import pandas as pd
from collections import Counter
from mlxtend.preprocessing import TransactionEncoder; from mlxtend.frequent_patterns import fpgrowth
tiny = [["milk", "bread", "butter"], ["milk", "bread"], ["milk", "tea", "sugar"], ["bread", "butter"], ["milk", "tea"]]
count = Counter(i for b in tiny for i in b); min_count = 2                 # min_support 0.4 = 2 of 5 baskets
order = sorted((i for i in count if count[i] >= min_count), key=lambda i: (-count[i], i))
print("item counts:", dict(count), "  kept, most popular first:", order)
tree = {}                                                                # node: item -> [count, children]
for b in tiny:
    node = tree
    for i in [i for i in order if i in b]:                               # the basket's frequent items, sorted
        node.setdefault(i, [0, {}]); node[i][0] += 1; node = node[i][1]
def show(node, depth=1):
    for i, (c, kids) in node.items(): print("  " * depth + f"{i} {c}"); show(kids, depth + 1)
print("root"); show(tree)
te = TransactionEncoder(); df = pd.DataFrame(te.fit(tiny).transform(tiny), columns=te.columns_)
F = fpgrowth(df, min_support=0.4, use_colnames=True)
print(sorted((sorted(s), round(v, 1)) for v, s in zip(F.support, F.itemsets)))

Output:

item counts: {'milk': 4, 'bread': 3, 'butter': 2, 'tea': 2, 'sugar': 1}   kept, most popular first: ['milk', 'bread', 'butter', 'tea']
root
  milk 4
    bread 2
      butter 1
    tea 2
  bread 1
    butter 1
[(['bread'], 0.6), (['bread', 'butter'], 0.4), (['bread', 'milk'], 0.4), (['butter'], 0.4), (['milk'], 0.8), (['milk', 'tea'], 0.4), (['tea'], 0.4)]

Counter counts the items; setdefault creates a node the first time an item appears on a path, then the count is increased by 1. The printed tree matches the hand-drawn one, and mlxtend's fpgrowth finds exactly the 7 itemsets mined by hand. The tree stores 6 nodes for 11 kept items: shared starts are stored once.

Quick quiz

1. 1,000 baskets. Tea is in 200, sugar in 250, tea and sugar together in 150. What is the lift of tea → sugar? Options: 0.75, 1.5, 3.0, 6.0.

Answer

3.0. Confidence = 150 / 200 = 0.75; support(sugar) = 250 / 1,000 = 0.25; lift = 0.75 / 0.25 = 3.0. Tea buyers take sugar three times as often as a random customer. (0.75 is the confidence, not the lift.)

2. How many non-empty itemsets can you make from 5 items?

Answer

2^5 − 1 = 31. Each item is in or out (2^5 = 32 ways), minus the empty set.

3. Suppose that with minimum support 0.05, {soap, ghee} has support 0.03. Can {soap, ghee, milk} be frequent?

Answer

No. Support is anti-monotone: adding milk can only keep it at 0.03 or lower. Apriori prunes it without counting.

4. support(A) = 0.40, support(A and B) = 0.30, support(B) = 0.50. Confidence and lift of A → B?

Answer

Confidence = 0.30 / 0.40 = 0.75; lift = 0.75 / 0.50 = 1.5.

5. paneer → milk has confidence 0.567 and milk's support is 0.61. A good combo offer?

Answer

No. The lift is below 1 (0.934 in Practice 2): paneer buyers take milk slightly less often than everyone else.

6. Do apriori and fpgrowth give different frequent itemsets?

Answer

No, both are exact: 115 and 115 on Riya's baskets. They differ in speed and method (candidates vs a tree), not in the answer.

Interview questions

  1. What is market basket analysis? Finding items that appear together in transactions (baskets), to drive offers, shelf placement and recommendations. It is unsupervised: no labels.
  2. Define support, confidence and lift. support(X) = share of transactions containing all of X; confidence(A → B) = support(A ∪ B) / support(A) = P(B | A); lift = confidence / support(B) = support(A ∪ B) / (support(A) support(B)).
  3. Why is confidence alone misleading? It ignores the consequent's base rate: any rule towards a popular item (milk at 61%) gets high confidence. soap → milk had 0.62 confidence but lift 1.02.
  4. What do lift = 1, > 1 and < 1 mean? Independent; bought together more than chance; less than chance (possible substitutes).
  5. Is lift symmetric? Is confidence? Lift yes (tea → sugar and sugar → tea both 3.40); confidence no (0.73 vs 0.68).
  6. Why can't you count all itemsets? n items give 2^n − 1 itemsets: about a million for 20 items, about 10^301 for 1,000.
  7. State the Apriori principle. Support is anti-monotone: a superset is never more frequent than its subsets, so every subset of a frequent itemset is frequent, and any superset of a rare itemset can be skipped (Agrawal and Srikant, 1994).
  8. Walk through the Apriori algorithm. Level by level: count frequent 1-itemsets; join frequent k-itemsets into (k + 1)-candidates; prune candidates with any infrequent k-subset; count the survivors; repeat until none survive. On Riya's data: 392 sets counted instead of 1,048,575.
  9. What is the main cost of Apriori? Generating many candidates and scanning the whole dataset once per level; with low support or long baskets the candidate lists explode.
  10. How does FP-growth differ? It compresses the transactions into an FP-tree (a prefix tree of popularity-sorted frequent items with counts) and mines frequent itemsets from it recursively, with no candidate generation (Han, Pei and Yin, 2000). Same result as Apriori.
  11. What input format does mlxtend need? A one-hot True/False DataFrame (one row per transaction, one column per item), e.g. from TransactionEncoder; min_support is a share in (0, 1].
  12. How do you choose min_support? High enough that rules cover enough transactions to act on, low enough to keep interesting rules; too low floods you (967 itemsets at 0.01 vs 115 at 0.05) with noise.
  13. A rule has high lift. Should the shop act on it? Not blindly: co-occurrence is correlation, not causation. A/B test the offer in some stores first.

Glossary

Term Meaning (plain words + example)
Market basket analysis Finding which items are bought together: Riya's "frequently bought together" offers
Unsupervised learning Learning from data with no answer column (Episode 1)
Transaction One basket (one bill): ['potato', 'sugar', 'tea']
Transaction data A list of baskets of different lengths: Riya's 5,000 bills
Item One product: milk
Itemset Any set of items: {bread, butter}
k-itemset An itemset with k items: {bread, butter} is a 2-itemset
Support Share of baskets containing all items of an itemset: milk 0.61
Minimum support (min_support) The support threshold you choose, as a share in (0, 1]: 0.05
Frequent itemset Itemset with support ≥ the minimum: 115 at 0.05
Association rule "If A, then B": bread → butter
Antecedent The "if" part of a rule: bread
Consequent The "then" part of a rule: butter
Rule support support(A and B): how many baskets the rule touches
Confidence support(A and B) ÷ support(A) = P(B | A): butter → bread 0.84
Conditional probability P(B | A) How often B happens among the cases with A (Episode 9)
Base rate How common something is anyway: milk in 61% of baskets
Lift confidence ÷ support(B): how many times A raises B's chance; butter → bread 3.34, soap → milk 1.02
Independent Unrelated: knowing A does not change B's chance; lift ≈ 1
Substitutes Items that replace each other; can show as lift < 1
Combinatorial explosion The number of combinations blowing up: 2^n − 1 itemsets
2^n − 1 Non-empty itemsets from n items: 31 for 5, 1,048,575 for 20
Subset / superset X ⊆ Y: every item of X is in Y; Y is a superset of X
Anti-monotone (downward closed) Support never grows when a set grows: support({bread, butter}) ≤ support({bread})
Apriori principle A set can only be frequent if all its subsets are; rare sets prune their supersets
Candidate An itemset we must count to know if it is frequent: 180 at size 3
Join Combine frequent k-itemsets into (k + 1)-candidates
Prune Drop a candidate that has an infrequent subset, without counting it
Apriori algorithm Count, join, prune, repeat level by level (Agrawal and Srikant, 1994): 392 counted, not 1,048,575
Level All itemsets of one size in Apriori: size 1, size 2, ...
FP-growth Frequent-pattern growth: mine itemsets from an FP-tree with no candidate generation (Han, Pei and Yin, 2000)
FP-tree Prefix tree of each basket's frequent items sorted by popularity, with counts: the data compressed
Prefix tree A tree where sequences that start the same share a branch: milk → bread for both milk-bread baskets
Conditional pattern base The paths leading to one item in the FP-tree: for butter, (milk, bread) and (bread)
Candidate generation Guessing sets to count, as Apriori does; FP-growth skips it
One-hot table One row per basket, one True/False column per item: shape (5000, 20)
TransactionEncoder mlxtend tool that turns a list of baskets into a one-hot table
columns_ The item names learned by TransactionEncoder.fit
mlxtend Python library with apriori, fpgrowth and association_rules
apriori, fpgrowth mlxtend functions: one-hot table → frequent itemsets with support
use_colnames=True Write item names instead of column numbers in the result
association_rules Build rules from frequent itemsets, filtered by metric ≥ min_threshold
metric, min_threshold Which number to filter rules on ("confidence", "lift") and its minimum
antecedents, consequents Columns of association_rules holding the if and then parts as frozensets
Set, frozenset Unordered collection without repeats; a frozenset cannot change and can be a dict key
<= on sets, \| on sets Subset test; union
itertools.combinations, permutations, chain All unordered groups; all ordered pairs; glue lists into one stream
comb(n, k) Number of ways to choose k of n: comb(1000, 2) = 499,500
value_counts pandas: how often each value appears
Counter Python: counts items, Counter(...) → milk 4, bread 3
NaN "Not a number": pandas' mark for an empty cell
null_values mlxtend option for allowing NaN; off by default
ValueError Python error for a bad value: `min_support` must be ... Got 50.
DeprecationWarning Works now, may stop in a future version: non-bool DataFrames in mlxtend
Standard output / standard error The normal printout vs the stream for warnings and errors
textwrap.wrap Splits long text into lines of a given width
Correlation vs causation Bought together does not mean one causes the other: chips and soda at a party
A/B test Try a change in some stores (A), compare with stores without it (B)
Combo offer "Buy tea, get sugar at 10% off": the decision a rule supports

Summary

  • A basket is a transaction; any set of items is an itemset; support is the share of baskets containing it; frequent itemsets have support ≥ a minimum you choose.
  • A rule A → B (antecedent → consequent) has support, confidence = P(B | A), and lift = confidence ÷ support(B).
  • Confidence misleads when B is popular: soap → milk 0.62 with lift 1.02. Lift compares with the base rate: butter → bread 3.34. 30 of 56 confident rules had lift below 1.1.
  • Counting all 2^n − 1 itemsets explodes (1,048,575 for 20 items, about 10^301 for 1,000).
  • Apriori principle: support is anti-monotone, so rare itemsets prune their supersets. Apriori (count, join, prune) counted 392 sets and found 115 frequent itemsets.
  • mlxtend: TransactionEncoder → one-hot table → apriori or fpgrowth (same 115) → association_rules. min_support is a share in (0, 1].
  • FP-growth builds an FP-tree (a prefix tree with counts) and mines it with no candidate generation.
  • Rules show items bought together, not causes: filter by support and confidence, sort by lift, and A/B test offers before rolling them out.

Next episode: PCA from scratch: when a table has too many columns to look at, squeeze it down without losing what matters, with covariance, principal components and explained variance.