Algoritma AdaBoost (Adaptive Boosting) 20

Algoritma Adaptive Boosting adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai penentuan penerimaan pengajuan kredit sepeda motor baru berdasarkan kelompok data yang sudah ada.

Diasumsikan ada 8 data pelanggan yang sudah diketahui datanya, yaitu Pelanggan A,B,C,D,E,F,G,H
Masing-masing pelanggan memiliki kriteria, yaitu umur, jenis kelamin, skor kepribadian, dan memiliki nilai hasil yaitu Diterima / Ditolak
Diasumsikan 8 data tersebut adalah sebagai berikut:

Contoh data awal adalah sebagai berikut:

Dim data(9)() As String
data(0) = New String() {44, "Laki-laki", 3.55, "Diterima"}
data(1) = New String() {52, "Perempuan", 4.71, "Diterima"}
data(2) = New String() {60, "Perempuan", 6.56, "Ditolak"}
data(3) = New String() {56, "Laki-laki", 6.8, "Ditolak"}
data(4) = New String() {51, "Laki-laki", 6.94, "Ditolak"}
data(5) = New String() {46, "Perempuan", 6.52, "Ditolak"}
data(6) = New String() {48, "Laki-laki", 4.25, "Diterima"}
data(7) = New String() {58, "Perempuan", 5.71, "Diterima"}

Selanjutnya ada 2 orang pelanggan baru yang mengajukan kredit sepeda motor
Maka tentukan pelanggan ini nantinya akan termasuk dalam kelompok Diterima / Ditolak
Diasumsikan data awalnya adalah sebagai berikut:

Contoh data yang baru adalah sebagai berikut:
Untuk kriteria Nilai Hasil:
Karena belum diketahui nilai hasilnya, maka semua inputan data adalah kosong

data(8) = New String() {47, "Perempuan", 6.05, ""}
data(9) = New String() {52, "Laki-laki", 5, ""}

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
Kriteria hasil dikelompokan menjadi 2 bagian yaitu untuk kelompok Diterima dan Ditolak

Dim kriteria() As String = {"Umur", "JK", "Skor", "Hasil"}

Dim kelompokKriteria(kriteria.Length - 1)() As String
kelompokKriteria(0) = New String() {"Dibawah 40", "41 s/d 50", "Diatas 50"}
kelompokKriteria(1) = New String() {"Laki-laki", "Perempuan"}
kelompokKriteria(2) = New String() {"Dibawah 4", "4 s/d 5", "5 s/d 6", "Diatas 6"}
kelompokKriteria(3) = New String() {"Ditolak", "Diterima"}

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

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

For i = 0 To data.Length - 1
	For j = 0 To data(i).Length - 1
		Dim v As Integer = -1

		For k = 0 To kelompokKriteria(j).Length - 1
			If j = 0 Then
				If data(i)(j) < 40 Then
					v = 0
				ElseIf data(i)(j) < 50 Then
					v = 1
				ElseIf data(i)(j) >= 50 Then
					v = 2
				End If

			ElseIf j = 1 Then
				If data(i)(j) = kelompokKriteria(j)(k) Then
					v = k
				End If

			ElseIf j = 2 Then
				If data(i)(j) < 4 Then
					v = 0
				ElseIf data(i)(j) < 5 Then
					v = 1
				ElseIf data(i)(j) < 6 Then
					v = 2
				ElseIf data(i)(j) >= 6 Then
					v = 3
				End If

			ElseIf j = 3 Then
				If data(i)(j) = kelompokKriteria(j)(k) Then
					v = k
					If v = 0 Then v = -1
				End If
			End If
		Next k

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

3. Tentukan pelajar-pelajar yang didapatkan dari contoh data
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan dibawah ini (poin 3a – 3b)

Dim daftarPelajar As List(Of Pelajar) = TentukanPelajar(kelompokKriteria, contohData)

Memasuki perhitungan pada fungsi TentukanPelajar

* Tentukan pelajar yang memenuhi kriteria (poin 3a)

3a. Lakukan perhitungan pada masing-masing kelompok kriteria yang ada (poin 3a1 – 3a3)

For k = 0 To kelompokKriteria.Length - 2
	For n = 0 To kelompokKriteria(k).Length - 1
	. . .

3a1. Tentukan nilai untuk masing-masing kelompok kriteria yang ada
Jika fungsi ini mengembalikan nilai 0, maka nilai tingkat kesalahan untuk kelompok kriteria tersebut adalah >= 0.5
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim nilaiHasil As Integer = hitungKemungkinanBesar(k, n, data)

3a2. Jika nilai hasil adalah 0, maka kelompok kriteria tersebut tidak memiliki nilai,
maka lewati kelompok kriteria ini dan lanjutkan ke kriteria berikutnya

If nilaiHasil = 0 Then Continue For

3a3. Masukkan nilai hasil yang didapatkan ke dalam daftar pelajar

Dim pelajar As New Pelajar(k, n, nilaiHasil, -1.0, -1.0, -1.0)
hasil.Add(pelajar)

* Hitung nilai tingkat kesalahan masing-masing pelajar yang telah ditemukan (poin 3b)

3b. Lakukan perulangan pada masing-masing pelajar yang ditemukan (poin 3b1 – 3b2)

For i = 0 To hasil.Count - 1
. . .

3b1. Lakukan perhitungan pada masing-masing data pelajar (poin 3b1a – 3b1c)

For k = 0 To data.Length - 1
. . .

3b1a. Jika Jika aturan pelajar tidak berlaku pada data yang sedang dihitung, maka lanjutkan ke data berikutnya
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

If CekAturanPelajar(hasil(i), data(k)) = False Then Continue For

* Gunakan fungsi ini untuk menentukan apakah aturan pelajar dapat diterapkan pada data

Private Function CekAturanPelajar(ByVal Pelajar As Pelajar, ByVal data() As Integer) As Boolean
	Dim ti As Integer = Pelajar.kriteria
	If data(ti) = Pelajar.nilaiKriteria Then
		Return True
	Else
		Return False
	End If
End Function

3b1b. Hitung jumlah data yang telah dihitung

jumlahData = jumlahData + 1

3b1c. Jika nilai hasil perhitungan tidak sama dengan nilai hasil pada data awal,
Catat jumlah ketidakcocokan antara kedua nilai hasil tersebut

Dim act As Integer = data(k)(data(k).Length - 1)
If hasil(i).nilaiHasil <> act Then jumlahDataSalah = jumlahDataSalah + 1

3b2. Hitung tingkat kesalahan dengan membagi jumlah ketidakcocokan data dengan jumlah data yang dihitung

If jumlahData = 0 Then
	hasil(i).tingkatKesalahan = 0.0
Else
	hasil(i).tingkatKesalahan = (jumlahDataSalah * 1.0) / jumlahData
End If

4. Tentukan nilai alpha dari masing-masing pelajar
Alpha adalah tingkat kepercayaan dari para pelajar sebelum digunakan dalam perhitungan data yang baru
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan dibawah ini (poin 4a – 4c)

CariNilaiAlpha(contohData, daftarPelajar, daftarPelajarTerbaik)

Memasuki perhitungan pada fungsi CariNilaiAlpha

4a. Inisialisasi bobot dengan nilai yang sama (1 / n) untuk semua (n) data

Dim bobot(data.Length - 1) As Double
For i = 0 To bobot.Length - 1
	bobot(i) = 1.0 / bobot.Length
Next i

4b. Lakukan perulangan sampai kondisi terpenuhi (poin 4b1 – 4b7)

Do While selesai = False
. . .

4b1. Hitung bobot nilai tingkat kesalahan untuk masing-masing pelajar
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4b1a)

UpdateEpsilons(daftarPelajar, data, bobot)

Memasuki perhitungan pada fungsi UpdateEpsilons

* Update nilai epsilon dilakukan dengan cara menjumlahkan bobot nilai tingkat kesalahan

4b1a. Lakukan perulangan pada masing-masing data setiap pelajar yang ada (poin 4b1a1 – 4b1a3)

For i = 0 To daftarPelajar.Count - 1
	For k = 0 To data.Length - 1
	. . .

4b1a1. Jika aturan pelajar tidak berlaku pada data yang sedang dihitung, maka lanjutkan ke data berikutnya
Penjelasan tentang fungsi ini sudah dijelaskan pada penjelasan diatas

If CekAturanPelajar(daftarPelajar(i), data(k)) = False Then Continue For

4b1a2. Jika nilai hasil data awal tidak sama dengan nilai hasil perhitungan pelajar tersebut,
maka tambahkan bobot data tersebut ke dalam nilai epsilon

Dim nilaiSebenarnya As Integer = data(k)(data(k).Length - 1)    'Nilai hasil dari matriks data
Dim nilaiHasilPelajar As Integer = daftarPelajar(i).nilaiHasil  'Nilai hasil dari pelajar
If nilaiSebenarnya <> nilaiHasilPelajar Then
	epsilon = epsilon + bobot(k)
End If

4b1a3. Masukkan nilai epsilon yang telah ditemukan ke dalam nilai epsilon masing-masing pelajar

daftarPelajar(i).epsilon = epsilon

4b2. Cari indeks pelajar terbaik dan nilai epsilon nya
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4b2a – 4b2e)

Dim indeksTerbaik As Integer = cariPelajarTerbaik(daftarPelajar, epsilonT, daftarPelajarTerpakai)

Memasuki perhitungan pada fungsi cariPelajarTerbaik

4b2a. Pastikan paling sedikit ada 1 pelajar yang masih belum terpakai

Dim x As Integer = Array.IndexOf(daftarPelajarTerpakai, 0)
If x < 0 Then
	Throw New Exception("Pada fungsi CariPelajarTerbaik, tidak ditemukan pelajar yang belum terpakai")
End If

4b2b. Lakukan perhitungan pada masing-masing pelajar yang ada (poin 4b2b1 – 4b2b2)

For i = 0 To daftarPelajar.Count - 1
. . .

4b2b1. Jika pelajar ini sudah terpakai, maka lanjutkan perhitungan ke pelajar berikutnya

If daftarPelajarTerpakai(i) = 1 Then Continue For

4b2b2. Jika nilai epsilon pelajar ini lebih rendah dari nilai epsilon terendah,
maka ambil indeks pelajar ini sebagai indeks pelajar terbaik

If daftarPelajar(i).epsilon < epsilonTerendah Then
	epsilonTerendah = daftarPelajar(i).epsilon
	indeksTerbaik = i
End If

4b2c. Tampilkan pesan kesalahan apabila nilai epsilon kurang dari 0

If epsilonTerendah < 0.0 Then
	Throw New Exception("Pada fungsi CariPelajarTerbaik, nilai epsilon tidak boleh negatif")
End If

4b2d. Tampilkan pesan kesalahan apabila tidak ada pelajar yang ditemukan

If indeksTerbaik = -1 Then
	Throw New Exception("Pada fungsi CariPelajarTerbaik, pelajar terbaik tidak ditemukan")
End If

4b2e. Lakukan update nilai epsilon dan beri tanda pada pelajar terbaik bahwa pelajar tersebut sudah terpakai

epsilon = epsilonTerendah
daftarPelajarTerpakai(indeksTerbaik) = 1
Return indeksTerbaik

4b3. Jika bobot nilai tingkat kesalahan mendekati 0.5, maka tidak perlu melanjutkan perhitungan

If Math.Abs(0.5 - epsilonT) <= 0.00001 Then Exit Do

4b4. Tambahkan pelajar dengan indeks terbaik ke dalam daftar pelajar terbaik

daftarPelajarTerbaik.Add(indeksTerbaik)

4b5. Hitung nilai alpha pada iterasi ke t
Nilai alphaT akan semakin tinggi apabila nilai epsilonT semakin rendah
Kemudian masukkan nilai alpha tersebut ke dalam daftar pelajar dengan indeks terbaik

Dim alphaT As Double = 0.5 * Math.Log((1.0 - epsilonT) / epsilonT)
daftarPelajar(indeksTerbaik).alpha = alphaT

4b6. Lakukan update pada data yang cocok dengan aturan pelajar yang memiliki indeks terbaik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4b6a – 4b6c)

UpdateBobot(bobot, data, daftarPelajar, alphaT, indeksTerbaik)

Memasuki perhitungan pada fungsi UpdateBobot

* nilai bobot yang baru dihitung dengan rumus:
bobot baru = bobot lama * konstanta e dipangkatkan (-alpha * nilai hasil data sebenarnya * nilai hasil pelajar)

4b6a. Lakukan perhitungan pada masing-masing bobot data (poin 4b6a1 – 4b6a2)

For i = 0 To bobot.Length - 1
. . .

4b6a1. Jika aturan pelajar tidak berlaku pada data yang sedang dihitung, maka lanjutkan ke data berikutnya
Penjelasan tentang fungsi ini sudah dijelaskan pada penjelasan diatas

If CekAturanPelajar(daftarPelajar(indeksTerbaik), data(i)) = False Then Continue For

4b6a2. Hitung nilai bobot sementara yang baru menggunakan rumus yang sudah dijelaskan sebelumnya

Dim nilaiSebenarnya As Integer = data(i)(data(0).Length - 1) 'bernilai -1 atau +1
bobot(i) = bobot(i) * Math.Exp(-alphaT * nilaiSebenarnya * daftarPelajar(indeksTerbaik).nilaiHasil)

4b6b. Jumlahkan semua nilai bobot baru yang telah dihitung sebelumnya

Dim Z As Double = 0.0
For i = 0 To bobot.Length - 1
	Z = Z + bobot(i)
Next i

4b6c. Lakukan normalisasi bobot dengan cara membagi masing-masing bobot dengan jumlah bobotnya

For i = 0 To bobot.Length - 1
	bobot(i) = bobot(i) / Z
Next i

4b7. Hentikan perhitungan jika semua pelajar sudah terpakai

t = t + 1
If t = daftarPelajar.Count Then selesai = True

4c. Urutkan indeks pelajar menjadi 0 sampai dengan 5 agar nilai pengembalian mudah dibaca (tidak harus dilakukan)

daftarPelajarTerbaik.Sort()

5. Tentukan pengelompokan data untuk masing-masing data baru
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan dibawah ini (poin 5a – 5b)

Dim Y As Integer = Pengelompokan(dataBaru(i), daftarPelajar, daftarPelajarTerbaik)

Memasuki perhitungan pada fungsi Pengelompokan

5a. Lakukan perhitungan pada setiap pelajar terbaik yang ada (poin 5a1 – 5a2)

For t = 0 To daftarPelajarTerbaik.Count - 1
. . .

5a1. Jika aturan pelajar ini tidak berlaku pada data, maka lanjutkan perhitungan ke pelajar berikutnya karena pelajar ini tidak dapat melakukan voting
Penjelasan tentang fungsi ini sudah dijelaskan pada penjelasan diatas

If CekAturanPelajar(daftarPelajar(idx), data) = False Then Continue For

5a2. Jumlahkan semua nilai vote untuk semua pelajar yang memenuhi kriteria data baru

Dim vote As Double = daftarPelajar(idx).nilaiHasil * daftarPelajar(idx).alpha
jumlahVote += vote

5b. Lakukan pengelompokan data berdasarkan nilai vote positif dan negatif

If jumlahVote > 0.0 Then
	Return 1
ElseIf jumlahVote < 0.0 Then
	Return -1
Else
	Return 0
End If

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Pelajar untuk menampung semua data pelajar, yaitu kriteria, nilai kriteria, epsilon, alpha, dll. Deklarasi Class Pelajar adalah sebagai berikut:

Public Class Pelajar
    Public kriteria As Integer          'Kriteria: Umur, Jenis kelamin, Skor Kepribadian
    Public nilaiKriteria As Integer     'Nilai Kriteria: 50, ..., Laki-laki, ..., 5.0, ...
    Public nilaiHasil As Integer        'Nilai hasil: -1 (Ditolak) atau +1 (Diterima)
    Public tingkatKesalahan As Double   'Nilai tingkat kesalahan pelajar dalam menganalisa data
    Public epsilon As Double            'Nilai bobot tingkat kesalahan (karena beda data awal beda bobotnya)
    Public alpha As Double              'Nilai penentu bobot pelajar

    Public Sub New(ByVal kriteria As Integer, ByVal nilaiKriteria As Integer, ByVal nilaiHasil As Integer, ByVal tingkatKesalahan As Double, ByVal epsilon As Double, ByVal alpha As Double)
        Me.kriteria = kriteria
        Me.nilaiKriteria = nilaiKriteria
        Me.nilaiHasil = nilaiHasil
        Me.tingkatKesalahan = tingkatKesalahan
        Me.epsilon = epsilon
        Me.alpha = alpha
    End Sub
End Class

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.