Apriori on restaurant orders

Apriori algorithm and pruning principle

Apriori principle: if an itemset is frequent, all its subsets are frequent; so if an itemset is infrequent, no superset of it can be frequent. This pruning removes candidates without counting them.

L1 = frequent 1-itemsets (scan database)
for k = 2; L(k-1) not empty; k++:
    Ck = join L(k-1) with itself
    prune candidates having an infrequent (k-1)-subset
    scan database, count Ck
    Lk = candidates with count >= min_support
return all Lk

Solution (minimum support = 2 transactions)

Transactions: T1 {Beer, chicken, peanut}; T2 {Whisky, buff, coke, lemon}; T3 {Beer, buff, coke, lemon}; T4 {buff, coke, peanut}; T5 {Beer, peanut, lemon, fish}; T6 {peanut, coke}.

C₁ and L₁

L₁ = {Beer, buff, coke, lemon, peanut}

C₂ (all 10 pairs of L₁) and L₂

L₂ = {Beer-lemon, Beer-peanut, buff-coke, buff-lemon, coke-lemon, coke-peanut}

C₃ (join of L₂ pairs having the same first item, then prune)

L₃ = {buff, coke, lemon} (count 2). No C₄ can be formed, so the algorithm stops.

Answer: candidate sets C₁, C₂, C₃ as above. Large (frequent) itemsets: L₁ = {Beer, buff, coke, lemon, peanut}; L₂ = the six pairs; L₃ = {buff, coke, lemon}.