Algoritma ID3 (Iterative Dichotomiser 3)

Algoritma ID3 (Iterative Dichotomiser 3) adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan kriteria pembeli dalam pembelian Sepeda Motor dengan kriteria tertentu.

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

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

Dim data(,) As String = New String(,) { _
	{10000000, "baik", 39, 125, 5}, _
	{9000000, "baik", 40, 110, 8}, _
	{13000000, "baik", 40, 125, 12}, _
	{16000000, "baik", 38, 125, 13}, _
	{16500000, "cukup", 45, 125, 12}, _
	{20000000, "cukup", 43, 110, 3}, _
	{12000000, "cukup", 47, 110, 13}, _
	{9500000, "buruk", 35, 125, 7}, _
	{9700000, "cukup", 42, 125, 18}, _
	{18000000, "buruk", 47, 125, 12}, _
	{10000000, "buruk", 45, 125, 15}, _
	{14000000, "buruk", 37, 110, 13}, _
	{15000000, "baik", 46, 125, 15}, _
	{19000000, "buruk", 40, 110, 9} _
	}

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 3 bagian yaitu untuk harga <= 10.000.000, 10.000.001 s/d 15.000.000, > 15.000.000
Kriteria model dikelompokan menjadi 3 bagian yaitu untuk baik, cukup, buruk
Kriteria jarak tempuh per liter hanya dikelompokan menjadi 2 bagian yaitu untuk jarak tempuh <= 40 dan > 40
Kriteria cc hanya dikelompokan menjadi 2 bagian yaitu untuk cc 110 dan 125

Dim KriteriaHarga As New Atribut("harga", New String() {"<=10jt", "10-15jt", ">15jt"})
Dim KriteriaModel As New Atribut("model", New String() {"baik", "cukup", "buruk"})
Dim KriteriaJarakTempuh As New Atribut("jaraktempuh", New String() {"<=40", ">40"})
Dim KriteriaCC As New Atribut("cc", New String() {"110", "125"})

Dim DaftarAtribut As Atribut() = New Atribut() {KriteriaHarga, KriteriaModel, KriteriaJarakTempuh, KriteriaCC}

2. Tentukan matriks data awal untuk data yang sudah mengalami pengelompokan
Kriteria banyak unit terjual hanya dikelompokan menjadi 2 bagian yaitu
“False” untuk unit yang tidak laris terjual, yaitu unit yang terjual kurang dari sama dengan 10 unit
“True” untuk unit terjual laris terjual, yaitu unit yang terjual lebih dari 10 unit

Dim dataAwal As New DataTable("dataAwal")
Dim column As DataColumn = dataAwal.Columns.Add("harga")
column.DataType = GetType(String)

column = dataAwal.Columns.Add("model")
column.DataType = GetType(String)

column = dataAwal.Columns.Add("jaraktempuh")
column.DataType = GetType(String)

column = dataAwal.Columns.Add("cc")
column.DataType = GetType(String)

column = dataAwal.Columns.Add("laristerjual")
column.DataType = GetType(Boolean)

For i As Integer = 0 To 13
	dataAwal.Rows.Add(New Object() {
		IIf(data(i, 0) <= 10000000, "<=10jt", IIf(data(i, 0) <= 15000000, "10-15jt", ">15jt")), _
		data(i, 1), _
		IIf(data(i, 2) <= 40, "<=40", ">40"), _
		data(i, 3), _
		IIf(data(i, 4) <= 10, False, True)})
Next

3. Tentukan proses perhitungan menggunakan algoritma ini
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3a – 3g)

Dim id3 As New AlgorimaID3()
Dim akar As TreeNode = id3.mountTree(dataAwal, "laristerjual", DaftarAtribut)

Memasuki perhitungan utama pada fungsi mountTree

3a. Lakukan perulangan pada semua data awal
Apabila semua data tersebut memiliki nilai hasil Laris (positif), maka nilai jawaban telah ditemukan,
yaitu tidak ada satupun kriteria yang menentukan kriteria hasil

Dim st As Boolean = True
For Each row As DataRow In mDataAwal.Rows
	If CBool(row(targetAtribut)) = False Then
		st = False
		Exit For
	End If
Next
If st Then Return New TreeNode(New Atribut(True))

3b. Lakukan perulangan pada semua data awal
Apabila semua data tersebut memiliki nilai hasil Tidak Laris (negatif), maka nilai jawaban telah ditemukan
yaitu tidak ada satupun kriteria yang menentukan kriteria hasil

st = True
For Each row As DataRow In mDataAwal.Rows
	If CBool(row(targetAtribut)) = True Then
		st = False
		Exit For
	End If
Next
If st Then Return New TreeNode(New Atribut(False))

3c. Catat jumlah data awal dan target atribut atau atribut pada kriteria hasil
Pencatatan ini hanya untuk memudahkan perhitungan saja.

If DaftarAtribut.Length = 0 Then
	Return New TreeNode(New Atribut(cariNilaiDenganKemunculanTerbanyak(mDataAwal, targetAtribut)))
End If

mTotal = mDataAwal.Rows.Count
mTargetAtribut = targetAtribut

3d. Hitung banyak data yang menghasilkan nilai Ya (positif)

mTotalPositif = 0
For Each aRow As DataRow In mDataAwal.Rows
	If CBool(aRow(mTargetAtribut)) = True Then
		mTotalPositif += 1
	End If
Next

3e. Lakukan perhitungan nilai entropi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3e1 – 3e5)

mTotalEntropi = hitungEntropi(mTotalPositif, mTotal - mTotalPositif)

* Gunakan fungsi ini untuk menghitung nilai entropi
yaitu dengan rumus: (-p+ * log2(p+)) + (-p- * log2(p-))
p+ adalah persentasi dari nilai positif
p- adalah persentasi dari nilai negatif

3e1. Hitung persentase nilai positif terhadap nilai total

Dim rasioPositif As Double = CDbl(positif) / total

3e2. Hitung persentase nilai negatif terhadap nilai total

Dim rasioNegatif As Double = CDbl(negatif) / total

3e3. Hitung (-p+ * log2(p+))

If rasioPositif <> 0 Then
	rasioPositif = -(rasioPositif) * Math.Log(rasioPositif, 2)
End If

3e4. Hitung (-p- * log2(p-))

If rasioNegatif <> 0 Then
	rasioNegatif = -(rasioNegatif) * Math.Log(rasioNegatif, 2)
End If

3e5. Jumlahkan kedua nilai yang sudah didapatkan sebelumnya

Dim hasil As Double = rasioPositif + rasioNegatif

3f. Cari atribut dengan nilai Gain tertinggi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3f1 – 3f2)

Dim maksGain As Double = 0.0
Dim AtributTerbaik As Atribut = Nothing

For Each Atribut As Atribut In DaftarAtribut
	Dim aux As Double = HitungGain(mDataAwal, Atribut)
	If aux > maksGain Then
		maksGain = aux
		AtributTerbaik = Atribut
	End If
Next

* Gunakan fungsi ini untuk menghitung nilai Gain dalam sebuah atribut

3f1. Lakukan perulangan pada masing-masing nilai atribut

3f1a. Pada nilai atribut yang terpilih,
Catat jumlah nilai Laris (positif) untuk data dengan kriteria hasil Laris dan Tidak Laris (negatif) untuk data dengan kriteria hasil Tidak Laris

Dim Positif As Integer = 0, negatif As Integer = 0
For Each aRow As DataRow In dataAwal.Rows
	If (DirectCast(aRow(Atribut.NamaAtribut), String) = nilai(i)) Then
		If CBool(aRow(mTargetAtribut)) = True Then
			Positif += 1
		Else
			negatif += 1
		End If
	End If
Next

3f1b. Kemudian hitung entropi menggunakan nilai positif dan negatif yang telah dicari sebelumnya

Dim entropi As Double = hitungEntropi(Positif, negatif)

3f1c. Hitung nilai total Gain sementara,
Yaitu dengan rumus total = -(positif + negatif) / jumlah data * entropi

total += -CDbl(Positif + negatif) / mTotal * entropi

3f2. Hitung nilai Gain akhir dengan rumus nilai entropi pada semua nilai atribut + total nilai gain sementara yang sudah dicari sebelumnya

Return mTotalEntropi + total

3g. Lakukan perulangan pada semua nilai yang terdapat dalam atribut terbaik

3g1. Pada nilai atribut terbaik yang sedang terpilih,
Cari semua data yang mengandung nilai tersebut

aDataAwal.Rows.Clear()

Dim rows As DataRow() = mDataAwal.[Select]((Convert.ToString((AtributTerbaik.NamaAtribut & Convert.ToString(" = ")) + "'") & nilaiAtributTerbaik) + "'")

For Each row As DataRow In rows
	aDataAwal.Rows.Add(row.ItemArray)
Next

3g2. Catat semua atribut selain atribut terbaik

Dim aDaftarAtribut As New ArrayList(DaftarAtribut.Length - 1)
For i As Integer = 0 To DaftarAtribut.Length - 1
	If DaftarAtribut(i).NamaAtribut <> AtributTerbaik.NamaAtribut Then
		aDaftarAtribut.Add(DaftarAtribut(i))
	End If
Next

3g3. Jika tidak ada data dengan nilai atribut terbaik yang sedang terpilih
maka cari nilai kemunculan terbanyak pada semua data awal
Selain itu, ulangi proses poin 3a – 3g untuk sisa atribut selain atribut terpilih
dan tambahkan atribut ini sebagai cabang atribut dari atribut terbaik sebelumnya

If aDataAwal.Rows.Count = 0 Then
	Return New TreeNode(New Atribut(cariNilaiDenganKemunculanTerbanyak(aDataAwal, targetAtribut)))
Else
	Dim dc3 As New AlgorimaID3()
	Dim anak As TreeNode = dc3.mountTree(aDataAwal, targetAtribut, DirectCast(aDaftarAtribut.ToArray(GetType(Atribut)), Atribut()))
	akar.TambahCabangAtribut(anak, nilaiAtributTerbaik)
End If

* Gunakan fungsi ini untuk menambahkan titik anak pada titik akar

Public Sub TambahCabangAtribut(anak As TreeNode, nilaiAtribut As String)
	Dim indeks As Integer = mAtributCabang.indeksNilaiAtribut(nilaiAtribut)
	mAnakCabang(indeks) = anak
End Sub

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.