Algoritma AdaBoost

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:

Pelanggan	Umur	Jenis Kelamin	Skor Kepribadian	Hasil
Pelanggan A	44	Laki-laki	3.55	Diterima
Pelanggan B	52	Perempuan	4.71	Diterima
Pelanggan C	60	Perempuan	6.56	Ditolak
Pelanggan D	56	Laki-laki	6.8	Ditolak
Pelanggan E	51	Laki-laki	6.94	Ditolak
Pelanggan F	46	Perempuan	6.52	Ditolak
Pelanggan G	48	Laki-laki	4.25	Diterima
Pelanggan H	58	Perempuan	5.71	Diterima

Contoh data awal adalah sebagai berikut:

1 2 3 4 5 6 7 8 9

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:

Pelanggan	Umur	Jenis Kelamin	Skor Kepribadian
Pelanggan I	47	Perempuan	6.05
Pelanggan J	52	Laki-Laki	5

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

1 2	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

1 2 3 4 5 6 7

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

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)

1	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)

1 2 3

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

1	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

1	If nilaiHasil = 0 Then Continue For

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

1 2	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)

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

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

1 2	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

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

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

1 2 3 4 5 6 7 8

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

1	jumlahData = jumlahData + 1

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

1 2	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

1 2 3 4 5

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)

1	CariNilaiAlpha(contohData, daftarPelajar, daftarPelajarTerbaik)

Memasuki perhitungan pada fungsi CariNilaiAlpha

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

1 2 3 4

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)

1 2	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)

1	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)

1 2 3

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

1	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

1 2 3 4 5

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

1	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)

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

Memasuki perhitungan pada fungsi cariPelajarTerbaik

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

1 2 3 4

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)

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

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

1	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

1 2 3 4

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

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

1 2 3

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

1 2 3

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

1 2 3

epsilon = epsilonTerendah daftarPelajarTerpakai(indeksTerbaik) = 1 Return indeksTerbaik

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

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

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

1	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

1 2	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)

1	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)

1 2	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

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

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

1 2	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

1 2 3 4

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

1 2 3

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

4b7. Hentikan perhitungan jika semua pelajar sudah terpakai

1 2	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)

1	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)

1	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)

1 2	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

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

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

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

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

1 2 3 4 5 6 7

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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