Iterative Dichotomiser 3 (ID3) adalah algoritma decision tree learning
(algoritma pembelajaran pohon keputusan) yang paling dasar. Algoritma ini melakukan pencarian secara menyeluruh (greedy) pada semua kemungkinan pohon keputusan.
Salah satu algoritma induksi pohon keputusan yaitu ID3 (Iterative Dichotomiser 3). ID3 dikembangkan oleh J. Ross Quinlan. Algoritma ID3 dapat diimplementasikan menggunakan fungsi rekursif (fungsi yang memanggil dirinya sendiri). Algoritma ID3 berusaha membangun decision tree (pohon keputusan) secara top-down (dari atas ke bawah) (David, 2004).
Contoh Soal : Kita menggunakan data 10 di bawah ini untuk membentuk suatu pohon keputusan sehingga apabila data baru dapat kita uji menggunkan poho keputusan di bawah ini :
Asal Sekolah (SMA/MA/SMK) NEM(Bahasa, Matematika, B Ing SMA) IPK (Informatika)
| NIM | AsalSekolah | Bhs | Mtk | BIng | IPK |
| 1 | MA | Istimewa9 | Sangat Baik( 7,3) | Baik (5,2) | 3,8 |
| 2 | SMA | Baik5 | Cukup (3,1) | Kurang (0,8) | 3,4 |
| 3 | SMK | cukup | Kurang (1,7) | Cukup (3,1) | 2,5 |
| 4 | MA | Baik | Baik (4,3) | Cukup (3,5) | 3,3 |
| 5 | SMA | cukup | Baik (5,2) | Sangatbaik (6,2) | 3,6 |
| 6 | SMK | kurang | Cukup (2,8) | Kurang (1,1) | 1,9 |
| 7 | SMA | baik | Istimewa (9,3) | Sangatbaik (7,5) | 3,2 |
| 8 | SMK | baik | Cukup (2,5) | Baik (4,6) | 2,6 |
| 9 | MA | cukup | Baik (4,4) | Cukup (2,3) | 2,8 |
| 10 | SMA | baik | Sangatbaik (6,8) | Baik (4,3) | 3,3 |
Keterangan:
Istimewa : 8-10
sangat baik : 6-8
baik : 4-6
cukup :2-4
kurang : 0-2
Memuaskan : 3-4
Mengecewakan: 0
Jawab:
| NIM | AsalSekolah | Bhs | Mtk | BIng | IPK | Kategori | ||
| 1 | MA | Istimewa | Sangat Baik | Baik | 3,8 | Memuaskan | ||
| 2 | SMA | Baik | Cukup | Kurang | 3,4 | Memuaskan | ||
| 3 | SMK | cukup | Kurang | Cukup | 2,5 | Mengecewakan | ||
| 4 | MA | Baik | Baik | Cukup | 3,3 | Memuaskan | ||
| 5 | SMA | cukup | Baik | Sangatbaik | 3,6 | Memuaskan | ||
| 6 | SMK | kurang | Cukup | Kurang | 1,9 | Mengecewakan | ||
| 7 | SMA | baik | Istimewa | Sangatbaik | 3,2 | Memuaskan | ||
| 8 | SMK | baik | Cukup | Baik | 2,6 | Mengecewakan | ||
| 9 | MA | cukup | Baik | Cukup | 2,8 | Mengecewakan | ||
| 10 | SMA | baik | Sangat Baik | Baik | 3,3 | Memuaskan | ||
| Memuaskan | 6 | |||||||
| Mengecewakan | 4 | |||||||
| Total | 10 | |||||||
Rumus Entropi
Mencari Entropi total :
Entopi
Entopi 0,970950594
Hitung entropi tiap nilai-nilainya kemudian hitung gain per atributnya dengan rumus=
Sehingga didapatkan hasil:
| node | atribut | nilai | frekuensi | Frek. sum | Frek. (puas) | Frek. (kecewa) | entropi | gain |
| 1 | Asal Sekolah | MA | 3 | 10 | 2 | 1 | 0,918295834 | 0,695461844 |
| SMA | 4 | 4 | 0 | 0 | ||||
| SMK | 3 | 0 | 3 | 0 | ||||
| Bhs | Istimewa | 1 | 10 | 1 | 0 | 0 | 0,334497797 | |
| Baik | 5 | 4 | 1 | 0,721928095 | ||||
| cukup | 3 | 1 | 2 | 0,918295834 | ||||
| kurang | 1 | 0 | 1 | 0 | ||||
| Mtk | Istimewa | 1 | 10 | 1 | 0 | 0 | 0,419973094 | |
| Sangat Baik | 2 | 2 | 0 | 0 | ||||
| Baik | 3 | 2 | 1 | 0,918295834 | ||||
| Cukup | 3 | 1 | 2 | 0,918295834 | ||||
| Kurang | 1 | 0 | 1 | 0 | ||||
| Bing | Sangatbaik | 2 | 10 | 2 | 0 | 0 | 0,219973094 | |
| Baik | 3 | 2 | 1 | 0,918295834 | ||||
| Cukup | 3 | 1 | 2 | 0,918295834 | ||||
| Kurang | 2 | 1 | 1 | 1 |
Karena nilai gain terbesar adalah Gain (Asal Sekolah), maka atribut “Asal Sekolah” menjadi node akar (root node).
Kemudian pada “Asal Sekolah” MA, memiliki 3 kasus dan frekuensi kedua kategori (puas dan kecewa) tidak bernilai 0. Dengan demikian “Asal Sekolah” MA menjadi node.
Sedangkan pada “Asal Sekolah” SMA dan SMK keduanya memiliki nilai 0 pada salah satu frekuensi kategori (puas dan kecewa). Dengan demikian “Asal Sekolah” SMA dan SMK menjadi daun atau leaf.
Sehingga pohon keputusan node 1 menjadi:
Kemudian dilanjutkan dengan perhitungan pada node 1.1
Pilih nilai atribut yang berasal dari “Asal Sekolah” MA. Setelah didapatkan kemudian menghitung kembali entropi tiap nilai atribut tersebut.
Kemudian menghitung kembali Gain tiap atribut dengan menggunakan entropi “Asal Sekolah” yaitu : 0,695461844
Sehingga didapatkan hasil:
| node | atribut | nilai | frekuensi | frek sum | Frek. (puas) | Frek. (kecewa) | entropi | gain |
| 1.1 | Bhs | Istimewa | 1 | 3 | 1 | 0 | 0 | 0,918295834 |
| Baik | 1 | 1 | 0 | 0 | ||||
| cukup | 1 | 0 | 1 | 0 | ||||
| Mtk | Sangat Baik | 1 | 3 | 1 | 0 | 0 | 0,251629167 | |
| Baik | 2 | 1 | 1 | 1 | ||||
| Bing | Baik | 1 | 3 | 1 | 0 | 0 | 0,251629167 | |
| Cukup | 2 | 1 | 1 | 1 |
Dari data diatas di dapatkan gain terbesar yaitu Bhs. Sehingga atribut “Bhs” menjadi node 1.1
Kemudian pada atribut “Bhs” memiliki 3 nilai yaitu Istimewa, baik, dan Cukup. Dimana ketiganya memiliki nilai 0 pada salah satu frekuensi kategori (puas dan kecewa). Dengan demikian “Bhs” Istimewa, Baik, dan Cukup menjadi daun atau leaf semua.
Sehingga hasil hasil akhir pohon keputusan menjadi:
DATA UJI
Misal di sajikan data berikut:
Kita mempunyai 10 data baru yang dapat kita gunakan sebagai data uji
| NIM | Nama | Asal Sekolah | Bhs | Mtk | B.ing | IPK |
| 1 | Lila | MA | 9 | 8 | 8 | 3,3 |
| 2 | April | MA | 9 | 5 | 7 | 2,8 |
| 3 | Seto | SMA | 6 | 8 | 7.5 | 2,8 |
| 4 | Cucum | MA | 5 | 9 | 8 | 2,9 |
| 5 | Indri | SMA | 4 | 7.25 | 8 | 2,4 |
| 6 | Hanif | SMA | 8.6 | 9 | 9 | 3,6 |
| 7 | Aziz | SMA | 9 | 7.25 | 6 | 3,0 |
| 8 | Ilham | MA | 8.4 | 9 | 7 | 3,2 |
| 9 | Iqbal | SMA | 4 | 9 | 8.6 | 2,6 |
| 10 | Alvin | SMK | 4 | 6 | 8 | 2,4 |
Langkah pertama beri keterangan kategori berdasarkan ketentuan awal, sehingga menjadi:
| NIM | Nama | Asal Sekolah | Bhs | Mtk | B.Ing | IPK | Kategori | |||
| 1 | Lila | MA | 9 | Istimewa | 8 | Sangat Baik | 8 | Sangat Baik | 3,3 | Memuaskan |
| 2 | April | MA | 9 | Istimewa | 5 | Baik | 7 | Sangat Baik | 2,8 | Mengecewakan |
| 3 | Seto | SMA | 6 | Baik | 8 | Sangat Baik | 7.5 | Istimewa | 2,8 | Mengecewakan |
| 4 | Cucum | MA | 5 | Baik | 9 | Istimewa | 8 | Sangat Baik | 2,9 | Mengecewakan |
| 5 | Indri | SMA | 4 | Cukup | 7.25 | Istimewa | 8 | Sangat Baik | 2,4 | Mengecewakan |
| 6 | Hanif | SMA | 8.6 | Istimewa | 9 | Istimewa | 9 | Istimewa | 3,6 | Memuaskan |
| 7 | Aziz | SMA | 9 | Istimewa | 7.25 | Istimewa | 6 | Baik | 3,0 | Mengecewakan |
| 8 | Ilham | MA | 8.4 | Istimewa | 9 | Istimewa | 7 | Sangat Baik | 3,2 | Memuaskan |
| 9 | Iqbal | SMA | 4 | Cukup | 9 | Istimewa | 8.6 | Istimewa | 2,6 | Mengecewakan |
| 10 | Alvin | SMK | 4 | Cukup | 6 | Baik | 8 | Sangat Baik | 2,4 | Mengecewakan |
Kemudian cek apakah data sudah akurat sesuai dengan pohon tree di atas, hasilnya adalah :
| NIM | Nama | Asal Sekolah | Bhs | Mtk | B.Ing | IPK | Kategori | Hasil | |||
| 1 | Lila | MA | 9 | Istimewa | 8 | Sangat Baik | 8 | Sangat Baik | 3,3 | Memuaskan | Akurat |
| 2 | April | MA | 9 | Istimewa | 5 | Baik | 7 | Sangat Baik | 2,8 | Mengecewakan | tidak akurat |
| 3 | Seto | SMA | 6 | Baik | 8 | Sangat Baik | 7.5 | Istimewa | 2,8 | Mengecewakan | tidak akurat |
| 4 | Cucum | MA | 5 | Baik | 9 | Istimewa | 8 | Sangat Baik | 2,9 | Mengecewakan | tidak akurat |
| 5 | Indri | SMA | 4 | Cukup | 7.25 | Istimewa | 8 | Sangat Baik | 2,4 | Mengecewakan | tidak akurat |
| 6 | Hanif | SMA | 8.6 | Istimewa | 9 | Istimewa | 9 | Istimewa | 3,6 | Memuaskan | akurat |
| 7 | Aziz | SMA | 9 | Istimewa | 7.25 | Istimewa | 6 | Baik | 3,0 | Mengecewakan | tidak akurat |
| 8 | Ilham | MA | 8.4 | Istimewa | 9 | Istimewa | 7 | Sangat Baik | 3,2 | Memuaskan | Akurat |
| 9 | Iqbal | SMA | 4 | Cukup | 9 | Istimewa | 8.6 | Istimewa | 2,6 | Mengecewakan | tidak akurat |
| 10 | Alvin | SMK | 4 | Cukup | 6 | Baik | 8 | Sangat Baik | 2,4 | Mengecewakan | Akurat |
Sumber :
Click to access 100742-ID-algoritma-iterative-dichotomiser-3-id3-u.pdf
Data Mining 2020 