Algoritma K-Means (K-Means Algorithm)

K-Means merupakan metode klasterisasi yang paling terkenal dan banyak digunakan di berbagai bidang karena sederhana, mudah diimplementasikan, memiliki kemampuan untuk mengklaster data yang besar, mampu menangani data outlier, dan kompleksitas waktunya linear O(nKT) dengan n adalah jumlah dokumen, K adalah jumlah kluster, dan T adalah jumlah iterasi. K-means merupakan metode pengklasteran secara partitioning yang memisahkan data ke dalam kelompok yang berbeda. Dengan partitioning secara iteratif, KMeans mampu meminimalkan rata-rata jarak setiap data ke klasternya. Metode ini dikembangkan oleh Mac Queen pada tahun 1967.



Dasar algoritma K-means adalah sebagai berikut :

1. Tentukan nilai k sebagai jumlah klaster yang ingin dibentuk.

2. Bangkitkan k centroid (titik pusat klaster) awal secara random.

3. Hitung jarak setiap data ke masing-masing centroid menggunakan rumus korelasi antar dua objek yaitu Euclidean Distance dan kesamaan Cosine.

4. Kelompokkan setiap data berdasarkan jarak terdekat antara data dengan centroidnya.

5. Tentukan posisi centroid baru ( k C ) dengan cara menghitung nilai rata-rata dari data-data yang ada pada centroid yang sama.



Dimana k n adalah jumlah dokumen dalam cluster k dan i d adalah dokumen dalam cluster k.

6. Kembali ke langkah 3 jika posisi centroid baru dengan centroid lama tidak sama.

Adapun karakteristik dari algoritma K-Means salah satunya adalah sangat sensitif dalam penentuan titik pusat awal klaster karena K-Means membangkitkan titik pusat klaster awal secara random. Pada saat pembangkitan awal titik pusat yang random tersebut mendekati solusi akhir pusat klaster, K-Means mempunyai posibilitas yang tinggi untuk menemukan titik pusat klaster yang tepat. Sebaliknya, jika awal titik pusat tersebut jauh dari solusi akhir pusat klaster, maka besar kemungkinan ini menyebabkan hasil pengklasteran yang tidak tepat. Akibatnya K-Means tidak menjamin hasil pengklasteran yang unik. Inilah yang menyebabkan metode K-Means sulit untuk mencapai optimum global, akan tetapi hanya minimum lokal. Selain itu, algoritma K-Means hanya bisa digunakan untuk data yang atributnya bernilai numeric.