K-Means

Algoritma K-Means, pemilihan jumlah cluster, dan keterbatasannya.

Daftar isi

Topik ini membahas K-Means sebagai algoritma clustering yang paling banyak dijadikan titik awal, mulai dari empat langkah kerjanya, cara memilih jumlah cluster, hingga keterbatasan yang perlu diantisipasi. Satu skrip Python menjalankan K-Means pada dataset iris tanpa menyentuh label, lalu hasilnya diperiksa dengan tabel silang (crosstab) dan skor silhouette. Setelah topik ini, mekanisme algoritma beserta alasan di balik setiap keterbatasannya dapat dijelaskan secara runtut.

Empat langkah algoritma K-Means#

K-Means membagi data menjadi $k$ kelompok dengan meminimalkan jarak setiap titik ke titik tengah kelompoknya. Titik tengah itu disebut centroid, yaitu rata-rata seluruh anggota cluster pada ruang fitur. Algoritmanya terdiri atas empat langkah yang berulang:

Menempatkan $k$ centroid awal pada posisi yang tersebar, biasanya dengan metode k-means++ yang memilih posisi awal saling berjauhan.
Menetapkan setiap titik data ke centroid terdekat.
Menggeser setiap centroid ke rata-rata anggota-anggotanya.
Mengulang penetapan dan penggeseran sampai tidak ada titik yang pindah cluster, yaitu saat algoritma dinyatakan konvergen.

Seluruh proses itu merupakan penurunan satu nilai yang sama, yaitu jumlah kuadrat jarak antara setiap titik dan centroid clusternya:

J = \sum_{i=1}^{n} \lVert x_i - c_{k(i)} \rVert^2

dengan $x_i$ titik data ke- $i$ , $n$ jumlah titik, dan $c_{k(i)}$ centroid tempat $x_i$ ditugaskan. Setiap langkah tidak pernah menaikkan $J$ , sehingga algoritma selalu berhenti. Titik berhentinya adalah minimum lokal, bukan jaminan minimum global, dan hasil akhirnya bergantung pada posisi awal centroid. Argumen n_init mengulang algoritma beberapa kali dengan posisi awal berbeda, lalu hasil dengan $J$ terkecil dipertahankan, sedangkan random_state menetapkan seed agar pengulangan itu dapat direproduksi. Sepanjang jalur ini, n_init=10 dan random_state=42 dituliskan eksplisit pada setiap pemanggilan KMeans.

Memilih jumlah cluster#

Nilai $k$ tidak ditemukan oleh algoritma, melainkan ditetapkan sebelum pelatihan sebagai hyperparameter. Dua alat bantu paling umum bekerja dengan mencoba beberapa nilai $k$ lalu membandingkan hasilnya. Pertama, metode siku (elbow) menggambar kurva inersia terhadap $k$ , dan titik belok tempat penurunan mulai melandai dijadikan kandidat. Kedua, skor silhouette dihitung untuk setiap $k$ , dan pembagian dengan rata-rata tertinggi menjadi kandidat terkuat.

Kedua alat bantu itu memberi saran, bukan putusan. Inersia menurun terus seiring bertambahnya $k$ , sehingga titik sikunya kadang tidak jelas pada data yang tidak terpisah tegas, misalnya data dengan batas kelompok yang samar. Skor silhouette yang hampir sama tingginya untuk beberapa $k$ menandakan ada lebih dari satu pembagian yang sama wajar. Kelemahan kedua ukuran itu berbeda, sehingga membaca keduanya bersamaan lebih aman daripada mengandalkan salah satunya saja. Keputusan akhir tetap mempertimbangkan makna kelompok menurut domain, misalnya jumlah segmen yang masih masuk akal untuk diberi perlakuan berbeda.

Keterbatasan K-Means#

K-Means mengasumsikan cluster berbentuk cembung dan berukuran mirip, karena keanggotaan ditentukan hanya oleh jarak ke centroid. Data berbentuk memanjang, cincin, atau lengkungan yang saling bertaut tidak tertangkap dengan benar, sebab batas antar cluster yang dihasilkan selalu berupa potongan garis lurus antara dua centroid. Kelompok dengan ukuran yang berbeda jauh juga rawan terbelah. Batas antar cluster selalu terletak di tengah dua centroid, sehingga batas itu mudah jatuh di dalam wilayah kelompok kecil dan sebagian wilayahnya berpindah ke kelompok besar.

Algoritma ini juga sensitif terhadap skala fitur. Jarak dihitung dari selisih nilai fitur secara langsung, sehingga satu fitur berskala besar mendominasi seluruh perhitungan dan fitur berskala kecil nyaris tidak berperan. Penghasilan tahunan dalam rupiah menjadi contoh fitur yang berskala besar. Standardisasi dengan StandardScaler membuat setiap fitur berkontribusi setara sebelum jarak dihitung. Keterbatasan terakhir bersifat struktural, yaitu $k$ harus ditetapkan di muka, sehingga data yang jumlah kelompok alaminya tidak diketahui membutuhkan percobaan pada beberapa nilai $k$ .

Contoh pada dataset iris#

Skrip berikut menjalankan K-Means pada dataset iris menggunakan keempat fitur pengukuran bunga, tanpa menyertakan kolom label sama sekali. Jumlah cluster ditetapkan sebesar tiga untuk keperluan pemeriksaan, karena jumlah spesies pada dataset ini memang diketahui. Kesesuaian antara cluster dan spesies kemudian dihitung dengan crosstab dari pandas, dan perhitungan itu hanya alat pemeriksaan hasil, bukan bagian dari pelatihan. Jalankan skrip dari folder topik dengan perintah python3 -B kmeans-iris.py.

python kmeans-iris.py

"""K-Means pada dataset iris tanpa label beserta pemeriksaan hasilnya."""

import pandas as pd
from sklearn.cluster import KMeans
from sklearn.datasets import load_iris
from sklearn.metrics import silhouette_score

pd.set_option("display.width", 80)

iris = load_iris()
X = iris.data  # keempat fitur dipakai, kolom label tidak diberikan ke model

kmeans = KMeans(n_clusters=3, n_init=10, random_state=42)
cluster = kmeans.fit_predict(X)

# ukuran tiap cluster
ukuran = pd.Series(cluster).value_counts().sort_index()
for id_cluster, n in ukuran.items():
    print(f"cluster {id_cluster}: {n} baris")

# kesesuaian cluster dengan spesies, hanya untuk pemeriksaan hasil
spesies = pd.Series(iris.target).map(dict(enumerate(iris.target_names)))
tabel = pd.crosstab(cluster, spesies, rownames=["cluster"], colnames=["spesies"])
print(tabel)

print(f"silhouette: {silhouette_score(X, cluster):.4f}")

text Keluaran

cluster 0: 62 baris
cluster 1: 50 baris
cluster 2: 38 baris
spesies  setosa  versicolor  virginica
cluster
0             0          48         14
1            50           0          0
2             0           2         36
silhouette: 0.5528

Ukuran cluster terbagi menjadi 62, 50, dan 38 baris, sedangkan tabel silang memberi gambaran yang lebih tajam. Cluster 1 memuat seluruh 50 baris setosa tanpa campuran, artinya kelompok yang paling khas tertangkap sempurna tanpa label. Cluster 0 mencampur 48 versicolor dengan 14 virginica, sedangkan cluster 2 mencampur 2 versicolor dengan 36 virginica. Pola campuran itu bukan kegagalan alat, melainkan gambaran jujur bahwa versicolor dan virginica memang saling tumpang tindih pada fitur yang tersedia. Skor silhouette 0.5528 berada di tengah rentang, sesuai dengan data yang sebagian terpisah rapi dan sebagian tumpang tindih.

Kesalahan umum#

Ketiga kesalahan berikut muncul bahkan pada data yang sama sekali wajar, sehingga pemeriksaannya perlu menjadi kebiasaan. Ketiganya berpangkal pada sifat K-Means yang menilai titik hanya dari jarak dan nomor urut. Setiap butir menyebut penyebabnya beserta perbaikannya.

Membiarkan fitur berskala berbeda jauh. Penyebabnya, jarak dihitung dari selisih nilai fitur secara langsung, sehingga satu fitur berskala besar mendominasi seluruh perhitungan dan cluster hanya membedakan fitur itu. Akibatnya, kelompok yang terbentuk mengikuti skala angka, bukan struktur data yang sebenarnya. Perbaikannya, standarkan fitur dengan StandardScaler agar setiap fitur berkontribusi setara sebelum pelatihan dimulai.
Menganggap nomor cluster sebagai kelas. Penyebabnya, nomor cluster bergantung pada inisialisasi centroid dan dapat tertukar antar eksekusi, sehingga nomor yang sama tidak menjamin isi yang sama. Akibatnya, kode yang menyamakan satu nomor dengan satu kelas menghasilkan keputusan yang salah ketika nomor itu berpindah. Perbaikannya, periksa isi setiap cluster dengan crosstab terhadap variabel yang bermakna, lalu beri nama cluster dari pembacaan tersebut.
Memilih $k$ hanya dari nilai inersia terkecil. Penyebabnya, inersia menurun terus ketika $k$ dinaikkan, sehingga kriteria itu mendorong $k$ sebanyak mungkin tanpa memperhatikan keterbacaan kelompok. Akibatnya, pembagian yang dihasilkan terlalu halus dan sulit diberi makna. Perbaikannya, bandingkan kurva inersia dan skor silhouette pada rentang nilai $k$ , lalu putuskan jumlah cluster bersama pertimbangan domain.

Ringkasan#

K-Means mengulangi penetapan anggota dan penggeseran centroid untuk meminimalkan jumlah kuadrat jarak ke centroid, dengan n_init dan random_state menjaga hasil yang stabil dan dapat direproduksi.
Jumlah cluster dipilih dengan membaca kurva inersia dan skor silhouette, lalu diputuskan bersama pertimbangan domain.
K-Means mengasumsikan cluster cembung berukuran mirip, sensitif terhadap skala fitur, dan menuntut $k$ ditetapkan di muka.
Nomor cluster bukan kelas, sehingga kesesuaiannya diperiksa dengan crosstab dan penamaannya tetap pekerjaan manusia.

Referensi#

sklearn.cluster.KMeans — scikit-learn — Dokumentasi API K-Means beserta argumen n_init, random_state, dan atribut inertia_.
Clustering — scikit-learn — Panduan resmi metode clustering yang membahas keterbatasan K-Means.
sklearn.metrics.silhouette_score — scikit-learn — Dokumentasi perhitungan skor silhouette yang dipakai pada skrip.
sklearn.preprocessing.StandardScaler — scikit-learn — Dokumentasi standardisasi fitur sebelum algoritma berbasis jarak.