Algoritma Apriori & Frequent Itemsets

Capaian Pembelajaran

Setelah minggu ini kamu bisa:

1. Menjelaskan market basket analysis dan manfaat bisnisnya.
2. Menghitung support dan confidence secara manual.
3. Menjelaskan prinsip Apriori (sifat anti-monoton) dan mengapa ia memangkas ruang pencarian.
4. Menjalankan algoritma Apriori langkah demi langkah (join → prune → hitung → filter).
5. Mengimplementasikan Apriori dari nol dan dengan pustaka mlxtend.

1. Market Basket Analysis

Pertanyaan bisnis: "Produk apa yang sering dibeli bersamaan?"

Pemanfaatan:

2. Istilah Dasar

• Item: satu produk, mis. roti.
• Itemset: himpunan item, mis. {roti, mentega}. k-itemset = itemset berisi k item.
• Transaksi: satu keranjang belanja (sebuah itemset) dengan ID.
• Support count σ(X): jumlah transaksi yang memuat seluruh item di X.
• Support s(X) = σ(X) / N (N = jumlah transaksi).
• Frequent itemset: itemset dengan support ≥ minimum support (min_sup).
• Aturan asosiasi X ⇒ Y (X ∩ Y = ∅), misalnya {roti} ⇒ {mentega}.
  • support(X ⇒ Y) = s(X ∪ Y)
  • confidence(X ⇒ Y) = s(X ∪ Y) / s(X) = P(Y | X)

Contoh: 5 transaksi

• s({roti}) = 4/5 = 0.8
• s({roti, susu}) = 3/5 = 0.6 (TID 1, 4, 5)
• confidence({roti} ⇒ {susu}) = 0.6 / 0.8 = 0.75
• confidence({susu} ⇒ {roti}) = 0.6 / 0.8 = 0.75 (kebetulan sama; umumnya berbeda)

Penambangan aturan asosiasi = dua langkah:

1. Temukan semua frequent itemset (bagian yang mahal).
2. Bangkitkan aturan kuat dari frequent itemset: confidence ≥ min_conf (Minggu 5).

3. Masalah Ledakan Kombinasi

Dengan d item terdapat 2ᵈ − 1 itemset tak kosong. Untuk d = 100 → ≈ 1.27 × 10³⁰ itemset. Mustahil dihitung satu per satu (brute force).

4. Prinsip Apriori

Jika sebuah itemset frequent, semua subset-nya juga frequent. Ekuivalen (kontrapositif): jika sebuah itemset tidak frequent, semua superset-nya juga tidak frequent.

Ini berlaku karena support bersifat anti-monoton: X ⊆ Y ⇒ s(X) ≥ s(Y). Menambah item ke keranjang tidak mungkin menambah jumlah transaksi yang memuatnya.

Akibatnya: begitu {kopi} ternyata tidak frequent, kita tidak perlu menghitung {kopi, roti}, {kopi, susu, roti}, dst. → ruang pencarian terpangkas besar.

5. Algoritma Apriori (level-wise, breadth-first)

L1 = {1-itemset frequent}
k = 2
while L(k-1) tidak kosong:
    Ck = apriori_gen(L(k-1))           # JOIN + PRUNE
    for setiap transaksi t:            # SCAN database
        tambah count kandidat c ∈ Ck yang c ⊆ t
    Lk = {c ∈ Ck | count(c) ≥ min_sup}
    k = k + 1
return ∪ Lk

apriori_gen:

1. Join: gabungkan dua itemset di L(k−1) yang k−2 item pertamanya sama (setelah diurutkan) → kandidat berukuran k.
2. Prune: buang kandidat yang memiliki subset (k−1) yang tidak ada di L(k−1).

6. Contoh Lengkap (Han & Kamber)

9 transaksi, min_sup count = 2 (≈ 22%):

Iterasi 1 — C1 = L1 (semua ≥ 2):

Iterasi 2 — C2 = semua pasangan dari L1 (10 kandidat):

L2 = 6 itemset.

Iterasi 3 — Join L2 (prefix sama): {I1,I2}+{I1,I3} → {I1,I2,I3}, {I1,I2}+{I1,I5} → {I1,I2,I5}, {I1,I3}+{I1,I5} → {I1,I3,I5}, {I2,I3}+{I2,I4} → {I2,I3,I4}, {I2,I3}+{I2,I5} → {I2,I3,I5}, {I2,I4}+{I2,I5} → {I2,I4,I5}.

Prune:

• {I1,I3,I5}: subset {I3,I5} ∉ L2 → buang
• {I2,I3,I4}: {I3,I4} ∉ L2 → buang
• {I2,I3,I5}: {I3,I5} ∉ L2 → buang
• {I2,I4,I5}: {I4,I5} ∉ L2 → buang

C3 = {I1,I2,I3} (count 2), {I1,I2,I5} (count 2) → L3 = keduanya.

Iterasi 4 — Join L3 → {I1,I2,I3,I5}; prune: subset {I2,I3,I5} ∉ L3 → buang. C4 kosong → selesai.

Total frequent itemset = 5 + 6 + 2 = 13.

7. Kompleksitas & Kelemahan Apriori

• Banyak scan database (sebanyak panjang itemset terpanjang + 1).
• Kandidat bisa sangat banyak: 10⁴ item frequent → ≈ 10⁷ kandidat 2-itemset.
• Min_sup terlalu rendah → ledakan kandidat; terlalu tinggi → pola menarik (item jarang tapi bernilai tinggi) terlewat.

Perbaikan: hash-based counting, partitioning, sampling, dan FP-Growth (Minggu 5) yang tidak membangkitkan kandidat.

8. Representasi Ringkas: Closed & Maximal

• Maximal frequent itemset: frequent, dan tidak ada superset yang frequent.
• Closed itemset: tidak ada superset dengan support yang sama.

Hubungan: maximal ⊆ closed ⊆ frequent. Pada contoh di atas, maximal = {I1,I2,I3}, {I1,I2,I5}, {I2,I4}.

9. Format Data untuk Pustaka

mlxtend membutuhkan DataFrame one-hot boolean (baris = transaksi, kolom = item):

from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori

te = TransactionEncoder()
onehot = pd.DataFrame(te.fit(transaksi).transform(transaksi), columns=te.columns_)
fi = apriori(onehot, min_support=0.05, use_colnames=True)

Ringkasan

• support = proporsi transaksi yang memuat itemset; confidence = P(Y|X).
• Support anti-monoton → jika X tidak frequent, semua superset X tidak frequent.
• Apriori: level-wise; tiap level = join → prune → scan & hitung → filter min_sup.
• Kelemahan: banyak scan dan kandidat → motivasi FP-Growth.

Bacaan

• Han, Kamber & Pei — Bab 6 (Mining Frequent Patterns, Associations, and Correlations).
• Agrawal & Srikant (1994) — Fast Algorithms for Mining Association Rules.

Tugas Minggu Ini

1. Kerjakan lab.ipynb sampai selesai.
2. Kerjakan kuis (di web, atau baca quiz.json).
3. Isi exercise.py, lalu cek: python check.py 4