k-means-clustering

K-Means Clustering

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.

    • K-Means ClusteringContoh penerapan K-Means Cluster

    Data Attribut / fitur
    X Y
    A 5,09 5,80
    B 3,24 5,90
    C 1,68 4,90
    D 1,00 3,17
    E 1,48 1,38
    F 2,91 0,20
    G 4,76 0,10
    H 6,32 1,10
    I 7,00 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 !!!

    Apabila ada yang ingin didiskusikan, silahkan isi komentar yak. Sampai jumpa di artikel selanjutnya.

    Source Code : https://github.com/ekojs/machine_learning/blob/master/unsupervised/ejs_kmeans.js

    Sumber :

    • https://en.wikipedia.org/wiki/K-means_clustering
    • http://people.revoledu.com/kardi/tutorial/kMean/NumericalExample.htm
    • http://mnemstudio.org/clustering-k-means-introduction.htm