Frequent Patterns & the Apriori Algorithm
Market basket analysis, support and confidence, the Apriori property, the join and prune steps, a full worked example, and generating strong association rules.
▶Lecture videos
Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.
Apriori Algorithm
Step-by-step Apriori on a transaction database.
00:02Support and confidence00:52Example: shirt and tie, 13.5% support01:39Example: rules from the frequent itemset ABE04:50The Apriori algorithm: the idea05:38Generating (k+1) candidates from frequent k-itemsets06:25Worked example: minimum support and level-wise passes09:33Apriori pruning: infrequent subsets → infrequent supersetsAnimation on Apriori (no narration)
Short silent animation of the level-wise search.
1Frequent patterns
Frequent patterns are patterns that appear in a dataset frequently. There are three kinds:
| Type | Example |
|---|---|
| Frequent itemset | {milk, bread} bought together often |
| Frequent sequential pattern (subsequence) | Buy a PC → then a digital camera → then a memory card |
| Frequent structured pattern (substructure) | Frequent subgraphs, subtrees, sublattices |
Finding frequent patterns is essential for mining associations and correlations. It also helps classification and clustering. This lesson focuses on frequent itemset mining.
2Market basket analysis
Market basket analysis analyses customer buying habits by finding associations between items placed in "shopping baskets". If customers buy milk, how likely are they to buy bread (and which bread) on the same trip?
How retailers use the results:
| Use | Example |
|---|---|
| Store layout: place related items close together | Computer display near antivirus software display |
| Store layout: place them far apart | (Alternatively) spread them apart so shoppers pass more products |
| Sales and discounts | Customers buy computers and printers together → a sale on printers boosts both |
| Catalogue design, cross-marketing, behaviour analysis | Which products to advertise together |
3Association rules, support and confidence
Patterns are written as association rules:
| Measure | Reflects | Meaning in the example | Formula |
|---|---|---|---|
| Support | Usefulness | 2% of all transactions contain both computer and antivirus | support(A⇒B) = P(A ∪ B) = count(A and B) / total transactions |
| Confidence | Certainty | 60% of customers who bought a computer also bought antivirus | confidence(A⇒B) = P(B | A) = support_count(A ∪ B) / support_count(A) |
A rule is interesting (strong) if it meets both a minimum support and a minimum confidence threshold, set by users or domain experts.
- Find all frequent itemsets: each occurs at least min_sup times.
- Generate strong association rules from them: rules satisfying min_sup and min_conf.
Step 1 is the expensive part.
Mining often produces a huge number of frequent itemsets, especially with a low min_sup, because every subset of a frequent itemset is also frequent. A frequent 100-itemset has 2¹⁰⁰ − 1 frequent subsets.
4The Apriori algorithm
- Proposed by R. Agrawal and R. Srikant (1994) for mining frequent itemsets for Boolean association rules.
- Name: it uses prior knowledge of frequent-itemset properties.
- Level-wise search: frequent k-itemsets are used to explore (k+1)-itemsets.
- Scan the DB → L₁ (frequent 1-itemsets) → use L₁ to find L₂ → L₃ … until no more are found.
- Each Lₖ needs one full database scan.
All non-empty subsets of a frequent itemset must also be frequent.
Equivalently, if an itemset is infrequent, all its supersets are infrequent. Adding item A to an itemset I can't make it occur more often: P(I ∪ A) ≤ P(I) < min_sup.
Each level has two steps
1. Join step
Build Cₖ (candidates) by joining Lₖ₋₁ ⋈ Lₖ₋₁. Two (k−1)-itemsets are joined if their first k−2 items are the same.
2. Prune step
Remove any candidate in Cₖ that has a (k−1)-subset not in Lₖ₋₁. By the Apriori property it can't be frequent. Then scan the DB to count the survivors and keep those ≥ min_sup → Lₖ.
5Full worked example (|D| = 9, min_sup = 2)
| TID | Items |
|---|---|
| T100 | I1, I2, I5 |
| T200 | I2, I4 |
| T300 | I2, I3 |
| T400 | I1, I2, I4 |
| T500 | I1, I3 |
| T600 | I2, I3 |
| T700 | I1, I3 |
| T800 | I1, I2, I3, I5 |
| T900 | I1, I2, I3 |
min_sup = 2 is absolute support (a count). The relative support is 2/9 = 22%.
Level 1
| C₁ itemset | count | in L₁? |
|---|---|---|
| {I1} | 6 | ✓ |
| {I2} | 7 | ✓ |
| {I3} | 6 | ✓ |
| {I4} | 2 | ✓ |
| {I5} | 2 | ✓ |
All five items are frequent.
Level 2. C₂ = L₁ ⋈ L₁ gives all 10 pairs. Nothing is pruned, since every 1-subset is frequent.
| C₂ itemset | count | in L₂? |
|---|---|---|
| {I1, I2} | 4 | ✓ |
| {I1, I3} | 4 | ✓ |
| {I1, I4} | 1 | ✗ |
| {I1, I5} | 2 | ✓ |
| {I2, I3} | 4 | ✓ |
| {I2, I4} | 2 | ✓ |
| {I2, I5} | 2 | ✓ |
| {I3, I4} | 0 | ✗ |
| {I3, I5} | 1 | ✗ |
| {I4, I5} | 0 | ✗ |
Level 3.
- Join: L₂ ⋈ L₂ = { {I1,I2,I3}, {I1,I2,I5}, {I1,I3,I5}, {I2,I3,I4}, {I2,I3,I5}, {I2,I4,I5} }
- Prune:
- {I1,I3,I5} has subset {I3,I5}, which is not frequent → ✗
- {I2,I3,I4} has subset {I3,I4} → ✗
- {I2,I3,I5} has subset {I3,I5} → ✗
- {I2,I4,I5} has subset {I4,I5} → ✗
- C₃ after prune = { {I1,I2,I3}, {I1,I2,I5} }. Scanning gives counts 2 and 2, so both go into L₃.
Level 4. L₃ ⋈ L₃ = { {I1,I2,I3,I5} }. Its subset {I2,I3,I5} is not frequent, so it is pruned. C₄ = ∅ and the algorithm terminates.
Apriori is level-wise, so all smaller subsets were already checked at earlier levels. Checking the (k−1)-subsets is enough.
6Generating strong association rules
For each frequent itemset l, take every non-empty proper subset s and form the rule s ⇒ (l − s). Output it if:
Since l is frequent, support is automatically satisfied. Only confidence needs checking.
Non-empty proper subsets: {I1,I2}, {I1,I5}, {I2,I5}, {I1}, {I2}, {I5}
| Rule | Confidence | Strong at 70%? |
|---|---|---|
| I1 ∧ I2 ⇒ I5 | 2/4 = 50% | ✗ |
| I1 ∧ I5 ⇒ I2 | 2/2 = 100% | ✓ |
| I2 ∧ I5 ⇒ I1 | 2/2 = 100% | ✓ |
| I1 ⇒ I2 ∧ I5 | 2/6 = 33% | ✗ |
| I2 ⇒ I1 ∧ I5 | 2/7 = 29% | ✗ |
| I5 ⇒ I1 ∧ I2 | 2/2 = 100% | ✓ |
With min_conf = 70%, only the 2nd, 3rd and last rules are strong.
Association rules can have more than one item on the right-hand side, e.g. I5 ⇒ I1 ∧ I2.
Apriori calculations are almost guaranteed in the exam. Show C₁/L₁, C₂/L₂, the join result for C₃, which candidates are pruned and why, the final L₃, and then the rules with confidence fractions. Use the machine above to check your own practice answers.
7Quick revision sheet
| Concept | Remember it as |
|---|---|
| Frequent pattern types | Itemsets · sequential patterns · structured patterns |
| Market basket analysis | Items bought together → layout, sales, catalogue, cross-marketing |
| Support | Usefulness; % of all transactions containing A ∪ B |
| Confidence | Certainty; P(B | A) = count(A ∪ B) / count(A) |
| Strong rule | ≥ min_sup and ≥ min_conf |
| 2-step mining | Find frequent itemsets → generate strong rules |
| Apriori | Agrawal & Srikant 1994; level-wise; one DB scan per level |
| Apriori property | Every subset of a frequent itemset is frequent; infrequent ⇒ supersets infrequent |
| Join | Lₖ₋₁ ⋈ Lₖ₋₁ where the first k−2 items match |
| Prune | Drop candidates with an infrequent (k−1)-subset |
| Rules | s ⇒ (l − s), confidence = sup(l)/sup(s) |
| Classic example result | L₃ = {I1,I2,I3}, {I1,I2,I5}; C₄ pruned |
?Self-check quiz
11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.