Definition
A kirana store owner notices that people who buy tea leaves often also buy sugar and biscuits. Placing them close together, or offering a combo, increases sales. Association rule mining finds such patterns automatically in thousands of bills.
Association rule mining discovers rules of the form A → B, meaning "baskets that contain A tend also to contain B", from transaction data. Three measures judge a rule: support, the share of all baskets containing both A and B; confidence, the share of baskets with A that also contain B; and lift, the confidence divided by the overall share of baskets with B, which shows how much more likely B becomes when A is present. The Apriori algorithm (1994) finds frequent itemsets efficiently by using the fact that every subset of a frequent itemset must itself be frequent.
In simple words
Look through a pile of shopping bills. If tea appears on 50 bills and 40 of those also show sugar, the rule "tea → sugar" has 80 per cent confidence. If sugar is on almost every bill anyway, though, the rule is not surprising; lift tells you whether tea really makes sugar more likely.
Overview
- Association rule mining finds rules like A → B: baskets with A also tend to contain B.
- Support measures how common an itemset is; confidence how often B follows A; lift how much A raises B's chance.
- Lift above 1 means a genuine association; lift below 1 suggests substitutes.
- The Apriori principle prunes the search: supersets of infrequent itemsets are infrequent.
- Rules show co-occurrence, not cause, so they should be tested before acting.
- Agrawal and Srikant published the Apriori algorithm in 1994.
Why it matters
Retailers, online shops and restaurants use association rules for product placement, "frequently bought together" suggestions, combo offers and stock planning. The same idea helps find symptoms that occur together, web pages visited in sequence and features often used together in software.
Key terms
- Transaction (basket)
- One set of items bought together, such as one bill.
- Itemset
- A set of one or more items, such as {tea, sugar}.
- Support
- The share of all baskets that contain an itemset.
- Confidence
- For A → B, the share of baskets with A that also contain B.
- Lift
- Confidence divided by the support of B; above 1 means A and B occur together more than by chance.
- Apriori principle
- If an itemset is infrequent, every larger set containing it is also infrequent, so it can be skipped.
Types
Several algorithms and measures exist for mining patterns. These types are the most important.
1. Apriori algorithm
A level-by-level algorithm for finding frequent itemsets.
- How it works: Count single items, keep frequent ones, build candidate pairs only from frequent items, and so on, pruning any candidate with an infrequent subset.
- Example: Finding 14 frequent itemsets in twelve shop bills, with atta → ghee at lift 3.0.
- When to use it: Use it for small and medium transaction data and for learning how frequent-pattern mining works.
2. FP-Growth
A faster algorithm that compresses transactions into a frequent-pattern tree (Han et al., 2000).
- How it works: It scans the data only twice and grows patterns from the tree without generating candidate itemsets.
- Example: Mining millions of supermarket transactions in minutes.
- When to use it: Use it for large data sets where Apriori becomes slow.
3. Interestingness measures: support, confidence and lift
Numbers that rank rules.
- How it works: Support filters rare patterns, confidence measures reliability, and lift (confidence ÷ support of B) corrects for items that are popular anyway; conviction and leverage are further options.
- Example: "Anything → milk" has high confidence but lift near 1 because milk is in most baskets.
- When to use it: Use lift together with a minimum support to find rules worth acting on.
4. Sequential pattern mining
Finding patterns in the order of events over time.
- How it works: Algorithms such as GSP and PrefixSpan find frequent sequences, such as "phone, then case, then screen guard".
- Example: Learning that students who watch the loops video often take the functions quiz next.
- When to use it: Use it when the order of actions matters, as in learning paths, web clicks and purchases over months.
5. Uses of association rules
Applying rules to product placement, recommendations, bundles and other co-occurrence problems.
- How it works: Strong rules suggest combos, shelf layouts and "frequently bought together" lists; they can also find symptoms that appear together.
- Example: A kirana shop offering an atta-and-dal combo after seeing a strong rule, and checking sales for two weeks.
- When to use it: Use them for exploration and simple recommendations, and confirm any rule with a small experiment.
Explained in detail
Support, confidence and lift
Support measures how common a pattern is. A rule with very low support, say 2 baskets out of 100,000, is not worth acting on even if it looks strong. Confidence measures how reliable the rule is, but it can mislead: if 90 per cent of all baskets contain milk, then almost any rule "X → milk" will have high confidence even when X has nothing to do with milk. Lift corrects for this by comparing the confidence with how often B appears anyway. Lift = 1 means A and B are independent; lift above 1 means they appear together more often than chance would predict, which is the interesting case; lift below 1 means A makes B less likely, which can reveal substitutes, such as two brands of the same product.
The Apriori algorithm
With 1,000 products there are about half a million possible pairs and over 160 million triples, so checking every combination is impossible. Apriori works level by level. First it counts single items and keeps those with support above a minimum, for example 1 per cent. Then it builds candidate pairs only from frequent single items, counts them and keeps the frequent pairs. Triples are built only from frequent pairs, and so on. The Apriori principle guarantees nothing is missed: if {tea, ghee} is rare, {tea, ghee, rice} must be rarer still. Finally, rules are generated from each frequent itemset and kept if their confidence and lift pass chosen thresholds. FP-Growth is a faster alternative that compresses transactions into a tree.
| Measure | Question it answers | Typical threshold |
|---|---|---|
| Support | Is this pattern common enough to matter? | 0.5 to 5 per cent of baskets |
| Confidence | When A is bought, how often is B bought too? | 50 per cent or more |
| Lift | Does A really raise the chance of B? | Above 1.2 |
Association rules show co-occurrence, not cause. Tea buyers may buy sugar because both are part of making chai, not because one purchase causes the other. Test a rule with a small experiment, such as a combo offer in some stores, before rearranging the whole shop. In the twelve example bills in the code below, Apriori finds 14 frequent itemsets; the strongest rules are atta → ghee and rice → dal, each with lift 3.0, followed by tea → sugar with confidence 0.80 and lift 2.4.
How it works
- Convert bills into a basket-by-item table of true or false values.
- Find frequent itemsets above a minimum support with Apriori.
- Generate rules and compute confidence and lift.
- Keep rules with enough support, confidence and lift above 1.
- Check the top rules with domain experts and test them before acting.
The maths
A shop has 10 bills. Bread appears on 6, butter on 4, and both together on 3. Support of {bread, butter} = 3 ÷ 10 = 0.3. Confidence of bread → butter = 0.3 ÷ 0.6 = 0.5: half of bread buyers also take butter. Support of butter alone is 0.4, so lift = 0.5 ÷ 0.4 = 1.25. Bread buyers are 25 per cent more likely than an average customer to buy butter. The reverse rule butter → bread has confidence 0.3 ÷ 0.4 = 0.75 but the same lift, 0.75 ÷ 0.6 = 1.25, because lift is symmetric.
In code
from itertools import combinations
import pandas as pd
bills = [
{"tea", "sugar", "milk"}, {"tea", "sugar", "biscuits"}, {"tea", "milk", "biscuits"},
{"atta", "dal", "ghee"}, {"atta", "dal", "rice"}, {"rice", "dal"},
{"tea", "sugar", "milk", "biscuits"}, {"atta", "ghee"}, {"tea", "sugar"},
{"milk", "bread"}, {"bread", "butter", "milk"}, {"atta", "dal", "ghee", "rice"},
]
items = sorted(set().union(*bills))
table = pd.DataFrame([[item in bill for item in items] for bill in bills], columns=items)
support = lambda s: table[list(s)].all(axis=1).mean()
# Apriori, level by level, with minimum support 0.2
min_sup = 0.2
frequent = {frozenset([i]): support([i]) for i in items if support([i]) >= min_sup}
level = list(frequent)
while level:
candidates = {a | b for a in level for b in level if len(a | b) == len(a) + 1}
level = [c for c in candidates if all(frozenset(s) in frequent for s in combinations(c, len(c) - 1)) and support(c) >= min_sup]
frequent.update({c: support(c) for c in level})
print("Frequent itemsets:", len(frequent), "| largest:", max(len(s) for s in frequent))
rules = []
for itemset in [s for s in frequent if len(s) > 1]:
for k in range(1, len(itemset)):
for a in map(frozenset, combinations(itemset, k)):
b = itemset - a
conf = frequent[itemset] / frequent[a]
rules.append((", ".join(sorted(a)), ", ".join(sorted(b)), frequent[itemset], conf, conf / frequent[b]))
rules = pd.DataFrame(rules, columns=["if", "then", "support", "confidence", "lift"])
print(rules[rules.confidence >= 0.6].sort_values("lift", ascending=False).round(2).head(6).to_string(index=False))Output
Frequent itemsets: 14 | largest: 2 if then support confidence lift atta ghee 0.25 0.75 3.0 ghee atta 0.25 1.00 3.0 rice dal 0.25 1.00 3.0 dal rice 0.25 0.75 3.0 tea sugar 0.33 0.80 2.4 sugar tea 0.33 1.00 2.4
Try it yourself
Rearranging a kirana shop
Sunita runs a neighbourhood store and wants to use three months of bills to boost sales.
Match the measure
Which measure answers each question?
- Support
- Confidence
- Lift above 1
- Lift below 1
Common mistakes
- Ranking rules by confidence alone, which favours very common items.
- Setting minimum support so low that thousands of chance rules appear.
- Treating a rule as proof that one purchase causes another.
Check yourself
Summary
- Association rules find items that appear together, written A → B.
- Support shows how common, confidence how reliable, and lift how surprising a rule is.
- Apriori prunes rare itemsets level by level; rules show co-occurrence, not cause.
Finished reading?
Sources: Agrawal and Srikant (1994), Fast Algorithms for Mining Association Rules, VLDB · Han, Kamber and Pei, Data Mining: Concepts and Techniques (chapter on frequent patterns)