Algoritma K-Means++ Clustering 2


Algoritma K-Means++ Clustering adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan jurusan siswa berdasarkan nilai skor siswa.
Algoritma ini merupakan pengembangan dari Algoritma K-Means Clustering. Perbedaan algoritma ini dengan algoritma sebelumnya, dimana pada algoritma sebelumnya, cara memasukkan data pertama kali ke dalam cluster kosong adalah dengan cara acak. Sedangkan pada algoritma ini, memasukkan data pada setiap cluster menggunakan perhitungan jarak tertentu, sehingga tidak lagi dengan sistem acak. Sisa perhitungannya sama seperti algoritma pendahulunya.



Diasumsikan ada 20 orang siswa, yaitu siswa A sampai dengan T
Masing-masing siswa memiliki rata-rata nilai IPA, IPS, dan Bahasa yang berbeda-beda
Maka tentukan semua siswa tersebut akan masuk ke dalam jurusan apa berdasarkan nilai skor yang dimiliki
Diasumsikan data awal nilai siswa adalah sebagai berikut

Nama Siswa Nilai IPA Nilai IPS Nilai Bahasa
Siswa A 50 60 70
Siswa B 65 80 73
Siswa C 72 70 65
Siswa D 83 65 80
Siswa E 40 82 73
Siswa F 95 71 85
Siswa G 60 74 96
Siswa H 75 75 92
Siswa I 83 55 70
Siswa J 91 60 65
Siswa K 92 91 55
Siswa L 76 80 59
Siswa M 75 65 74
Siswa N 74 76 89
Siswa O 63 79 69
Siswa P 58 93 76
Siswa Q 82 50 80
Siswa R 81 65 88
Siswa S 76 74 70
Siswa T 77 71 55

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan Jumlah Iterasi
Diasumsikan dalam kasus ini, jumlah iterasi adalah 100


Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pengelompokan data menggunakan algoritma ini
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1 – 5)

Memasuki perhitungan utama pada fungsi Cluster

1. Lakukan normalisasi data agar data dengan angka yang terlalu besar tidak mendominasi pengelompokan data
Normalisasi data dihitung dengan (rumus data – (rata-rata kriteria tersebut)) / standar deviasi kriteria tersebut
Rata-rata adalah jumlah semua data dibagi dengan jumlah datanya
Standar deviasi adalah akar dari ((kuadrat dari (jumlah dari (data – rata-rata))) / jumlah data)

1a. Salin data pada sebagai nilai awal jawaban data

1b. Hitung nilai rata-rata tiap-tiap kolom
yaitu dengan rumus: jumlah semua data dibagi dengan jumlah datanya

1c. Hitung nilai standar deviasi tiap-tiap kolom
yaitu dengan rumus: akar dari ((kuadrat dari (jumlah dari (data – rata-rata))) / jumlah data)

1d. Nilai akhir dihitung dengan rumus (data dikurangi rata-rata) dibagi nilai standar deviasi

2. Ini adalah fungsi utama dari algoritma K-Means++
Tentukan centroid / mean awal pada masing-masing cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 2a – 2b)

Memasuki perhitungan utama pada fungsi HitungMeansAwal

2a. Ambil data pertama secara acak
Cata data dengan indeks ini sebagai data yang sudah terpakai

2b. Lakukan perhitungan untuk setiap k mean berikutnya

2b1. Lakukan perulangan pada masing-masing data

2b1a. Hitung jarak dari masing-masing data pada mean ke k

* Gunakan fungsi ini untuk menghitung jarak dari data dan centroid / mean
metode yang digunakan adalah jarak Euclidean, dengan rumus akar dari (jumlah dari (kuadrat dari (data – centroid)))

2b1b. Hitung nilai kuadrat jarak pada data ini dengan rumus kuadrat jarak dari jarak terpendek

* Gunakan fungsi ini untuk mencari indeks dengan nilai data terendah
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Tentukan data yang akan diambil pada mean ke k
Metode yang digunakan mirip dengan seleksi roulette (roulette wheel selection)

2b2. Hitung total kuadrat jarak untuk digunakan pada perhitungan probabilitas kumulatif

2b3. Hitung probabilitas kumulatif

2b4. Jika nilainya lebih dari nilai acak, maka gunakan data ini sebagai mean berikutnya

2b5. Jika tidak maka, maka hitung kembali probabilitas kumulatif untuk data berikutnya pada perulangan berikutnya

2b6. Masukkan data dengan indeks terpilih sebagai jawaban mean ke k

Lakukan perulangan selama masih ada data yang berpindah cluster dan iterasi masih kurang dari batas perulangan (poin 3 dan 4)

3. Pindahkan semua data yang harus berpindah ke cluster lain
Kemudian tentukan apakah ada data yang berpindah cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3a – 3d)

Memasuki perhitungan utama pada fungsi UpdateCluster

3a. Lakukan perhitungan pada masing-masing data

3a1. Hitung jarak pada masing-masing cluster

3a2. Pilih cluster dengan jarak terpendek

3a3. Jika nilai cluster yang baru berbeda dari cluster sebelumnya, maka pindahkan data ini ke cluster yang baru

3b. Jika tidak ada data yang berpindah cluster, maka hentikan perhitungan

3c. Lakukan pengecekan terhadap cluster yang baru
Apabila perpindahan cluster menyebabkan salah satu cluster tidak memiliki data maka hentikan perhitungan

3d. Simpan cluster baru sebagai jawaban cluster

4. Hitung ulang nilai masing-masing atribut pada masing-masing mean
Kemudian tentukan apakah semua cluster memiliki setidaknya 1 data?
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4a – 4c)

Memasuki perhitungan utama pada fungsi UpdateMeans

4a. Lakukan pengecekan jumlah data pada masing-masing cluster
Apabila ada cluster yang tidak memiliki data awal maka hentikan perhitungan

4b. Lakukan perulangan untuk setiap data
Hitung jumlah nilai untuk masing-masing kriteria

4c. Bagi jumlah nilai dengan jumlah data per cluster untuk masing-masing atribut

5. Tampilkan semua data yang sudah dimasukan ke dalam cluster
Hitung nilai skornya untuk masing-masing kriteria dalam cluster tersebut
Ambil nilai skor tertinggi sebagai jawaban jurusan yang seharusnya diambil


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd56


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

2 pemikiran di “Algoritma K-Means++ Clustering