Kelemahan k-Means dan Contohnya

Algoritma k-Means sangat sensitif terhadap pencilan (outliers) karena object-object seperti ini sangat jauh letaknya/karakteristiknya dari mayoritas data lainnya, dan dengan demikian bila dimasukkan ke suatu cluster, data semacam ini bisa mendistorsi nilai rerata cluster secara dramatis. Hal ini secara tak sengaja akan mengubah penetapan object-object lainnya ke cluster-cluster. Efek ini diperburuk lagi karena penggunaan fungsi error kuadrat, seperti bisa dilihat di contoh berikut.

Contoh kelemahan k-Means. Misalkan ada enam titik dalam ruang 1-D (satu dimensi) yang nilai-nilainya adalah sebagai berikut: 1,2,3,8,9,10, dan 25. Secara intuitif, dengan melihat secara visual kita bisa membayangkan bahwa titik-titik tersebut dipartisi menjadi cluster {1,2,3} dan {8,9,10}. dimana titik 25 dikeluarkan karena terlihat sebagai suatu pencilan (outlier). Tetapi, bagaimanakah k-means akan mempartisi nilai-nilai tersebut? Jika kita menerapkan k-means dengan menggunakan k = 2 dan menggunakan persamaan dalam artikel sebelumnya tentang: [Penjelasan Cara Kerja Algoritma k-Means: Suatu Teknik Clustering Partisi Berbasis Centroid], partisi {{1,2,3}, {8,9,10,25}} akan memiliki simpangan di dalam cluster seperti berikut:

Contoh Ilustrasi Clustering Dengan Menggunakan k-Means dan Variannya: k-Modes

Misalkan ada satu set object yang berada di ruang 2-D (dua dimensi), seperti gambar a disamping. Tentukan k = 3, yang artinya, kita akan mempartisi atau membagi object-object menjadi tiga cluster.

Gambar a. posisi cluster awal
Berdasarkan penjelasan algoritma dalam artikel sebelumnya [Penjelasan Cara Kerja Algoritma k-Means], kita akan memilih secara acak tiga object sebagai pusat-pusat cluster di awal, dimana ketiga pusat cluster tersebut diberi tanda + (lihat gambar, mungkin salah satu cluster agak tidak kelihatan tanda + di gambar a disamping). Masing-masing object ditetapkan ke suatu cluster berdasarkan pusat cluster terdekat. Distribusi object seperti ini bisa dilihat diilustrasi gambar a disamping dengan obejct-object yang dibatasi oleh kurva dengan garis putus-putus.

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.

Metode-metode Dasar dalam Clustering

Menurut berbagai literatur, ada banyak algoritma clustering. Jadi agak sulit untuk memberikan pengkategorian yang pas untuk berbagai macam metode clustering karena akan menyebabkan overlap dalam kategori-kategori tersebut sehingga suatu metode mungkin saja memiliki ciri-ciri dari beberapa kategori. Namun, mungkin bermanfaat apabila disajikan gambaran yang relatif lebih terorganisir tentang metode-metode clustering. Secara umum, metode-metode utama dalam clustering yang mendasar bisa digolongkan menjadi kategori-kategori berikut dibawah ini. [Baca juga: Metode-metode dalam Data Mining]

Pengertian Clustering atau Analisa Cluster

Pengertian clustering atau analisa cluster adalah proses membagi (atau mempartisi) satu set objek data (atau observasi) menjadi beberapa subset. Masing-masing subset adalah satu cluster, sedemikian sehingga objek-objek di dalam suatu cluster adalah mirip satu sama lain, namun tidak mirip dengan objek-objek di dalam cluster lainnya. Set (atau kumpulan) cluster yang dihasilkan dari analisa cluster bisa disebut sebagai clustering. Di dalam konteks ini, berbagai metode clustering yang berbeda bisa menghasilkan clustering yang berbeda pada dataset yang sama. [Baca juga: Metode-metode Dasar dalam Clustering]. Proses membagi (atau mempartisi) tidak dilakukan oleh manusia, tetapi oleh algoritma clustering. Jadi, clustering sangat bermanfaat karena dapat membawa ke penemuan berbagai kelompok yang belum diketahui sebelumnya di dalam data.