The Apriori Algorithm

Source: Unit 4 §6

The itemset lattice has $2^d$ nodes, and Apriori is the observation that lets you refuse to look at most of them.

The Apriori principle

◎Exam cueThe principle, in both directions

If an itemset is FREQUENT, then all of its subsets must also be frequent.

Conversely - and this is the direction you actually use - if an itemset is INFREQUENT, then all of its supersets are also infrequent.

Formally, support is anti-monotone:

$$\forall X, Y : \; (X \subseteq Y) \Rightarrow s(X) \geq s(Y)$$

Adding an item to an itemset can never increase its support, because every transaction containing the bigger itemset already contained the smaller one.

One infrequent single item takes half the lattice with it. That is the whole of Apriori, drawn once.

Once {C} fails the support test, {A,C}, {B,C}, {C,D}, {A,B,C} and every other superset of {C} are known to fail as well, so they are never generated. This is what prunes the exponential lattice down to something countable.

The algorithm

→StepsApriori

1. Let k = 1.
2. Generate the frequent itemsets of length 1.
3. Repeat until no new frequent itemsets are found:
4.     Generate length-(k+1) candidate itemsets from the length-k frequent itemsets.
5.     Prune candidates that contain any infrequent length-k subset.
6.     Count the support of each surviving candidate by scanning the database.
7.     Eliminate the infrequent candidates, keeping only the frequent ones.
8.     k = k + 1.

Worked example 1

Database D with 4 transactions: {1,3,4}, {2,3,5}, {1,2,3,5}, {2,5}. Minimum support = 50%, which with 4 transactions means a count ≥ 2.

→StepsThree passes over D

1. Pass 1 - C1 → scan → L1. Counts: {1}:2, {2}:3, {3}:3, {4}:1 ✗, {5}:3. Item 4 appears once, below the threshold, so it is dropped. L1 = {1}, {2}, {3}, {5}.
2. Pass 2 - C2 (from L1) → scan → L2. Counts: {1,2}:1 ✗, {1,3}:2, {1,5}:1 ✗, {2,3}:2, {2,5}:3, {3,5}:2. Note that no pair involving item 4 was even generated. L2 = {1,3}, {2,3}, {2,5}, {3,5}.
3. Pass 3 - C3 → scan → L3. The only surviving candidate is {2,3,5} with a count of 2. L3 = {2,3,5}.
4. Stop. No 4-itemset candidate can be built from a single 3-itemset, so the frequent itemsets end at {2,3,5} with support 2.

Worked example 2: what pruning actually saves

Six items with a minimum support of 3. Coke (count 2) and Eggs (count 1) are both infrequent.

#Numbers41 candidates become 13

• Without pruning, you enumerate every subset: $\binom{6}{1} + \binom{6}{2} + \binom{6}{3} = 6 + 15 + 20 = \mathbf{41}$ candidates.
• With support-based pruning: $6 + 6 + 1 = \mathbf{13}$ candidates - no pair or triplet involving Coke or Eggs is ever generated.

Speeding up Apriori

Strategy	What it reduces	How
Reduce candidates	M	use the Apriori principle to prune, instead of the complete search with M = 2^d
Reduce transactions	N	shrink N as the itemset size grows (vertical mining)
Reduce comparisons	NM	use a hash tree so a transaction is matched only against the candidates in its bucket, not against every candidate

≡FactsHow the hash tree works

• The leaves hold the counters for the 3-item itemsets.
• Sort a transaction's items, then form all of its 3-item subsets.
• Hash each subset's items with hash(x) = x mod 3 to walk down to the right leaf, and increment the counter you land on.

Factors affecting complexity

Factor	Effect
Minimum support threshold	lower threshold → more frequent itemsets → more candidates and longer maximum itemsets
Dimensionality (number of items)	more space needed for support counts; more computation and I/O
Database size	Apriori makes multiple passes, so runtime grows with the number of transactions
Average transaction width	wider (denser) transactions → longer maximum itemsets and more hash-tree traversals