ALGORITMA DECISION TREE
(ID3)
1. SURYA PUJI SANTOSO
2. LUCKY NURFAIZ
3. PRASTIAJENG HARTININGRUM
4. BARDA BASOFI RAHARJA
APA ITU DECISION TREE ?
• Decision Tree adalah sebuah struktur pohon, dimana setiap node pohon
merepresentasikan atribut yang telah diuji, setiap cabang merupakan suatu
pembagian hasil uji, dan node daun (leaf) merepresentasikan kelompok kelas
tertentu.
• Level node teratas dari sebuah Decision Tree adalah node akar (root) yang
biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu
kelas tertentu.
APA ITU ALGORITMA ITERATIVE
DICHOTOMISER 3 (ID3) ?
• Iterative Dichotomiser 3 (ID3) merupakan sebuah metode yang digunakan
untuk membuat pohon keputusan yang telah dikembangkan oleh J. Ross
Quinlan sejak tahun 1986.
• Algoritma pada metode ini menggunakan konsep dari entropy informasi.
Algoritma ini melakukan pencarian secara rakus/menyeluruh (greedy) pada
semua kemungkinan pohon keputusan.
STEP – STEP ALGORITMA ID3 DALAM MEMBANGUN POHON
KEPUTUSAN
Secara umum Step algoritma ID3 untuk membangun pohon keputusan adalah
sebagai berikut :
1. Pilih atribut sebagai akar.
2. Buat cabang untuk tiap-tiap nilai.
3. Bagi kasus dalam cabang.
4. Ulangi proses untuk setiap cabang sampai semua kasus pada cabang
memiliki kelas yang sama.
CONTOH KASUS
PENETUAN KELAYAKAN KREDIT
DATA KEPUTUSAN KELAYAKAN KREDIT
No Nama Penghasilan Status Pekerjaan Sikap di Lingkungan Kepemilikan Rumah Layak Kredit?
1
Andy >3x angsuran Karyawan Tetap Bermasalah hak milik layak
2
Budi >3x angsuran Karyawan Tetap Baik hak milik layak
3
cindy >3x angsuran Mempunyai usaha Bermasalah kontrak layak
4
dony >3x angsuran Honorer Baik hak milik layak
5
eka 2-<3x angsuran Mempunyai usaha Bermasalah hak milik layak
6
fina 2-<3x angsuran Mempunyai usaha Baik kontrak layak
7
galih 2-<3x angsuran Honorer Baik hak milik layak
8
hanif <2x angsuran Mempunyai usaha Baik kontrak Tidak layak
9
intan <2x angsuran Honorer Baik hak milik Tidak layak
10
joko 2-<3x angsuran Mempunyai usaha Bermasalah kontrak Tidak layak
11
kurniawan 2-<3x angsuran Honorer baik kontrak Tidak layak
12
lukman <2x angsuran Karyawan Tetap Bermasalah hak milik Tidak layak
13 mery <2x angsuran Karyawan Tetap Bermasalah kontrak Tidak layak
14
Nugik <2x angsuran Mempunyai usaha Bermasalah hak milik Tidak layak
ALGORITMA ID3
Untuk memilih atribut sebagai akar, didasarkan pada nilai gain tertinggi dari atribut-atribut
yang ada.
Untuk menghitung gain digunakan rumus :
Keterangan :
• S : himpunan kasus
• A : atribut
• n : jumlah partisi atribut A
• |Si| : jumlah kasus pada partisi ke-i
• |S| : jumlah kasus dalam S
ALGORITMA ID3
Untuk perhitungan nilai entropi sbb :
Keterangan :
• S : himpunan kasus.
• A : fitur.
• n : jumlah partisi S.
• pi : proporsi dari Si terhadap S
MENGELOMPOKKAN DATA SESUAI ATRIBUT
• Literasi 1
Entropy(Total) =
((-7/14)*log2 (7/14) ) + ((- 7/14) * log2 (7/14) ) = 1
No Atribut Nilai Atribut Jmlh Kasus Total Layak Tidak Layak Entropy Gain
1 Total Total 14 7 7 1
penghasilan >3x angsuran 4 4 0 0 0,653231931
2-<3x angsuran 5 3 2 0,970950594
<2x angsuran 5 0 5 0
2 status pekerjaan Karyawan tetap 4 2 2 1 0,088936607
Mempunyai usaha 6 4 2 0,918295834
honorer 4 3 1 0,811278124
3 sikap diLingkungan Baik 7 6 1 0,591672779 0,211549543
Bermasalah 7 3 4 0,985228136
4 kepemilikan rumah Hak Milik 8 6 2 0,811278124 0,107841072
Kontrak 6 3 3 1
Gain(Total,penghasilan)
= 1 - ((4/14*0)+(5/14*0.087)+(5/14*0))
Jmlh Kasus
No Atribut Nilai Atribut Layak Tidak Layak Entropy Gain
Total
Total Total 14 7 7 1
1 penghasilan >3x angsuran 4 4 0 0 0,653231931
2-<3x angsuran 5 3 2 0,970950594
<2x angsuran 5 0 5 0
2 status pekerjaan Karyawan tetap 4 2 2 1 0,088936607
Mempunyai usaha 6 4 2 0,918295834
honorer 4 3 1 0,811278124
3 sikap diLingkungan Baik 7 6 1 0,591672779 0,211549543
Bermasalah 7 3 4 0,985228136
4 kepemilikan rumah Hak Milik 8 6 2 0,811278124 0,107841072
Kontrak 6 3 3 1
Penghasilan
>3x ang <2x ang
2-<3x ang Tidak Layak
Layak Kepemilika
n Rumah
ITERASI 2
Jmlh Kasus
No Atribut Nilai Atribut Layak Tidak Layak Entropy Gain
Total
penghasilan 2-<3 Total 5 3 2 0,970950594
status pekerjaan karyawan tetap 0 0 0 0,570950594
mempunyai usaha 3 3 0
honorer 2 1 1 1
sikap diLingkungan Baik 3 2 1 0,918295834 0,419973094
Bermasalah 2 2 0
kepemilikan rumah Hak Milik 2 2 0 0,419973094
Kontrak 3 2 1 0,918295834
Peghasilan
Penghasilan
>3x ang <2x ang
• Layak 2-<3x ang Tidak Layak
Status
Pekerjaan
honorer Punya usaha
Layak
ITERASI 3
NO Atribut Nilai atribut jumlah kasus layak tidak layak Entropy gain
0,918295834
Penghasilan 2-<3, Kep. Rumah (kontrak) total 3 2 1
0
status pekerjaan karyawan tetap 0 0 0 0,918295834
0
mempunyai usaha 2 2 0
0
honorer 1 0 1
1
sikap di lingkungan baik 2 1 1 0,251629167
0
bermasalah 1 0 1
Penghasilan
>3x ang <2x ang
Layak 2-<3x ang Tidak Layak
Status
Pekerjaan
honorer Punya usaha
Kepemilika Layak
n Rumah
kontrak Hak milik
Tidak
Layak
Layak
“
TERIMA KASIH
”