Algoritma C4.5

Algoritma C4.5 adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mementukan kriteria pembeli dalam pembelian Sepeda Motor dengan kriteria tertentu.
Perlu diperhatikan bahwa Algoritma C4.5 adalah pengembangan dari Algoritma ID3, tetapi karena referensi yang ada sekarang masih terbatas, sehingga terdapat ketidaksempurnaan dalam pembahasan ini. Penulis akan menyempurnakan pengembangan algoritma ini setelah mendapatkan referensi yang cukup. Jika membutuhkan algoritma pengambilan keputusan yang sudah benar, silahkan melihat ke Algoritma ID3

Diasumsikan ada 12 buah motor yang dapat dipilih yaitu Motor A,B,C,D,E,F,G,H,I,J,K,L
Masing-masing motor memiliki kriteria, yaitu harga, jarak tempuh per liter, nilai model
Sehingga dalam kasus ini, diasumsikan data awalnya adalah sebagai berikut:

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:
Untuk Kriteria Model:
Baik dilambangkan dengan angka 2
Cukup dilambangkan dengan angka 1
Buruk dilambangkan dengan angka 0

Dim data(11, 3) As Double
data(0, 0) = 15000000
data(0, 1) = 40
data(0, 2) = 2
data(0, 3) = 5
data(1, 0) = 17000000
data(1, 1) = 45
data(1, 2) = 1
data(1, 3) = 8
data(2, 0) = 16000000
data(2, 1) = 40
data(2, 2) = 0
data(2, 3) = 7
data(3, 0) = 20000000
data(3, 1) = 35
data(3, 2) = 2
data(3, 3) = 3
data(4, 0) = 18000000
data(4, 1) = 37.5
data(4, 2) = 1
data(4, 3) = 3
data(5, 0) = 20000000
data(5, 1) = 38
data(5, 2) = 0
data(5, 3) = 10
data(6, 0) = 12000000
data(6, 1) = 45
data(6, 2) = 2
data(6, 3) = 9
data(7, 0) = 10000000
data(7, 1) = 47
data(7, 2) = 1
data(7, 3) = 17
data(8, 0) = 10000000
data(8, 1) = 50
data(8, 2) = 0
data(8, 3) = 18
data(9, 0) = 13000000
data(9, 1) = 33
data(9, 2) = 2
data(9, 3) = 3
data(10, 0) = 14000000
data(10, 1) = 39
data(10, 2) = 1
data(10, 3) = 15
data(11, 0) = 14000000
data(11, 1) = 37.5
data(11, 2) = 0
data(11, 3) = 13

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Pengelompokan untuk masing-masing kriteria
Jumlah pengelompokan bebas tergantung keinginan
Contoh dalam kasus ini:
Kriteria harga hanya dikelompokan menjadi 2 bagian yaitu untuk harga lebih dari sama dengan 15.000.000 dan harga kurang dari 15.000.000
Kriteria jarak tempuh per liter hanya dikelompokan menjadi 2 bagian yaitu untuk jarak tempuh lebih dari sama dengan 40 dan jarak tempuh kurang dari 40
Kriteria model dikelompokan menjadi 3 bagian yaitu untuk baik, cukup, buruk
Kriteria banyak unit terjual hanya dikelompokan menjadi 2 bagian yaitu untuk unit terjual lebih dari 10 dan unit terjual kurang dari sama dengan 10

Dim kelompok(6) As String
kelompok(0) = "Harga lebih dari sama dengan 15.000.000"
kelompok(1) = "Harga kurang dari 15.000.000"
kelompok(2) = "Jarak Tempuh lebih dari sama dengan 40"
kelompok(3) = "Jarak Tempuh Kurang dari 40"
kelompok(4) = "Model Baik"
kelompok(5) = "Model Cukup"
kelompok(6) = "Model Buruk"

2. Tentukan matriks data awal untuk data yang sudah mengalami pengelompokan

Dim dataAwal(11, 3) As String
For i As Integer = 0 To 11
	If data(i, 0) >= 15000000 Then
		dataAwal(i, 0) = kelompok(0)
	Else
		dataAwal(i, 0) = kelompok(1)
	End If

	If data(i, 1) >= 40 Then
		dataAwal(i, 1) = kelompok(2)
	Else
		dataAwal(i, 1) = kelompok(3)
	End If

	If data(i, 2) = 2 Then
		dataAwal(i, 2) = kelompok(4)
	ElseIf data(i, 2) = 1 Then
		dataAwal(i, 2) = kelompok(5)
	ElseIf data(i, 2) = 0 Then
		dataAwal(i, 2) = kelompok(6)
	End If

	If data(i, 3) > 10 Then
		dataAwal(i, 3) = "Lebih dari 10"
		totalUnitTerjualLebihDari10 += 1
	Else
		dataAwal(i, 3) = "Kurang dari sama dengan 10"
		totalUnitTerjualuranghDari10 += 1
	End If
Next

3. hitung jumlah data untuk masing-masing pengelompokan data yang digunakan
Lanjutkan perhitungan jika jumlah datanya lebih dari 0

For j As Integer = 0 To 11
	If dataAwal(j, index) = kelompok(i) AndAlso dataAwal(j, 3) = "Lebih dari 10" AndAlso Not iUsed(index) Then totalLebih += 1
	If dataAwal(j, index) = kelompok(i) AndAlso dataAwal(j, 3) = "Kurang dari sama dengan 10" AndAlso Not iUsed(index) Then totalKurang += 1
Next

4. Hitung nilai entropi untuk masing-masing pengelompokan pada kriteria tersebut
Entropi dihitung dari jumlah ((-Persentase) * Logarima basis 2 dari persentase)) untuk masing-masing pengelompokan data pada hasil akhir, yaitu kriteria banyak unit terjual
Karena kriteria banyak unit terjual hanya dikelompokan menjadi 2 kelompok, maka ada 2 nilai entropi untuk masing-masing kelompok
Nilai entropi akhir adalah jumlah dari 2 nilai entropi tersebut

perhitungan(i, 0) = totalLebih
perhitungan(i, 1) = totalKurang
Dim persentasiLebih As Double = perhitungan(i, 0) / (perhitungan(i, 0) + perhitungan(i, 1))
Dim entropiLebih As Double = (-1 * persentasiLebih) * IIf(persentasiLebih = 0, 0, Math.Log(persentasiLebih, 2))

Dim persentasiKurang As Double = perhitungan(i, 1) / (perhitungan(i, 0) + perhitungan(i, 1))
Dim entropiKurang As Double = (-1 * persentasiKurang) * IIf(persentasiKurang = 0, 0, Math.Log(persentasiKurang, 2))

perhitungan(i, 2) = entropiLebih + entropiKurang

5. Hitung Gain untuk kelompok dalam kriteria tersebut
Gain dihitung dari nilai persentase kriteria terhadap semua data * entropi

Dim persentasi As Double = (perhitungan(i, 0) + perhitungan(i, 1)) / iTotal
perhitungan(i, 3) = persentasi * perhitungan(i, 2)
totalGain += perhitungan(i, 3)

6. Lakukan point 3, 4, 5 untuk setiap kelompok yang berbeda pada kriteria yang sama

i += 1
totalLebih = 0
totalKurang = 0
For j As Integer = 0 To 11
	If dataAwal(j, index) = kelompok(i) AndAlso dataAwal(j, 3) = "Lebih dari 10" AndAlso Not iUsed(index) Then totalLebih += 1
	If dataAwal(j, index) = kelompok(i) AndAlso dataAwal(j, 3) = "Kurang dari sama dengan 10" AndAlso Not iUsed(index) Then totalKurang += 1
Next

If totalLebih + totalKurang > 0 Then
	perhitungan(i, 0) = totalLebih
	perhitungan(i, 1) = totalKurang
	Dim persentasiLebih As Double = perhitungan(i, 0) / (perhitungan(i, 0) + perhitungan(i, 1))
	Dim entropiLebih As Double = (-1 * persentasiLebih) * IIf(persentasiLebih = 0, 0, Math.Log(persentasiLebih, 2))

	Dim persentasiKurang As Double = perhitungan(i, 1) / (perhitungan(i, 0) + perhitungan(i, 1))
	Dim entropiKurang As Double = (-1 * persentasiKurang) * IIf(persentasiKurang = 0, 0, Math.Log(persentasiKurang, 2))

	perhitungan(i, 2) = entropiLebih + entropiKurang

	Dim persentasi As Double = (perhitungan(i, 0) + perhitungan(i, 1)) / iTotal
	perhitungan(i, 3) = persentasi * perhitungan(i, 2)
	totalGain += perhitungan(i, 3)
End If

If i = 5 Then
	i += 1
	totalLebih = 0
	totalKurang = 0
	For j As Integer = 0 To 11
		If dataAwal(j, index) = kelompok(i) AndAlso dataAwal(j, 3) = "Lebih dari 10" AndAlso Not iUsed(index) Then totalLebih += 1
		If dataAwal(j, index) = kelompok(i) AndAlso dataAwal(j, 3) = "Kurang dari sama dengan 10" AndAlso Not iUsed(index) Then totalKurang += 1
	Next

	If totalLebih + totalKurang > 0 Then
		perhitungan(i, 0) = totalLebih
		perhitungan(i, 1) = totalKurang
		Dim persentasiLebih As Double = perhitungan(i, 0) / (perhitungan(i, 0) + perhitungan(i, 1))
		Dim entropiLebih As Double = (-1 * persentasiLebih) * IIf(persentasiLebih = 0, 0, Math.Log(persentasiLebih, 2))

		Dim persentasiKurang As Double = perhitungan(i, 1) / (perhitungan(i, 0) + perhitungan(i, 1))
		Dim entropiKurang As Double = (-1 * persentasiKurang) * IIf(persentasiKurang = 0, 0, Math.Log(persentasiKurang, 2))

		perhitungan(i, 2) = entropiLebih + entropiKurang

		Dim persentasi As Double = (perhitungan(i, 0) + perhitungan(i, 1)) / iTotal
		perhitungan(i, 3) = persentasi * perhitungan(i, 2)
		totalGain += perhitungan(i, 3)
	End If
End If

7. Jumlahkan semua nilai gain pada masing-masing kelompok untuk mendapatkan nilai Gain total untuk kriteria tersebut
Nilai terakhir adalah total perhitungan dari kriteria hasil (banyak unit terjual) – nilai Gain ini

perhitungan(i, 4) = totalUnitTerjualLebihDari10 + totalUnitTerjualuranghDari10 - totalGain

8. Bandingkan semua nilai Gain pada setiap kriteria, ambil nilai Gain yang paling tinggi

If maxGain < perhitungan(i, 4) Then
	maxGain = perhitungan(i, 4)
	iMaxGain = i
End If

9. Catat kesimpulan yang didapat dari perhitungan ini
Kemudian hapus baris data pada matriks data awal untuk data dengan kriteria tersebut
Matriks data awal ini akan digunakan untuk perhitungan selanjutnya

If iMaxGain = 1 Then
	Console.WriteLine(vbCrLf & "Kriteria solusi adalah kriteria Harga")
	iUsed(0) = indexKritera
	indexKritera += 1

	If perhitungan(iMaxGain - 1, 0) = 0 Then
		Console.WriteLine("Hasil Kriteria Harga untuk kelompok " & kelompok(iMaxGain - 1) & " selalu kurang dari sama dengan 10")
		iSt = 1
	ElseIf perhitungan(iMaxGain - 1, 1) = 0 Then
		Console.WriteLine("Hasil Kriteria Harga untuk kelompok " & kelompok(iMaxGain - 1) & " selalu lebih dari 10")
		iSt = 1
	End If

	If perhitungan(iMaxGain, 0) = 0 Then
		Console.WriteLine("Hasil Kriteria Harga untuk kelompok " & kelompok(iMaxGain) & " selalu kurang dari sama dengan 10")
		iSt = 2
	ElseIf perhitungan(iMaxGain, 1) = 0 Then
		Console.WriteLine("Hasil Kriteria Harga untuk kelompok " & kelompok(iMaxGain) & " selalu lebih dari 10")
		iSt = 2
	End If

	If perhitungan(iMaxGain - 1, 0) <> 0 AndAlso perhitungan(iMaxGain - 1, 1) <> 0 Then
		Console.WriteLine("Hasil Kriteria Harga untuk kelompok " & kelompok(iMaxGain - 1) & " akan dihitung pada perhitungan berikutnya")
	ElseIf perhitungan(iMaxGain, 0) <> 0 AndAlso perhitungan(iMaxGain, 1) <> 0 Then
		Console.WriteLine("Hasil Kriteria Harga untuk kelompok " & kelompok(iMaxGain) & " akan dihitung pada perhitungan berikutnya")
	End If

	totalUnitTerjualLebihDari10 = 0
	totalUnitTerjualuranghDari10 = 0
	iTotal = 0
	For i As Integer = 0 To 11
		If iSt = 1 And dataAwal(i, 0) = kelompok(iMaxGain - 1) Then
			dataAwal(i, 0) = ""
			dataAwal(i, 1) = ""
			dataAwal(i, 2) = ""
			dataAwal(i, 3) = ""
		ElseIf iSt = 2 And dataAwal(i, 0) = kelompok(iMaxGain) Then
			dataAwal(i, 0) = ""
			dataAwal(i, 1) = ""
			dataAwal(i, 2) = ""
			dataAwal(i, 3) = ""
		Else
			If dataAwal(i, 3) = "Lebih dari 10" Then
				totalUnitTerjualLebihDari10 += 1
			ElseIf dataAwal(i, 3) = "Kurang dari sama dengan 10" Then
				totalUnitTerjualuranghDari10 += 1
			End If
			iTotal += 1
		End If
	Next

	totalUnitTerjualLebihDari10 = (-1 * Math.Log(totalUnitTerjualLebihDari10 / iTotal, 2)) * (totalUnitTerjualLebihDari10 / iTotal)
	totalUnitTerjualuranghDari10 = (-1 * Math.Log(totalUnitTerjualuranghDari10 / iTotal, 2)) * (totalUnitTerjualuranghDari10 / iTotal)

ElseIf iMaxGain = 3 Then
	. . .
ElseIf iMaxGain = 6 Then
	. . .
End If

10. Lakukan perhitungan sampai ditemukan apabila nilai maksimal dari Gain adalah 0

If maxGain <= 0 Then
	Console.WriteLine(vbCrLf & "Perhitungan telah selesai karena nilai maksimal dari nilai Gain adalah 0")
	Console.WriteLine(vbCrLf & "Kesimpulan: ")
	For i As Integer = 0 To 2
		For j As Integer = 0 To 2
			If j = iUsed(i) - 1 Then
				Console.WriteLine("Kriteria " & j + 1 & " adalah: " & IIf(j = 0, "Harga", IIf(j = 1, "Jarak Tempuh per Liter", IIf(j = 2, "Model", ""))))
			End If
		Next
	Next
	Exit Do
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.