Algoritma K-Means Clustering 19


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 SiswaNilai IPANilai IPSNilai Bahasa
Siswa A506070
Siswa B658073
Siswa C727065
Siswa D836580
Siswa E408273
Siswa F957185
Siswa G607496
Siswa H757592
Siswa I835570
Siswa J916065
Siswa K929155
Siswa L768059
Siswa M756574
Siswa N747689
Siswa O637969
Siswa P589376
Siswa Q825080
Siswa R816588
Siswa S767470
Siswa T777155

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)

cmd30b

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



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.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

19 pemikiran di “Algoritma K-Means Clustering

    • pip Penulis

      Dalam algoritma ini, penentuan pusat cluster harus ditentukan secara acak tetapi tetap mengikuti aturan bahwa titik pusat harus memiliki jarak yang cukup dekat dengan masing-masing titik tetangga dalam cluster tersebut. Jika penentuan pusatnya tidak acak, berarti algoritma ini dimodifikasi dengan aturan tambahan, atau ada algoritma lain yang menentukan pusat cluster sehingga tidak perlu dihitung kembali. Jika benar demikian, maka selanjutnya adalah tergantung dari perhitungan algoritma yang digunakan untuk menentukan pusat cluster tersebut.

    • pip Penulis

      Skrip yang saya bagikan pada kasus ini sudah dalam bahasa Visual Basic .NET dan dapat anda ambil secara langsung. Saya sudah mencoba tombol downloadnya dan masih berfungsi dengan baik.

    • pip Penulis

      Tampilan bagaimanakah yang anda maksud? Skrip ini dibuat dengan menggunakan console sehingga tidak memiliki tampilan dalam bentuk form

  • Ridho Darmaizar

    mas misalkan kita mau mengelompokan sebuah gejala
    dimana kriteria gejala nya ada 3 yakni gejala berat, sedang dan ringan . Trus pemilihan bobot nilai nya dari data gejala dimana ada 23 gejala dgn masing-masing gejala sudah ditentukan sendri nilai ny
    jadi logika nya gimana y mas ?, Mohon bantuan nya mas
    trimakasih

    • pip Penulis

      Mohon maaf apakah anda dapat menjelaskan dengan menggunakan contoh konkrit karena saya masih belum memahami pemisalan yang anda sampaikan sebelumnya.

      • Ridho Darmaizar

        misal kan kita ingin mengelompokan seseorang kedalam sebuah klmpok yg trdiri dari 3 klmpok(klompok A,B dan C) mas dgn syarat pengelompokan tsb di seleksi dari 23 kriteria dimana tiap kriteria ada nilai ny untuk sbgai bahan acuan penilain pengelompokan tsb
        jadi yg ingin saya tnyakan logika coding ny gmana y mas klo kita menggunakan K-means ?
        mhon bntuan ny, trimakasih

        • pip Penulis

          Seperti penjelasan saya sebelumnya, saya belum dapat memahami kasus anda apabila belum anda jelaskan menggunakan contoh konkrit. Silahkan anda jelaskan mengenai kelompok A,B,C beserta dengan 23 kriteria yang anda miliki.

        • Ridho Darmaizar

          gini mas , sprti contoh koding di atas agan pakai 3 atribut kan … nh klo atribut ny di bikin 23 atribut dan kelompok cluster terdiri dari 3 kelompok gmana gan bisa gk t kira* mas ?
          mksih

        • pip Penulis

          Karena anda tidak menjelaskan contoh detail, maka saya hanya dapat memperkirakan saja.

          Dengan asumsi penggantian data dari 3 atribut menjadi 23 atribut, maka setiap data yang digunakan harus memiiliki 23 buah nilai kriteria sebagai nilai dari masing-masing atribut. Jumlah Cluser sudah benar sesuai dengan usulan sebelumnya, yaitu 3, karena anda hanya perlu mengklasifikasikan data menjadi 3 buah kelompok. Tanpa mengetahui detail kasus anda, maka skrip yang saya bagikan disini mungkin tidak memerlukan penyesuaian terhadap bagian2 lain selain hal yang sudah saya sampaikan sebelumnya.

    • pip Penulis

      Pembahasan algoritma pada pos ini saya lakukan dengan menggunakan bahasa visual basic .NET, dan contoh modul implementasi dapat diambil di bagian akhir pos.