Tugas Algoritma ID3 [PDF]

Citation preview

Tugas Algoritma ID3



Nama : Muhammad Reza NPM 188160069 Mata Kuliah : Kecerdasan Buatan (A) Diketahui sebuah data sebagai berikut : No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17



Cuaca Berawan Berawan Berawan Berawan Cerah Cerah Cerah Cerah Cerah Hujan Hujan Hujan Hujan Hujan Hujan Berawan Cerah



Suhu Dingin Panas Panas Sejuk Dingin Sejuk Panas Panas Sejuk Dingin Dingin Sejuk Sejuk Sejuk Dingin Sejuk Panas



Kelembaban Normal Normal Tinggi Tinggi Normal Normal Tinggi Tinggi Tinggi Normal Normal Normal Tinggi Tinggi Tinggi Normal Normal



Berangin Benar Salah Salah Benar Salah Benar Salah Benar Salah Salah Benar Salah Salah Benar Salah Benar Benar



Main Ya Ya Ya Ya Ya Ya Tidak Tidak Tidak Ya Ya Ya Ya Tidak Tidak Ya Tidak



Berdasarkan data-data berikut, buatlah pohon keputusan dengan menggunakan algoritma ID3 !



PERHITUNGAN PADA NODE Ke- 1 No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17



Cuaca Berawan Berawan Berawan Berawan Cerah Cerah Cerah Cerah Cerah Hujan Hujan Hujan Hujan Hujan Hujan Berawan Cerah



Suhu Dingin Panas Panas Sejuk Dingin Sejuk Panas Panas Sejuk Dingin Dingin Sejuk Sejuk Sejuk Dingin Sejuk Panas



Kelembaban Normal Normal Tinggi Tinggi Normal Normal Tinggi Tinggi Tinggi Normal Normal Normal Tinggi Tinggi Tinggi Normal Normal



Berangin Benar Salah Salah Benar Salah Benar Salah Benar Salah Salah Benar Salah Salah Benar Salah Benar Benar



Main Ya Ya Ya Ya Ya Ya Tidak Tidak Tidak Ya Ya Ya Ya Tidak Tidak Ya Tidak



Entropi Kesuluruhan Dataset Entropi (S) = (-(11/17) x 𝑙𝑜𝑔2(11/17)) + (-(6/17) x 𝑙𝑜𝑔2((6/17)) = 0.936667 Total Kasus 17



Sum (Ya)



Sum (Tidak) 11



6



Entropi Total 0.936667



Entropi Cuaca Entropi (Berawan) = (-(5/5) x 𝑙𝑜𝑔2(5/5)) + (-(0/5) x 𝑙𝑜𝑔2((0/5)) = 0 Entropi (Cerah) = (-(2/6) x 𝑙𝑜𝑔2(2/6)) + (-(4/6) x 𝑙𝑜𝑔2((4/6)) = 0.918296 Entropi (Hujan) = (-(4/6) x 𝑙𝑜𝑔2(4/6)) + (-(2/6) x 𝑙𝑜𝑔2((2/6)) = 0.918296 Entropi Suhu Entropi (Dingin) = (-(4/5) x 𝑙𝑜𝑔2(4/5)) + (-(1/5) x 𝑙𝑜𝑔2((1/5)) = 0.721928 Enctorpi (Panas) = (-(2/5) x 𝑙𝑜𝑔2(2/5)) + (-(3/5) x 𝑙𝑜𝑔2((3/5)) = 0.970951 Entropi (Sejuk) = (-(5/7) x 𝑙𝑜𝑔2(5/7)) + (-(2/7) x 𝑙𝑜𝑔2((2/7)) = 0.863121



Entropi Kelembaban Entropi (Normal) = (-(8/9) x 𝑙𝑜𝑔2(8/9)) + (-(1/9) x 𝑙𝑜𝑔2((1/9)) = 0.503258 Entropi (Tinggi) = (-(3/8) x 𝑙𝑜𝑔2(3/8)) + (-(5/8) x 𝑙𝑜𝑔2((5/8)) = 0.954434 Entropi Berangin Entropi (Benar) = (-(5/8) x 𝑙𝑜𝑔2(5/8)) + (-(3/8) x 𝑙𝑜𝑔2((3/8)) = 0.954434 Entropi (Salah) = (-(6/9) x 𝑙𝑜𝑔2(6/9)) + (-(3/9) x 𝑙𝑜𝑔2((3/9)) = 0.918296 Gain Gain (Cuaca) = 0.936667 – ( ((5/17) x 0) + ((6/17) x 0.918296) + ((6/17) x 0.918296) ) = 0.288459 Gain (Suhu) = 0.936667 – ( ((5/17) x 0.721928) + ((5/17) x 0.970951) + ((7/17) x 0.863121) ) = 0.083359 Gain (Kelembaban) = 0.936667 – ( ((9/17) x 0.503258) + ((8/17) x 0.954434) ) = 0.221091 Gain (Berangin) = 0.936667 – ( ((8/17) x 0.954434) + ((9/17) x 0.918296) ) = 0.001365 Node 1



Atribut Cuaca



Nilai Berawan Cerah Hujan



Suhu



Dingin Panas Sejuk



SUM(Nilai) SUM(Ya) SUM(Tidak) Entropi 5 5 0 0.00 6 2 4 0.918296 6 4 2 0.918296



Gain



0.288459 5 5 7



4 2 5



1 0.721928 3 0.970951 2 0.863121 0.083359



Kelembaban



Normal Tinggi



9 8



8 3



1 0.503258 5 0.954434



Berangin



Benar Salah



8 9



5 6



3 0.954434 3 0.918296



0.221091



0.001365



Hasil perhitungan menunjukan bahwa nilai Gain “Cuaca” yang paling tinggi, sehingga “Cuaca” menjadi root. 1. CUACA



Berawan



Hujan Cerah



?



?



?



PERHITUNGAN PADA NODE Ke- 1.1 Cuaca “Berawan” menunjukan semua data menyatakan “Ya”. Sehingga tidak perlu mencari nilai entropi 1. CUACA



Berawan



Hujan Cerah



Ya ?



?



PERHITUNGAN PADA NODE Ke- 1.2 No 1 2 3 4 5 6



Cuaca Cerah Cerah Cerah Cerah Cerah Cerah



Suhu Dingin Sejuk Panas Panas Sejuk Panas



Kelembaban Normal Normal Tinggi Tinggi Tinggi Normal



Berangin Salah Benar Salah Benar Salah Benar



Main Ya Ya Tidak Tidak Tidak Tidak



Entropi Keseluruhan Dataset (Cerah) Entropi (S) = (-(2/6) x 𝑙𝑜𝑔2(2/6)) + (-(4/6) x 𝑙𝑜𝑔2((4/6)) = 0.918296 Cuaca Cerah 6



Sum (Ya)



Sum (Tidak) 2



4



Entropi Total 0.918296



Entropi Suhu Entropi (Dingin) = (-(1/1) x 𝑙𝑜𝑔2(1/1)) + (-(0/1) x 𝑙𝑜𝑔2((0/1)) = 0 Entropi (Sejuk) = (-(1/2) x 𝑙𝑜𝑔2(1/2)) + (-(1/2) x 𝑙𝑜𝑔2((1/2)) = 1 Entropi (Panas) = (-(0/3) x 𝑙𝑜𝑔2(0/3)) + (-(3/3) x 𝑙𝑜𝑔2((3/3)) = 0 Entropi Kelembaban Entropi (Normal) = (-(2/3) x 𝑙𝑜𝑔2(2/3)) + (-(1/3) x 𝑙𝑜𝑔2((1/3)) = 0.918296 Entropi (Tinggi) = (-(0/3) x 𝑙𝑜𝑔2(0/3)) + (-(3/3) x 𝑙𝑜𝑔2((3/3)) = 0 Entropi Berangin Entropi (Benar) = (-(1/3) x 𝑙𝑜𝑔2(1/3)) + (-(2/3) x 𝑙𝑜𝑔2((2/3)) = 0.918296 Entropi (Salah) = (-(1/3) x 𝑙𝑜𝑔2(1/3)) + (-(2/3) x 𝑙𝑜𝑔2((2/3)) = 0.918296 Gain Gain (Suhu) = 0.918296 – ( ((1/6) x 0) + ((2/6) x 1) + ((3/6) x 0) ) = 0.584963 Gain (Kelembaban) = 0.918296 – ( ((3/6) x 0.918296) + ((3/6) x 0) ) = 0.459148 Gain (Berangin) = 0.918296 – ( ((3/6) x 0.918296) + ((3/6) x 0.918296) ) = 0



Node 1.2



Atribut Suhu



Nilai Dingin Sejuk Panas



Kelembaban



Normal Tinggi



Berangin



Benar Salah



Sum(Niali) Sum(Ya) Sum(Tidak) Entropi Gain 1 1 0 0 2 1 1 1 3 0 3 0 0.584963 3 2 1 0.918296 3 0 3 0 0.459148 3 1 2 0.918296 3 1 2 0.918296 0



Hasil perhitungan menujukan bahwa Gain “Suhu” yang paling tinggi. Sehingga “Suhu” menjadi Node 1.2 1. CUACA Berawan



Hujan Cerah



Ya



1.2 SUHU



Dingin



?



Sejuk ?



?



Panas



?



PERHITUNGAN PADA NODE Ke- 1.2.1 Cuaca “Cerah” Suhu “Dingin” menunjukan semua data menyatakan “Ya”. Sehingga tidak perlu mencari nilai entropi. 1. CUACA Hujan



Berawan Cerah Ya



1.2 SUHU Dingin



?



Panas



Sejuk



Ya ?



?



PERHITUNGAN PADA NODE Ke- 1.2.2 No 1 2



Suhu Sejuk Sejuk



Kelembaban Normal Tinggi



Berangin Benar Salah



Main Ya Tidak



Entropi Keseluruhan Dataset (Sejuk) Entropi (S) = (-(1/2) x 𝑙𝑜𝑔2(1/2)) + (-(1/2) x 𝑙𝑜𝑔2((1/2)) = 1 Cuaca Cerah 2



Sum (Ya)



Sum (Tidak) 1



Entropi Total 1



Entropi Kelembaban Entropi (Normal) = (-(1/1) x 𝑙𝑜𝑔2(1/1)) + (-(0/1) x 𝑙𝑜𝑔2((0/1)) = 0 Entropi (Tinggi) = (-(0/1) x 𝑙𝑜𝑔2(0/1)) + (-(1/1) x 𝑙𝑜𝑔2((1/1)) = 0 Entropi Berangin Entropi (Benar) = (-(1/1) x 𝑙𝑜𝑔2(1/1)) + (-(0/1) x 𝑙𝑜𝑔2((0/1)) = 0 Entropi (Salah) = (-(0/1) x 𝑙𝑜𝑔2(0/1)) + (-(1/1) x 𝑙𝑜𝑔2((1/1)) = 0



1



Gain Gain (Kelembaban) = 1 – ( ((1/2) x 0) + ((1/2) x 0) ) = 1 Gain (Berangin) = 1 – ( ((1/2) x 0) + ((1/2) x 0) ) = 1 Node 1.2.2



Atribut Kelembaban



Nilai Normal Tinggi



Berangin



Benar Salah



Sum(Nilai) Sum(Ya) Sum(Tidak) Entropi Gain 1 1 0 0 1 0 1 0 1 1 1



1 0



0 1



0 0 1



Karena Gain “Kelembaban” dan “Berangin” adalah 1. Disini saya mengambil “Berangin” untuk menjadi node 1.2.2. 1. CUACA



Berawan



Hujan Cerah 1.2 SUHU



Ya



Dingin



Sejuk



?



Panas



1.2.2 BERANGIN



Ya



Benar



?



?



Salah



?



PERHITUNGAN PADA NODE Ke- 1.2.2.1 Cuaca “Cerah” Suhu “Sejuk” Berangin “Benar” menunjukan semua data menyatakan “Ya”. Sehingga tidak perlu mencari nilai entropi. 1. CUACA Berawan



Hujan



Cerah 1.2 SUHU



Ya Dingin



? Panas



Sejuk 1.2.2 BERANGIN



Ya



?



Benar



Salah



Ya



?



PERHITUNGAN PADA NODE Ke- 1.2.2.2 Cuaca “Cerah” Suhu “Sejuk” Berangin “Salah” menunjukan semua data menyatakan “Tidak”. Sehingga tidak perlu mencari nilai entropi. 1. CUACA Berawan



Hujan



Cerah



Ya



1.2 SUHU Dingin



Sejuk



Ya



? Panas



1.2.2 BERANGIN Benar Ya



? Salah Tidak



PERHITUNGAN PADA NODE Ke- 1.2.3 Cuaca “Cerah” Suhu “Panas” menunjukan semua data menyatakan “Tidak”. Sehingga tidak perlu mencari nilai entropi. 1. CUACA Berawan



Hujan



Cerah



Ya



1.2 SUHU Dingin



? Panas



Sejuk 1.2.2 BERANGIN



Ya



Benar Ya



Tidak



Salah Tidak



PERHITUNGAN PADA NODE Ke- 1.3 No 1 2 3 4 5 6



Cuaca Hujan Hujan Hujan Hujan Hujan Hujan



Suhu Dingin Dingin Sejuk Sejuk Sejuk Dingin



Kelembaban Normal Normal Normal Tinggi Tinggi Tinggi



Berangin Salah Benar Salah Salah Benar Salah



Main Ya Ya Ya Ya Tidak Tidak



Entropi Kesuluruhan Dataset (Hujan) Entropi (S) = (-(4/6) x 𝑙𝑜𝑔2(4/6)) + (-(2/6) x 𝑙𝑜𝑔2((2/6)) = 0.918296 Total Kasus 6



Sum (Ya)



Sum (Tidak) 4



2



Entropi Total 0.918296



Entropi Suhu Entropi (Dingin) = (-(2/3) x 𝑙𝑜𝑔2(2/3)) + (-(1/3) x 𝑙𝑜𝑔2((1/3)) = 0.918296 Entropi (Sejuk) = (-(2/3) x 𝑙𝑜𝑔2(2/3)) + (-(1/3) x 𝑙𝑜𝑔2((1/3)) = 0.918296



Entropi Kelembaban Entropi (Normal) = (-(3/3) x 𝑙𝑜𝑔2(3/3)) + (-(0/3) x 𝑙𝑜𝑔2((0/3)) = 0 Entropi (Tinggi) = (-(1/3) x 𝑙𝑜𝑔2(1/3)) + (-(2/3) x 𝑙𝑜𝑔2((2/3)) = 0.918296 Entropi Berangin Entropi (Benar) = (-(1/2) x 𝑙𝑜𝑔2(1/2)) + (-(1/2) x 𝑙𝑜𝑔2((1/2)) = 1 Entropi (Salah) = (-(3/4) x 𝑙𝑜𝑔2(3/4)) + (-(1/4) x 𝑙𝑜𝑔2((1/4)) = 0.811278 Gain Gain (Suhu) = 0.918296 – ( ((3/6) x 0.918296) + ((3/6) x 0.918296) ) = 0 Gain (Kelembaban) = 0.918296 – ( ((3/6) x 0) + ((3/6) x 0.918296) ) = 0.459148 Gain (Berangin) = 0.918296 – ( ((2/6) x 1) + ((4/6) x 0.811278) ) = 0.04411 Node 1.3



Atribut Suhu



Nilai Dingin Sejuk



Sum(Niali) Sum(Ya) Sum(Tidak) Entropi Gain 3 2 1 0.918296 3 2 1 0.918296 0



Kelembaban



Normal Tinggi



3 3



3 1



0 0 2 0.918296 0.459148



Berangin



Benar Salah



2 4



1 3



1 1 1 0.811278 0.04411



Hasil perhitungan menunjukan baha Gain “Kelembaban” yang paling tinggi. Sehingga “Kelembaban” menjadi Node 1.3. 1. CUACA Hujan



Berawan



Cerah 1.3 KELEMBABAN



1.2 SUHU



Ya Dingin



Sejuk



Panas



1.2.2 BERANGIN



Ya



Normal Tidak



Benar



Salah



Ya



Tidak



?



Tinggi ?



PERHITUNGAN PADA NODE Ke- 1.3.1 Cuaca “Hujan” Kelembaban “Normal” menunjukan semua data menyatakan “Ya”. Sehingga tidak perlu mencari nilai entropi. 1. CUACA Hujan



Berawan



Cerah 1.3 KELEMBABAN



1.2 SUHU



Ya Dingin



Panas



Sejuk 1.2.2 BERANGIN



Ya



Normal Ya



Tidak



Benar



Salah



Ya



Tidak



PERHITUNGAN PADA NODE Ke- 1.3.2 No 1 2 3



Suhu Sejuk Sejuk Dingin



Kelembaban Tinggi Tinggi Tinggi



Berangin Salah Benar Salah



Main Ya Tidak Tidak



Entropi Kesuluruhan Dataset (Kelembaban Tinggi) Entropi (S) = (-(1/3) x 𝑙𝑜𝑔2(1/3)) + (-(2/3) x 𝑙𝑜𝑔2((2/3)) = 0.918296 Total Kasus 3



Sum (Ya)



Sum (Tidak) 1



2



Entropi Total 0.918296



Entropi Suhu Entropi (Sejuk) = (-(1/2) x 𝑙𝑜𝑔2(1/2)) + (-(1/2) x 𝑙𝑜𝑔2((1/2)) = 1 Entropi (Dingin) = (-(0/1) x 𝑙𝑜𝑔2(0/1)) + (-(1/1) x 𝑙𝑜𝑔2((1/1)) = 0



Tinggi ?



Entropi Berangin Entropi (Benar) = (-(0/1) x 𝑙𝑜𝑔2(0/1)) + (-(1/1) x 𝑙𝑜𝑔2((1/1)) = 0 Entropi (Salah) = (-(1/2) x 𝑙𝑜𝑔2(1/2)) + (-(1/2) x 𝑙𝑜𝑔2((1/2)) = 1 Gain Gain (Suhu) = 0.918296 – ( ((2/3) x 1) + ((1/3) x 0) ) = 0.251629 Gain (Berangin) = 0.918296 – ( ((1/3) x 0) + ((2/3) x 1) ) = 0..251629 Node 1.3.2



Atribut Suhu



Nilai Sejuk Dingin



Berangin



Benar Salah



Sum(Nilai) Sum(Ya) Sum(Tidak) Entropi Gain 2 1 1 1 1 0 1 0 0.251629 1 0 1 0 2 1 1 1 0.251629



Karena Gain “Suhu” dan Gain “Berangin” adalah sama. Maka saya mengambil “Berangin” untuk menjadi Node 1.3.2. 1. CUACA Hujan



Berawan



Cerah 1.3 KELEMBABAN



1.2 SUHU



Ya Dingin



Sejuk



Panas



1.2.2 BERANGIN



Ya



Tidak



Benar



Salah



Ya



Tidak



Tinggi



Normal



1.3.2 BERANGIN



Ya Salah ?



Benar ?



PERHITUNGAN PADA NODE Ke- 1.3.2.2 Cuaca “Hujan” Kelembaban “Tinggi” Berangin “Benar” menunjukan semua data menyatakan “Tidak”. Sehingga tidak perlu mencari nilai entropi. 1. CUACA Hujan



Berawan



Cerah 1.3 KELEMBABAN



1.2 SUHU



Ya Dingin



Sejuk



Panas



1.2.2 BERANGIN



Ya



Tidak



Benar



Salah



Ya



Tidak



Tinggi



Normal



1.3.2 BERANGIN



Ya Salah ?



Benar Tidak



PERHITUNGAN PADA NODE Ke- 1.3.2.1 No 1 2



Berangin Salah Salah



Suhu Sejuk Dingin



Main Ya Tidak



Dikarenakan data pada Cuaca “Hujan” Kelembaban “Tinggi” Berangin “Salah” hanya mempunyai dua data dimana Suhu “Sejuk” menunjukan data “Ya” sedangkan “Dingin” menunjukan data “Tidak”. Maka dapat dibuat : 1. CUACA Hujan



Berawan



Cerah 1.3 KELEMBABAN



1.2 SUHU



Ya Dingin



Sejuk



Panas



1.2.2 BERANGIN



Ya



Tidak



Benar



Salah



Ya



Tidak



Tinggi



Normal



1.3.2 BERANGIN



Ya



Benar



Salah 1.3.2.1 SUHU Sejuk Ya



Tidak Dingin Tidak



Sehingga dari proses yang telah dikerjakan, di dapat hasil : No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17



Cuaca Berawan Berawan Berawan Berawan Cerah Cerah Cerah Cerah Cerah Hujan Hujan Hujan Hujan Hujan Hujan Berawan Cerah



Suhu Dingin Panas Panas Sejuk Dingin Sejuk Panas Panas Sejuk Dingin Dingin Sejuk Sejuk Sejuk Dingin Sejuk Panas



Kelembaban Normal Normal Tinggi Tinggi Normal Normal Tinggi Tinggi Tinggi Normal Normal Normal Tinggi Tinggi Tinggi Normal Normal



CUACA



Berangin Benar Salah Salah Benar Salah Benar Salah Benar Salah Salah Benar Salah Salah Benar Salah Benar Benar



Main Ya Ya Ya Ya Ya Ya Tidak Tidak Tidak Ya Ya Ya Ya Tidak Tidak Ya Tidak



Tidak



Ya Hujan



Berawan



Cerah KELEMBABAN



SUHU



Ya Dingin



Sejuk



Ya



Panas Tidak



BERANGIN Benar



Salah



Ya



Tidak



Tinggi



Normal Ya



BERANGIN Benar



Salah SUHU



Sejuk



Tidak



Dingin