Apriori on four transactions, support 2

Apriori algorithm

L1 = {frequent 1-itemsets}
for k = 2 while L(k-1) is not empty:
    Ck = candidates from joining L(k-1) with itself
         (prune those having an infrequent (k-1)-subset)
    count Ck in the database; Lk = {c in Ck : count(c) >= min_sup}
return union of Lk

Candidate sets (C) are the itemsets generated at each level; large (frequent) sets (L) are those that meet the minimum support.

Solution (minimum support count = 2)

Transactions: 10: A C D; 20: B C E; 30: A B C E; 40: B E.

Scan 1: C₁

L₁ = {A, B, C, E}

Scan 2: C₂ (all pairs from L₁)

L₂ = {AC, BC, BE, CE}

C₃: join L₂ itemsets that share the first item: BC and BE give {B, C, E}. Prune check: its subsets BC, BE and CE are all in L₂, so it stays. (Other 3-itemsets such as {A, B, C} and {A, C, E} are not produced by the join, and they would be pruned anyway because they contain the infrequent AB or AE.)

Scan 3: count(BCE) = 2 (transactions 20 and 30) → L₃ = {B, C, E}.

C₄: no candidate can be formed from a single 3-itemset, so the algorithm stops.

Answer: Candidate sets: C₁, C₂ and C₃ = {BCE}. Large (frequent) itemsets: L₁ = {A, B, C, E}; L₂ = {AC, BC, BE, CE}; L₃ = {BCE}.