K-Means Clustering — Algoritma & Cara Kerjanya

K-means clustering adalah cara untuk mengelompokkan data numerik ke dalam $k$ cluster. Jika Anda memilih $k$ dan menggunakan versi Euclidean standar, algoritma ini mengulang satu siklus: tetapkan setiap titik ke pusat terdekat, lalu pindahkan setiap pusat ke nilai rata-rata dari titik-titik yang ditetapkan kepadanya.

Dalam bahasa sederhana, algoritma ini berusaha membuat titik-titik dalam kelompok yang sama saling berdekatan dan titik-titik di kelompok yang berbeda saling berjauhan. Metode ini cepat dan berguna, tetapi hanya bekerja baik ketika "kelompok" tersebut cukup kompak dan jarak memang bermakna.

Apa yang dioptimalkan oleh k-means clustering

Dalam bentuk Euclidean standar, k-means berusaha membuat titik-titik di dalam setiap cluster sedekat mungkin dengan centroid cluster tersebut. Salah satu objektif yang umum adalah

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Di sini, $C_j$ adalah cluster ke-$j$ dan $\mu_j$ adalah centroid-nya.

Ini adalah within-cluster sum of squares. Nilai yang lebih kecil berarti titik-titik yang ditetapkan berada lebih rapat di sekitar centroid-nya.

Objektif itu menjelaskan dua bagian dari algoritma:

• Jika centroid tetap, langkah terbaik adalah menetapkan setiap titik ke centroid terdekat.
• Jika penetapan tetap, centroid terbaik adalah rata-rata dari titik-titik yang ditetapkan.

Itulah sebabnya aturan pembaruannya tidak sembarang. "Means" dalam k-means benar-benar berarti rata-rata aritmetika.

Cara kerja algoritma k-means

Siklus yang biasa digunakan singkat:

1. Pilih $k$ centroid awal.
2. Tetapkan setiap titik ke centroid terdekat.
3. Hitung ulang setiap centroid sebagai rata-rata dari titik-titik yang ditetapkan kepadanya.
4. Ulangi sampai penetapan tidak berubah lagi atau peningkatannya sangat kecil.

Proses ini biasanya konvergen dengan cepat, tetapi tidak selalu menuju clustering terbaik yang mungkin. Centroid awal yang berbeda bisa menghasilkan jawaban akhir yang berbeda, jadi inisialisasi itu penting.

Contoh k-means clustering langkah demi langkah

Ambil titik data satu dimensi berikut:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Misalkan kita ingin $k = 2$ cluster dan kita mulai dengan centroid di $1$ dan $10$. Ini contoh yang baik karena centroid benar-benar berpindah setelah pembaruan pertama.

Langkah 1: tetapkan titik ke centroid terdekat

Titik $1, 2, 3$ lebih dekat ke $1$.

Titik $10, 11, 12$ lebih dekat ke $10$.

Jadi cluster-nya adalah

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Langkah 2: perbarui centroid

Centroid baru dari cluster pertama adalah

$$\mu_1 = \frac{1+2+3}{3} = 2$$

Centroid baru dari cluster kedua adalah

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Kedua centroid berpindah, dari $1$ ke $2$ dan dari $10$ ke $11$.

Langkah 3: tetapkan lagi

Sekarang periksa lagi centroid terdekat menggunakan $2$ dan $11$.

Titik $1, 2, 3$ tetap berada di cluster pertama, dan titik $10, 11, 12$ tetap berada di cluster kedua. Karena penetapannya tidak berubah lagi, algoritma telah konvergen.

Ini adalah contoh yang rapi karena data secara alami terpisah menjadi dua kelompok kompak. Dataset nyata biasanya lebih berantakan, dan di situlah k-means bisa mulai menyesatkan.

Kapan k-means bekerja dengan baik

K-means bekerja paling baik ketika kondisi berikut kurang lebih terpenuhi:

• Fiturnya numerik.
• Jarak Euclidean adalah cara yang masuk akal untuk mengukur kemiripan.
• Cluster cukup kompak, tidak memanjang atau melengkung.
• Fitur sudah diskalakan sehingga satu variabel tidak mendominasi yang lain.

Jika kondisi-kondisi itu tidak terpenuhi, hasilnya tetap bisa terlihat rapi meskipun tidak menangkap struktur sebenarnya dalam data.

Kesalahan umum dalam k-means

Menganggap k-means sebagai metode clustering universal

K-means bekerja paling baik ketika cluster cukup kompak dan rata-rata adalah ringkasan yang masuk akal. Metode ini bukan pilihan default yang baik untuk setiap dataset.

Mengabaikan penskalaan fitur

Jika satu fitur diukur pada skala yang jauh lebih besar daripada fitur lain, fitur itu bisa mendominasi perhitungan jarak. Standardisasi atau normalisasi fitur sering kali penting sebelum menjalankan k-means.

Menganggap jawabannya unik

K-means bisa konvergen ke minimum lokal yang berbeda dari titik awal yang berbeda. Itulah sebabnya pengulangan beberapa kali atau metode seperti inisialisasi k-means++ sering digunakan.

Menggunakan fitur non-numerik atau fitur yang dikodekan dengan buruk

Karena centroid adalah rata-rata, k-means standar dibuat untuk variabel numerik. Jika suatu fitur bersifat kategorikal, mengambil rata-rata aritmetika mungkin tidak masuk akal.

Menggunakannya pada cluster yang sangat tidak berbentuk bola

Jika kelompok sebenarnya memanjang, melengkung, atau memiliki kepadatan yang sangat tidak merata, k-means bisa membelah satu kelompok alami atau menggabungkan dua kelompok yang berbeda. Metode ini lebih menyukai cluster kompak berbasis centroid.

Lupa bahwa outlier dapat menarik centroid

Karena centroid adalah rata-rata, nilai ekstrem dapat menggesernya secara nyata. Jika outlier penting dalam data Anda, periksa hal ini sebelum mempercayai hasilnya.

Di mana k-means clustering digunakan

K-means sering digunakan untuk pengelompokan eksploratif, segmentasi pelanggan atau perilaku, kuantisasi warna gambar, dan sebagai baseline cepat dalam unsupervised learning.

Metode ini paling berguna ketika Anda memiliki fitur numerik, menginginkan model yang cepat dan sederhana, serta memperkirakan adanya cluster yang kurang lebih kompak dalam ruang Euclidean.

Model mental sederhana

Bayangkan Anda menempatkan $k$ pin yang bisa bergerak pada sebuah scatterplot. Setiap titik menempel ke pin terdekat. Lalu setiap pin bergeser ke lokasi rata-rata dari titik-titik yang menempel padanya. Ulangi sampai pin-pin itu hampir tidak bergerak lagi.

Gambaran itu bukan sekadar intuisi. Itu hampir merupakan keseluruhan algoritmanya.

Coba soal clustering serupa

Ambil sekumpulan kecil titik pada sebuah garis, pilih $k = 2$, lalu jalankan satu siklus penuh penetapan-pembaruan secara manual. Kemudian ubah centroid awal atau tambahkan satu outlier dan lihat bagaimana hasilnya berubah. Jika ingin melangkah sedikit lebih jauh, coba versi Anda sendiri pada dataset kecil dan bandingkan apa yang terjadi sebelum dan sesudah penskalaan fitur.