Decision Tree Learning: Pruning in C4.5 Algorithm

Pruning is a way to make a decision tree simpler so it makes more generalization of the data better, leading to more accurate prediction and more readable interpretation. By this way, we can avoid overfitting. There are some methods in pruning, one of them is what C4.5 algorithm does. It’s called pessimistic pruning and based on statistical correction. Moreover, it takes only training set to build the tree and doesn’t need validation set or test set to estimate errors while pruning. We can make pessimistic estimate of the error rate by using the upper confidence limit (one-tail), which calculated with this formula:

$$e=\frac{f+\frac{z^2}{2N}+z \sqrt{\frac{f}{N}-\frac{f^2}{N}+\frac{z^2}{4N^2}}}{1+\frac{z^2}{N}}$$

where $N$ is the number of samples, $f=\frac{E}{N}$, $E$ is number of errors, and $z$ is z-score for confidence interval $c$. As the default, C4.5 will use 25% confidence interval so that $z=0.67$ (you can get the z-score by looking at Z table).

I will recall a decision tree from this post to make example how pruning is conducted. DT below is the process of pruning.

First, we start from the lowest level of node, which is health plan contribution. We’re going to compare errors before and after pruning.

Node: Health Plan Contribution

Before Pruning

 Branch  $E$  $N$  $f$  $e$
 None  2  6  0.33  0.47
 Half  1  2  0.5  0.72
 Full  2  6  0.33  0.47

So instead of 33%, 50%, and 33% error rates from each branch, we will use the pessimistic estimate of 47%, 72%, 47% respectively. The final error is weighted error from three branches or leaves.

$\text{Final error}=\frac{6}{14}\times 33\text{%} + \frac{2}{14}\times 50\text{%} + \frac{6}{14}\times 33\text{%}=51%$

After Pruning

We’ll compute estimated error if this node is replaced by a majority class. This node has 9 bad examples and 5 good examples.

 Node  $E$  $N$  $f$  $e$
 Health Plan Contribution  5  14  0.36  0.46

You can see the estimated error after pruned is lower than before pruned, it means that the pruning is worth it. So this node will be replaced by majority class, which is bad.

Node: Working Hours per Week

Before Pruning

 Branch  $E$  $N$  $f$  $e$
<=36  1  2  0.5  0.72
>36  5  14  0.36  0.46

$\text{Final error}=\frac{2}{16}\times 72\text{%} + \frac{14}{16}\times 46\text{%}=50%$

After Pruning

 Node  $E$  $N$  $f$  $e$
Working Hours per Week  6  16  0.375  0.48

Since the estimated error after pruned is lower than before pruned, the node is replaced by a majority class, bad.

Note

Although this method gives better performance and quite fast, it often doesn’t prune enough. But we can improve the quality of decision tree by tuning parameter. In this case, we can change the underlying confidence interval (25%), into a more better number. This confidence interval also plays control on determining how strict our pruning would be. For example, increasing confidence interval will make z-score bigger and in turn the estimated error become more larger. As consequence, it’s harder to prune the tree (error before pruning >> error after pruning) and the decision tree will overfit. Simply put, too higher CI = overfit and too lower CI = underfit.

 

Reference:

Data Mining: Practical Machine Learning Tools and Techniques

Decision Tree Learning: Handling Numeric Attributes

Tidak semua data yang kita punya memiliki atribut kategori. Walaupun merupakan masalah klasifikasi tapi adakalanya data yang kita punya terdiri dari satu atau lebih atribut yang memiliki nilai numerik. Sejauh ini gw hanya membahas bagaimana splitting untuk data yang terdiri dari atribut kategori. Lalu bagaimana memilih node atau splitting ketika ada atribut yang nilainya numerik? Kita coba gunakan dataset berikut.

Cuaca Suhu Kelembapan Berawan Main
 Cerah  85  85  Tidak  Tidak
 Cerah  80  90  Ya  Tidak
 Mendung  83  86  Tidak  Ya
 Hujan  70  96  Tidak  Ya
 Hujan  68  80  Tidak  Ya
 Hujan  65  70  Ya  Tidak
 Mendung  64  65  Ya  Ya
 Cerah  72  95  Tidak  Tidak
 Cerah  69  70  Tidak  Ya
 Hujan  75  80  Tidak  Ya
 Cerah  75  70  Ya  Ya
 Mendung  72  90  Ya  Ya
 Mendung  81  75  Tidak  Ya
 Hujan  71  91  Ya  Tidak

Seperti yang gw tuliskan di tulisan sebelumnya, langkah pertama yang harus dilakukan ialah menghitung entropi atau information gain untuk setiap atribut. Tapi bagaimana menghitung entropi untuk atribut numerik? Caranya ialah kita urutkan dataset berdasarkan atribut tersebut kemudian kita bagi menjadi dua kategori, misalnya untuk atribut Suhu kita bagi dataset menjadi dua berdasarkan threshold, yaitu yang memiliki Suhu <= 71.5 dan Suhu > 71.5. Nilai threshold merupakan nilai tengah antara 2 data, dalam hal ini 71.5 merupakan nilai tengah antara 71 dan 72. Setelah terbentuk dua kategori ini barulah kita hitung entropinya.

 64  65  68  69  70  71  72  75  80  81  83  85
 yes  no  yes  yes  yes  no  no
yes
 yes
yes
 no  yes  yes  no

$$E(\text{Suhu})= P(\text{Suhu<=71.5}) \times E(\text{Suhu<=71.5}) + P(\text{Suhu>71.5}) \times E(\text{Suhu>71.5})$$

$$E(\text{Suhu})= \frac{6}{14} \times E(4, 2) + \frac{8}{14} \times E(5, 3)$$

$$E(\text{Suhu})=0.939$$

Lalu Gain dihitung seperti biasa. Tapi bagaimana mendapatkan threshold tersebut? Klasik, kita coba semua kemungkinan threshold lalu cari yang menghasilkan entropi paling rendah. Jadi ada $m-1$ kemungkinan, dengan $m$ merupakan jumlah nilai unik pada atribut numerik. Pada atribut suhu diatas terdapat 11 kemungkinan (64.5, 66.6, …, 84) dan kita hitung entropi berdasarkan 11 threshold tersebut.

Decision Tree Learning: Handling Missing Values

Dalam tulisan ini gw akan coba terangkan bagaimana algoritma C4.5 memperlakukan missing value. Dalam data di dunia nyata, dimana kesempurnaan merupakan sebuah keniscayaan, data yang sempurna merupakan sebuah mitos. Sering kali kita akan menemukan data yang tidak lengkap dan terdapat nilai yang kosong. Sedangkan dalam membentuk sebuah pohon keputusan, algoritma ID3 sangat bergantung pada kualitas data, algoritma ID3 tidak mampu menangani data yang tidak lengkap atau lebih dikenal dengan missing value. Algoritma C4.5 ini merupakan perbaikan dari ID3, salah satunya mampu menangani missing value.

Sangat tidak elok kalo kita meniadakan keberadaan missing value, dibiarkan saja begitu. Apalagi dibuang. Missing value bisa saja membawa informasi penting yang dapat membangun pattern pohon keputusan. Sejatinya yang menjadi pertanyaan terkait missing value dalam pohon keputusan ialah:

  1. Seperti sebelumnya gw udah jelasin kalo pemilihan atribut saat splitting dilakukan berdasarkan gain ratio atau entropi yang ujung-ujungnya melibatkan frekuensi kemunculan suatu data. Lalu jika ada dua atribut dengan jumlah missing value yang berbeda, bagaimana pengaruhnya pada pemilihan atribut saat splitting? Perubahan apa yang sebaiknya dilakukan untuk mengakomodir missing value ini?
  2. Setelah node dipilih, dan jika terdapat instances dengan missing value pada node tersebut, maka instances tersebut mau dimasukin ke branch mana? Instances tersebut kan tidak memiliki nilai, sedangkan gak ada branch bernama ‘missing values
  3. Ketika pohon keputusan digunakan untuk memprediksi atau mengklasifikasi suatu data baru, bagaimana jika terdapat missing value pada suatu decision node? Mirip pertanyaan sebelumnya, kan gak ada branch khusus untuk ‘missing values

Gw akan memberikan contoh menggunakan dataset yang udah gw pake pada tulisan-tulisan sebelumnya. Dari 14 instances terdapat sebuah instance yang memiliki missing value, yakni pada atribut Cuaca.

Tabel 1. Dataset

Cuaca Suhu Kelembapan Berawan Main
 Cerah  85  85  Tidak  Tidak
 Cerah  80  90  Ya  Tidak
 Mendung  83  86  Tidak  Ya
 Hujan  70  96  Tidak  Ya
 Hujan  68  80  Tidak  Ya
 Hujan  65  70  Ya  Tidak
 Mendung  64  65  Ya  Ya
 Cerah  72  95  Tidak  Tidak
 Cerah  69  70  Tidak  Ya
 Hujan  75  80  Tidak  Ya
 Cerah  75  70  Ya  Ya
 ?  72  90  Ya  Ya
 Mendung  81  75  Tidak  Ya
 Hujan  71  91  Ya  Tidak

Penghitungan Information Gain

$$E(\text{Parent Node})=E(8, 5)=-\frac{8}{13}log_2\frac{8}{13}-\frac{5}{13}log_2\frac{5}{13}=0.961$$

$$E(\text{Cerah})=E(2, 3)=0.971$$

$$E(\text{Mendung})=E(3, 0)=0$$

$$E(\text{Hujan})=E(3, 2)=0.971$$

$$E(\text{Cuaca})=\frac{5}{13} \times 0.971 + \frac{3}{13} \times 0 + \frac{5}{13} \times 0.971=0.747$$

$$Gain(\text{Cuaca})=\frac{13}{14} \times (0.961-0.747)=0.199$$

Information gain ini lebih kecil dari information gain jika tidak ada missing value. Selanjutnya missing value juga mempengaruhi split information. Dengan adanya missing value, kita diibaratkan membuat sebuah kategori baru.

$$SplitInfo(\text{Cuaca})=E(5, 3, 5, 1)=-\frac{5}{14}log_2\frac{5}{14}-\frac{3}{14}log_2\frac{3}{14}-\frac{5}{14}log_2\frac{5}{14}-\frac{1}{14}log_2\frac{1}{14}=1.809$$

Split information ini lebih besar dari split information jika tidak ada missing value. Selanjutnya kita hitung gain ratio untuk atribut Cuaca:

$$GainRatio(Cuaca)=\frac{Gain(Cuaca)}{SplitInfo(Cuaca)}=\frac{0.199}{1.809}$$

Yap, secara otomatis dengan information gain yang berkurang dan split information yang meningkat akan membuat gain ratio lebih kecil jika dibandingkan tidak ada missing value. Inilah jawaban untuk pertanyaan no. 1 diatas.

Membangun Subtree

Asumsikan setelah perhitungan gain ratio untuk semua atribut, yang menjadi root node ialah atribut Cuaca. Selanjutnya dari root node ini akan terbentuk 3 cabang, Cerah, Mendung, dan Hujan. 14 instances tersebut dibagi berdasarkan nilai pada atribut Cuaca, sehingga ada 5 instances ke cabang Cerah, 3 instances ke cabang Mendung, dan 5 instances ke cabang Hujan. 1 instance yang memiliki missing value kemana? 1 instance ini kita bagi sama rata ke semua cabang secara proporsional. Artinya ada 5/13 instance ke cabang Cerah, 3/13 instance ke cabang Mendung, dan 5/13 instance ke cabang Hujan. Jika ada 2 instance yang memiliki missing value (dataset terdiri 15 instances), maka proporsinya menjadi 10/13, 6/13, 10/13. Begitu seterusnya.

Tabel 2. Subset untuk branch Cuaca

Cuaca Suhu Kelembapan Berawan Main  Bobot
 Cerah  85  85  Tidak  Tidak  1
 Cerah  80  90  Ya  Tidak  1
 Cerah  72  95  Tidak  Tidak  1
 Cerah  69  70  Tidak  Ya  1
 Cerah  75  70  Ya  Ya  1
 ?  72  90  Ya  Ya  5/13

Tabel 3. Subset untuk branch Mendung

Cuaca Suhu Kelembapan Berawan Main Bobot
 Mendung  83  86  Tidak  Ya  1
 Mendung  64  65  Ya  Ya  1
 Mendung  81  75  Tidak  Ya  1
 ?  72  90  Ya  Ya  3/13

Tabel 4. Subset untuk branch Hujan

Cuaca Suhu Kelembapan Berawan Main Bobot
 Hujan  70  96  Tidak  Ya  1
 Hujan  68  80  Tidak  Ya  1
 Hujan  65  70  Ya  Tidak  1
 Hujan  75  80  Tidak  Ya  1
 Hujan  71  91  Ya  Tidak  1
 ?  72  90  Ya  Ya  5/13

Klasifikasi Data Baru

Gw coba lanjutkan membangun subtree untuk branch Cuaca = Cerah. Setelah dihitung gain ratio nya maka ditetapkanlah kelembapan sebagai node, dengan distribusi subset sebagai berikut:

Tabel 5. Subset untuk Kelembpan <= 75

Cuaca Suhu Kelembapan Berawan Main  Bobot
 Cerah  69  70  Tidak  Ya  1
 Cerah  75  70  Ya  Ya  1

Tabel 6. Subset untuk Kelembapan > 75

Cuaca Suhu Kelembapan Berawan Main  Bobot
 Cerah  85  85  Tidak  Tidak  1
 Cerah  80  90  Ya  Tidak  1
 Cerah  72  95  Tidak  Tidak  1
 ?  72  90  Ya  Ya  5/13

Terlihat bahwa pada subset Kelembapan > 75 leaf node menjadi tidak murni lagi. Ini juga terjadi pada cabang Cuaca = Hujan. Mungkin jika bobot missing value-nya  sangat kecil hal ini tidak akan terlalu masalah, namun jika bobotnya sudah besar apalagi lebih besar dari yang selain missing value, ini akan menimbulkan masalah dalam mengklasifikasi suatu data baru. Oleh karena itu kita perlu menangani hal ini.

Suatu contoh misalnya kita punya sebuah data baru, Cuaca=Cerah, Suhu=70, Kelembapan=?, dan Berawan=Tidak. Apa output yang dihasilkan dari pohon keputusan tersebut?

Oke, karena Cuaca=Cerah, maka selanjutnya kita tentukan dari nilai Kelembapan. Ups, tapi nilai Kelembapan merupakan missing value. Terdapat dua kemungkinan kalau begitu:

  • Jika Kelembapan <= 75, maka Main=Ya
  • Jika Kelembapan > 75, maka probabilitas Main=Ya adalah (5/13)/total = 12% dan probabilitas Main=Tidak adalah 3/Total = 88%.

Note: 5/13 = 0.4

Karena kita tidak tahu berapa nilai Kelembapan, maka kita gunakan weighting untuk menentukan persentase output. Total ada 5.4 instances dalam node ini yang terbagi menjadi dua cabang, masing-masing berjumlah 2 dan 3.4 instances. Probabilitas suatu data baru memiliki Kelembapan <= 75 ialah 2/5.4 sedangkan probabilitas suatu data baru memiliki Kelembapan > 75 ialah 3.4/5.4. Namun karena node ini tidak murni maka probabilitas akhirnya ialah:

Main=Ya : $\frac{2}{5.4} \times 100\text{%} + \frac{3.4}{5.4} \times 12\text{%}=44\text{%}$

Main=Tidak: $\frac{3.4}{5.4} \times 88\text{%} = 56\text{%}$

Decision Tree Learning: Avoiding Overfitting

Salah satu kelemahan dari metode divide-and-conquer ialah tidak adanya cara menghindari overfitting. Pohon keputusan yang dihasilkan cenderung terkesan ‘sangat rindang’ dan mengandung struktur yang tidak diperlukan sehingga dapat menyebabkan pohon keputusan tidak dapat melakukan generalisasi dengan baik. Dampaknya akan mengurangi akurasi prediksi atau klasifikasi data baru. Cara yang dilakukan untuk mengatasi hal ini ialah dengan pruning. Pruning bisa diartikan sebagai ‘memangkas pohon’, membuat pohon keputusan menjadi lebih simpel.

Terdapat dua cara pruning, yaitu postpruning dan prepruning. Kalo postpruning, pemangkasan dilakukan setelah pohon keputusan jadi dengan mengganti subtree menjadi leaf node. Sedangkan kalo prepruning, pemangkasan dilakukan selama pohon keputusan dikonstruksi, kapan harus berhenti dan tidak melanjutkan pembentukan subtree. Masing-masing memiliki kelebihan dan kekurangan.

Prepruning

Keuntungannya ialah lebih hemat waktu. Kita tidak membuang-buang waktu untuk membuat subtree yang pada akhirnya tidak digunakan (setelah dilakukan simplifikasi). Prepruning dilakukan dengan melakukan statistical significance test pada setiap splitting. Jika hasil tesnya dibawah threshold artinya konstruksi pohon keputusan berhenti. Menentukan threshold ini yang tidak mudah, karena jika terlalu tinggi maka pohon keputusan yang dihasilkan terlalu simple dan prematur (underfit) dan jika threshold terlalu rendah maka simplifikasinya terlalu kecil (overfit). Umumnya statistical significant test yang diterapkan ialah menggunakan chi-squared test.

Postpruning

Kebanyakan algoritma decision tree menerapkan postpruning ini. Walaupun membutuhkan waktu yang lebih banyak, postpruning menghasilkan simplified tree yang lebih baik akurasinya. Ada dua cara dalam melakukan postpruning ini. Pertama, subtree replacement. Ide dari subtree replacement ialah mengganti subtree dengan sebuah leaf node. Replacement berjalan mulai dari node yang paling bawah atau yang memiliki leaf node hingga root node. Pohon keputusan dibawah ini adalah contohnya. Konteksnya ialah dalam negosiasi kontrak antara pekerja dan perusahaan. Berdasarkan kondisi tertentu (kenaikan gaji, tunjangan kesehatan, jam kerja, dsb) apakah suatu kontrak bakal diterima kedua pihak atau ada satu pihak yang tidak menerima.

Selain subtree replacement, cara kedua untuk melakukan postpruning ialah subtree raising. Pada subtree raising, sebuah node akan dibuang dan digantikan dengan salah satu cabang node tersebut. Contohnya pada pohon keputusan dibawah ini. Terlihat bahwa setelah pruning dilakukan, node B sudah tidak ada lagi dan telah digantikan dengan salah satu cabangnya yakni node C. Dengan kata lain, node C naik satu level. Namun setelah node C naik level, kita perlu mengklasifikasi ulang data yang ada pada leaf node 4 dan 5. Jadi leaf node 1, 2, dan 3 setelah pruning akan mendapat anggota baru yang merupakan peralihan dari leaf node 4 dan 5, tergantung hasil klasifikasi ulang.

Biasanya subtree raising dilakukan jika salah satu cabang dari sebuah node memiliki instances jauh lebih banyak dibandingkan jumlah instances pada cabang yang lain. Pada contoh diatas, node C memiliki jumlah instances yang jauh lebih banyak dibandingkan leaf node 4 dan 5. Subtree raising lebih jarang digunakan dibandingkan subtree replacement.

Lalu bagaimana menentukan apakah suatu node lebih baik dipangkas atau tetap begitu saja?

Ada dua cara yang dapat digunakan. (1) yang melibatkan validation set dan training set, (2) hanya melibatkan training set. Training set ialah data yang kita gunakan untuk membuat pohon keputusan. Sedangkan validation set tidak dilibatkan dalam pembentukan pohon keputusan, namun digunakan untuk menghitung akurasi pohon keputusan tersebut. Kedua cara ini pada prinsipnya hampir sama, yakni dengan membandingkan error yang dihasilkan sebelum pruning dan setelah pruning. Jika error setelah pruning lebih kecil dari sebelum pruning maka pruning dilanjutkan, begitu sebaliknya.

Jika kita menggunakan cara (1) maka ada dua teknik yang dapat digunakan, yakni reduced-error pruning dan cost-complexity pruning. Reduced-error pruning hanya mengukur error akibat pruning semata-mata berdasarkan validation set, berapa error yang dihasilkan oleh validation set sebelum dan setelah pruning. Kekurangan dari teknik ini ialah pohon keputusan yang terbentuk dihasilkan dari training set yang lebih sedikit. Jadi teknik ini akan lebih bermanfaat jika jumlah data yang kita punya cukup banyak.

Berbeda dengan reduced-error pruning, pada cost-complexity pruning proses pruning ditentukan dari akurasi pohon keputusan dan kompleksitas pohon keputusan tersebut. Disini, banyaknya leaf node dihitung sebagai cost. Pohon keputusan setelah pruning ialah pohon keputusan yang memiliki cost akibat error dan cost akibat kompleksitas pohon keputusan paling rendah. Cost-complexity pruning ini yang diterapkan dalam algoritma CART.

Kemudian jika kita menggunakan cara (2) kita dapat menggunakan pendekatan statistik untuk mengestimasi error sebelum dan setelah pruning. Cara ini yang diterapkan dalam algoritma C4.5. Penjelasan lebih lanjut mengenai pruning di algoritma C4.5 dapat dibaca disini.

Referensi

C4.5: Programs for Machine Learning

Data Mining: Practical Machine Learning Tools and Techniques

 

Decision Tree Learning: Constructing Decision Tree

Decision Tree Learning (DTL) merupakan salah satu metode dalam pembelajaran mesin untuk menyelesaikan masalah klasifikasi. Berbeda dengan regresi linear yang menggunakan persamaan garis linear sebagai cara memodelkan, DTL menggunakan representasi pohon keputusan (decision tree) untuk memodelkan suatu masalah. Sebagai outputnya DTL akan menghasilkan sekumpulan rules atau aturan yang digunakan untuk mengklasifikasi suatu data baru.

Sebagai contoh misalnya kita ingin mengetahui bagaimana resiko sakit jantung seseorang berdasarkan atribut Umur, Jenis Kelamin, Kebiasaan Diet (Baik/Buruk), dan Status Merokok(Perokok/Bukan Perokok). Yang kita inginkan ialah jika diberikan suatu data baru, kita dapat mengklasifikasi apakah orang tersebut masuk ke dalam kategori dengan resiko sakit jantung yang tinggi atau rendah. Gambar dibawah ini merupakan pohon keputusan untuk masalah tersebut.

Perhatikan bahwa semua atribut input akan menjadi node dalam pohon keputusan dengan jumlah branch sesuai dengan jumlah kategori tiap atribut. Atribut target (resiko sakit jantung) akan menjadi leaf node. Pertanyaan selanjutnya ialah bagaimana membuat pohon keputusan tersebut? Mengapa atribut Merokok yang menjadi root node? Mengapa atribut Jenis Kelamin tidak dilibatkan?

Divide-and-Conquer DTL

Untuk memberikan gambaran bagaimana proses konstruksi pohon keputusan, gw bakal pake dataset dibawah. Dengan dataset ini kita ingin memprediksi apakah suatu komunitas skateboard di Bandung akan menggelar latihan atau tidak berdasarkan data cuaca, suhu, kelembapan, dan kondisi awan.

Cuaca Suhu Kelembapan Berawan Main
 Cerah  Panas  Tinggi  Tidak  Tidak
 Cerah  Panas  Tinggi  Ya  Tidak
 Mendung  Panas  Tinggi  Tidak  Ya
 Hujan  Sejuk  Tinggi  Tidak  Ya
 Hujan  Dingin  Normal  Tidak  Ya
 Hujan  Dingin  Normal  Ya  Tidak
 Mendung  Dingin  Normal  Ya  Ya
 Cerah  Sejuk  Tinggi  Tidak  Tidak
 Cerah  Dingin  Normal  Tidak  Ya
 Hujan  Sejuk  Normal  Tidak  Ya
 Cerah  Sejuk  Normal  Ya  Ya
 Mendung  Sejuk  Tinggi  Ya  Ya
 Mendung  Panas  Normal  Tidak  Ya
 Hujan  Sejuk  Tinggi  Ya  Tidak

Secara umum, proses konstruksi pohon keputusan ialah sebagai berikut:

  • Pertama, pilih sebuah atribut yang akan menjadi node
  • Setelah itu buatlah sejumlah cabang berdasarkan kemungkinan nilai dari atribut tersebut. Hal ini juga akan membagi dataset menjadi beberapa bagian sesuai jumlah cabang.
  • Ulangi proses diatas secara rekursif sampai yang menjadi leaf node ialah nilai dari atribut target.

Proses ini disebut juga proses divideandconquer.

Lalu bagaimana menentukan atribut mana yang harus dipilih menjadi node terlebih dahulu?

Menentukan Root Node

Oke, gw kasih contoh lain dulu. Misalnya kita punya sebuah dataset yang memiliki 10 data dan terdiri dari 3 atribut input dan 1 atribut output. Kita ingin menentukan dari 3 atribut input tersebut atribut mana yang semestinya dipilih terlebih dahulu untuk menjadi node.

 A B C X
 A1  B1  C1  Ya
 A2  B1  C1  Tidak
 A2  B2  C1  Ya
A1  B2  C2  Tidak
 A2  B2  C2  Tidak
 A2  B3  C1  Ya
 A1  B1  C2  Tidak
 A2  B3  C1  Ya
 A1  B3  C1  Ya
 A2  B1  C2  Tidak

Sekarang menurut lo atribut mana yang seharusnya pilihan pertama untuk jadi root node, A, B, atau C?

Harusnya, lo bisa pilih dengan hanya melihat atau menghitung jumlah Ya dan Tidak dalam suatu atribut. Lo bisa lihat bahwa atribut C paling homogen, 5/6 bernilai Ya pada C1 dan 4/4 bernilai Tidak pada C2. Dengan kondisi seperti ini kita akan lebih yakin dalam mengklasifikasi suatu data baru, misalnya kalo ada data dengan nilai C=C2 maka secara pasti output-nya bernilai Tidak (karena berdasarkan dataset, output seluruh data dengan nilai C2 pada atribut C ialah Tidak). Hal ini berbeda kalo ada data baru dengan nilai A=A1, kemungkinannya masih 50:50. Jelas?

Konsep homogenitas diatas dinamakan (im)purity, yaitu seberapa murni output yang dihasilkan dari suatu atribut. Semakin homogen suatu atribut maka purity nya semakin tinggi, begitu juga sebaliknya. Oleh karena itu, kita pilih atribut yang memiliki purity yang paling tinggi. Secara kuantitatif, kita bisa menghitung kadar purity atau impurity berdasarkan nilai entropi. Entropi ini mirip dengan entropi dalam kimia yang menggambarkan tingkat ketidakteraturan suatu sistem. Semakin tinggi nilai entropi maka semakin tinggi ketidakteraturannya, atau dengan kata lain semakin tinggi impurity nya. Sebaliknya, semakin rendah nilai entropi maka semakin teratur, semakin homogen, semakin tinggi purity nya. Kita ingin mencari atribut yang memiliki nilai entropi terendah atau information gain tertinggi untuk dipilih sebagai node.

$$E(a_1, a_2, …, a_n)=-p_1 log_2 p_1-p_2 log_2 p_2…-p_n log_2 p_n$$

dimana $n$ merupakan jumlah kemungkinan output. Kalo kemungkinan output-nya Ya atau Tidak maka $n=2$. $a_1, a_2, …, a_n$ merupakan jumlah output suatu data. $p_1, p_2, …, p_n$ merupakan probabilitas output suatu data dimana $p_1=\frac{a_1}{a_1+a_2+…+a_n}$. Pada data skateboard diatas, output-nya terdiri dari 9 Ya dan 5 Tidak, sehingga:

$$E(9, 5)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940$$

Nilai entropi berkisar antara nol hingga $log_2(jumlah kemungkinan output)$. Jadi untuk data skateboard, yang merupakan klasifikasi biner, nilai entropi berkisar dari nol sampai $log_2(2)$, atau dari 0-1.

Selanjutnya kita hitung entropi tiap atribut. Untuk atribut Cuaca terdiri dari 3 kemungkinan nilai (Cerah, Mendung, Hujan) dengan distribusi sebagai berikut:

 Ya  Tidak
 Cerah  2  3  5
 Mendung  4  0  4
 Hujan  3 2  5

Sebelum menghitung entropi atribut Cuaca, kita hitung terlebih dahulu entropi tiap-tiap kemungkinan nilainya.

$$E(\text{Cerah})=E(2, 3)=0.971$$

$$E(\text{Mendung})=E(4, 0)=0$$

$$E(\text{Hujan})=E(3, 2)=0.971$$

Selanjutnya entropi Cuaca dihitung secara kumulatif dengan pembobotan

$$E(\text{Cuaca})= P(\text{Cerah}) \times E(\text{Cerah}) + P(\text{Mendung}) \times E(\text{Mendung}) + P(\text{Hujan}) \times E(\text{Hujan})$$

$$E(\text{Cuaca})=\frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971$$

$$E(\text{Cuaca})=0.693$$

Setelah kita mendapatkan nilai entropi calon atribut dan parent node, selanjutnya kita hitung information gain untuk atribut tersebut. Information gain merupakan selisih antara entropi parent node dengan entropi calon atribut. Information gain menggambarkan seberapa besar ketidakpastian yang  dapat dihindari jika memilih atribut tersebut. Oleh karena itu kita mencari atribut yang memiliki information gain tertinggi.

$$Gain(\text{Cuaca})=0.940-0.693=0.247$$

Dengan cara yang sama kita dapat menghitung entropi untuk semua atribut lain, sehingga akan menghasilkan:

$Gain(\text{Cuaca})=0.247$

$Gain(\text{Suhu})=0.029$

$Gain(\text{Kelembapan})=E(\text{Kelembapan})=0.152$

$Gain(\text{Berawan})=E(\text{Berawan})=0.048$

Dari keempat information gain diatas, atribut Cuaca memiliki information gain yang paling tertinggi, sehingga atribut ini yang kita jadikan node. Dari node ini terbentuk 3 cabang, masing-masing untuk Cerah, Mendung, dan Hujan.

Menentukan Internal Node

Langkah selanjutnya setelah kita dapatkan root node beserta cabang-cabangnya ialah melakukan langkah sebelumnya secara rekursif. Sekarang gw akan perlihatkan bagaimana menentukan atribut yang tepat untuk cabang Cuaca=Cerah. Kita pilih data yang memilki Cuaca=Cerah sehingga tampak seperti dataset berikut.

Suhu Kelembapan Berawan Main
 Panas  Tinggi  Tidak  Tidak
 Panas  Tinggi  Ya  Tidak
 Sejuk  Tinggi  Tidak  Tidak
 Dingin  Normal  Tidak  Ya
 Sejuk  Normal  Ya  Ya

Selanjutnya kita hitung entropi tiap atribut. Untuk atribut Suhu terdiri dari 3 kemungkinan nilai (Panas, Sejuk, Dingin) dengan distribusi sebagai berikut:

 Ya  Tidak
 Panas  0  2  2
 Sejuk  1  1  2
 Dingin  1  0  1

Pertama, kita hitung entropi dataset ini, yang merupakan parent node

E(\text{Parent Node})=E(2, 3)==-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.971$$

Selanjutnya kita hitung entropi untuk atribut Cuaca dengan terlebih dahulu menghitung entropi tiap-tiap kemungkinan nilainya.

$$E(\text{Panas})=E(0, 2)=0$$

$$E(\text{Sejuk})=E(1, 1)=1$$

$$E(\text{Dingin})=E(1, 0)=0$$

Selanjutnya entropi Suhu dihitung secara kumulatif dengan pembobotan

$$E(\text{Suhu})= P(\text{Panas}) \times E(\text{Panas}) + P(\text{Sejuk}) \times E(\text{Sejuk}) + P(\text{Dingin}) \times E(\text{Dingin})$$

$$E(\text{Suhu})=\frac{2}{5} \times 0 + \frac{2}{5} \times 1 + \frac{1}{5} \times 0$$

$$E(\text{Suhu})=0.4$$

$$Gain(\text{Suhu})=Entropi(\text{Parent Node})-Entropi(\text{suhu})=0.971-0.4=0.571$$

Dengan cara yang sama kita dapat menghitung entropi untuk semua atribut lain, sehingga akan menghasilkan:

$Gain(\text{Suhu})=0.571$

$Gain(\text{Suhu})=0.971$

$Gain(\text{Suhu})=0.020$

Dari ketig information gain diatas, atribut Kelembapan memiliki information gain yang paling tinggi, sehingga atribut ini yang kita jadikan node. Dari node ini terbentuk 2 cabang, masing-masing untuk Tinggi dan Normal.

Langkah-langkah diatas diulangi sehingga hasil akhirnya akan tampak seperti pohon keputusan berikut:

Atribut Super

Dari dataset saat ini misalnya gw tambah sebuah atribut baru bernama Hari yang kemungkinan nilainya mulai dari H1 sampai H14.

Hari Cuaca Suhu Kelembapan Berawan Main
 H1  Cerah  Panas  Tinggi  Tidak  Tidak
 H2  Cerah  Panas  Tinggi  Ya  Tidak
 H3  Mendung  Panas  Tinggi  Tidak  Ya
 H4  Hujan  Sejuk  Tinggi  Tidak  Ya
 H5  Hujan  Dingin  Normal  Tidak  Ya
 H6  Hujan  Dingin  Normal  Ya  Tidak
 H7  Mendung  Dingin  Normal  Ya  Ya
 H8  Cerah  Sejuk  Tinggi  Tidak  Tidak
 H9  Cerah  Dingin  Normal  Tidak  Ya
 H10  Hujan  Sejuk  Normal  Tidak  Ya
 H11  Cerah  Sejuk  Normal  Ya  Ya
 H12  Mendung  Sejuk  Tinggi  Ya  Ya
 H13  Mendung  Panas  Normal  Tidak  Ya
 H14  Hujan  Sejuk  Tinggi  Ya  Tidak

Apa yang akan terjadi terhadap pohon keputusan setelah penambahan atribut ini? Coba kita cari dulu root node nya dengan menghitung entropi Hari.

$$E(\text{Hari})=\frac{1}{14} \times E(0, 1) + \frac{1}{14} \times E(0, 1) + … + \frac{1}{14} \times E(0, 1)$$

Nilai dari $E(0, 1)$ adalah $0$ sehingga $E(\text{Hari})=0$. Ini artinya, atribut Hari memiliki entropi yang paling rendah atau information gain yang paling tinggi sehingga otomatis menjadi root node. Root node dengan 14 cabang!

Gimana kalo punya data baru dengan Hari=H32, Cuaca=Cerah, Suhu=Panas, Kelembapan=Tinggi, dan Berawan=Ya? Gak bisa coy! Dengan kondisi seperti ini kita tidak bisa melakukan prediksi, bahkan pohon keputusan tersebut tidak memberikan informasi bermanfaat mengenai proses klasifikasi. Inilah yang disebut atribut super.

Lalu bagaimana mengatasinya?

Kita bisa atasi dengan memberikan penalti berdasarkan banyak cabang. Semakin banyak cabang makin besar penaltinya. Penalti ini dinamakan Split Information. Split information menunjukkan seberapa murni cabang suatu atribut. Jika semakin sedikit maka semakin murni, begitu pula sebaliknya. Oleh karena itu perhitungan penalti atau split information ini menggunakan perhitungan entropi. Misalnya split information atribut Cuaca ialah:

$$SplitInfo(\text{Cuaca})=E(5, 4, 5)=-\frac{5}{14}log_2\frac{5}{14}-\frac{4}{14}log_2\frac{4}{14}-\frac{5}{14}log_2\frac{5}{14}$$

$$SplitInfo(\text{Cuaca})=1.577$$

Dengan cara yang sama maka split information dari atribut Hari ialah 3.807. Selanjutnya untuk menentukan atribut mana yang dipilih sebagai node, kita hitung berdasarkan nilai Gain dibagi SplitInfo. Nilai ini dinamakan GainRatio.

$$GainRatio(Atribut)=\frac{Gain(Atribut)}{SplitInfo(Atribut)}$$

Berikut ini GainRatio untuk seluruh atribut diatas:

$$GainRatio(Hari)=0.247$$

$$GainRatio(Cuaca)=0.156$$

$$GainRatio(Temperature)=0.019$$

$$GainRatio(Kelembapan)=0.152$$

$$GainRatio(Berawan)=0.049$$

Mengapa gain ratio atribut Hari masih yang tertinggi? Hal ini karena data yang sedikit. Bayangkan jika ada 200 instances unik, maka split information akan jauh lebih besar dan gain ratio yang dihasilkan akan jauh lebih kecil.