Algoritma Category Utility Clustering

Algoritma Category Utility Clustering adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan penerimaan pengajuan kredit sepeda motor.
Algoritma ini memiliki kemiripan dengan Algoritma Entropy Minimization Clustering. Pada algoritma tersebut, cluster terbaik diukur dengan nilai Entropy, semakin rendah nilai Entropy, maka semakin baik pengelompokan data yang dilakukan. Sedangkan pada algoritma ini, cluster terbaik diukur dengan nilai CU (Category Utility), semakin tinggi nilai CU, maka semakin baik pengelompokan data yang dilakukan.

Diasumsikan ada 13 data pelanggan, yaitu Pelanggan A,B,C,D,E,F,G,H,I,J,K,L,M
Masing-masing pelanggan memiliki kriteria, yaitu umur, jenis kelamin, skor kepribadian
Maka tentukan kelompok data pelanggan menjadi 2 bagian, yaitu kelompok data Diterima atau Ditolak
Diasumsikan 13 data tersebut adalah sebagai berikut:

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:

Dim data(12)() As String
data(0) = New String() {44, "Laki-laki", 3.55}
data(1) = New String() {52, "Perempuan", 4.71}
data(2) = New String() {47, "Perempuan", 6.56}
data(3) = New String() {37, "Laki-laki", 6.8}
data(4) = New String() {43, "Laki-laki", 6.94}
data(5) = New String() {35, "Perempuan", 6.52}
data(6) = New String() {61, "Laki-laki", 4.25}
data(7) = New String() {53, "Perempuan", 5.71}
data(8) = New String() {60, "Perempuan", 6.05}
data(9) = New String() {54, "Laki-laki", 5}
data(10) = New String() {52, "Laki-laki", 5.7}
data(11) = New String() {46, "Laki-laki", 3.9}
data(12) = New String() {56, "Perempuan", 4.85}

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* 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 2 kelompok, yaitu kelompok Diterima dan Ditolak

Const jumlahCluster As Integer = 2

* Tentukan Jumlah iterasi yang diperlukan untuk mendapatkan data awal pada masing-masing cluster
Diasumsikan dalam kasus ini, jumlah iterasi adalah 10

Const jumlahIterasi As Integer = 10

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Pengelompokan untuk masing-masing kriteria
Jumlah pengelompokan bebas tergantung keinginan
Contoh dalam kasus ini:
Kriteria umur hanya dikelompokan menjadi 3 bagian yaitu untuk umur dibawah 40, 41 sampai dengan 50, diatas 50
Kriteria jenis kelamin dikelompokan menjadi 2 bagian yaitu untuk laki-laki dan perempuan
Kriteria skor kepribadian dikelompokan menjadi 4 bagian yaitu untuk skor dibawah 4, 4 sampai dengan 5, 5 sampai dengan 6, diatas 6

Dim atribut As String()() = New String(2)() {}
atribut(0) = New String() {"Dibawah 40", "41 s/d 50", "Diatas 50"}
atribut(1) = New String() {"Laki-laki", "Perempuan"}
atribut(2) = New String() {"Dibawah 4", "4 s/d 5", "5 s/d 6", "Diatas 6"}

2. Tentukan matriks data awal untuk data yang sudah mengalami pengelompokan data sesuai kriteria diatas

Dim dataAwal As Integer()() = New Integer(data.Length - 1)() {}
For i As Integer = 0 To data.Length - 1
	dataAwal(i) = New Integer(atribut.Length - 1) {}

	For j As Integer = 0 To atribut.Length - 1
		Dim v As String = ""
		If j = 0 Then
			If data(i)(j) <= 40 Then
				v = atribut(j)(0)
			ElseIf data(i)(j) <= 50 Then
				v = atribut(j)(1)
			ElseIf data(i)(j) > 50 Then
				v = atribut(j)(2)
			End If
		ElseIf j = 1 Then
			v = data(i)(j)
		ElseIf j = 2 Then
			If data(i)(j) <= 4 Then
				v = atribut(j)(0)
			ElseIf data(i)(j) <= 5 Then
				v = atribut(j)(1)
			ElseIf data(i)(j) <= 6 Then
				v = atribut(j)(2)
			ElseIf data(i)(j) > 6 Then
				v = atribut(j)(3)
			End If
		End If

		dataAwal(i)(j) = lookup(j)(v)
	Next
Next

3. Lakukan perhitungan untuk mencari cluster awal
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3a – 3c)

Cluster(dataAwal, atribut, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster, jumlahIterasi)

3a. Pilih data sebanyak jumlah cluster, yang datanya dianggap tidak memiliki kemiripan

Dim jumlahCluster As Integer = jumlahDataPerCluster.Length
Dim indeksCukupBaik As Integer() = cariIndeksCukupBaik(dataAwal, atribut, jumlahIterasi, jumlahCluster)

* Gunakan fungsi ini untuk mencari indeks yang cukup baik pada masing-masing cluster
indeks yang cukup baik adalah indeks data yang dianggap paling berbeda (tidak memiliki kemiripan)
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Private Function cariIndeksCukupBaik(dataAwal As Integer()(), atribut As String()(), jumlahIterasi As Integer, jumlahCluster As Integer) As Integer()

3a1. Pada setiap kali perulangan,
Lakukan inisialisasi data cluster mini, yaitu cluster dengan isian masing-masing hanya 1 data

Dim miniData As Integer()() = New Integer(jumlahCluster - 1)() {}
For i As Integer = 0 To miniData.Length - 1
	miniData(i) = New Integer(dataAwal(0).Length - 1) {}
Next

Dim minidaftarCluster As Integer() = New Integer(dataAwal.Length - 1) {}
For i As Integer = 0 To minidaftarCluster.Length - 1
	minidaftarCluster(i) = -1
Next

Dim minijumlahDataPerKriteriaPerCluster As Integer()()() = New Integer(atribut.Length - 1)()() {}
For i As Integer = 0 To minijumlahDataPerKriteriaPerCluster.Length - 1
	minijumlahDataPerKriteriaPerCluster(i) = New Integer(atribut(i).Length - 1)() {}

	For j As Integer = 0 To minijumlahDataPerKriteriaPerCluster(i).Length - 1
		minijumlahDataPerKriteriaPerCluster(i)(j) = New Integer(jumlahCluster - 1) {}

		For k As Integer = 0 To minijumlahDataPerKriteriaPerCluster(i)(j).Length - 1
			minijumlahDataPerKriteriaPerCluster(i)(j)(k) = 0
		Next
	Next
Next

Dim minijumlahDataPerKriteria As Integer()() = New Integer(atribut.Length - 1)() {}
For i As Integer = 0 To minijumlahDataPerKriteria.Length - 1
	minijumlahDataPerKriteria(i) = New Integer(atribut(i).Length - 1) {}
Next

Dim minijumlahDataPerCluster As Integer() = New Integer(jumlahCluster - 1) {}

3a2. Cari indeks acak sejumlah banyak cluster, dengan indeks acak yang tidak boleh ada yang sama

Dim d As New Dictionary(Of Integer, Boolean)()
Dim indeksAcak As Integer() = New Integer(jumlahCluster - 1) {}
Dim ct As Integer = 0
Dim batasPerulangan As Integer = 0
While ct < jumlahCluster AndAlso batasPerulangan < 10000
	batasPerulangan += 1
	Dim idx As Integer = random.[Next](0, dataAwal.Length)
	If d.ContainsKey(idx) = False Then
		indeksAcak(ct) = idx
		d(idx) = True
		ct += 1
	End If
End While

3a3. Masukkan ke dalam cluster mini yang sudah dibuat sebelumnya

For i As Integer = 0 To miniData.Length - 1
	For j As Integer = 0 To miniData(i).Length - 1
		miniData(i)(j) = dataAwal(indeksAcak(i))(j)
	Next
Next

For k As Integer = 0 To indeksAcak.Length - 1
	Assign(k, miniData, k, minidaftarCluster, minijumlahDataPerKriteriaPerCluster, minijumlahDataPerKriteria, minijumlahDataPerCluster)
Next

3a4. Tentukan nilai CU (Category Utility) untuk cluster mini yang sudah ditentukan
Jika nilai CU yang baru ternyata lebih baik, maka ambil indeks nya sebagai indeks terbaik

Dim cu As Double = HitungCategoryUtility(minijumlahDataPerKriteriaPerCluster, minijumlahDataPerKriteria, minijumlahDataPerCluster)

If cu > CUTerbaik Then
	CUTerbaik = cu
	Array.Copy(indeksAcak, indeksTerbaik, indeksAcak.Length)
End If

3b. Masukkan data ini kedalam masing-masing cluster sebagai data awal

For k As Integer = 0 To jumlahCluster - 1
	Assign(indeksCukupBaik(k), dataAwal, k, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
Next

3c. Kemudian untuk masing-masing data yang belum terpilih:

3c1. Hitung nilai CU untuk setiap cluster apabila data ini dimasukkan ke cluster tersebut

Dim calonNilaiCU As Double() = New Double(jumlahCluster - 1) {}
For k As Integer = 0 To jumlahCluster - 1
	Assign(t, dataAwal, k, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
	calonNilaiCU(k) = HitungCategoryUtility(jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
	Unassign(t, dataAwal, k, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
Next

* Gunakan fungsi ini untuk memasukkan data ke dalam cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Private Sub Assign(indeksData As Integer, dataAwal As Integer()(), cluster As Integer, daftarCluster As Integer(), jumlahDataPerKriteriaPerCluster As Integer()()(), jumlahDataPerKriteria As Integer()(), jumlahDataPerCluster As Integer())
	daftarCluster(indeksData) = cluster
	For i As Integer = 0 To jumlahDataPerKriteriaPerCluster.Length - 1
		Dim v As Integer = dataAwal(indeksData)(i)
		jumlahDataPerKriteriaPerCluster(i)(v)(cluster) += 1
		jumlahDataPerKriteria(i)(v) += 1
	Next
	jumlahDataPerCluster(cluster) += 1
End Sub

* Gunakan fungsi ini untuk mengeluarkan data dari sebuah cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Private Sub Unassign(indeksData As Integer, dataAwal As Integer()(), cluster As Integer, daftarCluster As Integer(), jumlahDataPerKriteriaPerCluster As Integer()()(), jumlahDataPerKriteria As Integer()(), jumlahDataPerCluster As Integer())
	daftarCluster(indeksData) = -1
	For i As Integer = 0 To jumlahDataPerKriteriaPerCluster.Length - 1
		Dim v As Integer = dataAwal(indeksData)(i)
		jumlahDataPerKriteriaPerCluster(i)(v)(cluster) -= 1
		jumlahDataPerKriteria(i)(v) -= 1
	Next
	jumlahDataPerCluster(cluster) -= 1
End Sub

3c2. Cari nilai CU Terbaik untuk mendapatkan cluster tujuan tempat memasukkan data ini
Cluster yang terpilih adalah cluster yang menghasilkan nilai CU terbaik

Dim CUTerbaik As Double = 0.0
Dim indeksCUTerbaik As Integer = 0
For k As Integer = 0 To calonNilaiCU.Length - 1
	If calonNilaiCU(k) > CUTerbaik Then
		CUTerbaik = calonNilaiCU(k)
		indeksCUTerbaik = k
	End If
Next

3c3. Masukkan data tersebut ke dalam cluster yang menghasilkan nilai CU terbaik

Assign(t, dataAwal, indeksCUTerbaik, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)

4. Tentukan nilai CU (Category Utility) untuk cluster yang sudah ditentukan
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4a – 4d)

Dim cu As Double = HitungCategoryUtility(jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)

Lakukan perhitungan Category Utility dengan rumus:
CU(C) = E P(Ck) * [ EE P(Ai=Vij|Ck)^2 – EE P(Ai=Vij)^2 ] / n

4a. Hitung P(Ck)

For k As Integer = 0 To jumlahCluster - 1
	probClusterK(k) = (jumlahDataPerCluster(k) * 1.0) / jumlahDataAssigned
Next

4b. Hitung nilai EE P(Ai=Vij)^2, atau dinamakan probabilitas tidak terkondisi,
yaitu jumlah dari (kuadrat dari (probabilitas nilai atribut pada semua cluster))

Dim probTidakTerkondisi As Double = 0.0
For i As Integer = 0 To jumlahDataPerKriteria.Length - 1
	For j As Integer = 0 To jumlahDataPerKriteria(i).Length - 1
		Dim p As Double = (jumlahDataPerKriteria(i)(j) * 1.0) / jumlahDataAssigned
		probTidakTerkondisi += (p * p)
	Next
Next

4c. Hitung nilai EE P(Ai=Vij|Ck)^2, atau dinamakan probabilitas terkondisi,
yaitu jumlah dari (kuadrat dari (probabilitas nilai atribut pada masing-masing cluster))

Dim probTerkondisi As Double() = New Double(jumlahCluster - 1) {}
For k As Integer = 0 To jumlahCluster - 1

	For i As Integer = 0 To jumlahDataPerKriteriaPerCluster.Length - 1
		For j As Integer = 0 To jumlahDataPerKriteriaPerCluster(i).Length - 1
			Dim p As Double = (jumlahDataPerKriteriaPerCluster(i)(j)(k) * 1.0) / jumlahDataPerCluster(k)
			probTerkondisi(k) += (p * p)
		Next
	Next
Next

4d. Hitung nilai akhir dengan rumus
CU(C) = E P(Ck) * [ EE P(Ai=Vij|Ck)^2 – EE P(Ai=Vij)^2 ] / n

Dim summation As Double = 0.0
For k As Integer = 0 To jumlahCluster - 1
	summation += probClusterK(k) * (probTerkondisi(k) - probTidakTerkondisi)
Next

Return summation / jumlahCluster

5. Lakukan proses perbaikan cluster untuk menghasilkan cluster yang lebih baik
Untuk setiap cluster baru, hitung nilai CU (Category Utility) nya
Apabila nilai CU nya lebih baik, maka ambil cluster ini sebagai cluster terbaik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 5a – 5d)

Perbaikan(20, dataAwal, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)

5a. Pada setiap proses perbaikan,
Cari indeks data acak, dimana data tersebut berada pada cluster yang memiliki lebih dari 1 data lainnya

Dim indeksDataAcak As Integer = -1
Dim batasPerulangan As Integer = 0
While batasPerulangan < 10000
	batasPerulangan += 1
	Dim ri As Integer = random.[Next](0, dataAwal.Length)
	Dim c As Integer = daftarCluster(ri)
	If jumlahDataPerCluster(c) > 1 Then
		indeksDataAcak = ri
		Exit While
	End If
End While

5b. Cari cluster acak yang posisi clusternya berbeda dari indeks data acak yang sudah ditentukan sebelumnya

Dim clusterLainnya As Integer = -1
Dim batasPerulangan2 As Integer = 0
While batasPerulangan2 < 10000
	batasPerulangan2 += 1
	Dim c As Integer = random.[Next](0, jumlahDataPerCluster.Length)
	If c <> clusterDataAcak Then
		clusterLainnya = c
		Exit While
	End If
End While

5c. Hitung nilai CU untuk posisi awal
Keluarkan data [indeks acak] dari cluster nya
Masukkan data tersebut ke cluster yang baru
Hitung nilai CU baru untuk posisi yang baru

Dim CUSekarang As Double = HitungCategoryUtility(jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
Unassign(indeksDataAcak, dataAwal, clusterDataAcak, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
Assign(indeksDataAcak, dataAwal, clusterLainnya, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
Dim CUBaru As Double = HitungCategoryUtility(jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)

5d. Jika nilai CU yang baru ternyata lebih baik, maka ambil cluster ini sebagai cluster terbaik
Jika tidak maka kembalikan posisi data seperti semula

If CUBaru > CUSekarang Then
	Console.Write("Ditemukan cluster yang lebih baik yaitu: ")
	For i As Integer = 0 To daftarCluster.Length - 1
		Console.Write(daftarCluster(i) & " ")
	Next
	Console.WriteLine("")
	Console.WriteLine("Nilai CU (Category Utility) terbaik sementara = " & CUBaru.ToString("F4"))
	Console.WriteLine("")

Else
	Unassign(indeksDataAcak, dataAwal, clusterLainnya, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
	Assign(indeksDataAcak, dataAwal, clusterDataAcak, daftarCluster, jumlahDataPerKriteriaPerCluster, jumlahDataPerKriteria, jumlahDataPerCluster)
End If

6. Hitung nilai data pada masing-masing cluster
Nilai pada setiap data dihitung dari penjumlahan nilai kelompok kriteria pada masing-masing kolom
Pada Kriteria umur, semakin rendah kelompok kriteria, maka semakin tinggi nilai kolomnya, dan sebaliknya.
Pada Kriteria jenis kelamin dan skor kepribadian, semakin tinggi kelompok kriteria, maka semakin tinggi nilai kolomnya, dan sebaliknya.

If j = 0 Then
	total(k) += atribut(0).Length - v
Else
	total(k) += v
End If

7. Lihat kembali matriks data awal yang sudah terkelompok
Bandingkan nilai total data antara kedua cluster
Nilai total data yang lebih tinggi akan masuk ke dalam kelompok Diterima, sedangkan nilai total data yang lebih rendah akan masuk ke dalam kelompok Ditolak

If total(0) > total(1) Then
	Console.WriteLine("Nilai Kelompok pertama (" & total(0) & ") lebih dari Kelompok kedua (" & total(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Diterima")
	Console.WriteLine("Kelompok kedua adalah kelompok Ditolak")
Else
	Console.WriteLine("Nilai Kelompok pertama (" & total(0) & ") kurang dari Kelompok kedua (" & total(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Ditolak")
	Console.WriteLine("Kelompok kedua adalah kelompok Diterima")
End If

Hasil akhir adalah: (klik untuk perbesar gambar)

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.