Market baskets, Apriori, PCY, FP-Growth, limited-pass algorithms, stream itemsets and recommenders, with Labs 10 and 11.
Frequent-itemset mining finds groups of items that occur together in at least a minimum share of transactions, and turns them into association rules such as "customers who buy diapers also buy beer". The algorithms in this chapter all find the same itemsets; they differ in how many passes they make over the data and how much memory they need. One small dataset is used throughout so that the methods can be compared. This chapter covers the first half of syllabus Unit IV; Chapter 10 covers clustering.
9.1 Mining frequent itemsets
A transaction (or basket) is a set of items bought together, and an itemset is any set of items; an itemset with k items is a k-itemset. The support of an itemset is the fraction (or count) of transactions that contain it. An itemset is frequent if its support is at least a user-chosen minimum support threshold. An association rule A ⇒ B states that transactions containing A tend also to contain B. Its strength is measured by confidence, conf(A ⇒ B) = support(A ∪ B) / support(A), which estimates P(B | A), and by lift, lift(A ⇒ B) = conf(A ⇒ B) / support(B), which compares the rule with what would happen by chance: lift > 1 means positive association, lift = 1 independence and lift < 1 negative association. Mining has two steps: (1) find all frequent itemsets, and (2) generate from them the rules that meet a minimum confidence. Step 1 is the expensive one, because d distinct items can form 2^d − 1 itemsets — over a million for just 20 items.
The running dataset. Five shopping baskets:
| TID | Items |
|---|---|
| T1 | Bread, Milk |
| T2 | Bread, Diaper, Beer, Eggs |
| T3 | Milk, Diaper, Beer, Cola |
| T4 | Bread, Milk, Diaper, Beer |
| T5 | Bread, Milk, Diaper, Cola |
Worked example – support, confidence and lift.
- {Milk, Diaper, Beer} appears in T3 and T4, so support = 2 / 5 = 0.4.
- {Milk, Diaper} appears in T3, T4 and T5, so support = 3 / 5 = 0.6.
- Confidence of {Milk, Diaper} ⇒ {Beer} = 0.4 / 0.6 = 0.67: two-thirds of baskets with milk and diapers also have beer.
- Beer appears in T2, T3 and T4, so support(Beer) = 0.6. Lift = 0.67 / 0.6 = 1.11 > 1, a mild positive association.
9.2 Market basket modelling
Market basket modelling (market basket analysis) applies frequent-itemset mining to retail transactions to discover which products customers buy together. The results guide many decisions: store layout (placing associated items near each other, or deliberately apart so customers walk past other products), cross-selling and bundling ("frequently bought together" offers), promotions (discounting one item to lift sales of its partner), inventory planning and online recommendations. The same idea applies outside retail: symptoms that occur together in medical records, web pages visited in the same session, or words that appear in the same documents. A good rule needs all three measures to be satisfactory: enough support to matter, high confidence to be reliable, and lift above 1 to show a real association rather than the popularity of the right-hand item.
Worked example – a rule with high confidence but no real association.
- Rule {Bread} ⇒ {Milk}: support(Bread, Milk) = 3 / 5 (T1, T4, T5) = 0.6 and support(Bread) = 4 / 5 = 0.8, so confidence = 0.6 / 0.8 = 0.75.
- support(Milk) = 4 / 5 = 0.8, so lift = 0.75 / 0.8 = 0.94 < 1. Although 75% of bread buyers also buy milk, 80% of all customers buy milk — bread buyers are slightly less likely to buy milk than average. The high confidence comes only from milk's popularity.
- Rule {Bread} ⇒ {Cola}: support(Bread, Cola) = 1 / 5 = 0.2 (T5), confidence = 0.2 / 0.8 = 0.25, support(Cola) = 0.4, lift = 0.25 / 0.4 = 0.625 — a clearly negative association.
Read more on the blog: Basic Concept of Market Basket Analysis.
9.3 Apriori algorithm
The Apriori algorithm finds frequent itemsets level by level, using the Apriori property: every subset of a frequent itemset must itself be frequent, or equivalently, if an itemset is infrequent, all its supersets are infrequent. The algorithm first scans the data to count single items and keeps the frequent ones (L₁). It then repeats two steps. In the join step, frequent k-itemsets that share their first k − 1 items are combined to form candidate (k + 1)-itemsets, Cₖ₊₁. In the prune step, any candidate with an infrequent k-subset is removed without counting it. The remaining candidates are counted in one pass over the data, and those meeting the minimum support form Lₖ₊₁. The process stops when no new frequent itemsets are found. Apriori is simple and effective, but it may generate very many candidates and needs one pass over the data for each level.
The pruning step (shaded) is what makes Apriori efficient: candidates with an infrequent subset are discarded before the expensive counting scan.
Worked example – Apriori on the running dataset with minimum support count = 3 (60%).
- Pass 1 – count items (C₁): Bread 4, Milk 4, Diaper 4, Beer 3, Cola 2, Eggs 1. Keep counts ≥ 3: L₁ = {Bread}, {Milk}, {Diaper}, {Beer}.
- Join → C₂: all pairs of L₁ items: {Bread, Milk}, {Bread, Diaper}, {Bread, Beer}, {Milk, Diaper}, {Milk, Beer}, {Diaper, Beer}.
- Pass 2 – count C₂: {Bread, Milk} = 3 (T1, T4, T5); {Bread, Diaper} = 3 (T2, T4, T5); {Bread, Beer} = 2 (T2, T4); {Milk, Diaper} = 3 (T3, T4, T5); {Milk, Beer} = 2 (T3, T4); {Diaper, Beer} = 3 (T2, T3, T4). L₂ = {Bread, Milk}, {Bread, Diaper}, {Milk, Diaper}, {Diaper, Beer}.
- Join → C₃: {Bread, Milk, Diaper} (from {Bread, Milk} + {Bread, Diaper}); {Bread, Diaper, Beer}; {Milk, Diaper, Beer}.
- Prune: {Bread, Diaper, Beer} has the subset {Bread, Beer}, which is not in L₂, so it is removed without counting; {Milk, Diaper, Beer} is removed because {Milk, Beer} is not in L₂. Only {Bread, Milk, Diaper} survives.
- Pass 3: {Bread, Milk, Diaper} appears in T4 and T5 only, count = 2 < 3. L₃ is empty, so the algorithm stops.
- Rules from {Diaper, Beer} with minimum confidence 70%: Diaper ⇒ Beer has confidence 3 / 4 = 75% ✓; Beer ⇒ Diaper has confidence 3 / 3 = 100% ✓, with lift 1.0 / 0.8 = 1.25.
Read more on the blog: Apriori Algorithm.
Blog lab: Lab 7 – Association analysis in R
Lab 10 (R) – Association analysis and evaluating its accuracy
Aim: mine association rules with Apriori on the Groceries transactions (9,835 baskets), then check how well the rules hold on unseen transactions.
install.packages(c("arules", "arulesViz"))
library(arules); library(arulesViz)
data("Groceries") # or: trans <- read.transactions("basket.csv", format = "basket", sep = ",")
summary(Groceries)
itemFrequencyPlot(Groceries, topN = 10, type = "relative")
# Hold out 30% of transactions to evaluate the rules
set.seed(1)
idx <- sample(length(Groceries), 0.7 * length(Groceries))
train <- Groceries[idx]; test <- Groceries[-idx]
# Mine rules on training data
rules <- apriori(train, parameter = list(supp = 0.005, conf = 0.4, minlen = 2))
rules <- rules[!is.redundant(rules)]
rules <- sort(rules, by = "lift")
inspect(head(rules, 10)) # support, confidence, coverage, lift, count
# Evaluate: recompute each rule's quality on the test set
test_q <- interestMeasure(rules, c("support", "confidence", "lift"), transactions = test)
compare <- data.frame(rule = labels(rules),
train_conf = quality(rules)$confidence,
test_conf = test_q$confidence,
test_lift = test_q$lift)
head(compare, 10)
# Rule accuracy = confidence on unseen data (share of baskets with the LHS that also have the RHS)
cat("Mean test confidence :", round(mean(compare$test_conf, na.rm = TRUE), 3), "\n")
cat("Mean |train - test| :", round(mean(abs(compare$train_conf - compare$test_conf), na.rm = TRUE), 3), "\n")
cat("Rules still lift > 1 :", mean(compare$test_lift > 1, na.rm = TRUE) * 100, "%\n")
plot(head(rules, 15), method = "graph") # visualise the top rules
Rules whose confidence and lift stay high on the test set generalise well; a large drop signals rules that fit only the training data.
9.4 Handling large data sets in main memory
In real retail data there may be 100,000 distinct items and billions of baskets. The main bottleneck of frequent-itemset mining is main memory: the counts for all candidate pairs must fit in RAM during the counting pass, and if they do not, the algorithm thrashes — swapping counts to and from disk — and becomes thousands of times slower. Pairs are the critical case, because the number of candidate pairs is usually far larger than the number of candidate triples. Two layouts are used to store pair counts. The triangular matrix stores a count for every possible pair (i, j) with i < j in a one-dimensional array; with items numbered 1 to n, pair (i, j) is stored at position k = (i − 1)(n − i/2) + j − i, using 4 bytes per pair. The triples method stores only pairs that actually occur, as (i, j, count) records of 12 bytes each, so it wins when fewer than one-third of all possible pairs occur. Algorithms such as PCY, Multistage and Multihash use spare memory to reduce the number of candidate pairs, and FP-Growth avoids generating candidates altogether.
Worked example 1 – memory for pair counts. With n = 100,000 items:
- Possible pairs = n(n − 1) / 2 = 100,000 × 99,999 / 2 ≈ 5 × 10⁹.
- Triangular matrix: 5 × 10⁹ × 4 bytes = 20 GB — too large for many machines.
- If only 10⁸ pairs actually occur, the triples method needs 10⁸ × 12 bytes = 1.2 GB, which fits.
- Index check for n = 5 and pair (2, 4): k = (2 − 1)(5 − 2/2) + 4 − 2 = 1 × 4 + 2 = 6. Listing the pairs in order — (1,2), (1,3), (1,4), (1,5), (2,3), (2,4) — confirms that (2, 4) is the 6th.
PCY algorithm (Park–Chen–Yu). PCY uses the memory that sits idle during Apriori's first pass. In pass 1 it counts single items as usual, and at the same time it hashes every pair in each basket into a hash table of buckets, adding 1 to the bucket's count. Between the passes, the bucket counts are replaced by a bitmap: 1 if a bucket's count reached the support threshold (a frequent bucket) and 0 otherwise — 1 bit instead of a 4-byte integer, a 32-fold saving. In pass 2, a pair {i, j} is counted only if both i and j are frequent items and the pair hashes to a frequent bucket. This works because a bucket whose total count is below the threshold cannot contain any frequent pair, so all its pairs can be skipped. Multistage adds a further pass with a second hash table to filter candidates even more, and Multihash uses several hash tables in the same first pass.
Worked example 2 – PCY on the running dataset with support threshold 4. Number the items Bread = 1, Milk = 2, Diaper = 3, Beer = 4, Eggs = 5, Cola = 6, and hash pairs with h(i, j) = (i + j) mod 7.
- Pass 1, item counts: 1 → 4, 2 → 4, 3 → 4, 4 → 3, 5 → 1, 6 → 2. Frequent items: Bread, Milk, Diaper.
- Pass 1, bucket counts (all 25 pairs in the five baskets hashed): bucket 0 = 4, bucket 1 = 3, bucket 2 = 3, bucket 3 = 4, bucket 4 = 3, bucket 5 = 5, bucket 6 = 3.
- Bitmap (count ≥ 4): buckets 0, 3 and 5 are frequent → bitmap 1 0 0 1 0 1 0.
- Candidates for pass 2: pairs of frequent items are (1, 2), (1, 3) and (2, 3). (1, 2) → (1 + 2) mod 7 = 3, bit 1 ✓. (1, 3) → 4 mod 7 = 4, bit 0 ✗ — pruned. (2, 3) → 5, bit 1 ✓.
- Apriori would count 3 pairs in pass 2; PCY counts only 2. On real data with millions of pairs, this pruning is what makes the second pass fit in memory. (The actual counts are 3, 3 and 3, so no pair reaches 4.)
FP-Growth. The Frequent Pattern Growth algorithm finds the same frequent itemsets without generating candidates, in just two passes. Pass 1 counts items and sorts the frequent ones in descending order of frequency. Pass 2 inserts each transaction, with its items in that order, into a compact prefix tree called the FP-tree, in which transactions that share a prefix share a path and each node stores a count. Frequent itemsets are then mined from the tree recursively: for each item, starting from the least frequent, the algorithm collects its conditional pattern base (the prefix paths that lead to it) and builds a smaller conditional FP-tree from them.
Worked example 3 – FP-Growth with support count 3. Order: Bread 4, Milk 4, Diaper 4, Beer 3.
- Ordered transactions: T1 = Bread, Milk; T2 = Bread, Diaper, Beer; T3 = Milk, Diaper, Beer; T4 = Bread, Milk, Diaper, Beer; T5 = Bread, Milk, Diaper.
- FP-tree paths: Bread(4) → Milk(3) → Diaper(2) → Beer(1); Bread(4) → Diaper(1) → Beer(1); Milk(1) → Diaper(1) → Beer(1).
- Conditional pattern base of Beer: {Bread, Milk, Diaper}: 1, {Bread, Diaper}: 1, {Milk, Diaper}: 1. In it Diaper has count 3, Bread 2, Milk 2, so only {Diaper, Beer} (count 3) is frequent.
- Repeating for Diaper, Milk and Bread yields {Bread, Diaper}, {Milk, Diaper} and {Bread, Milk} — exactly Apriori's L₂, found with two scans and no candidate lists.
Read more on the blog: Handling Large Dataset in Memory · Frequent Pattern Growth.
9.5 Limited pass algorithms
Limited pass algorithms find frequent itemsets in at most two passes over the data, which matters when the dataset is so large that every extra scan is costly. Three are standard. The simple randomised algorithm takes a random sample small enough to fit in memory and runs Apriori on it with the support threshold scaled down in proportion to the sample size. It is fast but can produce false positives (itemsets frequent in the sample but not in the whole data) and false negatives (itemsets frequent in the whole data but missed in the sample); lowering the threshold slightly reduces false negatives, and a second full pass removes false positives. The SON algorithm (Savasere, Omiecinski and Navathe) divides the data into chunks that each fit in memory. In pass 1 it finds the itemsets that are frequent within each chunk, using the support fraction scaled to the chunk; the union of these is the candidate set. In pass 2 it counts every candidate over the whole data and keeps those that are truly frequent. SON produces no false negatives, because an itemset frequent overall must be frequent in at least one chunk, and it is naturally parallel (it maps well onto MapReduce). Toivonen's algorithm uses one pass over a sample and one full pass and, when it succeeds, gives neither false positives nor false negatives. It finds the frequent itemsets in a sample using a lowered threshold, and also builds the negative border: itemsets that are not frequent in the sample but all of whose immediate subsets are frequent in the sample. The full pass counts both groups. If no negative-border itemset is frequent in the full data, the answer is exactly correct; if any is, some frequent itemset may have been missed, and the algorithm must be repeated with a new sample.
Worked example 1 – scaling the threshold for a sample. The full data has 10 million baskets and the support threshold is 10,000 baskets (0.1%). A 1% sample has 100,000 baskets, so the scaled threshold is 10,000 × 0.01 = 100. To reduce false negatives the analyst uses 0.9 × 100 = 90 in the sample, then verifies the candidates on the full data.
Worked example 2 – SON on the running dataset with support fraction 0.6. Chunk 1 = T1–T3 (local threshold 0.6 × 3 = 1.8, i.e. count ≥ 2); chunk 2 = T4–T5 (0.6 × 2 = 1.2, i.e. count ≥ 2).
- Pass 1, chunk 1: pair counts — {Diaper, Beer} = 2 (T2, T3); every other pair = 1. Locally frequent pair: {Diaper, Beer}.
- Pass 1, chunk 2: {Bread, Milk} = 2, {Bread, Diaper} = 2, {Milk, Diaper} = 2; others ≤ 1. Locally frequent: {Bread, Milk}, {Bread, Diaper}, {Milk, Diaper}.
- Candidates = union = four pairs.
- Pass 2, full counts: each of the four has count 3 ≥ 3 (60% of 5), so all four are frequent — the same L₂ as Apriori, found in two passes.
Worked example 3 – Toivonen with a failed check. Sample = {T1, T4, T5} with sample threshold 2; full threshold 3.
- Frequent in the sample: Bread 3, Milk 3, Diaper 2; {Bread, Milk} 3, {Bread, Diaper} 2, {Milk, Diaper} 2; {Bread, Milk, Diaper} 2. Beer (1) and Cola (1) are not frequent; Eggs does not appear.
- Negative border: {Beer}, {Cola} and {Eggs} are not frequent, and their only immediate subset, the empty set, is frequent — so all three are in the border. No pair is in the border, because every pair of frequent items is itself frequent.
- Full pass: Beer has count 3 (T2, T3, T4) ≥ 3, so a negative-border itemset is frequent in the full data.
- The algorithm cannot guarantee its answer — indeed it has missed {Beer} and {Diaper, Beer}. It must repeat with a new sample (usually a larger one, or with a lower sample threshold).
Read more on the blog: SON Algorithm.
9.6 Counting frequent itemsets in a stream
In a stream, baskets arrive continuously, cannot be re-scanned, and what is frequent changes over time, so the batch algorithms above cannot be used directly. Three approaches are common. Sampling methods treat a chunk of the stream as a file, run an in-memory algorithm such as Apriori, PCY or Toivonen on it, and then keep running counts for the itemsets found, periodically sampling a new chunk to catch itemsets that have become frequent and dropping those whose counts fall. The decaying-window method (section 8.4) gives every tracked itemset a score that decays by a factor (1 − c) at each new basket. When a basket arrives, all scores are multiplied by (1 − c); 1 is added to the score of every tracked itemset contained in the basket; a new itemset starts being tracked only if all its immediate subsets were already tracked (the Apriori property — single items may always start); and itemsets whose score falls below a threshold such as ½ are dropped. Lossy counting divides the stream into buckets of width w = ⌈1/ε⌉, where ε is the allowed error. It keeps entries (item, count, Δ), where Δ is the maximum count the item could have missed before it was first recorded, and at the end of each bucket b it deletes entries with count + Δ ≤ b. Items with count ≥ (s − ε)N are output, where s is the support threshold and N the stream length. Lossy counting guarantees that no truly frequent item is missed and that every count is too low by at most εN. A Count-Min sketch — a small two-dimensional array of counters indexed by d hash functions, whose estimate for an item is the minimum of its d counters — is widely used to find "heavy hitters" in very large streams.
Worked example 1 – decaying window for itemsets with c = 0.1. Baskets arrive: {a, b}, {a}, {a, b}.
- Basket 1 {a, b}: a and b start with score 1. {a, b} cannot start, because a and b were not tracked before this basket.
- Basket 2 {a}: multiply by 0.9 → a = 0.9, b = 0.9; add 1 to a → a = 1.9, b = 0.9.
- Basket 3 {a, b}: multiply → a = 1.71, b = 0.81; add 1 to both → a = 2.71, b = 1.81. Now a and b were tracked, so {a, b} starts with score 1.
Worked example 2 – lossy counting with ε = 0.2, so w = ⌈1 / 0.2⌉ = 5. Stream: a b a c a | b a d a b (N = 10).
- Bucket 1 (items 1–5): entries a = (3, Δ 0), b = (1, 0), c = (1, 0). At the end of bucket 1, delete entries with count + Δ ≤ 1: b and c are deleted. Remaining: a = (3, 0).
- Bucket 2 (items 6–10): b arrives and is new, so it enters as (1, Δ = 1), because it could have been missed in bucket 1. a → 4; d enters as (1, 1); a → 5; b → 2.
- At the end of bucket 2, delete entries with count + Δ ≤ 2: d (1 + 1 = 2) is deleted; b (2 + 1 = 3) stays. Remaining: a = (5, 0), b = (2, 1).
- With support s = 0.3, output items with count ≥ (0.3 − 0.2) × 10 = 1: a and b. True counts are a = 5 and b = 3; b's count is low by 1, within the guaranteed bound εN = 0.2 × 10 = 2.
9.7 Recommendation systems
Recommendation systems suggest items a user is likely to want, extending market-basket thinking from "items bought together" to "items this user will like". Content-based systems recommend items similar to those the user liked before, using item features such as genre or brand. Collaborative filtering uses the ratings of many users: user-based collaborative filtering finds users with similar tastes and recommends what they liked, while item-based collaborative filtering finds items rated similarly by the same users. Similarity is usually measured by cosine similarity, cos(u, v) = (u · v) / (‖u‖ ‖v‖), over the items both have rated, and a missing rating is predicted as the similarity-weighted average of the neighbours' ratings. Hybrid systems combine both approaches. Accuracy is evaluated by hiding some known ratings and measuring RMSE or MAE of the predictions, and by the precision and recall of the top-N recommended lists.
Worked example – user-based collaborative filtering. Ratings (1–5) for four movies; U1 has not rated movie 3.
| User | M1 | M2 | M3 | M4 |
|---|---|---|---|---|
| U1 | 5 | 3 | ? | 1 |
| U2 | 4 | — | 4 | 1 |
| U3 | 1 | 1 | 5 | 5 |
- Similarity U1–U2 on co-rated movies M1 and M4: (5 × 4 + 1 × 1) / (√(5² + 1²) × √(4² + 1²)) = 21 / (5.099 × 4.123) = 21 / 21.02 = 0.999.
- Similarity U1–U3 on M1, M2 and M4: (5 × 1 + 3 × 1 + 1 × 5) / (√35 × √27) = 13 / (5.916 × 5.196) = 13 / 30.74 = 0.423.
- Predicted rating of U1 for M3 = (0.999 × 4 + 0.423 × 5) / (0.999 + 0.423) = (3.996 + 2.115) / 1.422 = 6.111 / 1.422 = 4.30.
- U1's tastes closely match U2's, who rated M3 as 4, so M3 is predicted at about 4.3 and is a good recommendation.
Lab 11 (R) – Build a recommendation system and evaluate its accuracy
install.packages("recommenderlab")
library(recommenderlab)
data(MovieLense) # 943 users x 1664 movies, ratings 1-5
# Keep active users and popular movies to reduce sparsity
ratings <- MovieLense[rowCounts(MovieLense) >= 50, colCounts(MovieLense) >= 100]
ratings
image(ratings[1:50, 1:50], main = "Rating matrix (sample)")
# Evaluation scheme: 80% users train; for test users 10 ratings are given, rest hidden
set.seed(7)
scheme <- evaluationScheme(ratings, method = "split", train = 0.8,
given = 10, goodRating = 4)
# Three recommenders
rec_ubcf <- Recommender(getData(scheme, "train"), method = "UBCF") # user-based CF
rec_ibcf <- Recommender(getData(scheme, "train"), method = "IBCF") # item-based CF
rec_pop <- Recommender(getData(scheme, "train"), method = "POPULAR") # baseline
# 1. Rating-prediction accuracy: RMSE, MSE, MAE on hidden ratings
acc <- rbind(
UBCF = calcPredictionAccuracy(predict(rec_ubcf, getData(scheme, "known"), type = "ratings"), getData(scheme, "unknown")),
IBCF = calcPredictionAccuracy(predict(rec_ibcf, getData(scheme, "known"), type = "ratings"), getData(scheme, "unknown")),
POPULAR = calcPredictionAccuracy(predict(rec_pop, getData(scheme, "known"), type = "ratings"), getData(scheme, "unknown")))
round(acc, 3)
# 2. Top-N accuracy: precision, recall, TPR/FPR for 1, 5, 10 recommendations
results <- evaluate(scheme, list(UBCF = list(name = "UBCF"),
IBCF = list(name = "IBCF"),
POPULAR = list(name = "POPULAR")),
type = "topNList", n = c(1, 5, 10))
plot(results, annotate = TRUE, legend = "topleft") # ROC curve
plot(results, "prec/rec", annotate = TRUE)
# Top 5 recommendations for the first user
as(predict(rec_ubcf, ratings[1], n = 5), "list")
The best model has the lowest RMSE/MAE and the highest precision and recall at the chosen N.
Independent study notes written in my own words, for learning purposes. Not affiliated with any university or course provider. R, RStudio, Hadoop, Amazon S3, Tableau, Power BI and other product names are trademarks of their respective owners.