Association Rule Mining: Apriori, FP-Growth and Market-Basket Analysis

A supermarket notices that customers who buy lentils and rice often buy cooking oil. A pharmacy sees certain medicines prescribed together. A learning platform finds that students who complete the statistics module usually attempt the machine learning module next. Association rule mining finds such co-occurrence patterns in large collections of transactions. It is an unsupervised, highly interpretable technique and one of the classic methods of data mining.

Terminology#

• A transaction is a set of items (one shopping basket, one patient's prescriptions).
• An itemset is any set of items, e.g. {rice, lentils}.
• An association rule $X \Rightarrow Y$ says: transactions containing $X$ tend to contain $Y$ ($X \cap Y = \emptyset$).

Measuring rules#

For $N$ transactions:

• Support — how common the pattern is.
• Confidence — how often the rule is right when it applies.
• Lift — how much more likely $Y$ is given $X$ than in general. Lift > 1 indicates positive association; = 1 independence; < 1 negative association.

The mining problem#

Find all rules with support ≥ min_support and confidence ≥ min_confidence. The difficulty: with $d$ items there are $2^d$ possible itemsets. For a shop with 10,000 products, brute force is impossible.

The solution splits into two steps:

1. Find all frequent itemsets (support ≥ threshold).
2. Generate high-confidence rules from them.

The Apriori principle#

Every subset of a frequent itemset is frequent. Equivalently: if an itemset is infrequent, all its supersets are infrequent. This anti-monotonicity of support lets us prune the search massively.

Apriori algorithm (Agrawal & Srikant, 1994):

1. Count single items; keep frequent ones ($L_1$).
2. For $k = 2, 3, \dots$: generate candidate $k$-itemsets by joining frequent $(k-1)$-itemsets; prune any candidate with an infrequent $(k-1)$-subset; scan the data to count support; keep the frequent ones ($L_k$).
3. Stop when no new frequent itemsets appear.

Its weakness is repeated database scans and potentially huge candidate sets.

FP-Growth#

FP-Growth (Han et al., 2000) compresses the database into a prefix tree (the FP-tree), where transactions sharing frequent items share paths. It then mines frequent itemsets recursively from conditional trees without candidate generation, needing only two scans of the data. It is usually much faster than Apriori on large datasets.

Example#

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth, association_rules

transactions = [
    ["rice", "lentils", "oil", "salt"],
    ["rice", "lentils", "oil"],
    ["rice", "oil", "sugar"],
    ["lentils", "oil", "onion"],
    ["rice", "lentils", "onion", "oil"],
    ["tea", "sugar", "milk"],
    ["tea", "sugar", "biscuits"],
    ["tea", "milk", "biscuits", "sugar"],
    ["rice", "lentils", "salt"],
    ["tea", "sugar"],
]
te = TransactionEncoder()
df = pd.DataFrame(te.fit_transform(transactions), columns=te.columns_)

itemsets = fpgrowth(df, min_support=0.3, use_colnames=True)
rules = association_rules(itemsets, metric="confidence", min_threshold=0.7)
cols = ["antecedents", "consequents", "support", "confidence", "lift"]
print(rules[cols].sort_values("lift", ascending=False).round(2).to_string(index=False))

Rules such as {rice, lentils} ⇒ {oil} and {tea} ⇒ {sugar} emerge with lift well above 1.

Applications#

• Retail: store layout, cross-selling, promotions, bundle design.
• Healthcare: co-occurring diagnoses or adverse drug combinations (for further study, not conclusions).
• Web usage mining: pages visited together; navigation design.
• Education: modules or resources that students use together.
• Supply planning: items requested together at distribution points, helping pack kits efficiently.

Interpreting rules responsibly#

• Association is not causation. Buying a phone case does not cause buying a phone; they co-occur.
• Multiple testing: mining thousands of rules guarantees some spurious ones. Validate rules on held-out transactions or over time.
• Thresholds strongly shape the output: too high misses interesting niche patterns; too low floods analysts with trivial rules.
• Redundancy: many rules restate each other; summarise with closed or maximal itemsets.