Algoritma K-Means Clustering
Dalam data mining, terdapat beberapa teknik atau metode yang dapat digunakan dalam menganalisis data. Salah satunya adalah metode clustering. Clustering merupakan metode penganalisisan data dalam data mining yang tujuannya untuk mengelompokkan data dengan karakteristik yang sama ke suatu wilayah yang sama dan data dengan karakteristik yang berbeda ke wilayah yang lain, atau dengan kata lain untuk mendapatkan kelompok objek yang memiliki nilai atau karakteristik yang sama. Proses membagi atau mempartisi satu objek data (observasi) menjadi beberapa subset. Masing-masing subset adalah satu cluster, sedemikian sehingga objek-objek di dalam suatu klaster adalah mirip satu sama lain. Proses membagi atau mempartisi ini tidak dilakukan oleh manusia, tetapi oleh algoritma clustering. Salah satu algoritma clustering yang akan dibahas kali ini yaitu algoritma k-means.
Algoritma k-means merupakan salah satu metode partitional clustering berbasis titik pusat (centroid) dimana proses clustering dilakukan dengan meminimalkan jarak sum squares antara data dengan masing-masing pusat cluster. Algoritma k-means dalam penerapannya memerlukan tiga parameter yang seluruhnya ditentukan pengguna yaitu jumlah cluster k, inisialisasi cluster, dan jarak.
Berikut merupakan langkah-langkah melakukan clustering dengan menggunakan algoritma k-means:
- Menentukan jumlah k cluster. Dimana syarat untuk nilai k ini tidak boleh lebih besar dari jumlah data.
- Inisialisasikan K pusat cluster. Inisialisasi ini dilakukan dengan cara acak sebanyak k buah, dimana titik ini akan menjadi pusat (centroid) dari masing-masing kelompok.
- Hitung jarak dan alokasikan masing-masing data ke centroid/rata-rata terdekat. Kedekatan dua objek ditentukan berdasarkan jarak kedua objek tersebut. Demikian juga kedekatan suatu daya ke cluster tertentu ditentukan jarak antara data dengan pusat cluster. Jarak paling dekat antara satu data dengan data satu cluster tertentu akan menentukan suatu data masuk dalam cluster yang mana. Ada 3 cara pehitungan untuk menghitung jarak terdekat antara data dengan centroid. Yaitu Euclidean Distance, Manhattan Distance, dan Minkowski Distance.
- Tentukan centroid baru/rata-rata dari data yang ada di masing-masing cluster.
- Kembali ke langkah-3, jika masih ada data yang berpindah cluster atau ada perubahan nilai centroid. Jika tidak ada maka hentikan proses clustering.
Saya akan menjelaskan contoh kasus dari k-means clustering secara manual.,,
Data diatas merupakan data karyawan yang berisi 2 kolom dan 4 baris. Disini kita akan mengklaster data dari data karyawan tersebut. Diketahui bahwa jumlah data karyawan (k)=4
Kita ikuti langkah proses clustering seperti yang sudah dijelaskan sebelumnya.
ITERASI 1
- Menentukan jumlah k klaster, untuk penentuan klaster pertama ini dilakukan secara acak. k klaster ini akan menjadi centroid pada iterasi pertama. Berikut centroid pertama yang dipilih.
syarat untuk penentuan k klaster ini jumlah k tidak boleh melebihi jumlah data. Maka diketahui:
k=2
Centroid cluster 1 (CC-1)= {A,B}={1,1}
Centroir cluster 2 (CC-2)= {A,B}={2,1}
2. Hitung jarak data ke centroid.
- Jarak data ke centroid 1
Perhitungan jarak ini menggunakan rumus jarak euclidean distance.
Keterangan:
k1,k2,…= data karyawan ke-1,2.. dst
c1= centroid 1
- Jarak data ke centroid 2
- Berikut hasil perhitungan jarak pada iterasi 1
- Kemudian kelompokkan data sesuai klasternya, yaitu kelompokkan berdasarkan data yang memiliki jarak terpendek.
1. d(k1,c1) < d(k1,c2)
maka k1 (karyawan 1) masuk ke dalam cluster 1 (C-1)
2. d(k2,c1) > d(k2,c2)
maka k2 (karyawan 2) masuk ke dalam cluster 2 (C-2)
3. d(k3,c1) > d(k3,c2)
maka k3 (karyawan 3) masuk ke dalam cluster 2 (C-2)
4. d(k4,c1) > d(k4,c2)
maka k4 (karyawan 4) masuk ke dalam cluster 2 (C-2)
Jadi, pengklasteran tersebut dilakukan berdasarkan jarak terdekat, misalnya pada karyawan ke-4, klaster 1 lebih besar jaraknya dari pada ke klaster dua, artinya pada karyawan 4 ini memiliki jarak terpendek ke klaster 2 dibandingkan ke klaster 1, maka kayawan ini masuk ke dalam klaster 2.
- Hasil Klastering iterasi-1
ITERASI 2
Selanjutnya kita masuk ke iterasi ke-2. Proses klastering masih sama seperti pada iterasi-1, pertama tentukan centroid , tetapi penentuan centroid ini berbeda dengan penentuan centroid pada iterasi 1 yang dilakukan secara acak, sedangkan centroid pada iterasi ke-2 ini dilakukan berdasarkan nilai rata-rata dari hasil penjumlahan data pada masing-masing klaster.
- Pada cluster-1 terdapat 1 data yaitu karyawan 1. Maka nilai rata-rata pada cluster-1 adalah:
Average(K1A) = Average(1) = 1
Average(K1B) = Average(1) = 1
keterangan: K1A artinya nilai pada kolom A karyawan 1.
- Pada cluster-2 terdapat 3 data yaitu karyawan 2,3 dan 4. Maka nilai rata-rata pada cluster-2 adalah:
Average(K2A+K3A+K4A) = Average(2+4+5) = 3,67
Average(K2B+k3B+K4B) = Average(1+3+4) = 2,67
keterangan: K2A artinya nilai pada kolom A karyawan 2.
Maka didapatkan centroid pada iterasi ke-2, sebagai berikut:
centroid pada cluster-1 (CC-1) = {1,1}
centroid pada cluster-2 (CC-2) = {3,67;2,67}
- Selanjutnya kita hitung jarak antara data dengan centroid seperti yang dilakukan pada iterasi-1. Dan berikut hasil perhitungan jarak pada iterasi ke-2:
- Kemudian kelompokkan data sesuai cluster
1. d(k1,c1) < d(k1,c2)
maka k1 (karyawan 1) masuk ke dalam cluster 1 (C-1)
2. d(k2,c1) <d(k2,c2)
maka k2 (karyawan 2) masuk ke dalam cluster 1(C-1)
3. d(k3,c1) > d(k3,c2)
maka k3 (karyawan 3) masuk ke dalam cluster 2 (C-2)
4. d(k4,c1) > d(k4,c2)
maka k4 (karyawan 4) masuk ke dalam cluster 2 (C-2)
- Hasil Klastering iterasi-2
Kita bisa lihat pada iterasi ke-2 ini ada perubahan yang terjadi pada pengelompokkan cluster, yaitu pada cluster 1 yang tadinya hanya 1 data menjadi 2 data, kemudian pada cluster 2 yang tadinya ada 3 data menjadi 2 data.
Langkah akan diulang hingga tidak ada lagi perubahan. Karena pada iterasi ke-2 ini terdapat perubahan, maka proses dilanjutkan ke Iterasi-3.
ITERASI-3
Tahap berikutnya:
- Cek apakah pada centroid iterasi-3 sama dengan iterasi sebelumnya.
- Jika tetap atau sama maka hentikan perhitungan
- Jika berbeda, ulangi langkah-langkah seperti pada iterasi-2
Hitung centroid pada iterasi ke-3 ini berdasarkan rata-rata data pada tiap cluster seperti yang dilakukan pada iterasi sebelumnya, dan berikut hasil perhitungan centroid baru:
centroid cluster-1 (CC-1) = {1,5;1}
centroid cluster-2 (CC-2) = {4,5;3,5}
karena centroid pada iterasi-3 ini berbeda dengan iterasi-2 maka proses dilanjutkan
- Menghitung jarak data ke centroid. Berikut hasilnya:
- Kelompokkan data sesuai klaster, yaitu berdasarkan jarak terpendek
1. d(k1,c1) < d(k1,c2)
maka k1 (karyawan 1) masuk ke dalam cluster 1 (C-1)
2. d(k2,c1) <d(k2,c2)
maka k2 (karyawan 2) masuk ke dalam cluster 1(C-1)
3. d(k3,c1) > d(k3,c2)
maka k3 (karyawan 3) masuk ke dalam cluster 2 (C-2)
4. d(k4,c1) > d(k4,c2)
maka k4 (karyawan 4) masuk ke dalam cluster 2 (C-2)
- Hasil Klastering itersi-3
Dapat dilihat pada hasil klaster di iterasi ke-3 ini, tidak ada perubahan klaster dari iterasi sebelumnya, Tidak ada data karyawan yang pindah. Maka untuk centroid berikutnya tidak akan ada lagi perubahan data.
- Hasil perhitungan centroid baru
centroid iterasi-3 = centroid-2, Maka tidak perlu dilanjutkan ke proses iterasi selanjutnya.
Maka iterasi dihentikan dan proses clustering menghasilkan:
- Cluster-1 berisi karyawan 1 dan 2
- Cluster-2 berisi karyawan 3 dan 4
Semoga Bermanfaat :)
Referensi:
Anggoro, J. W., Awaluddin, M., & Nugraha, A. L. (2019). ZONASI DAERAH RAWAN PENCURIAN KENDARAAN BERMOTOR (CURANMOR) DI KOTA SEMARANG DENGAN MENGGUNAKAN METODE CLUSTER ANALYSIS. Jurnal Geodesi Undip, 8(4), 225–234.
Nanda, C. A., Nugraha, A. L., & Firdaus, H. S. (2019). ANALISIS TINGKAT DAERAH RAWAN KRIMINALITAS MENGGUNAKAN METODE KERNEL DENSITY DI WILAYAH HUKUM POLRESTABES KOTA SEMARANG. Jurnal Geodesi Undip, 8(4), 50–58.
