ID3 : Induksi Decision Tree

Artificial Intelligence - STTS

ID3 : Induksi Decision Tree Singkatan: Iterative Dichotomiser 3 Induction of Decision "3" (baca: Tree) Pembuat: Ross Quinlan, sejak akhir dekade 70-an. Pengembangan Lanjut: Cikal bakal algoritma C4.5, pada tahun 1993. Features: Tahap belajar yang cepat; time complexity yang rendah; ketelitian klasifikasi yang tinggi. Kategori Learning: Concept Learning, dengan tujuan mendeskripsikan "Konsep umum apakah yang digunakan?"

x1 x2 x3 : xn

FUNGSI YANG TIDAK DIKETAHUI

y = f (x1,x2,x3, ..... , xn)

Tujuan Algoritma: mendapatkan decision tree (salah satu bentuk "Classification Models") yang terbaik. Problem: Upaya mendapatkan decision tree terbaik (minimal) yang konsisten dari sekumpulan data, termasuk dalam kategori algoritma NP-Hard / Completeness. Mekanisme Konstruksi: Dilakukan secara top-down, diawali pertanyaan: "Attribute mana yang harus diperiksa pada root dari decision tree?" Dibentuk dengan mempartisi training examples. Kekuatan Algoritma yang Terutama: fungsi heuristik information gain untuk memilih attribute terbaik. Overview pada Algoritma: Mewujudkan Greedy Heuristic Search: Hill-Climbing TANPA Backtracking.


Algoritma ID3 PROCEDURE ID3 (Examples, TargetAttribute, Attributes) 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 )


Beberapa Terms dan Contoh 14 Minggu Permainan Tenis pada Setiap Sabtu Pagi Examples (S), adalah training examples yang ditunjukkan oleh tabel di bawah ini: Day Outlook Temperature Humidity D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14

Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain

Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild

High High High High Normal Normal Normal High Normal Normal Normal High Normal High

Wind Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong

Play Tennis No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No

Target Attribute adalah PlayTennis yang memiliki value yes atau no. Attribute adalah Outlook, Temperature, Humidity, dan Wind.

Tunjukkan Model Klasifikasi Decision Tree untuk Pengambilan Keputusan: "Bermain tenis atau tidak?", dari 14 minggu pengalaman seperti ditunjukkan oleh tabel di atas, dengan menggunakan Algoritma ID3 !


Solusi S adalah koleksi dari 14 contoh dengan 9 contoh positif dan 5 contoh negatif, ditulis dengan notasi [9+,5-]. Entropy dari S adalah: c

Entropy(S) =Σ − p i log 2 p i 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:

Gain(S, A) = Entropy(S) −

Σ v∈Values(A)

Sv S

Entropy(S v )


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) = High, Normal

= [3+,4-] = [6+,1-] Gain(S,Humidity) = Entropy(S) - (7/14)Entropy(SHigh) -

SHigh SNormal

(7/14)Entropy(SNormal)

= 0.94029 - (7/14)0.98523 - (7/14)0.59167 = 0.15184 Values(Temperature) = Hot, Mild, Cool

SHot SMild SCool

= [2+,2-] = [4+,2-] = [3+,1-] Gain(S,Temperature) = 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) = Sunny, Overcast, Rain

= [2+,3-] = [4+,0-] = [3+,2-] Gain(S,Outlook) = 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

SSunny SOvercast SRain

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

Tampak bahwa attribute Outlook akan menyediakan prediksi terbaik untuk target attribute PlayTennis.


[D1, D2, ... D14] [9+,5-]

Outlook

Sunny

Over cast

?

Yes

? [D1, D2, D8, D9, D11] [2+,3-]

Rain

[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 D1 D2 D8 D9 D11

Sunny Sunny Sunny Sunny Sunny

Hot Hot Mild Cool Mild

High High High Normal Normal

Wind

Play Tennis Weak No Strong No Weak No Weak Yes 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) = Weak, Strong = [1+,2-] SWeak = [1+,1-] SStrong Gain(SSunny, Wind) = Entropy(SSunny) - (3/5)Entropy(SWeak) (2/5)Entropy(SStrong) = 0.97075 - (3/5)0.91830 - (2/5)1.00000 = 0.01997

Attribute Humidity menyediakan prediksi terbaik pada level ini. [D1, D2, ... D14] [9+,5-]

Outlook

[D1, D2, D8, D9, D11] [2+,3-]

Over cast

Sunny

Rain

Yes

Humidity

[D3, D7, D12, D13] [4+,0-]

High

Normal

No

Yes

[D1, D2, D8] [0+,3-]

[D9, D11] [2+,0-]

[D4, D5, D6, D10, D14] [3+,2-]

?


Untuk branch node Outlook=Rain, SRain = [D4, D5, D6, D10, D14] Day Outlook Temperature Humidity D4 D5 D6 D10 D14

Rain Rain Rain Rain Rain

Mild Cool Cool Mild Mild

High Normal Normal Normal High

Wind

Play Tennis Weak Yes Weak Yes Strong No Weak Yes Strong No

Values(Temperature) = Mild, Cool {Perhatikan: Tidak ada lagi temperature=hot saat ini}

SMild SCool

= [2+,1-] = [1+,1-] Gain(SRain, Temperature) = 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

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

Attribute Wind menyediakan prediksi terbaik pada level ini.


[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

Normal

Weak

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: 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


Studi Kasus Komite ujian untuk sebuah kampus bertemu mendiskusikan hasil ujian sejumlah mahasiswanya. Terdapat 3 (tiga) kemungkinan hasil evaluasi, mahasiswa bisa:

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 NMarg Att Ext

Ant

: Jumlah ujian yang gagal : Jumlah ujian yang gagal, dengan nilai pada batas berhasil / gagal : Catatan kehadiran mahasiswa : Ada / tidaknya kondisi yang meringankan, misalnya kondisi sakit yang menyebabkan kegagalan yang tak diinginkan. : Hasil yang telah diantisipasi.

Induksi decision treenya dilakukan. 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.


Tabel contoh mula-mula: Example Number 1 2 3 4 5 6 7 8 9 10 11 12 13

NFails NMarg 0 0 0 3 3 3 3 2 2 1 1 1 1

0 0 0 0 1 0 2 1 2 0 1 1 0

Att good poor good good poor good good poor good poor good good poor

Ext Ant Result no yes yes no no no yes no yes yes yes no no

P F F F F P P F P P F F F

P P P F F F R R R R R R F

Penambahan dan modifikasinya adalah sebagai berikut: Example Number 8 14 15 16 17

NFails NMarg 2 3 2 2 2

1 2 2 1 0

Att poor good good good poor

Ext Ant Result no no no yes no

F P F P F

F F R R F

ID3 : Induksi Decision Tree

Recommend Documents