Dari Akar hingga Daun: Cara Decision Tree Mengambil Keputusan
Memahami Decision Tree: Konsep, Logika, dan Variannya
1. Pengantar: Apa Itu Decision Tree?
Dalam dunia machine learning dan pemrosesan data, pengambilan keputusan otomatis merupakan fondasi dari berbagai aplikasi cerdas. Salah satu metode yang paling populer, ampuh, dan paling intuitif untuk melakukan tugas ini adalah algoritma Decision Tree (Pohon Keputusan).
Bayangkan Anda sedang menentukan apakah hari ini cocok untuk bermain tenis:
- Anda melihat cuaca (Outlook): cerah, mendung, atau hujan?
- Jika cerah, Anda memeriksa kelembapan (Humidity): tinggi atau normal?
- Jika kelembapan normal, keputusannya: ya, bermain tenis.
Aturan bercabang seperti ini mudah ditelusuri langkah demi langkah, sehingga Decision Tree disebut model white-box: alasan di balik setiap prediksi bisa dibaca dan dijelaskan, bahkan kepada orang non-teknis.
Dua Strategi di Balik Layar
Saat membangun pohon, algoritma ini bertumpu pada dua strategi dasar:
- Divide-and-conquer (memecah dan menaklukkan): dataset yang kompleks dibagi secara rekursif menjadi subset yang lebih kecil dan lebih homogen, berdasarkan pengujian atribut tertentu.
- Greedy search (pencarian serakah): di setiap langkah, algoritma memilih pemisahan terbaik saat itu juga secara top-down, tanpa memperhitungkan dampak jangka panjang terhadap keseluruhan pohon.
Prinsip Occam's Razor
Decision Tree juga sejalan dengan prinsip Occam's Razor: "entitas tidak boleh diperbanyak melebihi kebutuhan". Cabang baru hanya layak ditambahkan jika benar-benar meningkatkan akurasi. Pohon yang lebih kecil umumnya memberi penjelasan lebih jernih dan lebih baik dalam menggeneralisasi data baru (unseen data). Prinsip ini akan sangat penting saat kita membahas overfitting di bagian 5.
Sebelum masuk ke matematikanya, mari kenali dulu bagian-bagian fisik sebuah pohon keputusan.
2. Anatomi Pohon Keputusan
Decision Tree mengalirkan data dari atas ke bawah (top-down) melewati serangkaian pengujian atribut sampai tiba di keputusan akhir. Strukturnya terdiri dari empat elemen:
| Elemen | Posisi | Fungsi |
|---|---|---|
| Root node (simpul akar) | Paling atas | Titik awal alur keputusan, tanpa cabang masuk. Mewakili seluruh dataset dan atribut yang paling berpengaruh dalam membedakan kelas. |
| Internal node (simpul internal) | Tengah | Titik percabangan tempat sebuah atribut diuji untuk membagi data menjadi subset yang lebih homogen. |
| Branch (cabang) | Antar simpul | Hasil pengujian atribut; menghubungkan satu simpul ke simpul berikutnya. |
| Leaf node (simpul daun) | Paling bawah | Titik akhir tanpa cabang keluar. Menyimpan keputusan final: label kelas (klasifikasi) atau rata-rata nilai numerik (regresi). |
Pada contoh tenis tadi, Outlook adalah root node, Humidity adalah internal node, dan "Ya, bermain tenis" adalah leaf node. Menelusuri jalur dari akar ke daun sama dengan membaca satu aturan keputusan.
Pertanyaan teknis berikutnya adalah yang paling penting: bagaimana algoritma menentukan atribut mana yang pantas menjadi akar atau simpul internal? Jawabannya ada pada ukuran kemurnian data.
3. Logika Pemisahan Data: Mengukur Ketidakmurnian
Pada setiap simpul, algoritma memilih atribut yang paling menurunkan ketidakmurnian (impurity) data. Prosesnya berulang secara rekursif:
- Hitung ketidakmurnian data pada simpul saat ini.
- Uji setiap atribut: seberapa besar penurunan ketidakmurnian jika atribut itu dipakai untuk memisahkan data?
- Pilih atribut dengan penurunan terbaik sebagai simpul pemisah.
- Bagi data ke cabang-cabang baru, lalu ulangi sampai data murni atau kriteria penghentian terpenuhi.
3.1 Entropi
Entropi, ukuran dari teori informasi, menggambarkan derajat ketidakpastian atau keacakan sebuah himpunan data S:
\[ Entropy(S) = - \sum_{c} p(c) \log_2 p(c) \]dengan p(c) adalah proporsi data yang termasuk kelas c. Pada kasus dua kelas, nilainya berkisar dari 0 hingga 1:
- 0 berarti data murni: seluruhnya berada di satu kelas.
- 1 berarti data paling acak: terbagi seimbang, misalnya 50% positif dan 50% negatif.
Catatan: batas atas 1 berlaku untuk dua kelas. Untuk c kelas, entropi maksimum adalah \(\log_2(c)\).
3.2 Information Gain
Information Gain mengukur seberapa efektif sebuah atribut A memisahkan data, yaitu selisih entropi sebelum dan sesudah pemisahan:
\[ Gain(S, A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v) \]Aturannya sederhana: atribut dengan Information Gain tertinggi dipilih sebagai simpul pemisah.
3.3 Studi Kasus: Memilih Akar Pohon
Kita pakai 14 sampel data cuaca untuk memprediksi keputusan bermain tenis: 9 sampel "Ya" dan 5 sampel "Tidak".
Langkah 1: entropi awal.
\[ Entropy(Tenis) = -\frac{9}{14}\log_2\frac{9}{14} - \frac{5}{14}\log_2\frac{5}{14} \approx 0{,}94 \]Langkah 2: Information Gain atribut Kelembapan. Nilai "Tinggi" punya 7 sampel (3 Ya, 4 Tidak) dengan entropi 0,985. Nilai "Normal" punya 7 sampel (6 Ya, 1 Tidak) dengan entropi 0,592.
\[ Gain(Tenis, Kelembapan) = 0{,}94 - \frac{7}{14}(0{,}985) - \frac{7}{14}(0{,}592) \approx 0{,}151 \]Langkah 3: ulangi untuk atribut lain. Hasilnya:
| Atribut | Information Gain |
|---|---|
| Outlook | 0,246 |
| Humidity (Kelembapan) | 0,151 |
| Wind (Angin) | 0,048 |
| Temperature (Suhu) | 0,029 |
Outlook menang, sehingga menjadi root node. Setelah itu seluruh proses diulang pada setiap cabang Outlook.
3.4 Gain Ratio
Information Gain punya kelemahan: ia bias terhadap atribut dengan banyak nilai unik (misalnya kolom ID atau tanggal, yang memecah data hingga tiap subset hanya berisi satu sampel). Gain Ratio mengoreksi bias ini dengan membagi Information Gain dengan SplitInfo, yaitu entropi dari distribusi ukuran subset hasil pemisahan.
3.5 Gini Impurity
Gini Impurity dipakai luas pada algoritma CART. Metrik ini mengukur peluang sebuah sampel acak salah diklasifikasikan jika dilabeli menurut distribusi kelas di simpul tersebut:
\[ Gini(S) = 1 - \sum_{c} p(c)^2 \]Nilai 0 berarti simpul murni sempurna. Pada kasus dua kelas, nilai maksimumnya 0,5 (data terbagi 50:50). Semakin rendah Gini, semakin ideal pemisahannya. Secara komputasi Gini juga lebih ringan karena tidak memerlukan logaritma.
Perbandingan Empat Metrik
| Metrik | Fungsi | Nilai | Dipakai oleh |
|---|---|---|---|
| Entropy | Mengukur ketidakpastian data | 0 (murni) hingga 1 (paling acak, dua kelas) | ID3, C4.5 |
| Information Gain | Mengukur penurunan entropi setelah pemisahan | Lebih tinggi lebih baik; bias ke atribut banyak kategori | ID3, C4.5 |
| Gain Ratio | Menormalisasi Information Gain dengan SplitInfo | Mencegah preferensi pada atribut banyak kategori | C4.5 |
| Gini Impurity | Mengukur peluang salah klasifikasi | 0 (murni) hingga 0,5 (dua kelas) | CART |
4. Varian Populer: ID3, C4.5, CART, dan Soft Decision Tree
Gagasan Decision Tree berakar pada Algoritma Hunt (1960-an), yang awalnya dirancang untuk memodelkan cara manusia belajar. Dari sana lahir beberapa varian utama:
- ID3 (Iterative Dichotomiser 3): dikembangkan J. Ross Quinlan (1986). Memakai Entropy dan Information Gain, fokus pada atribut kategorikal, dan tidak menangani missing values secara langsung.
- C4.5: penerus ID3 (Quinlan, 1993). Memakai Gain Ratio, menangani atribut diskrit maupun kontinu, mendukung missing values, dan menyediakan pruning.
- CART (Classification and Regression Trees): diperkenalkan Leo Breiman. Membentuk pohon biner, memakai Gini Impurity, melayani klasifikasi maupun regresi, dan mendukung pruning.
- Soft Decision Tree-ID3 (SDT-ID3): varian modern yang memadukan pohon keputusan dengan teori himpunan fuzzy (soft discretization) untuk menangani ketidakpastian data, seperti keraguan, ketidaktepatan, dan ketidaklengkapan informasi (dikaji antara lain oleh Sari, 2009).
Cara C4.5 Menangani Data Kontinu
Untuk atribut numerik, C4.5 mengurutkan nilai \(v_1, v_2, \dots, v_m\), lalu menguji \(m-1\) kandidat ambang batas (threshold) di antara nilai-nilai yang berurutan:
\[ c = \frac{v_i + v_{i+1}}{2} \]Threshold yang menghasilkan Gain terbesar dipilih sebagai titik pemisah.
Perbandingan Fitur
| Fitur | ID3 | C4.5 | CART | SDT-ID3 |
|---|---|---|---|---|
| Pencetus | J. R. Quinlan (1986) | J. R. Quinlan (1993) | Leo Breiman | Adaptasi teori fuzzy set |
| Tugas | Klasifikasi | Klasifikasi | Klasifikasi dan regresi | Klasifikasi |
| Metrik pemisahan | Entropy, Information Gain | Gain Ratio | Gini Impurity | Fuzzy set / soft discretization |
| Data kontinu | Tidak | Ya (threshold) | Ya (binary split) | Ya (logika fuzzy) |
| Missing values | Tidak | Ya | Ya | Ya (fungsi keanggotaan fuzzy) |
| Pruning | Tidak ada | Ya (post-pruning / pessimistic error) | Ya (cost-complexity) | Bergantung konfigurasi |
Seluruh varian ini kuat memetakan pola data, tetapi pohon yang dibiarkan tumbuh tanpa batas akan menghadapi masalah klasik: overfitting.
5. Mengendalikan Kompleksitas: Overfitting dan Pruning
Overfitting terjadi ketika pohon tumbuh terlalu dalam karena ikut "menghafal" noise dan outlier pada data latih. Hasilnya: akurasi nyaris sempurna pada data latih, tetapi error tinggi pada data baru. Ini adalah Occam's Razor yang dilanggar: model lebih rumit daripada yang dibutuhkan data.
Obatnya adalah pruning (pemangkasan): membuang cabang yang redundan atau tidak signifikan secara statistik. Ada dua pendekatan.
Pre-Pruning (Forward Pruning)
Pertumbuhan cabang dihentikan lebih awal, saat pohon sedang dibangun. Pembentukan simpul berhenti jika nilai pengujian berada di bawah ambang tertentu. Parameter yang lazim dipakai:
- kedalaman maksimum pohon (maximum depth),
- jumlah sampel minimum per simpul (minimum number of objects, minObj),
- uji statistik Chi-square untuk menilai apakah pemisahan signifikan,
- batas tingkat kesalahan (error rate) berdasarkan tingkat kepercayaan statistik.
Post-Pruning (Backward Pruning)
Pohon dibiarkan tumbuh penuh terlebih dahulu, lalu cabang yang tidak signifikan dipangkas setelah konstruksi selesai. Teknik populernya:
- Reduced Error Pruning (REP): data dibagi menjadi data latih (untuk membangun pohon utuh) dan data validasi (untuk menghitung error rate). Sebuah sub-pohon diganti menjadi leaf node jika error pada data validasi tidak bertambah.
- Cost-Complexity Pruning (CCP): memangkas sub-pohon dengan menimbang biaya salah klasifikasi terhadap jumlah simpul. Parameter alpha (
ccp_alphadi scikit-learn) mengatur seberapa agresif pemangkasan; makin besar alpha, makin kecil pohon. - Teknik lain: Error Complexity Pruning, Minimum Error Pruning, dan Cost-based Pruning.
Manfaat Pruning
- Generalisasi lebih baik: model tidak lagi menyesuaikan diri dengan noise, sehingga akurasi pada data baru meningkat.
- Model lebih sederhana: aturan keputusan lebih ringkas dan mudah dibaca manusia.
- Lebih efisien: pohon yang lebih dangkal memakai lebih sedikit memori dan memprediksi lebih cepat.
6. Kelebihan dan Keterbatasan
Decision Tree unggul dalam kemudahan interpretasi, tetapi rapuh terhadap overfitting dan perubahan data. Berikut neracanya:
| Kelebihan | Keterbatasan |
|---|---|
| Mudah dipahami: logika percabangan transparan (white-box) dan mudah dijelaskan kepada pihak non-teknis. | Rentan overfitting: tanpa pruning, pohon menghafal data latih dan kehilangan daya generalisasi. |
| Preprocessing minimal: tidak perlu normalisasi atau standardisasi skala fitur. | Tidak stabil (varians tinggi): perubahan kecil pada data latih dapat mengubah struktur pohon secara drastis. |
| Fleksibel: menangani data kategorikal dan numerik; varian seperti C4.5 menangani missing values. | Komputasi pohon besar mahal: pencarian greedy pada dataset besar berdimensi tinggi memakan waktu dan memori. |
| Seleksi fitur otomatis: atribut paling informatif ditempatkan di bagian atas pohon. | Bias ke atribut banyak kategori: ID3 cenderung memilih atribut dengan kategori unik terbanyak jika tanpa normalisasi. |
| Prediksi cepat: cukup serangkaian perbandingan sederhana dari akar ke daun. | Tidak bisa mengekstrapolasi: pada regresi, tidak dapat memprediksi nilai di luar rentang data latih, dan kurang halus memodelkan pola aditif kontinu. |
| Fondasi ansambel: menjadi building block Random Forest dan Bagging yang menekan varians. |
7. Penutup
Decision Tree adalah titik awal yang ideal untuk belajar kecerdasan buatan: alurnya visual, intuitif, dan transparan. Ia sangat cocok sebagai baseline model pada dataset kecil hingga menengah, terutama ketika keputusan harus bisa dijelaskan.
Ingat tiga hal kunci: (1) pohon memilih pemisah dengan mengukur penurunan ketidakpastian (entropi atau Gini); (2) pohon yang dibiarkan tumbuh bebas akan overfitting, sehingga pruning wajib dipertimbangkan; (3) satu pohon saja tidak stabil. Kelemahan terakhir inilah yang menjadi pintu masuk ke algoritma ansambel seperti Random Forest, Bagging, dan Gradient Boosting, yang menggabungkan banyak pohon untuk hasil yang lebih akurat dan stabil.
Referensi
- Alverina, D. (2017). Perbandingan Algoritma C4.5 dan CART Dalam Memprediksi Kategori Indeks Prestasi Mahasiswa. Skripsi, Universitas Kristen Duta Wacana, Yogyakarta.
- Gifari, J. (2024). Bagaimana Cara Mengatasi Overfitting Dalam Model Decision Tree? Scientify Education.
- Guna, E. A., Ghifary, M. D. D., Sihombing, E. F., & Datubara, A. P. (2023). Implementasi Algoritma Decision Tree untuk Klasifikasi Data Evaluation Car Menggunakan Python. JUSIIK, 1(4), 167-177.
- IBM Data and AI. (2024). Apa itu decision tree? IBM.
- Julianto, W., Yunitarini, R., & Sophan, M. K. (2014). Algoritma C4.5 Untuk Penilaian Kinerja Karyawan. Jurnal SCAN, 9(2), 33-39.
- Liputan6. (2024). Decision Tree Adalah Metode Pengambilan Keputusan yang Efektif, Ini Penjelasannya. Liputan6.com.
- Optimaise. (2025). Kelebihan dan Kekurangan Algoritma Decision Tree. Optimaise Digital Agency.
- Patel, N., & Upadhyay, S. (2012). Study of Various Decision Tree Pruning Methods with their Empirical Comparison in WEKA. IJCA, 60(12), 20-25.
- Sari, L. P. (2009). Analisis dan Implementasi Klasifikasi Data Menggunakan Soft Decision Tree - ID3. Skripsi, Universitas Telkom, Bandung.
Komentar
Posting Komentar