FP-Growth & Evaluasi Aturan Asosiasi

Capaian Pembelajaran

Setelah minggu ini kamu bisa:

1. Membangun FP-Tree dari data transaksi secara manual.
2. Menjelaskan cara kerja FP-Growth (conditional pattern base & conditional FP-tree).
3. Membandingkan kinerja Apriori vs. FP-Growth.
4. Membangkitkan aturan asosiasi dari frequent itemset.
5. Menilai aturan dengan lift, leverage, conviction dan menafsirkannya untuk strategi bisnis.

1. Motivasi

Apriori lambat karena (1) membangkitkan sangat banyak kandidat dan (2) men-scan database berulang kali. FP-Growth (Han, Pei & Yin, 2000):

• Hanya 2 kali scan database.
• Tanpa pembangkitan kandidat — memakai pendekatan divide-and-conquer.
• Data dikompres ke struktur pohon prefix: FP-Tree (Frequent Pattern Tree).

2. Membangun FP-Tree

1. Scan 1: hitung support tiap item; buang item tidak frequent; susun F-list = item frequent diurutkan support menurun (seri → urut nama).
2. Scan 2: untuk setiap transaksi, buang item tidak frequent, urutkan sesuai F-list, lalu sisipkan sebagai jalur dari akar (null). Prefix yang sama berbagi node → count bertambah.
3. Header table: untuk tiap item simpan daftar (node-link) semua node item tersebut di pohon.

Contoh (Han & Kamber, min_sup count = 2)

Support: I2:7, I1:6, I3:6, I4:2, I5:2 → F-list = I2, I1, I3, I4, I5

FP-Tree hasil:

null
├── I2:7
│   ├── I1:4
│   │   ├── I5:1
│   │   ├── I4:1
│   │   └── I3:2
│   │       └── I5:1
│   ├── I4:1
│   └── I3:2
└── I1:2
    └── I3:2

9 transaksi (22 item) dikompres menjadi 10 node.

3. Menambang FP-Tree (FP-Growth)

Proses item dari bawah F-list (paling jarang) ke atas. Untuk item a:

1. Conditional pattern base (CPB) dari a: kumpulan prefix path dari akar menuju setiap node a, dengan count = count node a.
2. Bangun conditional FP-tree dari CPB (buang item yang count totalnya < min_sup).
3. Tambang secara rekursif; setiap pola yang ditemukan diberi akhiran (suffix) a.

Contoh untuk I5

• CPB(I5) = { ⟨I2, I1⟩ : 1, ⟨I2, I1, I3⟩ : 1 }
• Hitung: I2 = 2, I1 = 2, I3 = 1 (< 2, buang)
• Conditional FP-tree: null → I2:2 → I1:2
• Pola: {I2, I5}:2, {I1, I5}:2, {I2, I1, I5}:2

Ringkasan tiap item

Hasilnya sama persis dengan Apriori (13 frequent itemset) — hanya caranya yang berbeda.

4. Apriori vs. FP-Growth

5. Dari Frequent Itemset ke Aturan

Untuk setiap frequent itemset L dan setiap subset tak kosong A ⊂ L: bentuk aturan A ⇒ (L − A), simpan jika confidence ≥ min_conf.

Contoh L = {I1, I2, I5} (support 2/9):

6. Confidence Saja Bisa Menyesatkan

Contoh klasik: 10.000 transaksi; 6.000 membeli game, 7.500 membeli video, 4.000 membeli keduanya.

• confidence(game ⇒ video) = 4000/6000 = 66.7% → tampak kuat.
• Tetapi P(video) = 75%! Membeli game justru menurunkan peluang membeli video.

Maka perlu metrik korelasi:

Untuk contoh game–video: lift = 0.4 / (0.6 · 0.75) = 0.89 < 1 → korelasi negatif.

Contoh perhitungan lengkap

s(roti) = 0.40, s(mentega) = 0.30, s(roti ∪ mentega) = 0.24.

• confidence(roti ⇒ mentega) = 0.24 / 0.40 = 0.60
• lift = 0.24 / (0.40 · 0.30) = 2.0 → pembeli roti 2× lebih mungkin membeli mentega dibanding rata-rata
• leverage = 0.24 − 0.12 = 0.12
• conviction = (1 − 0.30) / (1 − 0.60) = 1.75

Lift bersifat simetris (lift(A⇒B) = lift(B⇒A)); confidence dan conviction tidak.

7. Dari Aturan ke Strategi Bisnis

Ringkasan

• FP-Growth: 2 scan, tanpa kandidat; FP-Tree memadatkan transaksi berbagi prefix.
• Tambang dari item paling jarang: CPB → conditional FP-tree → rekursif.
• Aturan: A ⇒ L − A; saring dengan min_conf.
• Gunakan lift/leverage/conviction — confidence tinggi belum tentu korelasi positif.

Bacaan

• Han, Kamber & Pei — Bab 6.2.4 (FP-Growth) dan 6.3 (Pattern Evaluation).
• Han, Pei & Yin (2000) — Mining Frequent Patterns without Candidate Generation.

Tugas Minggu Ini

1. Kerjakan lab.ipynb (perbandingan waktu Apriori vs. FP-Growth).
2. Kerjakan kuis (di web, atau baca quiz.json).
3. Isi exercise.py, lalu cek: python check.py 5