Penjelasan Cara Kerja Algoritma k-Means: Suatu Teknik Clustering Partisi Berbasis Centroid

Salah satu teknik clustering partisi yang paling populer adalah k-Means. Berikut adalah penjelasan
k-Means berdasarkan penerapan secara teknis. Misalkan ada suatu dataset D, yang berisi object sebanyak n dalam ruang Euclidean (ruang dua dimensi). Metode partisi akan mendistribusikan object-object di dalam D ke dalam cluster-cluster sebanyak k, C1, ... , Ck, yang artinya bahwa, Ci ⊂ D dan Ci ∩ Cj= ∅ untuk (1 ≤ i , j ≤ k). Suatu fungsi yang obyektif digunakan untuk menilai kualitas partisi sehingga object-object di dalam suatu cluster mirip satu sama lain dan tidak mirip dengan object-object di cluster yang lain. Artinya, fungsi obyektif tersebut bertujuan untuk menilai kemiripan yang tinggi pada object-object di dalam cluster yang sama dan kemiripan yang rendah pada cluster yang berbeda.

Teknik-teknik partisi berbasis centroid menggunakan centroid (pusat) cluster, Ci, untuk menyajikan clusternya. Secara konsep, centroid suatu cluster adalah titik pusatnya. Centroid bisa diterapkan dengan berbagai macam cara misalnya menggunakan mean (rerata) atau medoid object-object (atau titik-titik) yang ditunjuk pada cluster tersebut. Perbedaan antara suatu object p ∈ Ci dan ci, sebagai wakil dari cluster yang bersangkutan (centroid), diukur berdasarkan dist(p,ci), dimana dist(x,y) adalah jarak Euclidean antara dua titik x dan y. Kualitas cluster Ci bisa diukur dengan variasi (simpangan/perbedaan) di dalam cluster, yang berarti adalah jumlah error/simpangan kuadrat antara semua object di dalam Ci dan centroid ci, di definisikan sebagai berikut:

Dimana E adalah jumlah error/simpangan kuadrat semua object di dataset; p adalah titik di dalam ruang yang mewakili object tertentu, dan ci adalah centroid (atau pusat) cluster Ci (p dan ci adalah multidimensional). Dengan kata lain, untuk setiap object di dalam setiap cluster, jarak object ke pusat cluster di kuadratkan, dan jaraknya dijumlahkan. Fungsi obyektif ini mencoba membuat hasil cluster-cluster k (k adalah jumlah cluster) sepadat dan seterpisah mungkin.

Melakukan optimasi variasi (selisih perbedaan) di dalam cluster secara komputasi adalah suatu tantangan tersendiri. Hal terburuknya adalah bahwa kita harus meng-enumerasi sejumlah proses partisi yang mungkin dilakukan dan ini adalah eksponensial terhadap jumlah cluster, dan men-cek nilai-nilai variasi (selisih perbedaan) di dalam cluster. 

Bagaimana cara kerja algoritma k-means? Algoritma k-means mendefinisikan centroid dari suatu cluster sebagai nilai rerata titik-titik di dalam cluster. Jadi seperti berikut ini. Pertama, algoritma akan memilih secara acak k dari object-object di dalam D, dimana masing-masing k mewakili nilai rerata atau pusat dari suatu cluster. Untuk object-object lainnya ditetapkan ke cluster dimana yang memiliki kemiripan/kedekatan paling tinggi berdasarkan jarak Euclidean antara object dan rerata (pusat) cluster. Algoritma k-means akan secara iteratif meningkatkan variasi (selisih perbedaan) di dalam cluster. Untuk masing-masing cluster, algoritma ini akan menghitung rerata baru dengan menggunakan object-object yang ditetapkan ke cluster tersebut pada iterasi sebelumnya. Semua object kemudian ditetapkan ulang dengan menggunakan rerata baru yang sudah diupdate dan digunakan sebagai pusat atau centroid yang baru. Iterasi ini akan terus berlanjut hingga penetapan centroid atau pusat cluster stabil, yang artinya, cluster-cluster yang dibentuk dalam putaran saat ini akan sama dengan putaran sebelumnya. Berikut adalah ringkasan dari algoritma k-means.

Algoritma: k-means.

Input:

• k: jumlah cluster
• D: dataset yang berisi object sebanyak n

Output: satu set cluster-cluster k

Metode:

(1) Secara acak memilih object-object k dari D sebagai pusat awal cluster;

(2) Repeat

(3) Tetapkan(ulang) setiap object ke cluster dimana object tersebut paling mirip/dekat, berdasarkan nilai rerata dari object-object di dalam cluster;

(4)   Update rerata cluster, yang artinya, hitung nilai rerata object-object untuk setiap cluster

(5) Until stabil (tidak ada perubahan)

Artikel terkait clustering:

• Pengertian Clustering atau Analisa Cluster
• Metode-metode Dasar dalam Clustering
• Penjelasan Cara Kerja Algoritma k-Means: Suatu Teknik Clustering Partisi Berbasis Centroid
• Contoh Ilustrasi Clustering Dengan Menggunakan k-Means dan Variannya: k-Modes
• Kelemahan k-Means dan Contohnya
• Penjelasan k-Medoids, Algoritma, dan Contohnya
• k-Means vs k-Medoids, Kelemahan k-Medoids dan Solusinya: CLARA