Apriori on 8 transactions, 25% support

Apriori algorithm

L1 = frequent items (scan database)
for k = 2 while L(k-1) is not empty:
    Ck = join(L(k-1)) and prune candidates with an infrequent subset
    scan database, count candidates
    Lk = candidates with support >= min_support
output all Lk; then generate rules with confidence >= min_conf

Principle: every subset of a frequent itemset must be frequent.

Solution

8 transactions, minimum support 25% → 0.25 × 8 = 2 transactions. The minimum confidence is not given, so 60% is assumed.

C₁ → L₁: A 5, B 2, C 5, D 6, E 6. All items have count ≥ 2, so L₁ = {A, B, C, D, E}.

C₂ counts: AB 1, AC 3, AD 4, AE 3, BC 1, BD 1, BE 1, CD 3, CE 3, DE 5. L₂ = {AC:3, AD:4, AE:3, CD:3, CE:3, DE:5} (AB, BC, BD, BE removed, so B appears in no larger itemset).

C₃ by joining L₂: ACD, ACE, ADE, CDE (others like ADC are the same). All 2-subsets are frequent (no pruning). Counts: ACD 2, ACE 1, ADE 3, CDE 2. L₃ = {ACD:2, ADE:3, CDE:2}.

C₄: ACDE would need ACE, which is infrequent, so it is pruned. Stop.

Frequent itemsets: A, B, C, D, E; AC, AD, AE, CD, CE, DE; ACD, ADE, CDE.

Rules from {A, D, E} (support 3)

Rules from some 2-itemsets

D → E 5/6 = 83.3%; E → D 5/6 = 83.3%; A → D 4/5 = 80%; D → A 4/6 = 66.7%; A → C 3/5 = 60%.

Rules from {A, C, D} and {C, D, E} (support 2)

A, C → D 2/3 = 66.7%; C, D → A 66.7%; C, D → E 66.7%; C, E → D 66.7%; the others (A, D → C 50%, D, E → C 40%, etc.) are weak.

Answer: frequent itemsets are listed above (largest {A, D, E}, {A, C, D}, {C, D, E}). Strong rules (confidence ≥ 60%) include A,E → D (100%), D → E (83.3%), E → D (83.3%), A → D (80%), A,D → E (75%), D → A (66.7%).