### 6.2 ID3

_Decision tree_  adalah varian dari _inductive learning_. ID3 adalah salah satu
algoritma varian _decision tree_ [34]. _Decision tree_ dibangun berdasarkan asumsi
bila atribut yang ada memberikan informasi yang cukup memadai maka kita
mampu membangun _decision tree_ yang mampu mengklasifikasikan seluruh
_instance_ di _training data_ [34]. Akan tetapi, kita tentunya ingin melakukan
generalisasi, yaitu _decision tree_ yang juga mampu mengklasifikasikan objek
dengan benar untuk _input_ yang tidak ada di _training data_ ( _unseen instances_ ).
Oleh karena itu, kita harus mampu mencari hubungan antara kelas dan nilai
atribut.

```
Gambar 6.1:Final decision tree
```
```
id outlook temperature humidity windy play ( _class_ )
1 sunny hot high false no
2 sunny hot high true no
3 overcast hot high false yes
4 rainy mild high false yes
5 rainy cool normal false yes
6 rainy cool normal true no
7 overcast cool normal true yes
8 sunny mild high false no
9 sunny cool normal false yes
10 rainy mild normal false yes
11 sunny mild normal true yes
12 overcast mild high true yes
13 overcast hot normal false yes
14 rainy mild high true no
```
```
Tabel 6.1: Contoh dataset _play tennis_ (UCI machine learning repository).
```

```
6.2 ID3 85
```
St _rate_ gi pembangunan ID3 adalah berdasarkan _top-down_ rekursif. Pertama,
kita pilih atribut untuk _root_ pohon, lalu membuat cabang untuk setiap
nilai atribut yang mungkin. Untuk masing-masing cabang, kita buat _subtree_.
Kita hentikan proses ini ketika kita sudah mencapai _leaf_ (tidak bisa mencabang
lebih jauh). _Leaf_ ditandai apabila seluruh _instance_ pada cabang tersebut
memiliki kelas yang sama. Atribut yang sudah dipilih pada _ancestor_ tidak
akan dicoba pada percabangan di cabang tertentu.
Sebagai contoh, perhatikanlah Gambar 6.1 yang merupakan hasil ID3
untuk Tabel 6.1. Bentuk elips merepresentasikan nama atribut, sementara
_edge_ (panah) merepresentasikan nilai atribut. Bentuk segi empat merepresentasikan
klasifikasi kelas ( _leaf_ ). Pohon keputusan pada Gambar 6.1 dapat
dikonversi menjadi kumpulan aturan klasifikasi berbentuk logika preposisi
dengan menelusuri setiap cabang pada pohon tersebut, yaitu:

- if _outlook=sunny_ and _humidity=high_ then _play=no_
- if _outlook=sunny_ and _humidity=normal_ then _play=yes_
- if _outlook=overcast_ then _play=yes_
- if _outlook=rainy_ and _windy=false_ then _play=yes_
- if _outlook=rainy_ and _windy=true_ then _play=no_

Karena _decision tree_ dapat interpretasikan sebagai logika preposisi, model ini
tergolong _interpretable_. Artinya, manusia dapat mengerti proses yang terjadi
pada model dengan mudah.
Pada setiap langkah membangun ID3, kita menggunakaninformation
gainuntuk memilih kandidat atribut terbaik. _Information gain_ mengukur
kemampuan suatu atribut untuk memisahkan _training data_ berdasarkan kelas
[7].
Sebelum masuk ke perumusan _information gain_, penulis akan mengingatkan _entropy_ terlebih
dahulu. Entropy (derajat ketidakteraturan) adalah
informasi yang dibutuhkan untuk memprediksi sebuah kejadian, diberikan
distribusi probabilitas. Secara matematis, entropy didefinisikan pada persamaan
6.1 (xadalah kumpulan nilai probabilitas).

```
_entropy_ (x) =−
```
#### ∑N

```
i=1
```
```
xilogxi (6.1)
```
Kita juga definisikanInfo sebagai persamaan 6.2, dimana ci adalah
banyaknya instance diklasifikasikan sebagai kelas ke-i (atau secara lebih
umum, ke _node_ -i).


86 6 Pohon Keputusan

```
Info(c 1 ,c 2 ,...,cN) = entropy(
```
```
c 1
∑N
j cj
```
#### ,

```
c 2
∑N
j cj
```
#### ,...,

```
cN
∑N
j cj
```
#### ) (6.2)

_Information gain_ dihitung sebagai persamaan 6.3, dimanaciadalah jumlah _instance_ untuk
kelas ke-i,vadalah nilai atribut,cvadalah banyaknya
_instance_  ketika dicabangkan dengan nilai atributv,cvxadalah banyaknya
_instance_ kelas saat percabangan. _Information gain_ dapat dimaknai sebagai
pengurangan entropy karena melakukan percabangan.

```
IG(c 1 ,c 2 ,...,cN) = Info(c 1 ,c 2 ,...,cN)−
```
#### ∑

```
vV
```
```
cv
∑N
i=1ci
```
```
Info(c 1 v,c 2 v,...,cNv)
```
(6.3)
Sebagai contoh, mari kita hitung _Information gain_ untuk atribut _outlook_
sebagai _root_. Dari keseluruhan data terdapat 9 _instance_ untuk _play=yes_ dan
5 instanceuntuk _play=no_. Kita hitung Info semesta sebagai (logbasis 2)

```
Info([9,5]) = entropy
```
#### ([

#### 9

#### 14

#### ,

#### 5

#### 14

#### ])

#### =−

#### 9

#### 14

```
log
```
#### (

#### 9

#### 14

#### )

#### −

#### 5

#### 14

```
log
```
#### (

#### 5

#### 14

#### )

#### = 0. 940

Kita hitung _entropy_ untuk masing-masing nilai atribut _outlook_ sebagai berikut:

- outlook=sunny
    Ada dua _instance_ dengan _play=yes_ dan tiga _instance_ dengan _play=no_
    saat _outlook=sunny_, dengan demikian kita hitung Info-nya.

```
Info([2,3]) = entropy
```
#### (

#### 2

#### 5

#### ,

#### 3

#### 5

#### )

#### =−

#### 2

#### 5

```
log
```
#### (

#### 2

#### 5

#### )

#### −

#### 3

#### 5

```
log
```
#### (

#### 3

#### 5

#### )

#### = 0. 971

- outlook=overcast
    Ada empat _instance_ dengan _play=yes_ dan tidak ada _instance_ dengan
    play=nosaat _outlook=overcast_, dengan demikian kita hitung Info-nya.

```
Info([4,0]) = entropy
```
#### (

#### 4

#### 4

#### ,

#### 0

#### 4

#### )

#### =−

#### 4

#### 4

```
log
```
#### (

#### 4

#### 4

#### )

#### −

#### 0

#### 4

```
log
```
#### (

#### 0

#### 4

#### )

#### = 0

```
Perhatikan log 0 pada matematika adalah tidak terdefinisi, tapi kita
anggap 0 log 0 sebagai 0 dalam komputasi.
```

```
6.2 ID3 87
```
- outlook=rainy
    Ada tiga _instance_ dengan _play=yes_ dan dua _instance_ dengan _play=no_
    saat _outlook=rainy_, dengan demikian kita hitung Info-nya.

```
Info([3,2]) = _entropy_
```
#### (

#### 3

#### 5

#### ,

#### 2

#### 5

#### )

#### =−

#### 3

#### 5

```
log
```
#### (

#### 3

#### 5

#### )

#### −

#### 2

#### 5

```
log
```
#### (

#### 2

#### 5

#### )

#### = 0. 971

Kita hitung _information gain_ untuk atribut _outlook_ sebagai

```
IG( _outlook_ ) = Info ([9,5])−
(
5
14
```
```
×Info ([3,2]) +
```
#### 4

#### 14

```
×Info([4,0]) +
```
#### 5

#### 14

```
×Info([3,2])
```
#### )

#### = 0. 940 −

#### (

#### 5

#### 14

#### × 0 .971 +

#### 4

#### 14

#### ×0 +

#### 5

#### 14

#### × 0. 971

#### )

#### = 0. 940 − 0. 693

#### = 0. 247

Dengan metode yang sama, kita hitung _information gain_ untuk atribut lain-
nya.

- IG(temperature) = 0. 029
- IG( _humidity_ ) = 0. 152
- IG(windy) = 0. 048

Dengan demikian, kita memilih atribut _outlook_ sebagai _root_.
Kita lanjutkan lagi membuat _subtree_ setelah memilih atribut _outlook_ sebagai _root_.
Kita hitung atribut yang tepat pada cabangoutook=sunny, seperti
diilustrasikan pada Gambar 6.2.
Pada _outlook=sunny_, terdapat dua _instance_ dengan kelas _play=yes_
dan tiga _instance_ dengan kelas _play=no_. Kita hitung _information gain_ saat
melanjutkan cabang dengan atribut _humidity_.

```
IG( _humidity_ ) = Info([2,3])−
```
#### (

#### 3

#### 5

```
×Info([0,3]) +
```
#### 2

#### 5

```
×Info([2,0])
```
#### )

#### = 0. 971 − 0

#### = 0. 971

Untuk setiap kedalaman, kita coba menggunakan atribut yang belum pernah
dicoba pada level-level lebih atas, seperti yang sudah diilutrasikan. Proses ini
dilanjutkan sampai kita tidak bisa atau tidak perlu mencabang lagi.


88 6 Pohon Keputusan

```
Gambar 6.2: Percabangan
```
