Apriori Algorithm — 15-Transaction Database (9 Binary Attributes)

Given: min_sup count = 2, min_conf = 70%, database D of 15 transactions over items A1–A9.

Step 1: Scan D → Count 1-itemsets (C1)

Item	Support count	Frequent (≥2)?
A1	2	✅
A2	6	✅
A3	6	✅
A4	4	✅
A5	8	✅
A6	5	✅
A7	7	✅
A8	4	✅
A9	2	✅

L1 = {A1, A2, A3, A4, A5, A6, A7, A8, A9} — every item clears the low min_sup=2 threshold.

L1: [A1]─[A2]─[A3]─[A4]─[A5]─[A6]─[A7]─[A8]─[A9]
     2    6    6    4    8    5    7    4    2

Step 2: Generate C2 (all pairs of L1), scan D, prune → L2

Only pairs with support count ≥ 2 survive (out of the 36 possible pairs, most drop out):

Pair	Count	Pair	Count
A1,A5	2 ✅	A4,A7	2 ✅
A2,A3	3 ✅	A5,A6	3 ✅
A2,A4	3 ✅	A5,A7	5 ✅
A2,A6	2 ✅	A5,A8	2 ✅
A2,A7	2 ✅	A6,A7	3 ✅
A2,A9	2 ✅	A6,A8	2 ✅
A3,A5	3 ✅
A3,A7	3 ✅

(All other 22 pairs, e.g. A1-A2, A1-A3, A2-A5, A3-A4, A4-A5, A7-A8, etc., had count ≤1 and were pruned.)

L2 = {A1A5, A2A3, A2A4, A2A6, A2A7, A2A9, A3A5, A3A7, A4A7, A5A6, A5A7, A5A8, A6A7, A6A8} (14 itemsets)

        L1 (9 items) ──join+prune──▶ L2 (14 pairs, out of 36 possible)

Step 3: Generate C3 via apriori-gen (join L2 with itself + prune using apriori property)

Joining pairs sharing a common first item, keeping only candidates whose every 2-subset is in L2:

Candidate	2-subsets check	Valid?	DB count	Frequent?
A2,A3,A7	A2A3✅ A2A7✅ A3A7✅	✅	0	❌
A2,A4,A7	A2A4✅ A2A7✅ A4A7✅	✅	1	❌
A2,A6,A7	A2A6✅ A2A7✅ A6A7✅	✅	2	✅
A3,A5,A7	A3A5✅ A3A7✅ A5A7✅	✅	3	✅
A5,A6,A7	A5A6✅ A5A7✅ A6A7✅	✅	1	❌
A5,A6,A8	A5A6✅ A5A8✅ A6A8✅	✅	2	✅

L3 = {A2A6A7(2), A3A5A7(3), A5A6A8(2)}

Step 4: Try C4

No two itemsets in L3 share a common 2-item prefix (A2A6A7, A3A5A7, A5A6A8 are all disjoint in their first two items) → no valid C4 candidates → algorithm terminates.

Final Frequent Itemsets

L1 (9):  A1 A2 A3 A4 A5 A6 A7 A8 A9
L2 (14): A1A5  A2A3  A2A4  A2A6  A2A7  A2A9  A3A5
         A3A7  A4A7  A5A6  A5A7  A5A8  A6A7  A6A8
L3 (3):  A2A6A7   A3A5A7   A5A6A8

Total = 26 frequent itemsets

Strong Rules Example (from the maximal itemset A3,A5,A7 — count 3)

Confidence check for rules generated from {A3,A5,A7}:

• A3,A5 ⇒ A7: conf = 3/support(A3A5)=3/3 = 100% ✅ strong
• A3,A7 ⇒ A5: conf = 3/support(A3A7)=3/3 = 100% ✅ strong
• A5,A7 ⇒ A3: conf = 3/support(A5A7)=3/5 = 60% ❌ below 70% threshold

Only the first two rules meet min_conf = 70% and would be output as strong association rules.