Untuk post ketiga, kali ini saya akan membahas tentang metode clustering dengan K-Means. di post ini saya akan jelaskan secara nutshell, dan mudah-mudahan saya akan sempat menyertakan algoritmanya secara umum di postingan berikutnya ;)
Metode
K-Means cluster adalah metode
pengelompokan yang bertujuan mengelompokan individu sedemikian hingga jarak
setiap individu ke pusat kelompok dalam satu kelompok adalah minimum (Dillon,
1984). Proses clustering dengan
menggunakan algoritma K-Means
memiliki langkah-langkah sebagai berikut :
1. Tentukan jumlah cluster (sebanyak K cluster)
2. Menentukan centroid setiap cluster secara
acak.
3. Menghitung jarak setiap objek ke centroid
4. Memasukkan objek ke centroid terdekat.
5. Perbaharui kembali centroid setiap cluster.
6. Kembali ke langkah 3, apabila masih ada
data yang berpindah cluster.
Jarak
antara data dengan centroid dihitung dengan menggunakan rumus Euclidian adalah sebagai berikut :
Dimana
:
x
= Objek Data.
y
= Data Cluster.
m=
Jumlah Atribut.
Untuk
implementasinya, kita bisa bayangkan kasus sederhananya seperti ini; andaikan
suatu jurusan di suatu universitas pada gelombang pertama memiliki lulusan
sebanyak 10 mahasiswa, dan kita ingin membagi ke-10 mahasiswa tersebut menjadi
empat kelompok sehingga anggota satu kelompok memiliki karakteristik yang jauh
berbeda dengan kelompok yang lain (untuk kasus yang ini karakteristik yang dimaksud
adalah berdasarkan IPK dan lama studi).
Berikut
adalah data mahasiswa lulusan gelombang pertama:
Mahasiswa
ke-
|
IPK
|
Lama Studi
|
1
|
3,15
|
3,9
|
2
|
2,93
|
4,1
|
3
|
3,19
|
5,1
|
4
|
3,63
|
3,9
|
5
|
2,95
|
4,1
|
6
|
3,03
|
4,1
|
7
|
2,97
|
4,1
|
8
|
2,62
|
4,9
|
9
|
3,16
|
3,9
|
10
|
3,26
|
3,9
|
klik untuk memperbesar
Gambar diatas dibuat untuk memudahkan anda memvisualisasikannya, terlihat pada plot diatas kita mempunya 10 titik yang merepresentasikan ke-10 mahasiswa dengan masing-masing koordinat bernilai IPK dan lama studinya, karena gambar tersebut dibuat di Excel harap dimaklumi jika beberapa titik gambar ini dan gambar kedepannya berdempetan karena saya tidak tahu cara mengatur skala axis dan ordinal di software ini :p
Sekarang kita akan melakukan langkah pertama
di metode ini. Pada iterasi pertama kita akan menentukan berapa banyak kelompok
(cluster) yang akan dibentuk. Dan seperti
yang dijelaskan sebelumnya kita menetapkan data tersebut akan dibagi menjadi 4
kelompok (cluster), lalu kita akan
menentukan centroid awal pada masing-masing kelompok. Sebenarnya dalam
algoritma ini centroid awal bisa ditentukan nilainya dengan acak, namun kita
akan menetapkan centroid masing-masing cluster awalnya sebagai berikut:
Centroid Cluster ke-
|
IPK
|
Lama Studi
|
1
|
3,30
|
3,95
|
2
|
3,30
|
4,05
|
3
|
3,05
|
3,95
|
4
|
3,05
|
4,05
|
klik untuk memperbesar
Gambar diatas menunjukan
centroid yang direpresentasikan oleh persegi merah, centroid terlihat hanya
seperti berjumlah 2 dikarenakan ada jarak centroid yang terlalu berdekatan
sehingga berdempet
Setelah
itu jarak data setiap mahasiswa dengan centroid di setiap cluster akan kita
hitung dengan rumus Euclidian sebagai
berikut :
Dimana
:
x
= Data Mahasiswa
y
= Data Cluster
m=
Jumlah Atribut (atribut dikasus ini berjumlah dua yaitu IPK dan lama studi)
Berikut ini merupakan contoh proses perhitungan
jarak centroid masing-masing cluster
dengan data mahasiswa pertama menggunakan rumus
diatas
Hasil dari perhitungan data tersebut diperoleh data
seperti yang dapat dilihat pada Tabel dibawah :
Mahasiswa ke-
|
IPK
|
Lama Studi
|
Jarak dari Mahasiswa ke-n dengan centroid cluster
ke-c
|
|||
Centroid Cluster ke-1
|
Centroid Cluster ke-2
|
Centroid Cluster ke-3
|
Centroid Cluster ke-4
|
|||
1
|
3,15
|
3,9
|
0,1581139
|
0,212132
|
0,1118034
|
0,1802776
|
Setelah semua jarak
mahasiswa pertama dengan masing-masing cluster telah dihitung, lakukan juga
terhadap mahasiswa kedua, ketiga sampai terakhir. Untuk visualisasi kita bisa
melihat hasil perhitungan jarak antara centroid di cluster pertama dengan
mahasiswa ketiga pada gambar dibawah
Berikut adalah hasil
perhitungan jarak setiap mahasiswa dengan masing-masing cluster
Mahasiswa
ke-
|
IPK
|
Lama Studi
|
Jarak dari
Mahasiswa ke-n dengan centroid cluster ke-c
|
|||
Centroid Cluster ke-1
|
Centroid Cluster ke-2
|
Centroid Cluster ke-3
|
Centroid Cluster ke-4
|
|||
1
|
3,15
|
3,9
|
0,158113883
|
0,212132034
|
0,111803399
|
0,180277564
|
2
|
2,93
|
4,1
|
0,399249296
|
0,373363094
|
0,192093727
|
0,13
|
3
|
3,19
|
5,1
|
1,155248891
|
1,055746182
|
1,158490397
|
1,059292217
|
4
|
3,63
|
3,9
|
0,333766385
|
0,362491379
|
0,582151183
|
0,599082632
|
5
|
2,95
|
4,1
|
0,380788655
|
0,353553391
|
0,180277564
|
0,111803399
|
6
|
3,03
|
4,1
|
0,308868904
|
0,274590604
|
0,15132746
|
0,053851648
|
7
|
2,97
|
4,1
|
0,362491379
|
0,333766385
|
0,17
|
0,094339811
|
8
|
2,62
|
4,9
|
1,168289348
|
1,08853112
|
1,042784733
|
0,952575456
|
9
|
3,16
|
3,9
|
0,148660687
|
0,205182845
|
0,12083046
|
0,186010752
|
10
|
3,26
|
3,9
|
0,064031242
|
0,155241747
|
0,215870331
|
0,258069758
|
Mari kita lihat jarak mahasiswa
pertama dengan masing-masing centroid di setiap cluster, logikanya disini
adalah jika jarak antara dua titik semakin dekat, maka semakin dekatlah pula
kesamaan antara kedua titik tersebut. Mahasiswa pertama mempunyai jarak peling
dekat dengan centroid di kelompok 3 dibandingkan dengan centroid dari kelompok
lain, maka kita bisa menyimpulkan bahwa mahasiswa pertama mempunyai
karakteristik paling dekat dengan kelompok satu dibanding dengan kelompok lain
sehingga mahasiswa pertama dimasukan kedalam kelompok satu, simpel bukan ; ) ?
Lakukan pengelompokkan mahasiswa lainnya dengan cara yang sama juga, sehingga semua
mahasiswa telah masuk ke kelompoknya masing masing
Anggota
Cluster 1
|
||
Mahasiswa
ke-
|
IPK
|
Lama Studi
|
4
|
3,63
|
3,9
|
10
|
3,26
|
3,9
|
Anggota
Cluster 2
|
||
Mahasiswa
ke-
|
IPK
|
Lama Studi
|
3
|
3,19
|
5,1
|
6
|
3,03
|
4,1
|
Anggota
Cluster 3
|
||
Mahasiswa
ke-
|
IPK
|
Lama Studi
|
1
|
3,15
|
3,9
|
9
|
3,16
|
3,9
|
Anggota
Cluster 4
|
||
Mahasiswa
ke-
|
IPK
|
Lama Studi
|
2
|
2,93
|
4,1
|
5
|
2,95
|
4,1
|
7
|
2,97
|
4,1
|
8
|
2,62
|
4,9
|
klik untuk memperbesar
Setelah semua mahasiswa masuk dalam kelompoknya, kita akan menghitung kembali centroid baru masing-masing cluster dengan cara menjumlahkan data-data yang ada di masing-masing cluster dan membaginya dengan jumlah data pada cluster itu. Contohnya, centroid baru pada kelompok satu untuk koordinat IPK akan benilai 3,445 yang dihitung dengan cara IPK masing-masing anggota kelompok satu ditambahkan lalu dibagi dengan jumlah anggota kelompok satu --> (3,6+3,26)/2=3,445, lakukan hal yang sama untuk mencari koordinat lama studi.
Centroid baru yang akan
digunakan untuk iterasi kedua adalah
Centroid
Baru untuk iterasi yang kedua
|
||
Centroid Cluster ke-
|
IPK
|
Lama Studi
|
1
|
3,445
|
3,9
|
2
|
3,11
|
4,6
|
3
|
3,155
|
3,9
|
4
|
2,8675
|
4,3
|
klik untuk memperbesar
Pada iterasi kedua,
lakukan penghitungan jarak setiap mahasiswa dengan masing-masing cluster dengan
centroid masing-masing cluster yang baru tersebut. Loh, terus iterasinya berhenti kapan? Iterasi bisa selesai jika pada
suatu iterasi ke-n, tidak ada pertukaran anggota sama sekali antar cluster (anggota
masing2 cluster sama dengan iterasi sebelumnya). Anggap saja misalnya ada satu season
di Liga Inggris dimana skuad pemain di ke-20 klub tersebut tetap sama seperti season
sebelumnya (no transfer in and out). Nah jika kondisi tersebut terpenuhi maka
iterasi dihentikan dan kita bisa melihat para anggota final masing-masing
kelompok pada iterasi ini (atau sebelumnya, kan sama saja).
Nah begitulah penjelasan
singkat tentang metode ini, mohon maaf jika agak berantakan dan semoga bermanfaat ; )
sumber : Kharismawan,Bagus 2015 (Unpad: University of Padjadjaran) Aplikasi K-Means dan Fuzzy C-Means Clustering untuk Mengelompokkan Data Mahasiswa FMIPA
sumber : Kharismawan,Bagus 2015 (Unpad: University of Padjadjaran) Aplikasi K-Means dan Fuzzy C-Means Clustering untuk Mengelompokkan Data Mahasiswa FMIPA
