Partitioning & Hierarchical Clustering

Capaian Pembelajaran

Setelah minggu ini kamu bisa:

1. Membedakan pembelajaran terarah (supervised) dan tak terarah (unsupervised).
2. Menjalankan K-Means secara manual dan menghitung SSE.
3. Menjelaskan K-Medoids/PAM dan kapan lebih baik dari K-Means.
4. Melakukan agglomerative clustering dengan single, complete, dan average linkage; membaca dendrogram.
5. Menentukan jumlah klaster dengan Elbow Method dan Silhouette Score.
6. Menginterpretasi profil klaster untuk segmentasi pasar.

1. Apa itu Clustering?

Clustering = mengelompokkan objek sehingga objek dalam satu klaster mirip (jarak kecil, high intra-cluster similarity) dan objek antar klaster berbeda (low inter-cluster similarity) — tanpa label.

Kategori metode

⚠️ Clustering berbasis jarak → normalisasi fitur dulu (z-score/min-max), sama seperti KNN.

2. K-Means

Algoritma (Lloyd)

1. Pilih k centroid awal (acak / k-means++).
2. ASSIGN : tiap titik masuk ke klaster dengan centroid terdekat (Euclidean).
3. UPDATE : centroid baru = rata-rata titik anggota klaster.
4. Ulangi 2–3 sampai penugasan tidak berubah (konvergen) / iterasi maksimum.

Fungsi objektif yang diminimalkan — SSE (Sum of Squared Errors, disebut juga inertia / WCSS):

SSE = Σ_{j=1..k} Σ_{x ∈ C_j} ‖x − μ_j‖²

Contoh manual

Data 7 titik: A(1,1), B(1.5,2), C(3,4), D(5,7), E(3.5,5), F(4.5,5), G(3.5,4.5). k = 2, centroid awal μ1 = A(1,1), μ2 = C(3,4).

Iterasi 1 — assign (jarak kuadrat):

Update: μ1 = mean(A, B) = (1.25, 1.5); μ2 = mean(C, D, E, F, G) = (3.9, 5.1).

Iterasi 2 — assign dengan centroid baru: penugasan tidak berubah → konvergen.

SSE akhir = 0.3125 + 0.3125 + 2.02 + 4.82 + 0.17 + 0.37 + 0.52 = 8.525.

Sifat penting K-Means

Solusi umum: k-means++ (centroid awal saling berjauhan) dan menjalankan beberapa kali (n_init) lalu pilih SSE terkecil.

3. K-Medoids & PAM

Medoid = titik data nyata yang paling sentral dalam klaster (total jarak ke anggota lain minimum). Karena memakai titik nyata dan jarak (bukan rata-rata kuadrat), K-Medoids lebih tahan outlier dan bisa memakai sembarang ukuran jarak (Manhattan, Hamming untuk kategorikal).

Biaya (cost): Σ_j Σ_{x ∈ C_j} d(x, m_j)

PAM (Partitioning Around Medoids)

1. Pilih k medoid awal.
2. Assign setiap titik ke medoid terdekat.
3. Untuk setiap pasangan (medoid m, non-medoid o):
      hitung perubahan biaya jika m ditukar dengan o (SWAP).
4. Lakukan swap yang paling menurunkan biaya; ulangi sampai tidak ada perbaikan.

PAM akurat tetapi mahal O(k(n−k)²) per iterasi. Varian lebih cepat: CLARA (PAM pada sampel), CLARANS, atau iterasi bergantian (alternate / Voronoi iteration) seperti K-Means: assign → di tiap klaster pilih titik dengan total jarak minimum sebagai medoid baru → ulangi. Versi bergantian inilah yang kita implementasikan di exercise.py.

Contoh: klaster berisi nilai 1D {2, 3, 4, 100}. Mean = 27.25 (tertarik outlier) sedangkan medoid = 3 (atau 4) — jauh lebih representatif.

4. Agglomerative Hierarchical Clustering

Pendekatan bottom-up:

1. Setiap titik = 1 klaster (n klaster).
2. Hitung jarak antar semua pasangan klaster.
3. Gabungkan 2 klaster terdekat.
4. Perbarui jarak; ulangi sampai tersisa 1 klaster (atau k klaster).

Hasilnya divisualisasikan sebagai dendrogram; memotong dendrogram pada ketinggian tertentu menghasilkan k klaster. (Kebalikannya, divisive/DIANA, bersifat top-down.)

Linkage — jarak antar klaster

Contoh: A = {(1,1), (1.5,2)}, B = {(3,4), (3.5,4.5)}.

Single = 2.500, Complete = 4.301, Average = (3.606 + 4.301 + 2.5 + 3.202)/4 = 3.402.

5. Menentukan Jumlah Klaster

5.1 Elbow Method

Plot SSE vs k. SSE selalu turun saat k naik (k = n → SSE = 0). Cari "siku" (elbow) — titik setelah penurunan SSE melandai.

5.2 Silhouette Score

Untuk tiap titik i:

a(i) = rata-rata jarak i ke anggota klaster sendiri          (kekompakan)
b(i) = rata-rata jarak i ke anggota klaster TERDEKAT lainnya (keterpisahan)
s(i) = (b(i) − a(i)) / max(a(i), b(i))          ∈ [−1, 1]

Silhouette Score = rata-rata s(i) seluruh titik. Pilih k dengan nilai tertinggi.

Contoh: a(i) = 2, b(i) = 5 → s = (5 − 2)/5 = 0.6.

5.3 Evaluasi lain

• Eksternal (jika label asli ada, hanya untuk latihan): Adjusted Rand Index (ARI), purity.
• Bisnis: apakah segmen bisa dijelaskan dan ditindaklanjuti?

6. Studi Kasus: Segmentasi Pelanggan RFM

RFM = Recency (hari sejak belanja terakhir), Frequency (jumlah transaksi), Monetary (nilai belanja).

Alur: hitung RFM → normalisasi (z-score; monetary sering di-log dulu) → K-Means dengan k dari elbow/silhouette → profil rata-rata tiap klaster → beri nama & strategi:

Ringkasan

• K-Means meminimalkan SSE dengan iterasi assign–update; sensitif inisialisasi, outlier, dan bentuk klaster.
• K-Medoids/PAM memakai titik nyata sebagai pusat → lebih robust.
• Agglomerative menggabungkan klaster terdekat; linkage menentukan definisi "terdekat"; hasil berupa dendrogram.
• Pilih k dengan Elbow (SSE) dan Silhouette; validasi dengan makna bisnis.
• Selalu normalisasi fitur sebelum clustering berbasis jarak.

Bacaan

• Han, Kamber & Pei — Bab 10 Cluster Analysis: Basic Concepts and Methods (10.2 partisi, 10.3 hierarkis, 10.6 evaluasi).
• Dokumentasi scikit-learn: Clustering (KMeans, AgglomerativeClustering, silhouette_score).

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 10