🧲 K-Means Clustering

Algoritma clustering paling populer: bagi data menjadi k kelompok tanpa label.

🎬 Animasi: K-Means: Iterasi Centroid

Tiap iterasi: titik memilih centroid terdekat (assign), lalu centroid pindah ke pusat kelompok (update). Ulangi sampai stabil.

📌 1. Konsep: Mengelompok Tanpa Jawaban

Clustering = menemukan kelompok alami dalam data tanpa label. Aplikasi: segmentasi pelanggan, grup dokumen, deteksi anomali, kompresi gambar.

Algoritma K-Means:
1. PILIH k centroid acak (biasanya titik data acak)
2. ASSIGN  : setiap titik → centroid terdekat
3. UPDATE  : centroid baru = rata-rata titik anggota
4. Ulangi 2–3 sampai centroid berhenti bergerak

Yang di-minimize: INERTIA = Σ jarak² tiap titik ke centroidnya
    (total "kekacauan" di dalam cluster)

Karakter:
• Cepat (O(n·k·iter)) — bisa untuk jutaan titik
• k HARUS DITENTUKAN MANUAL (elbow method / silhouette)
• Sensitif inisialisasi → K-Means++ (pilih centroid awal cerdas)
• Hanya menemukan cluster "bulat/konveks" (bukan bulan/cincin)

📌 2. Contoh: K-Means Langkah demi Langkah

print("=== K-MEANS: LANGKAH DEMI LANGKAH ===\n")
random_seed(42)
X, y = make_blobs(90, centers=[(2, 2), (8, 3), (5, 8)], spread=0.8)

k = 3
random_seed(1)
idx = shuffle(list(range(len(X))))[:k]
centroids = [X[i][:] for i in idx]
print("Centroid awal (acak):")
for i, c in enumerate(centroids):
    print("  C%d = (%.2f, %.2f)" % (i, c[0], c[1]))

for it in range(1, 21):
    # ── ASSIGN: tiap titik ke centroid terdekat ──
    labels = []
    for p in X:
        d = [euclidean(p, c) for c in centroids]
        labels.append(argmin(d))
    # ── UPDATE: centroid = rata-rata anggota ──
    new_c = []
    for ci in range(k):
        members = [p for p, l in zip(X, labels) if l == ci]
        if members:
            new_c.append([mean([q[0] for q in members]),
                          mean([q[1] for q in members])])
        else:
            new_c.append(centroids[ci])
    moved = sum(euclidean(a, b) for a, b in zip(centroids, new_c))
    centroids = new_c
    print("iter %2d: centroid bergeser total %.3f" % (it, moved))
    if moved < 0.01:
        print("→ KONVERGEN (centroid stabil)")
        break

labels = [argmin([euclidean(p, c) for c in centroids]) for p in X]
print("\nUkuran cluster: %s" % [labels.count(i) for i in range(k)])
plot_points(X, labels, title="Hasil K-Means (k=3)")
print("(bandingkan dengan label asli: %s)" % [y.count(i) for i in range(3)])

Output:

ID cluster (0/1/2) bersifat arbitrary — bisa tertukar dengan label asli, tapi bentuk kelompoknya yang penting.

📌 3. Contoh: Elbow Method — Memilih k

Inertia turun seiring k bertambah, tapi setelah k "sebenarnya" penurunannya melambat — membentuk "siku" (elbow).

print("=== ELBOW METHOD: MEMILIH k ===\n")
random_seed(42)
X, _ = make_blobs(120, centers=[(2, 2), (8, 3), (5, 8)], spread=0.8)

def kmeans(X, k, seed=1, iters=30):
    random_seed(seed)
    idx = shuffle(list(range(len(X))))[:k]
    cents = [X[i][:] for i in idx]
    for _ in range(iters):
        labels = [argmin([euclidean(p, c) for c in cents]) for p in X]
        new_c = []
        for ci in range(k):
            mem = [p for p, l in zip(X, labels) if l == ci]
            new_c.append([mean([q[0] for q in mem]), mean([q[1] for q in mem])]
                         if mem else cents[ci])
        moved = sum(euclidean(a, b) for a, b in zip(cents, new_c))
        cents = new_c
        if moved < 0.01:
            break
    labels = [argmin([euclidean(p, c) for c in cents]) for p in X]
    inertia = sum(min(euclidean(p, c) ** 2 for c in cents) for p in X)
    return labels, inertia

inertias = []
print("k │ inertia")
print("-" * 24)
for k in range(1, 8):
    _, inertia = kmeans(X, k)
    inertias.append(inertia)
    print("%d │ %8.1f" % (k, inertia))

line_chart([("inertia", inertias)], title="Elbow method (siku di k=3?)")
print("\n→ Penurunan tajam k=1→2→3, lalu landai. Jawaban: k=3.")
print("  (Metode lain: silhouette score — lihat latihan.)")

Output:

⚠️ Elbow method subjektif — kadang siku-nya tidak jelas. Di praktik: coba beberapa k, lalu nilai dengan silhouette score atau (jika ada label) Adjusted Rand Index.

🧠 Latihan

Jalankan k-means dengan k=2 dan k=5 pada data yang sama. Apa yang terjadi pada bentuk cluster?
Buat data make_moons() lalu k-means k=2. Kenapa hasilnya buruk? (Petunjuk: bentuk cluster k-means.)
Implementasi sederhana silhouette score: untuk tiap titik, s = (b - a) / max(a, b) dengan a = jarak rata-rata ke cluster sendiri, b = jarak rata-rata ke cluster terdekat lain.
Ubah inisialisasi centroid dari acak menjadi 3 titik yang saling berjauhan (K-Means++ sederhana). Apakah konvergensinya lebih stabil?