K-Means Clustering Algorithm
[Link]
K-Means Clustering adalah salah satu algoritma dalam menentukan klasifikasi terhadap objek
berdasarkan attribut / fitur dari objek tersebut kedalam K kluster/partisi. K adalah angka positif yang
menyatakan jumlah grup/kluster/partisi terhadap objek. Pemartisian data dilakukan dengan mencari
nilai jarak minimum antara data dan nilai centroid yang telah di set baik secara random atau pun dengan
Initial Set of Centroids, kita juga dapat menentukan nilai centroid berdasarkan K object yang
berurutan.
Centroid adalah nilai rata-rata aritmetik dari sebuah bentuk objek dari seluruh titik dalam objek
tersebut. Penerapan K-Means Clustering ini dapat dilakukan dengan prosedur step by
step berikut :
Siapkan data training berbentuk vector.
Set nilai K cluster.
Set nilai awal centroids.
Hitung jarak antara data dan centroid menggunakan rumus Euclidean Distance.
Partisi data berdasarkan nilai minimum.
Kemudian lakukan iterasi selama partisi data masih bergerak (tidak ada lagi objek yang
bergerak ke partisi lain), bila masih maka ke poin 3.
Bila grup data sekarang sama dengan grup data sebelumnya, maka hentikan iterasi.
Data telah dipartisi sesuai nilai centroid akhir.
Contoh penerapan K-Means Cluster
Attribut / fitur
Data
X Y
A 5,09 5,8
B 3,24 5,9
C 1,68 4,9
D 1 3,17
E 1,48 1,38
F 2,91 0,2
G 4,76 0,1
H 6,32 1,1
I 7 2,83
J 6,52 4,62
Akan dilakukan pemartisian data terhadap data diatas sebanyak 2 partisi, maka tahapannya dalah
sebagai berikut :
K = 2, (K = Jumlah Cluster)
Nilai awal centroid (1.48,1.38) untuk partisi 0, dan centroid (4.76,0.10) untuk partisi 1
Maka perhitungan Euclidean Distance adalah dimana p adalah
data, c adalah centroid, n adalah jumlah data, i adalah iterasi.
Hasil perhitungan jarak minimum A adalah
Hasil perhitungan jarak minimum B adalah
Hasil perhitungan jarak keseluruhan
Hasil perhitungan partisi diambil dari jarak minimum, sehingga didapat sebagai berikut :
Contoh pada A, X = 5.707 lebih kecil dari Y = 5.710, maka A termasuk ke dalam Cluster 0.
Begitu juga dengan F, X = 1.854 lebih besar dari Y = 1.853, maka B masuk ke dalam Cluster
1.
Setelah data di partisi, maka selanjutnya nilai centroid harus dihitung ulang untuk menentukan
jarak minimum yang baru, berikut perhitungan centroid baru :
Hitung jarak minimumnya kembali dengan menggunakan centroid yang baru, sehingga di dapat
hasilnya sebagai berikut
Klasifikasikan kembali data berdasar jarak minimum diatas.
Karena tidak ada data yang berpindah ke cluster yang berbeda, sehingga iterasi kita cukupkan
sampai dengan nilai centroid akhir : (2.50,4.23), (5.50,1.77)
Berikut adalah tampilan kordinat cartesius dari sample data diatas :
Berikut adalah tampilan setelah penerapan K-Means Clustering dengan centroid akhir:
Aplikasi K-Means Clustering sangat sering digunakan, mulai dari unsupervised learning of
neural network, Pattern Recognitions, Classifications Analysis, Artificial Intelligence, Image
Processing, Computer Vision dan banyak lainnya.
Berikut adalah penerapan K-Means Clustering pada Bahasa Pemrograman JavaScript
(spidermonkey). Sample Test Program !!!
Source Code
: [Link]