www.hansmichael.com - Maret 2007 Diktat Kuliah Data Mining - Institut Informatika Indonesia Semester Genap 2006/2007 - Maret 2007 Sub Materi: ID3: Induksi Decision Tree Ross Quinlan Ross Quinlan Pengembang algoritma ID3 pada akhir dekade 70-an1, dalam upaya mewujudkan suatu sistem pakar yang mampu belajar dari kumpulan contoh. [CS 346 Spring 00] Quinlan memperbaiki algoritma ID3 menjadi C4.5 pada tahun 1993, yang hari ini banyak digunakan. [CS 346 Spring 00] Jauh hari sebelumnya, Hunt dan koleganya dari disiplin Pshychology menggunakan metode pencarian penuh pada decision tree untuk memodelkan belajar konsep pada manusia pada tahun 60-an. [CS 346 Spring 00]
ID3 Singkatan: Iterative Dichotomiser 32 Induction of Decision "3" (Tree)3 Mungkin merupakan algoritma Machine Learning yang paling banyak digunakan dalam literatur-literatur science dan sistem software komersil. [Solheim96] ID3 dikenal memiliki tahap belajar yang cepat; time complexity yang rendah; dan ketelitian klasifikasi yang tinggi, termasuk untuk training examples yang memiliki noise. [Solheim96] Versi original ID3 hanya menangani nilai-nilai attribute yang sedikit dan diskret, tetapi modifikasi selanjutnya mampu menangani nilai attribute yang ordered dan continuous. [Solheim96] Variasi algoritma ID3 lainnya memiliki kemampuan untuk menangani noise. [Solheim96] Termasuk kategori Concept Learning, yang tujuannya mendeskripsikan "Konsep umum apakah yang digunakan?" (Lihat Gambar) Tujuan dari ID3 adalah: mendapatkan decision tree yang terbaik. [CS 346 Spring 00]
x1 x2 x3 : xn
FUNGSI YANG TIDAK DIKETAHUI
y = f (x1,x2,x3, ..... , xn)
Sistem belajar tersupervisi yang membentuk rule-rule untuk klasifikasi dalam bentuk sebuah decision tree. [Solheim96] 1
Machine Learning Course Notes ELEG 867 - Decision Trees. Menyebutkan Quinlan mengembangkan ID3 pada tahun 1986. 2 Knowledge Acquisition for Expert Systems, Anna Hart, Kogan Page, 1989, p. 125. 3 Helge Grenager Solheim, http://www.pvv.unit.no/~hgs/project/report/node36.html, 4 Mei 1996.
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 1
www.hansmichael.com - Maret 2007 Decision tree adalah salah satu bentuk "Classification Models".4 [Ingargiola] Masalahnya adalah upaya untuk mendapatkan decision tree terbaik (baca: minimal) yang konsisten dengan sekumpulan data yang telah disediakan termasuk dalam kategori algoritma NP-Hard (Completeness). [CS 346 Spring 00] Konstruksi decision tree dilakukan secara top-down, diawali dengan pertanyaan: "Attribute mana yang harus diperiksa pada root dari decision tree?" [Mitchell97] Decision tree dibentuk dengan mempartisi training examples. [Solheim96] Kekuatan ID3 yang terutama adalah pada fungsi heuristik information gain untuk memilih attribute terbaik yang akan digunakan [Solheim96] Konsep Entropy yang digunakan untuk mengukur "seberapa informatifnya" sebuah node (yang biasanya disebut seberapa baiknya), diperkenalkan oleh Claude Shannon dalam Information Theory. [Ingargiola] ID3 adalah algoritma greedy, sehingga pemilihan yang keliru pada sebuah atribut akan memberikan efek pada hasil akhirnya. [Solheim96] Dalam hal ini algoritma tidak pernah melakukan backtracking untuk merevisi keputusan pemilihan attribute yang telah dilakukan sebelumnya. [Mitchell97] Recursive Algorithm mewujudkan Greedy Heuristic Search: Hill-Climbing tanpa backtracking. [CS 346 Spring 00] Tidak menjamin menghasilkan decision tree yang selalu -- walaupun biasanya -optimal. [CS 346 Spring 00]
Beberapa Terms Examples (S), adalah training examples yang ditunjukkan oleh tabel di bawah ini: Day
Outlook
Temperature
Humidity
Wind
PlayTennis
D1
Sunny
Hot
High
Weak
No
D2
Sunny
Hot
High
Strong
No
D3
Overcast
Hot
High
Weak
Yes
D4
Rain
Mild
High
Weak
Yes
D5
Rain
Cool
Normal
Weak
Yes
D6
Rain
Cool
Normal
Strong
No
D7
Overcast
Cool
Normal
Strong
Yes
D8
Sunny
Mild
High
Weak
No
D9
Sunny
Cool
Normal
Weak
Yes
D10
Rain
Mild
Normal
Weak
Yes
D11
Sunny
Mild
Normal
Strong
Yes
D12
Overcast
Mild
High
Strong
Yes
D13
Overcast
Hot
Normal
Weak
Yes
D14
Rain
Mild
High
Strong
No
Target attribute adalah PlayTennis yang memiliki value yes atau no, selama 14 minggu pada setiap Sabtu pagi. Attribute adalah Outlook, Temperature, Hunidity, dan Wind.
4
Building Classification Models: ID3 and C4.5, Ingargiola, http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html.
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 2
www.hansmichael.com - Maret 2007 Algoritma PROCEDURE ID3(Examples, TargetAttribute, Attributes)5 Examples are the training examples. Target-attribute is the attribute whose value is to be predicted by the tree. Attributes is a list of other attributes that may be tested by the learned decision tree. Returns a decision tree that correctly classifies the given Examples. Create a Root node for the tree If all Examples are positive, Return the single-node tree Root, with label = + If all Examples are negative, Return the single-node tree Root, with label = If Attributes is empty, Return the single-node tree Root, with label = most common value of Target_attribute in Examples Otherwise Begin A <--- the attribute from Attributes that best* classifies Examples The decision attribute for Root <--- A For each possible value, vi, of A, - Add a new tree branch below Root, corresponding to the test A = vi - Let Examplesvi be the subset of Examples that have value vi for A - If Examplesvi is empty Then below this new branch add a leaf node with label = most common value of Target_attribute in Examples Else below this new branch add the subtree Call ID3 (Examples, Target_attribute, Attributes - {A})) End Return Root * The best attribute is the one with highes information gain, as defined in Equation:
Gain(S, A) = Entropy(S) −
Σ v∈Values(A)
Sv S
Entropy(S v )
S adalah koleksi dari 14 contoh dengan 9 contoh positif dan 5 contoh negatif, ditulis dengan notasi [9+,5-]. Entropy dari S adalah:
Entropy(S) =Σ − p i log 2 p i c
i=1
Entropy([9+,5-])
= - (9/14)log2(9/14) - (5/14)log2(5/14) = 0.94029
Catatan: Entropy(S)=0, jika semua contoh pada S berada dalam kelas yang sama. Entropy(S)=1, jika jumlah contoh positif dan jumlah contoh negatif dalam S adalah sama. 0<Entropy(S)<1, jika jumlah contoh positif dan negatif dalam S tidak sama. Gain(S,A) adalah Information Gain dari sebuah attribute A pada koleksi contoh S.6 5
Machine Learning, Tom M. Mitchell, The McGraw-Hill Companies, Inc., International Edition, 1997, p. 56. 6 Decision Tree, http://javaboy.ice.cycu.edu.tw/ver98/product/dtree/main.html. Dijelaskan bahwa terdapat sedikitnya 3 (tiga) macam diversity, yaitu pengukuran yang digunakan untuk mengevaluasi splitter (pemisah value-value attribute) yang paling potensial: 1. Min(P(c1),P(c2))
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 3
www.hansmichael.com - Maret 2007 Values(Wind) SWeak SStrong Gain(S,Wind)
= Weak, Strong = [6+,2-] = [3+,3-] = Entropy(S) - (8/14)Entropy(SWeak) - (6/14)Entropy(SStrong) = 0.94029 - (8/14)0.81128 - (6/14)1.0000 = 0.04813
Values(Humidity) SHigh SNormal Gain(S,Humidity)
= High, Normal = [3+,4-] = [6+,1-] = Entropy(S) - (7/14)Entropy(SHigh) - (7/14)Entropy(SNormal) = 0.94029 - (7/14)0.98523 - (7/14)0.59167 = 0.15184
Values(Temperature) SHot SMild SCool Gain(S,Temperature)
= Hot, Mild, Cool = [2+,2-] = [4+,2-] = [3+,1-] = Entropy(S) - (4/14)Entropy(SHot) - (6/14)Entropy(SMild) - (4/14)Entropy(SCool) = 0.94029 - (4/14)1.00000 - (6/14)0.91830 - (4/14)0.81128 = 0.02922
Values(Outlook) SSunny SOvercast SRain Gain(S,Outlook)
= Sunny, Overcast, Rain = [2+,3-] = [4+,0-] = [3+,2-] = Entropy(S) - (5/14)Entropy(SSunny) - (4/14)Entropy(SOvercast) - (5/14)Entropy(SRain) = 0.94029 - (5/14)0.97075 - (4/14)1.000000 - (5/14)0.97075 = 0.24675
Jadi, information gain untuk 4 atribut yang ada adalah: Gain(S,Wind) = 0.04813 Gain(S,Humidity) = 0.15184 Gain(S,Temperature) = 0.02922 Gain(S,Outlook) = 0.24675 Dari perhitungan tersebut, tampak bahwa attribute Outlook akan menyediakan prediksi terbaik untuk target attribute PlayTennis.
2. 2P(c1)P(c2) 3. [P(c1)logP(c1)]+[P(c2)logP(c2)] (entropy/information).
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 4
www.hansmichael.com - Maret 2007 [D1, D2, ... D14] [9+,5-]
Outlook
Sunny
Over cast
Rain
?
Yes
? [D1, D2, D8, D9, D11] [2+,3-]
[D3, D7, D12, D13] [4+,0-]
[D4, D5, D6, D10, D14] [3+,2-]
Untuk branch node Outlook=Sunny, SSunny = [D1, D2, D8, D9, D11] Day
Outlook
Temperature
Humidity
Wind
PlayTennis
D1
Sunny
Hot
High
Weak
No
D2
Sunny
Hot
High
Strong
No
D8
Sunny
Mild
High
Weak
No
D9
Sunny
Cool
Normal
Weak
Yes
D11
Sunny
Mild
Normal
Strong
Yes
Values(Temperature) = Hot, Mild, Cool = [0+,2-] SHot = [1+,1-] SMild = [1+,0-] SCool Gain(SSunny, Temperature) = Entropy(SSunny) - (2/5)Entropy(SHot) - (2/5)Entropy(SMild) - (1/5)Entropy(SCold) = 0.97075 - (2/5)0.00000 - (2/5)1.00000 - (1/5)0.00000 = 0.57075 Values(Humidity) = High, Normal = [0+,3-] SHigh = [2+,0-] SNormal Gain(SSunny, Humidity) = Entropy(SSunny) - (3/5)Entropy(SHigh) - (2/5)Entropy(SNormal) = 0.97075 - (3/5)0.00000 - (2/5)1.00000 = 0.97075 Values(Wind) SWeak SStrong Gain(SSunny, Wind)
= Weak, Strong = [1+,2-] = [1+,1-] = Entropy(SSunny) - (3/5)Entropy(SWeak) - (2/5)Entropy(SStrong) = 0.97075 - (3/5)0.91830 - (2/5)1.00000 = 0.01997
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 5
www.hansmichael.com - Maret 2007 [D1, D2, ... D14] [9+,5-]
Outlook
[D1, D2, D8, D9, D11] [2+,3-]
Over cast
Sunny
Rain
[D4, D5, D6, D10, D14] [3+,2-]
?
Yes
Humidity
[D3, D7, D12, D13] [4+,0-]
High
Normal
No
Yes
[D1, D2, D8] [0+,3-]
[D9, D11] [2+,0-]
Untuk branch node Outlook=Rain, SRain = [D4, D5, D6, D10, D14] Day
Outlook
Temperature
Humidity
Wind
PlayTennis
D4
Rain
Mild
High
Weak
Yes
D5
Rain
Cool
Normal
Weak
Yes
D6
Rain
Cool
Normal
Strong
No
D10
Rain
Mild
Normal
Weak
Yes
D14
Rain
Mild
High
Strong
No
Values(Temperature) SMild SCool Gain(SRain, Temperature)
= Mild, Cool {Tidak ada lagi temperature=hot saat ini} = [2+,1-] = [1+,1-] = Entropy(SRain) - (3/5)Entropy(SMild) - (2/5)Entropy(SCold) = 0.97075 - (3/5)0.91830 - (2/5)1.00000 = 0.01997
Values(Humidity) SHigh SNormal Gain(SRain, Humidity)
= High, Normal = [1+,1-] = [2+,1-] = Entropy(SRain) - (2/5)Entropy(SHigh) - (3/5)Entropy(SNormal) = 0.97075 - (2/5)1.00000 - (3/5)0.91830 = 0.01997
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 6
www.hansmichael.com - Maret 2007 Values(Wind) SWeak SStrong Gain(SRain, Wind)
= Weak, Strong = [3+,0-] = [0+,2-] = Entropy(SRain) - (3/5)Entropy(SWeak) - (2/5)Entropy(SStrong) = 0.97075 - (3/5)0.00000 - (2/5)0.00000 = 0.97075 [D1, D2, ... D14] [9+,5-]
Outlook
[D1, D2, D8, D9, D11] [2+,3-]
Rain
Over cast
Sunny
Yes
Humidity
[D4, D5, D6, D10, D14] [3+,2-]
Wind
[D3, D7, D12, D13] [4+,0-]
High
Weak
Normal
Strong
No
Yes
Yes
No
[D1, D2, D8] [0+,3-]
[D9, D11] [2+,0-]
[D4, D5, D10] [3+,0-]
[D6, D14] [0+,2-]
Rule-Rule yang telah Dipelajari, dengan memperhatikan decision tree yang dihasilkan adalah:7 IF Outlook = Sunny AND Humidity = High THEN PlayTennis = No IF Outlook = Sunny AND Humidity = Normal THEN PlayTennis = Yes IF Outlook = Overcast THEN PlayTennis = Yes IF Outlook = Rain AND Wind = Strong THEN PlayTennis = No IF Outlook = Rain AND Wind = Weak THEN PlayTennis = Yes 7
Datamining and Machine Learning, Patricia Jean Riddle, http://www.cs.aukuni.ac.nz/~pat/706_99/In/www.html.
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 7
www.hansmichael.com - Maret 2007 Studi Kasus Sederhana8 Komite ujian untuk sebuah kuliah bertemu untuk mendiskusikan hasil ujian sejumlah mahasiswanya. Terdapat 3 (tiga) kemungkinan hasil evaluasi, mahasiswa dapat lulus (P=Pass), diberi kesempatan mengulang (R=Resit), atau gagal (F=Fail). Beberapa pertemuan untuk memberikan hasil evaluasi sering kali memakan waktu yang lama. Sering pula membutuhkan penasihat ahli (pakar) pendidikan yang telah memiliki pengalaman luas dari banyak pengambilan keputusan serupa. Para pakar ini diminta untuk merumuskan sebuah petunjuk (guidelines), dan mereka kemudian menyusun sekumpulan contoh dari berbagai kasus pengambilan keputusan. Target Attribute-nya adalah hasil evaluasi (Pass, Resit, dan Fail), sedangkan attributes-nya adalah: Nfails : Jumlah ujian yang gagal Nmarg : Jumlah ujian yang gagal, dengan nilai pada batas berhasil/gagal Att : Catatan kehadiran mahasiswa Ext : Ada/tidaknya kondisi yang meringankan, misalnya kondisi sakit yang menyebabkan kegagalan yang tak diinginkan. Ant : Hasil yang telah diantisipasi. Example Number
NFails
NMarg
Att
Ext
Ant
Result
1
0
0
good
no
P
P
2
0
0
poor
yes
F
P
3
0
0
good
yes
F
P
4
3
0
good
no
F
F
5
3
1
poor
no
F
F
6
3
0
good
no
P
F
7
3
2
good
yes
P
R
8
2
1
poor
no
F
R
9
2
2
good
yes
P
R
10
1
0
poor
yes
P
R
11
1
1
good
yes
F
R
12
1
1
good
no
F
R
13
1
0
poor
no
F
F
Hasil induksi decision tree-nya ditunjukkan pada gambar 1. Setelah pemeriksaan lanjut model pengambilan keputusan ini, para ahli memutuskan untuk menambahkan sejumlah contoh lagi pada kumpulan kasus, sebab mereka merasa bahwa aturan-aturan untuk sekitar 2 atau 3 hasil yang gagal belumlah cukup. Mereka juga memutuskan untuk memodifikasi contoh untuk nomor 8. Perubahannya adalah sebagai berikut: Example Number
NFails
NMarg
Att
Ext
Ant
Result
8
2
1
poor
no
F
F
14
3
2
good
no
P
F
15
2
2
good
no
F
R
16
2
1
good
yes
P
R
17
2
0
poor
no
F
F
Hasil induksi decision tree-nya setelah perubahan kumpulan contoh ditunjukkan pada gambar 2. Saat inilah para pakar merasa perlu untuk membuat perubahan pada decision tree-nya. Hasil akhirnya ditunjukkan pada gambar 3. Komentar para pakar atas kasus ini adalah: 8
Anna Hart, p. 126.
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 8
www.hansmichael.com - Maret 2007 "Banyak anggota komite memperdebatkan tentang catatan kehadiran dan hasil evaluasi yang diharapkan. Hal ini tampaknya tidak terlalu penting dibanding faktor-faktor lainnya. Saya berpikir decision tree terakhir merupakan ringkasan akhir seluruh model pengambilan keputusan ini, dan merupakan perkiraan yang cukup baik untuk apa yang telah terjadi. Saya dapat memberi lebih banyak contoh lagi dalam kumpulan kasus, tetapi saya berpikir bahwa itu tidak menggambarkan situasi sesungguhnya. Aturan-aturan tersebut kelihatannya dingin, tetapi semua itu menunjukkan apa yang biasanya anda semua lakukan. Semua ini akan membuat Anda semua merasa lebih baik dalam mengambil keputusan." ------oOo------
Materi Kuliah Data Mining I3- Genap 2006/2007
halaman 9
