data mining - decision tree
DESCRIPTION
statistikaTRANSCRIPT
Data MiningWeek 6: Decision Tree (Pohon Keputusan)
I Gede Mahendra Darmawiguna
S.Kom M.Sc
Jurusan Pendidikan Teknik Informatika
Universitas Pendidikan Ganesha
Decision Tree
• Metode Klasifikasi dan Prediksi yang sangat
baik
• Metode Decision Tree mengubah fakta yang
sangat besar menjadi pohon keputusan yang
merepresentasikan aturan.
• Aturan dapat dengan mudah dipahami dengan
bahasa alami (dapat diekspresikan dalam
Structured Query Languange)
Decision Tree
• Pohon keputusan digunakan untuk explorasidata, menemukan hubungan tersembunyiantara sejumlah calon variabel input dengansebuah variabel target.
• Pohon keputusan adalah STRUKTUR yang dapat digunakan membagi kumpulan data yang besar menjadi himpunan-himpunanrecord yang lebih kecil dengan menerapkan
serangkaian aturan keputusan.
Decision Tree
• Banyak algoritma yang dipakai dalampembentukan pohon keputusan antara lain: ID3, CART, dan C4.5. Algoritma C4.5 adalahpengembangan dari algoritma ID3.
• DATA dalam pohon keputusan biasanyadinyatakan dalam bentuk tabel dengan atributdan record.
– Atribut menyatakan suatu parameter yang dibuatsebagai kriteria dalam pembentukan pohonkeputusan.
Algoritma C4.5
No Cuaca Temperatur Kelembaban Berangin Bermain
1 Cerah Panas Tinggi FALSE Tidak
2 Cerah Panas Tinggi TRUE Tidak
3 Berawan Panas Tinggi FALSE Iya
4 Hujan Sejuk Tinggi FALSE Iya
5 Hujan Dingin Normal FALSE Iya
6 Hujan Dingin Normal TRUE Iya
7 Berawan Dingin Normal TRUE Iya
8 Cerah Sejuk Tinggi FALSE Tidak
9 Cerah Dingin Normal FALSE Iya
10 Hujan Sejuk Normal FALSE Iya
11 Cerah Sejuk Normal TRUE Iya
12 Berawan Sejuk Tinggi TRUE Iya
13 Berawan Panas Normal FALSE Iya
14 Hujan Sejuk Tinggi TRUE Tidak
Pada tabel di bawah ini akan dibuat pohon keputusan untuk menentukan main tenis
atau tidak dengan melihat keadaan cuaca, temperatur, kelembaban dan keadaang angin
Algoritma C4.5
• Secara umum algoritma C4.5 untuk
membangun pohon keputusan adalah sebagai
berikut:
– Pilih atribut sebagai akar
– Buat cabang untuk tiap-tiap nilai
– Bagi kasus dalam cabang
– Ulangi proses untuk setiap cabang sampai semua
kasus pada cabang memiliki kelas yang sama
Algoritma C4.5
• Untuk memilih atribut sebagai akar,
didasarkan pada 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 C4.5
• Perhitungan nilai entropi dapat dilihat dari
persamaan sebagai berikut:
Keterangan:
S = Himpunan Kasus,
A = Fitur
n = jumlah partisi atribut S
Pi = proposi dari Si terhadap S
Algoritma C4.5
• Menghitung jumlah kasus, jumlah kasus untuk
keputusan Iya, jumlah kasus Tidak, dan
Entropy dari semua kasus dan kasus dibagi
menjadi atribut Cuaca, Temperatur,
Kelembaban, dan Berangin
Algoritma C4.5
NODE JUMLAH KASUS TIDAK (s1) IYA (s2) ENTROPY GAIN
1TOTAL 14 4 10 0,863121
CUACA 0,258521
BERAWAN 4 0 4 0
HUJAN 5 1 4 0,721928
CERAH 5 3 2 0,970951
TEMPERATUR 0,1838509
DINGIN 4 0 4 0
PANAS 4 2 2 1
SEJUK 6 2 4 0,918296
KELEMBABAN
TINGGI 7 4 3 0,985228
NORMAL 7 0 7 0
BERANGIN 0,0059777
TRUE 8 2 6 0,811278
FALSE 6 4 2 0,918296
Algoritma C4.5
Baris TOTAL dari Kolom Entropy dihitung dengan
persamaan :
Algoritma C4.5
• Nilai Gain pada baris Cuaca dihitung dengan
penggunakan persamaan:
Algoritma C4.5
• Atribut dengan Gain tertinggi adalah
KELEMBABAN dengan nilai 0,37.
– Kelembaban menjadi NODE (Akar).
– Ada dua nilai atribut Kelembaban: TINGGI dan
NORMAL
– Nilai NORMAL sudah mengklasifikasikan kasus
menjadi satu yaitu keputusan IYA jadi tidak perlu
perhitungan, tapi nilai atribut TINGGI masih perlu
perhitungan.
Algoritma C4.5
1.
Kelemba
ban
1.1
?Yes
NORMALTINGGI
Algoritma C4.5
NODE JUMLAH KASUS TIDAK (s1) IYA (s2) ENTROPY GAIN
1HUMIDITY 7 4 3 0,985228
CUACA 0,6995139
BERAWAN 2 0 2 0
HUJAN 2 1 1 1
CERAH 3 3 0 0
TEMPERATUR 0,0202442
DINGIN 0 0 0 0
PANAS 3 2 1 0,918296
SEJUK 4 2 2 1
BERANGIN 0,0202442
TRUE 4 2 2 1
FALSE 2 2 1 0,918296
Gain tertinggi di CUACA. Terdapat 3 NILAI: BERAWAN, HUJAN, CERAH.
BERAWAN � IYA, dan CERAH � TIDAK, CLOUDY � harus dihitung
Algoritma C4.5
1
Kelemba
ban
1.1
Cuaca
1.1.2
?
Yes No
Yes
NORMALTINGGI
BERAWAN
HUJAN
CERAH
Algoritma C4.5
NODE JUMLAH KASUS TIDAK (s1) IYA (s2) ENTROPY GAIN
1
KELEMBABAN
TINGGI dan
CUACA HUJAN
2 1 1 1
TEMPERATUR 0
DINGIN 0 0 0 0
PANAS 0 0 0 0
SEJUK 2 1 1 1
BERANGIN 1
TRUE 1 0 1 0
FALSE 1 1 0 0
Algoritma C4.51
Kelem
baban
1.1
Cuaca
1.1
Windy
Yes
Yes No
Yes No
NORMALTINGGI
BERAWAN CERAHHUJAN
TRUEFALSE
Dengan
memperhatikan
pohon keputusan
semua kasus
sudah masuk ke
dalam kelas!