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