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 <= Bmeans "every item of A is also in B" (A is a subset of B).A | Bis 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
SeriesandDataFrame: 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
pgives each of the 20 items its own chance of being in a basket: milk 0.6 (60%), butter only 0.04.r.random() < qis true with probability q, sobis a basket where every item was "bought" independently, like 20 coin flips with different coins.habitshides 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 <= sis True when every item of the itemset is in baskets;sum(...)counts the Trues (True counts as 1), and/ nturns 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;peris the average time to count one itemset over all 5,000 baskets.:.3gprints 3 significant digits;1.05e+06means 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, ...):
- Count all single items; keep the frequent ones.
- Join: combine frequent sets of size k into candidates of size k + 1. Example: {bread, butter} and {bread, milk} join into {bread, butter, milk}.
- 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.
- 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
frozensetinstead ofset, because the itemsets are used as dictionary keys inkeep.- Join:
a | bfor 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. frequentcollects 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.shapeis (5000, 20): 5,000 baskets × 20 items.apriori(df, min_support=0.05, use_colnames=True)returns a table with asupportcolumn and anitemsetscolumn;use_colnames=Truewrites 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. Itsantecedentsandconsequentscolumns 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:
- 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.
- 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). ThenValueError: NaN values are not permitted in the DataFrame when null_values=False.(null_valuesis 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 is50 / 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) == 1keeps 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:
- Count: milk 4, bread 3, butter 2, tea 2, sugar 1. Sugar is below 2: drop it.
- Order by popularity: milk, bread, butter, tea (ties in alphabetical order).
- 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
- 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
- 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.
- 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)).
- 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.
- What do lift = 1, > 1 and < 1 mean? Independent; bought together more than chance; less than chance (possible substitutes).
- Is lift symmetric? Is confidence? Lift yes (tea → sugar and sugar → tea both 3.40); confidence no (0.73 vs 0.68).
- 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.
- 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).
- 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.
- 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.
- 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.
- 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_supportis a share in (0, 1]. - 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. - 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 →aprioriorfpgrowth(same 115) →association_rules.min_supportis 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.