Frequent Itemsets — Apriori vs FP-Growth (MONKEY Dataset)

Data: 5 transactions, min_sup = 60% → count ≥ 3, min_conf = 80%

TID	Items
T100	M, O, N, K, E, Y
T200	D, O, N, K, E, Y
T300	M, A, K, E
T400	M, U, C, K, Y
T500	C, O, K, I, E

---

Part A — Apriori Algorithm

Step 1: Scan DB → Count 1-itemsets (C1 → L1)

Item	Count	Frequent?
M	3	✅
O	3	✅
N	2	❌
K	5	✅
E	4	✅
Y	3	✅
D,A,U,C,I	1–2	❌

L1 = {M, O, K, E, Y}

Step 2: Generate C2 from L1 (join L1×L1), scan DB → count → prune (L2)

Pair	Count	Frequent?
{M,O}	1	❌
{M,K}	3	✅
{M,E}	2	❌
{M,Y}	2	❌
{O,K}	3	✅
{O,E}	3	✅
{O,Y}	2	❌
{K,E}	4	✅
{K,Y}	3	✅
{E,Y}	2	❌

L2 = {M,K}, {O,K}, {O,E}, {K,E}, {K,Y} (all count ≥3)

Step 3: Generate C3 from L2 (apriori-gen + prune by apriori property)

Only pairs sharing a prefix and whose all 2-subsets are in L2 survive:

• {K,M,O}: needs {M,O} ∈ L2? No → pruned
• {K,M,Y}: needs {M,Y} ∈ L2? No → pruned
• {K,O,Y}: needs {O,Y} ∈ L2? No → pruned
• {K,O,E}: needs {K,O}✅, {K,E}✅, {O,E}✅ → valid candidate

Count {K,O,E} across DB → appears in T100, T200, T500 → count = 3 → ✅ frequent

L3 = {K,O,E} (count 3)

No candidates can be generated for L4 (only one itemset in L3).

Final Frequent Itemsets (Apriori)

L1: {M}(3) {O}(3) {K}(5) {E}(4) {Y}(3)
L2: {K,M}(3) {K,O}(3) {O,E}(3) {K,E}(4) {K,Y}(3)
L3: {K,O,E}(3)

Total = 11 frequent itemsets

---

Part B — FP-Growth Algorithm

Step 1: One scan → order items by frequency (descending): K(5) > E(4) > M(3) = O(3) = Y(3)

Step 2: Second scan → build FP-tree (each transaction's frequent items reordered by the above list)

TID	Ordered frequent items
T100	K,E,M,O,Y
T200	K,E,O,Y
T300	K,E,M
T400	K,M,Y
T500	K,E,O

FP-Tree Structure

Root
└── K:5
    ├── E:4
    │   ├── M:2
    │   │   └── O:1
    │   │       └── Y:1
    │   └── O:2
    │       └── Y:1
    └── M:1
        └── Y:1

Step 3: Mine conditional pattern bases, bottom-up (least frequent item first)

Item	Conditional Pattern Base	Conditional FP-tree (≥3)	Frequent patterns generated
Y	{K,E,M,O:1}, {K,E,O:1}, {K,M:1}	K:3	{K,Y}:3
O	{K,E,M:1}, {K,E:2}	K:3, E:3	{K,O}:3, {O,E}:3, {K,O,E}:3
M	{K,E:2}, {K:1}	K:3	{K,M}:3
E	{K:4}	K:4	{K,E}:4

(Base single-item frequent sets {K}, {E}, {M}, {O}, {Y} carry over directly.)

Final Frequent Itemsets (FP-Growth) — identical to Apriori

{M}, {O}, {K}, {E}, {Y}, {K,M}, {K,O}, {O,E}, {K,E}, {K,Y}, {K,O,E} → 11 itemsets

---

Efficiency Comparison

Aspect	Apriori	FP-Growth
DB scans required	Multiple (1 per itemset-length level → 4 scans here)	Only 2 scans total
Candidate generation	Explicit — generates and tests many candidates (join + prune)	None — mines directly via conditional pattern bases
Memory	Candidate sets can explode for large/dense data	FP-tree is typically compact (shared prefixes)
Best suited for	Sparse data, small number of frequent items	Dense data, long frequent patterns
Overall for this dataset	Works fine (small data), but does more redundant counting passes	Fewer scans, no candidate explosion — generally faster/more scalable

Conclusion: Both algorithms produce the same 11 frequent itemsets, but FP-growth is generally more efficient because it avoids the costly candidate-generation-and-test cycle of Apriori, needing only two database scans regardless of how long the frequent itemsets are.