Clustering mencari kelompok lewat jarak dan PCA mencari arah lewat variansi — keduanya membutuhkan data berbentuk angka pada kolom-kolom fitur. Tetapi ada satu pola unsupervised yang bentuk datanya sama sekali berbeda: struk belanja. Di dalamnya tidak ada jarak antar pelanggan maupun variansi fitur; yang ada hanyalah daftar barang yang kebetulan dibayar bersama di kasir. Association rule mining adalah keluarga teknik yang menggolongkan pola dari kebersamaan itu: barang apa yang cenderung hadir satu struk dengan barang lain. Pertanyaan semacam “pembeli kopi bubuk biasanya membeli apa lagi?” dijawab tanpa label, tanpa model, murni dengan menghitung. Pada chapter ini kita bedah tiga ukurannya — support, confidence, lift — lalu membangun versi kecil algoritma Apriori dengan Python murni di atas dua belas struk Toko Kopi Kita.

Dari Struk ke Aturan #

Format datanya berbeda dari semua chapter sebelumnya. Clustering dan PCA memakai tabel — setiap baris satu objek, setiap kolom satu fitur. Market basket analysis (analisis keranjang pasar, sebutan klasik untuk association rule mining) memakai daftar transaksi: setiap elemen adalah satu struk, dinyatakan sebagai himpunan item yang dibeli. Dari format itu, yang dicari adalah aturan berbentuk X -> Y: “transaksi yang memuat item X cenderung juga memuat item Y”. X disebut antecedent (pendahulu) dan Y consequent (akibat).

Dua belas struk contoh kita memuat tujuh item berbeda: kopi bubuk, gula pasir, susu kental, teh celup, roti tawar, mie instan, dan satu yang jarang — sirup karamel. Aturan yang layak ditambang harus melewati tiga pintu ukuran berbeda, dan ketiganya dihitung dari hitungan sederhana.

Tiga Ukuran: Support, Confidence, Lift #

Support menjawab “seberapa sering aturan ini berlaku di seluruh data” — ia menyaring pola langka yang tidak layak tindak lanjut. Confidence menjawab “seberapa sering aturan ini benar” — dari semua struk yang memuat X, berapa persen yang juga memuat Y. Lift menjawab pertanyaan yang paling penting: “apakah Y memang khusus muncul bersama X, atau memang semua orang membeli Y sehingga kebersamaannya biasa saja”.

text 
support(X)          = jumlah struk yang memuat X / total struk
support(X -> Y)     = jumlah struk yang memuat X dan Y / total struk
confidence(X -> Y)  = support(X -> Y) / support(X)
lift(X -> Y)        = confidence(X -> Y) / support(Y)

Rumus lift menyimpan makna terdalam: karena confidence/support(Y) bisa ditulis ulang sebagai support(X dan Y) / (support(X) × support(Y)), lift adalah perbandingan antara kebersamaan yang teramati dengan kebersamaan yang diharapkan bila X dan Y saling bebas. Tafsirannya:

Nilai liftPembacaan
jauh di atas 1X dan Y saling menguatkan — muncul bersama lebih sering dari sekadar kebetulan
sekitar 1keberadaan X tidak mengubah peluang Y — keduanya bergerak sendiri-sendiri
di bawah 1X dan Y saling menggeser — pembeli X justru lebih jarang membeli Y

Menghitung Satu Aturan dengan Tangan #

Sebelum membangun algoritma, kita hitung dulu satu aturan secara teliti: kopi bubuk -> susu kental. Kodenya Python murni — himpunan (set) dan penghitungan, tanpa pustaka lain:

python 
# 12 struk belanja Toko Kopi Kita (satu himpunan item per struk)
transaksi = [
    {"kopi bubuk", "gula pasir", "susu kental"},
    {"kopi bubuk", "gula pasir"},
    {"kopi bubuk", "susu kental"},
    {"teh celup", "gula pasir"},
    {"kopi bubuk", "gula pasir", "susu kental"},
    {"mie instan", "teh celup"},
    {"mie instan", "roti tawar"},
    {"kopi bubuk", "gula pasir", "roti tawar"},
    {"teh celup", "gula pasir", "roti tawar"},
    {"kopi bubuk", "susu kental", "roti tawar", "sirup karamel"},
    {"mie instan", "roti tawar"},
    {"kopi bubuk", "gula pasir", "susu kental"},
]

n = len(transaksi)

def hitung(itemset):
    # berapa struk yang memuat seluruh item dalam itemset
    return sum(1 for t in transaksi if itemset <= t)

n_kopi = hitung({"kopi bubuk"})
n_susu = hitung({"susu kental"})
n_keduanya = hitung({"kopi bubuk", "susu kental"})

sup_kopi = n_kopi / n
sup_susu = n_susu / n
sup_keduanya = n_keduanya / n
conf = sup_keduanya / sup_kopi
lift = conf / sup_susu

print("total struk                : %d" % n)
print("struk memuat kopi bubuk    : %d  -> support(kopi)     = %d/%d = %.3f"
      % (n_kopi, n_kopi, n, sup_kopi))
print("struk memuat susu kental   : %d  -> support(susu)     = %d/%d = %.3f"
      % (n_susu, n_susu, n, sup_susu))
print("struk memuat keduanya      : %d  -> support(kopi,susu) = %d/%d = %.3f"
      % (n_keduanya, n_keduanya, n, sup_keduanya))
print()
print("aturan: kopi bubuk -> susu kental")
print("confidence = %.3f / %.3f = %.3f" % (sup_keduanya, sup_kopi, conf))
print("lift       = %.3f / %.3f = %.3f" % (conf, sup_susu, lift))

Output yang Dihasilkan:

text 
total struk                : 12
struk memuat kopi bubuk    : 7  -> support(kopi)     = 7/12 = 0.583
struk memuat susu kental   : 5  -> support(susu)     = 5/12 = 0.417
struk memuat keduanya      : 5  -> support(kopi,susu) = 5/12 = 0.417

aturan: kopi bubuk -> susu kental
confidence = 0.417 / 0.583 = 0.714
lift       = 0.714 / 0.417 = 1.714

Mari kita telaah baris-baris kodenya:

  1. transaksi adalah list of set — satu set per struk; format ini memungkinkan uji keanggotaan serentak lewat operator himpunan.
  2. itemset <= t bukan perbandingan angka melainkan subset: benar bila semua anggota itemset hadir di struk t; sum(1 for ...) menghitung berapa struk yang memenuhi syarat itu.
  3. Support dihitung dua tingkat: untuk item tunggal (7/12 dan 5/12) dan untuk pasangan (5/12) — pasangan kopi-susu hadir di 5 struk dari 12.
  4. Confidence 0,714 berarti 5 dari 7 pembeli kopi bubuk (71,4%) juga membawa susu kental pulang.
  5. Lift 1,714 berarti pembeli kopi bubuk 1,7 kali lebih mungkin membeli susu kental dibanding pelanggan yang diambil acak. Periksa lewat definisi harapan: bila kedua item bebas, support bersama yang diharapkan = 0,583 × 0,417 ≈ 0,243; yang teramati 0,417 — hampir dua kalinya.

Apriori Sederhana Buatan Sendiri #

Satu aturan bisa dihitung tangan; satu toko memiliki ratusan kandidat aturan. Algoritma Apriori menambangnya bertingkat-tingkat dengan satu prinsip penghematan yang cerdas: pasangan hanya bisa sering muncul bila kedua anggotanya juga sering muncul sendirian. Karena itu item yang jarang — seperti sirup karamel yang cuma satu struk — boleh dibuang sejak awal, dan pasangan yang menyentuhnya tidak perlu dihitung sama sekali. Kita bangun versi mini ini dengan dict untuk menghitung dan itertools.combinations untuk membuat kandidat pasangan:

python 
from itertools import combinations

transaksi = [
    {"kopi bubuk", "gula pasir", "susu kental"},
    {"kopi bubuk", "gula pasir"},
    {"kopi bubuk", "susu kental"},
    {"teh celup", "gula pasir"},
    {"kopi bubuk", "gula pasir", "susu kental"},
    {"mie instan", "teh celup"},
    {"mie instan", "roti tawar"},
    {"kopi bubuk", "gula pasir", "roti tawar"},
    {"teh celup", "gula pasir", "roti tawar"},
    {"kopi bubuk", "susu kental", "roti tawar", "sirup karamel"},
    {"mie instan", "roti tawar"},
    {"kopi bubuk", "gula pasir", "susu kental"},
]

n = len(transaksi)
min_transaksi = 2  # ambang: muncul di minimal 2 dari 12 struk

# Tingkat 1: hitung kemunculan tiap item dengan dict
hitung_item = {}
for t in transaksi:
    for item in t:
        hitung_item[item] = hitung_item.get(item, 0) + 1

semua_item = sorted(hitung_item)
sering = [i for i in semua_item if hitung_item[i] >= min_transaksi]
terjarang = [i for i in semua_item if hitung_item[i] < min_transaksi]

print("seluruh item unik : %d" % len(semua_item))
print("jarang, dibuang   : %s" % ", ".join(terjarang))
print("lulus tingkat 1   : %d item -> %s" % (len(sering), ", ".join(sering)))
print()

# Tingkat 2: hitung pasangan HANYA dari item yang lolos tingkat 1
hitung_pasangan = {}
for t in transaksi:
    for a, b in combinations(sorted(t & set(sering)), 2):
        hitung_pasangan[(a, b)] = hitung_pasangan.get((a, b), 0) + 1

sering_pasangan = {p: c for p, c in hitung_pasangan.items() if c >= min_transaksi}
print("pasangan yang lolos: %d" % len(sering_pasangan))
for (a, b), c in sorted(sering_pasangan.items()):
    print("  {%s, %s}: %d struk" % (a, b, c))

Output yang Dihasilkan:

text 
seluruh item unik : 7
jarang, dibuang   : sirup karamel
lulus tingkat 1   : 6 item -> gula pasir, kopi bubuk, mie instan, roti tawar, susu kental, teh celup

pasangan yang lolos: 7
  {gula pasir, kopi bubuk}: 5 struk
  {gula pasir, roti tawar}: 2 struk
  {gula pasir, susu kental}: 3 struk
  {gula pasir, teh celup}: 2 struk
  {kopi bubuk, roti tawar}: 2 struk
  {kopi bubuk, susu kental}: 5 struk
  {mie instan, roti tawar}: 2 struk

Mari kita telaah mekanismenya:

  1. Dict hitung_item adalah penghitung frekuensi: kunci berupa nama item, nilai berupa jumlah struk; dict.get(item, 0) + 1 menambah entri baru atau melanjutkan yang lama.
  2. Penyaringan tingkat 1 membuang sirup karamel (1 struk < ambang 2). Inilah kekuatan prinsip Apriori: dari 7 item, pasangan yang perlu dihitung tinggal C(6,2) = 15 — 6 kandidat yang menyentuh sirup karamel tidak pernah tersentuh, padahal hasilnya pasti sama dengan nol.
  3. t & set(sering) mengiris struk dengan item yang lolos (operator irisan himpunan), lalu combinations(sorted(...), 2) membentuk semua pasangan dari sisanya — pasangan selalu dibuat dari urutan terurut sehingga kunci (a, b) konsisten antar-struk.
  4. Dict hitung_pasangan menghitung frekuensi tiap pasangan lintas struk; saringan akhir menyisakan 7 pasangan yang muncul minimal dua kali.

Pada data 12 struk penghematan ini terasa kecil; pada 50 ribu struk dengan 5 ribu jenis item, memangkas ribuan item jarang sebelum membentuk kandidat adalah beda antara selesai dalam hitungan detik dan tidak selesai sama sekali.

Aturan Sederhana yang Ditemukan #

Tingkat terakhir: setiap pasangan sering menghasilkan dua aturan (X → Y dan Y → X), dihitung confidence dan lift-nya, disaring dengan ambang kepercayaan, lalu diurutkan berdasarkan lift:

python 
from itertools import combinations

transaksi = [
    {"kopi bubuk", "gula pasir", "susu kental"},
    {"kopi bubuk", "gula pasir"},
    {"kopi bubuk", "susu kental"},
    {"teh celup", "gula pasir"},
    {"kopi bubuk", "gula pasir", "susu kental"},
    {"mie instan", "teh celup"},
    {"mie instan", "roti tawar"},
    {"kopi bubuk", "gula pasir", "roti tawar"},
    {"teh celup", "gula pasir", "roti tawar"},
    {"kopi bubuk", "susu kental", "roti tawar", "sirup karamel"},
    {"mie instan", "roti tawar"},
    {"kopi bubuk", "gula pasir", "susu kental"},
]

n = len(transaksi)

def hitung(itemset):
    # jumlah struk yang memuat seluruh item dalam itemset
    return sum(1 for t in transaksi if itemset <= t)

def support(itemset):
    return hitung(itemset) / n

min_support = 2 / n   # pasangan minimal muncul di 2 struk
min_confidence = 0.4  # aturan minimal benar 40% kalau itemnya ada

semua_item = sorted(set().union(*transaksi))
sering = [i for i in semua_item if support({i}) >= min_support]

aturan = []
for a, b in combinations(sering, 2):
    if hitung({a, b}) / n < min_support:
        continue
    for x, y in ((a, b), (b, a)):             # dua arah: X -> Y dan Y -> X
        conf = hitung({a, b}) / hitung({x})   # dari hitungan bulat
        lift = conf / support({y})
        if conf >= min_confidence:
            aturan.append((x, y, support({a, b}), conf, lift))

aturan.sort(key=lambda r: (-r[4], r[0]))      # lift tertinggi dulu
print("aturan                          support  confidence   lift")
for x, y, s, conf, lift in aturan:
    print("%-18s -> %-12s %7.3f %11.3f %7.3f" % (x, y, s, conf, lift))

Output yang Dihasilkan:

text 
aturan                          support  confidence   lift
kopi bubuk         -> susu kental    0.417       0.714   1.714
susu kental        -> kopi bubuk     0.417       1.000   1.714
roti tawar         -> mie instan     0.167       0.400   1.600
mie instan         -> roti tawar     0.167       0.667   1.600
gula pasir         -> kopi bubuk     0.417       0.714   1.224
kopi bubuk         -> gula pasir     0.417       0.714   1.224
teh celup          -> gula pasir     0.167       0.667   1.143
gula pasir         -> susu kental    0.250       0.429   1.029
susu kental        -> gula pasir     0.250       0.600   1.029
roti tawar         -> gula pasir     0.167       0.400   0.686
roti tawar         -> kopi bubuk     0.167       0.400   0.686

Tabel ini layak dibaca pelan-pelan, karena di dalamnya tersimpan empat pelajaran sekaligus:

  1. Aturan terkuat: kopi bubuk -> susu kental dengan lift 1,714 — dan arah baliknya menarik: susu kental -> kopi bubuk ber-confidence 1,000, artinya semua pembeli susu kental (5 dari 5) tanpa kecuali juga membeli kopi bubuk. Susu kental adalah penanda kopi yang nyaris sempurna di toko ini.
  2. Confidence itu asimetris, lift tidak. kopi -> susu (0,714) dan susu -> kopi (1,000) berbeda jauh, tetapi keduanya ber-lift sama 1,714 — lift mengukur kekuatan hubungan, confidence mengukur arah keandalan aturan.
  3. Lift di sekitar 1 berarti tidak berita. gula pasir -> susu kental (1,029) praktis menyatakan kemerdekaan: membeli gula nyaris tidak mengubah peluang membeli susu. Aturan seperti ini banyak dihasilkan mesin, tetapi tidak bernilai tindak lanjut.
  4. Lift di bawah 1 juga berita. roti tawar -> kopi bubuk dan roti tawar -> gula pasir (0,686) memperlihatkan pembeli roti justru lebih jarang membeli kopi dan gula — kebiasaan belanja yang berbeda, mungkin kebutuhan sarapan keluarga yang tidak menyertakan kopi seduhan sendiri.

Dari sini tindak lanjut bisnisnya mengalir alami: menempatkan kopi bubuk dan susu kental dalam satu pandangan di rak, membuat paket “kopi + susu” dengan harga khusus, atau — dari temuan arah baliknya — menjadikan susu kental umpan tawaran produk kopi baru bagi pembeli susu. Seperti clustering, association rules adalah alat menemukan; keputusan bisnis tetap milik manusia yang memahami tokonya.

Rangkuman #

  • Association rule mining menggali pola kebersamaan item dalam transaksi — unsupervised learning pada data berbentuk daftar himpunan, bukan tabel fitur.
  • Tiga ukuran menopangnya: support (seberapa sering aturan berlaku), confidence (seberapa sering benar), lift (apakah kebersamaannya melebihi harapan bila item bebas); lift dihitung sebagai kebersamaan teramati dibagi harapan kemerdekaan.
  • Lift simetris sedangkan confidence tidak: kopi -> susu (0,714) berbeda dari susu -> kopi (1,000) meski lift keduanya 1,714.
  • Apriori menghemat hitungan lewat prinsip bertingkat: item jarang dibuang di tingkat pertama sehingga pasangannya tidak perlu dihitung — kita implementasikannya dengan dict penghitung dan itertools.combinations.
  • Lift di bawah 1 juga bermakna (asosiasi negatif), dan lift tinggi ber-support kecil wajib dicurigai sebelum menjadi kebijakan.

Kita kini melengkapi koleksi teknik unsupervised: mengelompokkan data, menilai pembagian, memroyalkan dimensi, dan menambang aturan kebersamaan. Satu langkah terakhir menentukan bernilai atau tidaknya semuanya: menjelaskan hasil kepada manusia — memberi nama pada cluster dan memastikan nama itu bertahan uji kenyataan. Lanjut ke chapter Interpretasi Hasil Clustering .

Referensi #

  1. Python Tutorial — Data Structures (set dan dict)