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

 

Leave a Reply

Your email address will not be published. Required fields are marked *