Pengelompokan Data Menggunakan Metode K-MeansApa itu K-Means?

Algoritma K-Means merupakan algoritma clustering iteratif sederhana di mana semua partisi dataset yang diberikan menjadi beberapa pengguna tertentu cluster, k. Algoritma ini sederhana untuk melaksanakan dan menjalankan, relatif cepat, mudah beradaptasi, dan umum dalam praktek [3].Algoritma K-Means merupakan algoritma clustering iteratif sederhana di mana semua partisi dataset yang diberikan menjadi beberapa pengguna tertentu cluster, k. Algoritma ini sederhana untuk melaksanakan dan menjalankan, relatif cepat, mudah beradaptasi, dan umum dalam praktek [1]. K-Means adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi. Metode k-means berusaha mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang lain. Dengan kata lain, metode ini berusaha untuk meminimalkan variasi antar data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang ada di cluster lainnya[2].

Bagaimana langkah-langkah algoritma K-Means? Algoritma k-means dimulai dengan pembentukan prototipe cluster di awal kemudian secara iteratif prototipe cluster ini diperbaiki hingga konvergen (tidak terjadi perubahan yang signifikan pada prototipe cluster). Perubahan ini diukur menggunakan fungsi objektif J yang umumnya didefinisikan sebagai jumlah atau rata-rata jarak tiap item data dengan pusat massa kelompoknya. Secara lebih detil algoritma k-means adalah seperti berikut : 1. inisialisasi nilai J (misal MAXINT)

2. Tentukan prototipe cluster awal (bisa secara acak ataupun dipilih salah satu secara acak dari koleksi data) 3. Masukkan tiap satuan data ke dalam kelompok yang jarak dengan pusat massa-nya paling dekat 4. ubah nilai pusat massa tiap cluster sebagai rata-rata (mean) dari seluruh anggota kelompok tersebut 5. Hitung fungsi objektif J 6. jika nilai J sama dengan sebelumnya, berhenti atau ulangi langkah 3 Algoritma k-means clustering walaupun proses pengerjaannya cepat tetapi keakuratannya tidak dijamin. Seringkali algoritma ini mengalami konvergensi prematur. Pada algoritma di atas juga tidak dijamin jarak antara masing-masing centroid tidak merentang sehingga jika ada dua atau lebih kelompok dengan titik pusat massa yang berdekatan atau terdapat kelompok yang tidak memiliki anggota maka hasilnya akan tidak memuaskan. Contoh Kasus Diberikan data Body Mass Index (BMI) dan ukuran kerangka 20 orang mahasiswa sebagai berikut: Mhs ke1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 BMI 22,21 43,25 19,71 21,05 17,93 17,72 18,71 25,86 19,15 18,42 22,94 26,89 24,91 22,99 26,81 19,14 21,09 18,71 20,58 27,66 Ukuran Kerangka 11.64 8.95 10.93 10.38 12.85 12.00 11.53 9.33 11.80 11.20 10.60 10.44 10.63 11.47 9.17 12.11 10.67 12.36 10.80 9.94

Kelompokkan data tersebut menjadi 3 kelompok. Jawab :

Langkah 1 : Tentukan pusat cluster secara acak. Disini kita tentukan kita tentukan c1 = (20,9); c2 = (23,10); dan c3 = (27,11). Langkah 2 : Hitung jarak setiap data yang ada terhadap setiap pusat cluster. Sebagai contoh untuk menghitung jarak data mahasiswa pertama dengan pusat cluster pertama adalah :

Jarak data mahasiswa pertama dengan pusat cluster kedua :

Jarak data mahasiswa pertama dengan pusat cluster ketiga :

Hasil perhitungan selengkapnya pada tabel berikut : Tabel Perhitungan Data Terhadap Masing-masing Cluster Mhs ke1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 BMI 22,21 43,25 19,71 21,05 17,93 17,72 18,71 25,86 19,15 18,42 22,94 26,89 24,91 22,99 26,81 19,14 Uk. Rangka 11.64 8.95 10.93 10.38 12.85 12.00 11.53 9.33 11.80 11.20 10.60 10.44 10.63 11.47 9.17 12.11 C1 4,97 25,25 2,58 3,34 3,85 3,01 2,63 7,87 3,03 2,24 5,19 9,01 7,10 5,56 8,82 3,31 C2 2,04 22,28 1,60 0,38 4,19 3,85 2,76 4,91 2,58 2,84 2,03 5,91 3,96 2,47 5,87 2,81 C3 1,91 19,36 4,29 3,02 6,35 6,36 5,32 2,50 4,91 5,58 1,13 2,95 0,99 1,12 3,36 4,98

17 18 19 20

21,09 18,71 20,58 27,66

10.67 12.36 10.80 9.94

3,51 3,43 3,14 9,71

0,67 3,29 0,91 6,66

2,93 5,46 3,43 3,81

Langkah 3 : Tentukan cluster dengan jarak terdekat pada masing-masing data. Sebagai contoh, pada data pertama dan kedua, cluster dengan jarak terdekat adalah cluster ketiga (C 3). Untuk lengkapnya dapat dilihat pada tabel berikut. Tabel Hasil Iterasi 1 Mhs ke1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 BMI Uk. Rangka 22,21 11.64 43,25 8.95 19,71 10.93 21,05 10.38 17,93 12.85 17,72 12.00 18,71 11.53 25,86 9.33 19,15 11.80 18,42 11.20 22,94 10.60 26,89 10.44 24,91 10.63 22,99 11.47 26,81 9.17 19,14 12.11 21,09 10.67 18,71 12.36 20,58 10.80 27,66 9.94 C1 C2 C3 * *

* * * * * * * * * * * * * * * * * *

Langkah 4 : Hitung pusat cluster baru. Untuk cluster pertama, ada 4 data yaitu data ke-5, 6, 7 dan data ke-10, sehingga: C11 = (17,93+17,72+18,71+18,42) / 4 = 18,19 C12 = (12,85+12,00+11,53+11,20) / 4 = 11,89

Untuk cluster kedua, ada 7 data yaitu data ke-3, 4, 9, 16, 17, 18 dan data ke-19, sehingga : C21 = (19,71+21,05+19,15+19,14+21,09+18,71+20,58) / 7 = 19,92 C22 = (10,93+10,38+11,8+12,11+10,67+12,36+10,8) / 7 = 11,29 Untuk cluster ketiga, ada 9 data yaitu data ke-1, 2, 8, 11, 12, 13, 14, 15 dan data ke20, sehingga C31 = (22,21+43,25+25,86+22,94+26,89+24,91+22,99+26,81+27,66) / 9 = 27,06 C32 = (11,64+8,95+9,33+10,6+10,44+10,63+11,47+9,17+9,94) / 9 = 10,24 Langkah 5 : Ulangi langkah 2,3 dan 4 hingga posisi data terhadap cluster sudah tidak mengalami perubahan.

Langkah 6 : Karena pada iterasi ke-8 dan ke-9 posisi cluster tidak berubah, maka iterasi dihentikan dan hasil akhir yang diperoleh adalah 3 cluster : Cluster pertama memiliki pusat (19,53; 11,52) Cluster kedua memiliki pusat (25,44; 10,22) Cluster ketiga memiliki pusat (43,25; 8,95)