Algoritma K-Means Clustering

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.
Kegunaan pengelompokan data ada beberapa macam. Pada kasus yang dibahas kali ini, data akan dikelompokkan ke dalam kelompok / cluster sehingga data-data yang memiliki kemiripan akan saling terkelompok, dan kemudian dapat dihitung kelompok tersebut merupakan kelompok apa. Contoh kasus pengembangan selanjutnya dari klasifikasi ini adalah menentukan data yang paling tidak cocok berada pada masing-masing cluster. Nantinya dapat ditarik kesimpulan apakah data tersebut dibuang atau dipindah ke cluster lain.

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

Nilai IPS

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:

Dim atribut() As String = {"IPA", "IPS", "Bahasa"}
Dim data(19)() As Double
data(0) = New Double() {50, 60, 70}
data(1) = New Double() {65, 80, 73}
data(2) = New Double() {72, 70, 65}
data(3) = New Double() {83, 65, 80}
data(4) = New Double() {40, 82, 73}
data(5) = New Double() {95, 71, 85}
data(6) = New Double() {60, 74, 96}
data(7) = New Double() {75, 75, 92}
data(8) = New Double() {83, 55, 70}
data(9) = New Double() {91, 60, 65}
data(10) = New Double() {92, 91, 55}
data(11) = New Double() {76, 80, 59}
data(12) = New Double() {75, 65, 74}
data(13) = New Double() {74, 76, 89}
data(14) = New Double() {63, 79, 69}
data(15) = New Double() {58, 93, 76}
data(16) = New Double() {82, 50, 80}
data(17) = New Double() {81, 65, 88}
data(18) = New Double() {76, 74, 70}
data(19) = New Double() {77, 71, 55}

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan Jumlah Atribut
Diasumsikan dalam kasus ini, jumlah atribut ada 3 buah, yaitu IPA, IPS, Bahasa

Dim jumlahAtribut As Integer = atribut.Length

* Tentukan Jumlah Cluster
Jumlah Cluster adalah jumlah dari pengelompokan data yang ingin dilakukan
Jumlah Cluster nilainya harus diantara 2 dan jumlah data
Diasumsikan dalam kasus ini, jumlah pengelompokan data ada 3 kelompok, yaitu jurusan IPA, jurusan IPS, jurusan Bahasa

Dim jumlahCluster As Integer = 3

* Tentukan Jumlah Iterasi
Diasumsikan dalam kasus ini, jumlah iterasi adalah 100

Dim jumlahIterasi As Integer = 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)

Dim daftarCluster() As Integer = Cluster(data, jumlahCluster, jumlahAtribut, jumlahIterasi)

Memasuki perhitungan utama pada fungsi Cluster

1. Pasang semua data pada cluster secara acak
Pastikan bahwa pada masing-masing cluster harus terdapat minimal 1 buah data

For i As Integer = 0 To jumlahCluster - 1
	daftarCluster(i) = i
Next i

Dim indeksTerakhir As Integer = -1
Dim rnd As Integer = indeksTerakhir
For i As Integer = jumlahCluster To daftarCluster.Length - 1
	Do While rnd = indeksTerakhir
		rnd = random.Next(0, jumlahCluster)
	Loop
	daftarCluster(i) = rnd
	indeksTerakhir = rnd
Next i

2. Hitung rata-rata untuk semua data yang sudah dipasang secara acak pada cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 2a – 2b)

Dim means(jumlahCluster - 1)() As Double
For k As Integer = 0 To jumlahCluster - 1
	means(k) = New Double(jumlahAtribut - 1) {}
Next k
UpdateMeans(data, daftarCluster, means)

Memasuki perhitungan utama pada fungsi UpdateMeans

2a. Lakukan perulangan untuk setiap data
Hitung jumlah nilai untuk masing-masing kriteria
Kemudian tambahkan 1 pada jumlah data per cluster untuk cluster tersebut

For i As Integer = 0 To data.Length - 1
	Dim cluster As Integer = daftarCluster(i)
	jumlahDataPerCluster(cluster) = jumlahDataPerCluster(cluster) + 1
	For j As Integer = 0 To data(i).Length - 1
		means(cluster)(j) = means(cluster)(j) + data(i)(j)
	Next j
Next i

2b. Bagi jumlah nilai dengan jumlah data per cluster untuk masing-masing atribut

For k As Integer = 0 To means.Length - 1
	For j As Integer = 0 To means(k).Length - 1
		means(k)(j) /= jumlahDataPerCluster(k)
	Next j
Next k

3. Kemudian hitung centroid untuk masing-masing cluster
Centroid adalah data pada masing-masing cluster yang paling mendekati nilai rata-rata yang sudah dihitung sebelumnya
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3a – 3b)

Dim centroids(jumlahCluster - 1)() As Double
For k As Integer = 0 To jumlahCluster - 1
	centroids(k) = New Double(jumlahAtribut - 1) {}
Next k
UpdateCentroids(data, daftarCluster, means, centroids)

Memasuki perhitungan utama pada fungsi UpdateCentroids

3a. Lakukan perhitungan pada semua data
Hitung jarak data dengan masing-masing centroid

Dim jarakSekarang As Double = HitungJarak(data(i), means(k))

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

Private Function HitungJarak(ByVal tuple() As Double, ByVal vector() As Double) As Double
	Dim jumlahKuadratDariSelisih As Double = 0.0
	For j As Integer = 0 To tuple.Length - 1
		jumlahKuadratDariSelisih = jumlahKuadratDariSelisih + Math.Pow((tuple(j) - vector(j)), 2)
	Next j
	Return Math.Sqrt(jumlahKuadratDariSelisih)
End Function

3b. Apabila jarak tersebut kurang dari jarak terpendek, ambil data ini sebagai centroid pada cluster tersebut.

If jarakSekarang < jarakTerpendek Then
	jarakTerpendek = jarakSekarang
	For j As Integer = 0 To centroid.Length - 1
		centroid(j) = data(i)(j)
	Next j
End If

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

4. Pindahkan semua data yang harus berpindah ke cluster lain
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4a – 4c)

bPindahCluster = UpdateCluster(data, daftarCluster, centroids)

Memasuki perhitungan utama pada fungsi UpdateCluster

4a. Hitung jarak dengan masing-masing centroid pada masing-masing cluster

For k As Integer = 0 To jumlahCluster - 1
	daftarJarak(k) = HitungJarak(data(i), centroids(k))
Next k

4b. Tentukan cluster baru yaitu cluster yang memiliki jarak terpendek

Dim clusterBaru As Integer = 0
Dim jarakTerpendek As Double = daftarJarak(0)
For k As Integer = 0 To daftarJarak.Length - 1
	If daftarJarak(k) < jarakTerpendek Then
		jarakTerpendek = daftarJarak(k)
		clusterBaru = k
	End If
Next k

4c. Jika nilai cluster yang baru berbeda dari cluster sebelumnya, maka pindahkan data ini ke cluster yang baru

If clusterBaru <> daftarCluster(i) Then
	bPindahCluster = True
	daftarCluster(i) = clusterBaru
End If

5. hitung ulang rata-rata untuk cluster dengan isian data tersebut
Dan hitung ulang nilai centroid untuk masing-masing cluster

UpdateMeans(data, daftarCluster, means)
UpdateCentroids(data, daftarCluster, means, centroids)

6. 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

Dim st() As Boolean = New Boolean() {False, False, False}
For k As Integer = 0 To jumlahCluster - 1
	Dim skor(jumlahCluster - 1) As Double
	For i As Integer = 0 To data.Length - 1
		If daftarCluster(i) = k Then
			Console.Write("Siswa " & Chr(i + 65) & vbTab)
			For j As Integer = 0 To data(i).Length - 1
				Console.Write(data(i)(j).ToString("F1").PadLeft(6) & " ")

				If st(j) = False Then skor(j) += data(i)(j)
			Next j
			Console.WriteLine("")
		End If
	Next i

	Dim maks As Double = Double.MinValue
	Dim idxmaks As Integer = -1
	For i As Integer = 0 To jumlahCluster - 1
		If maks < skor(i) Then
			maks = skor(i)
			idxmaks = i
		End If
	Next
	Console.WriteLine("Kelompok ini memiliki skor terbanyak pada kolom ke " & idxmaks + 1 & ", -> kelompok data " & atribut(idxmaks))
	Console.WriteLine("------------------------------")
Next k

Hasil akhir adalah: (klik untuk perbesar gambar)

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

[sdm_download id=”606″ fancy=”0″]

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.