LEARNING ARTIFICIAL INTELLIGENT
Dr. Muljono, S.Si, M. Kom
Outline
Decision tree learning Jaringan Syaraf Tiruan K-Nearest Neighborhood Naïve Bayes
Decision Tree Learning : Klasifikasi untuk penerimaan pegawai baru merupakan salah satu studi kasus yang akan dijabarkan. Dimana terdapat 11 orang yang mengikuti tes penerimaan pegawai baru dengan menggunakan 3 parameter atau atribut penilaian sebagai berikut: IPK dikatagorikan (Bagus, Cukup, Kurang) Psikologi dikatagorikan (Tinggi, Sedang, Rendah) Wawancara dikatagorikan (Baik, Buruk)
Bagaimana menemukan aturan? Pelamar P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12
IPK Bagus Bagus Bagus Bagus Cukup Cukup Cukup Cukup Kurang Kurang Kurang Kurang
Psikologi Tinggi Sedang Sedang Rendah Tinggi Sedang Sedang Rendah Tinggi Sedang Sedang Rendah
Wawancara Baik Baik Buruk Buruk Baik Baik Buruk Buruk Baik Baik Buruk Buruk
Diterima Ya Ya Tidak Tidak Ya Ya Tidak Tidak Ya Ya Tidak Tidak
Wawancara Baik
Ya
Buruk
Tidak
(Wawancara ' Baik' ) Diterima ' Ya'
Bagaimana menemukan aturan? Pelamar P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11
IPK Bagus Bagus Bagus Bagus Cukup Cukup Cukup Cukup Kurang Kurang Kurang
Psikologi Tinggi Sedang Sedang Rendah Tinggi Sedang Sedang Rendah Tinggi Sedang Rendah
Wawancara Baik Baik Buruk Buruk Baik Baik Buruk Buruk Baik Buruk Baik
Diterima Ya Ya Ya Tidak Ya Ya Ya Tidak Ya Tidak Ya
Wawancara Baik
Buruk
Psikologi
Ya Tinggi Tidak
Bagus Ya
Sedang
IPK
Cukup Ya
Rendah Tidak
Kurang Tidak
Rule
(Wawancara ' Baik ' ) ((Wawancara ' Buruk ' ) ( Psikologi ' Sedang ' ) ( IPK ' Bagus ' )) ( (Wawancara ' Buruk ' ) ( Psikologi ' Sedang ' ) ( IPK ' Cukup' )) Diterima ' Ya '
Masalah
Data tidak lengkap IPK
: 3 kemungkinan nilai Psikologi: 3 kemungkinan nilai Wawancara: 2 kemungkinan nilai Data lengkap = 3 x 3 x 2 = 18 records
Aturan yang men-generalisasi unseen data?
Learning
Bagaimana untuk data yang sangat banyak? Bagaimana menemukan aturan? Bagaimana jika datanya tidak lengkap? Aturan yang general untuk data yang akan datang? Menemukan perbedaan dari dua hal yang mirip? Menemukan kesamaan dari dua hal yang berbeda?
Data penerimaan pegawai baru Pelamar P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11
IPK Bagus Bagus Bagus Bagus Cukup Cukup Cukup Cukup Kurang Kurang Kurang
Psikologi Tinggi Sedang Sedang Rendah Tinggi Sedang Sedang Rendah Tinggi Sedang Rendah
Wawancara Baik Baik Buruk Buruk Baik Baik Buruk Buruk Baik Buruk Baik
Diterima Ya Ya Ya Tidak Ya Ya Ya Tidak Ya Tidak Ya
Langkah Pertama Tentukan akar dari pohon, akar atau node awal akan diambil dari atribut yang dipilih, dengan cara menghitung kemudian memilih informasi gain tertinggi dari masing-masing atribut. Namun sebelum menghitung gain dari atribut, harus dihitung dulu nilai entropy dari setiap tupel.
Jumlah sampel setiap atribut : Jumlah Sampel
Ya
Tidak
11
8
3
IPK
Bagus Cukup Kurang
4 4 3
3 3 2
1 1 1
Psikologi
Tinggi Sedang Rendah
3 5 3
3 4 1
0 1 2
Wawancara
Baik Buruk
6 5
6 2
0 3
Himpunan Kasus
Menghitung Entropy
Perhitungan untuk mencari nilai Entropy dari setiap tupel atribut masing-masing
Entropy
Parameter untuk mengukur heterogenitas (keberagaman) dari kumpulan sampel data. Jika kumpulan sampel data semakin heterogen, maka nilai entropy-nya semakin besar.
Entropy
S : Himpunan Kasus n : jumlah kelas pada atribut target (jumlah kelas klasifikasi). pi : Proporsi sampel untuk kelas i ( Proporsi dari Si terhadap S)
Jumlah sampel setiap atribut : Jumlah Sampel
Ya
Tidak
11
8
3
IPK
Bagus Cukup Kurang
4 4 3
3 3 2
1 1 1
Psikologi
Tinggi Sedang Rendah
3 5 3
3 4 1
0 1 2
Wawancara
Baik Buruk
6 5
6 2
0 3
Himpunan Kasus
Entropy (Total-Kelas)
Entropy IPK-Bagus
Entropy IPK-Cukup
Entropy IPK-Kurang
Entropy Psikologi-Tinggi
Entropy Psikologi-Sedang
Entropy Psikologi-Rendah
Entropy Wawancara-Baik
Entropy Wawancara-Buruk
Menghitung Information Gain (IG)
Efektivitas atribut dalam mengklasifikasikan data Dihitung berdasarkan entropy
Information Gain (IG)
S A n |Si | |S| Entropy(Si )
: himpunan kasus : atribut : jumlah partisi pada atribut A : jumlah sampel pada partisi ke i : jumlah seluruh sampel data pada kasus S : entropy untuk sampel-sampel pada partisi ke i
IG untuk IPK
IG untuk Psikologi
IG untuk Wawancara
Hasil Perhitungan Gain dan Entropy Jumlah kasus
Ya
Tidak
11
8
3
Bagus
4
3
1
0.811278124
Cukup
4
3
1
0.811278124
Himpunan kasus
IPK
Psikologi
Wawancara
Entropi
Gain
0.845350936
Kurang
3
2
1
0.918295834
Tinggi
3
3
0
0
Sedang
5
4
1
0.647517476
Rendah
3
1
2
0.918295834
Baik
6
6
0
0
Buruk
5
2
3
0.970950594
0.0048
0.300580492
0.404009756
Menentukan Root dari Decision Tree
Gain Tertinggi adalah atribut Wawancara (nilai = 0.404009756), Sehingga Atribut Wawancara menjadi root dari Decision Tree Atribut Wawancara (Nilai : Baik dan Buruk) Nilai : Baik ada 6 kasus “Ya” diterima dan 0 kasus “Tidak” diterima
Pohon Keputusan Pada Node Pertama
Penentuan Node Pada Wawancara - Nilai Buruk Pelamar
IPK
Psikologi
Wawancara
Diterima
P3
Bagus
Sedang
Buruk
Ya
P4
Bagus
Rendah
Buruk
Tidak
P7
Cukup
Sedang
Buruk
Ya
P8
Cukup
Rendah
Buruk
Tidak
P10
Kurang
Sedang
Buruk
Tidak
Menghitung Entropy dari Wawancara - nilai “Buruk”
Entropy IPK-Bagus
Entropy IPK-Cukup
Entropy IPK-Kurang
Entropy Psikologi-Sedang
Entropy Psikologi-Rendah
Menghitung Gain dari nilai “Buruk”
Hasil Perhitungan Entropy dan Gain Jumlah kasus
Ya
Tidak
5
2
3
Bagus Cukup
2 2
1 1
1 1
Kurang
1
0
1
Sedang
3
2
1
Rendah
2
0
2
Wawancara
IPK
Psikologi
Entropi
Gain
0.970950594 1 1 0.170950594 0
0.918295834 0.419973093
Penentuan Node Lanjutan
Gain tertinggi adalah Psikologi sebesar 0.419973093 atribut Psikologi dapat menjadi node lanjutan dari atribut Wawancara – Buruk Atribut Psikologi (Nilai : Sedang dan Rendah) Nilai : Rendah ada 2 kasus “Tidak” diterima dan 0 kasus “Ya” diterima
Pohon Keputusan Pada Node Lanjutan
Menentukan Daun/Leaf (Node Terakhir)
Pelamar
IPK
Psikologi Wawancara Diterima
P3
Bagus
Sedang
Buruk
Ya
P7
Cukup
Sedang
Buruk
Ya
P10
Kurang
Sedang
Buruk
Tidak
Menentukan Daun/Leaf (Node Terakhir)
Tanpa menghitung nilai Entropy dan Gain Hal ini dikarenakan, untuk nilai Psikologi – Sedang, hanya didapati sisa 3 cabang dan langsung melengkapi yang kurang
Pohon Keputusan Pada Node Terakhir
Atruan (Rule)
“JIKA wawancara = baik MAKA diterima” “JIKA wawancara = buruk AND psikologi = sedang AND ipk = bagus MAKA diterima” “JIKA wawancara = buruk AND psikologi = sedang AND ipk = cukup MAKA diterima” “JIKA wawancara = buruk AND psikologi = sedang AND ipk = kurang MAKA ditolak” “JIKA wawancara = buruk AND psikologi = rendah MAKA ditolak” “JIKA wawancara = buruk AND psikologi = tinggi MAKA ditolak”
Aturan (Rule)
(Wawancara ' Baik ' ) ((Wawancara ' Buruk ' ) ( Psikologi ' Sedang ' ) ( IPK ' Bagus ' )) ( (Wawancara ' Buruk ' ) ( Psikologi ' Sedang ' ) ( IPK ' Cukup' )) Diterima ' Ya '
Diskusi
Jika terdapat dua atribut dengan IG yang sama? Jika ada data yang sama tetapi kelasnya berbeda? Berapa jumlah learning data minimum? Imbalance Class?
Dua atribut dengan IG sama ?
Gain(S,IPK) = 0,0049 Gain(S,Psikologi) = 0,4040 Gain(S,Wawancara) = 0,4040
Data sama, kelasnya beda? Pelamar P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11
IPK Bagus Bagus Bagus Bagus Cukup Cukup Cukup Cukup Kurang Kurang Kurang
Psikologi Tinggi Sedang Sedang Rendah Tinggi Sedang Sedang Sedang Tinggi Sedang Rendah
Wawancara Baik Baik Buruk Buruk Baik Baik Buruk Buruk Baik Buruk Baik
Diterima Ya Ya Ya Tidak Ya Ya Ya Tidak Ya Tidak Ya
Jumlah learning data ?
Masalah Sentiment Analysis atau Email Spam Filtering 200.000 kata Masing-masing kata muncul 0 – 100 kali Training data: 10.000 postingan atau email
Imbalance Class?
Data latih untuk tiap kelas tidak seimbang Terutama untuk kasus data kesehatan (rekam medis) Misalnya: klasifikasi penyakit
Daftar Pustaka
Suyanto. 2007. Artificial Intelligence: Searching, Reasoning, Planning and Learning. Informatika, Bandung Indonesia. ISBN: 979-1153-05-1. Russel, Stuart and Norvig, Peter. 1995. Artificial Intelligence: A Modern Approach. Prentice Hall International, Inc.
