Introduction to Data Mining

<<< Previous Up Next >>>

Lesson 6.6.1

APRIORI's Frequent/Candidate generation

Frequent itemset generation

Scan D and count each itemset in C_k, if the count is greater than minSupp, then add that itemset to L_k.

Candidate itemset generation

For k = 1, C₁ = all itemsets of length = 1.

For k > 1, generate C_k from L_k-1 as follows:

The join step:

C_k = k-2 way join of L_k-1 with itself.

If both {a₁,..,a_k-2, a_k-1} & {a₁,.., a_k-2, a_k} are in L_k-1, then add {a₁,..,a_k-2, a_k-1, a_k} to C_k.

The items are always stored in the sorted order.

The prune step:

Remove {a₁, …,a_k-2, a_k-1, a_k}, if it contains a non-frequent (k-1) subset.

An Example

TID	Itemsets	1. scan D → C₁ = 1:2, 2:3, 3:3, 4:1, 5:3. → L₁ = 1:2, 2:3, 3:3, , 5:3. → C₂ = 12, 13, 15, 23, 25, 35. 2. scan D → C₂ = 12:1, 13:2, 15:1, 23:2, 25:3, 35:2. → L₂ = , 13:2, , 23:2, 25:3, 35:2. → C₃ = 235 → Pruned C₃= 235 3. scan D → C₃ = 235:2 → L₃ = 235:2
T100	1 3 4
T200	2 3 5
T300	1 2 3 5
T400	2 5
	minSupp = 0.5

An Example showing why order of items should be maintained

TID	Itemsets	1. scan D → C₁ = 1:2, 2:3, 3:3, 4:1, 5:3. → L₁ = 1:2, 2:3, 3:3, , 5:3. → C₂ = 12, 13, 15, 23, 25, 35. 2. scan D → C₂ = 12:1, 13:2, 15:1, 23:2, 25:3, 35:2. Suppose the order of items is now decided as: 5,4,3,2,1. → L₂ = , 31:2, , 32:2, 52:3, 53:2. → C₃ = 321, 532. → Pruned C₃= 532. 3. scan D → C₃ = 532:2 → L₃ = 532:2
T100	1 3 4
T200	2 3 5
T300	1 2 3 5
T400	2 5
	minSupp = 0.5

<<< Previous Up Next >>>

	C_k = k-2 way join of L_k-1 with itself.
	If both {a₁,..,a_k-2, a_k-1} & {a₁,.., a_k-2, a_k} are in L_k-1, then add {a₁,..,a_k-2, a_k-1, a_k} to C_k.
	The items are always stored in the sorted order.