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.

Gambar b. posisi cluster
setelah update (iterasi)

Berikutnya, pusat-pusat cluster di-update. Artinya, nilai rerata dari masing-masing cluster dihitung ulang berdasarkan object-object di dalam cluster saat itu. Dengan menggunakan pusat-pusat cluster yang baru, object-object kemudian di-distribusikan ulang ke cluster-cluster berdasarkan pusat cluster terdekat. Distribusi object-object yang baru ini seperti diilustrasikan dalam gambar b disamping (setelah update/iterasi).

Proses ini di ulang lagi, hingga ke gambar c. Proses secara iteratif menetapkan ulang object-object ke cluster-cluster untuk memperbaiki partisi, dan proses ini biasanya disebut dengan relokasi iteratif. Iterasi akan berakhir hingga tidak ada lagi perpindahan object-object ke cluster lain (atau pada posisi stabil). Cluster-cluster yang dihasilkan ini adalah hasil proses clustering.

Gambar c. posisi cluster
setelah stabil (tidak ada iterasi lagi)

Metode k-means tidak menjamin untuk mencapai optimum global dan seringkali berakhir dengan optimum lokal. Hasil-hasilnya bergantung pada pemilihan pusat-pusat cluster di awal yang dipilih secara acak. Untk mendapatkan hasil yang bagus, biasanya perlu menjalankan algoritma k-means ini beberapa kali dengan pusat-pusat cluster yang berbeda di awal.

Kompleksitas waktu dari algoritma k-means adalah O(nkt), dimana n adalah jumlah total object-objectnya, k adalah jumlah cluster, dan t adalah jumlah iterasi. Normalnya, k << n dan t << n. Karena itu, metode ini relatif bisa diubah-ubah ukuran atau skalanya dan efisien dalam memproses dataset yang besar.

Ada beberapa varian dari metode k-means. Perbedaannya bisa pada pemilihan k-means awal, penghitungan terhadap kemiripan/ketidakmiripan, dan strategi dalam menghitung rerata cluster-cluster.

Metode k-means bisa diterapkan hanya ketika rerata object-object bisa ditentukan. Jadi ini tidak mungkin terjadi pada beberapa penerapan ketika melibatkan atribut-atribut data nominal. Metode k-modes adalah varian dari k-means, yang merupakan kelanjutan paradigma k-means untuk meng-cluster data nominal dengan mengganti rerata cluster dengan mode (modus = nilai yang sering muncul). Metode ini menggunakan ukuran-ukuran ketidakmiripan baru untuk mengatasi object-object dengan data nominal dan metode berbasis frekwensi untuk meng-update modus dari cluster-cluster. Metode-metode k-means dan k-modes bisa digabungkan untuk mneg-cluster data yang bernilai campuran numerik dan nominal.

Kebutuhan user dalam menetapkan k, atau jumlah cluster, sebelumnya bisa dilihat sebagai suatu kelemahan. Ada beberapa kajian tentang bagaimana mengatasi hal ini, misalnya dengan cara menyediakan berbagai perkiraan nilai k, dan kemudian dengan menggunakan suatu teknik analitikal untuk menentukan k terbaik dengan membandingkan hasil-hasil clustering yang diperoleh dengan k yang berbeda-beda. Metode k-means tidak cocok untuk mendapatkan cluster-cluster dengan bentuk-bentuk yang nonconvex atau cluster-cluster dengan ukuran yang sangat berbeda. Selain itu, metode ini juga sensitif dengan data pencilan (outlier) dan data yang aneh (berbeda sendiri) karena data semacam ini meskipun sedikit saja bisa sangat mempengaruhi nilai rerata.

Apakah kita bisa membuat algoritma k-means bisa diubah-ubah atau disesuaikan ukurannya? Salah satu pendekatan untuk membuat metode k-means lebih efisien pada dataset yang besar adalah dengan menggunakan sampel data yang bagus ukurannya dalam clustering. Pendekatan lainnya adalah dengan menerapkan pendekatan penyaringan yang menggunakan ideks data hirarkikal spatial untuk menghemat proses penghitungan rerata. Pendekatan ketiga adalah mencari ide microclustering, yang pada awalnya mengelompokkan object-object yang yang berdekatan menjadi microcluster-microcluster dan kemudian melakukan clustering k-means pada microcluster-microcluster tersebut. Microcluster akan didiskusikan terpisah di artikel yang lain.

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