(1) Implementasi Manual Clustering dengan Metode K-MEANS

          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