ENID
Lensa ML

Decision Tree dan Split

Langkah 1 dari 6: Apa Itu Decision Tree?

Node, branch, dan leaf

-3-2-10123-3-2-10123
Depth
1
Area
2
Akurasi
67%

Decision tree membagi data dengan mengajukan pertanyaan ya/tidak. Pada depth 1, ia membuat satu potongan yang sejajar sumbu, dan setiap area berwarna memprediksi satu kelas. Satu potongan tidak bisa memisahkan cluster yang letaknya berselang-seling.

Geser max depth dari 1 ke 4 dan hitung jumlah areanya. Tree dengan depth d punya paling banyak 2^d leaf, jadi depth 4 memungkinkan sampai 16, tetapi tree ini berhenti di 8 karena sebagian node sudah murni dan tidak perlu di-split lagi. Setiap leaf adalah satu persegi panjang di ruang data. Membuat prediksi berarti berjalan dari root ke leaf, yang butuh paling banyak d perbandingan, jadi inference pada tree sangat cepat. Jalur itu juga menjelaskan prediksinya: isinya daftar pertanyaan yang dijawab input sepanjang perjalanan turun.

Langkah 2 dari 6: Kriteria Split

Gini impurity dan information gain

x = 0.0L: 15m + 0hR: 0m + 15h
Gini kiri
0.000
Gini kanan
0.000
Gini berbobot
0.000
Info gain
1.000

Split yang kuat: garisnya jatuh di antara kedua cluster. Sisi kiri sebagian besar merah (kemurnian 100%) dan sisi kanan sebagian besar hijau (kemurnian 100%). Gini berbobot 0,00 berarti node anak jauh lebih murni daripada node induk.

Geser split threshold x, lalu klik kartu mana saja untuk melihat rumusnya. Gini impurity adalah 1 − Σ p_i², dan entropy adalah −Σ p_i log₂ p_i. Untuk dua kelas dengan perbandingan 50/50, Gini bernilai 0,5 dan entropy bernilai 1 bit, yaitu nilai node induk di sini, sehingga information gain mencapai maksimum 1,0 untuk split yang sempurna. Threshold apa pun di celah antara x ≈ −0.9 dan x ≈ 0.8 mencapai nilai itu. CART, algoritma di balik tree scikit-learn, memakai Gini secara default, sedangkan ID3 dan C4.5 memakai information gain. Keduanya biasanya memilih split yang sama.

Langkah 3 dari 6: Menumbuhkan Tree

Recursive partitioning

Struktur treey≤0.1Ruang data-3-2-10123-3-2-10123
Depth
1
Leaf
2
Akurasi
67%
Penurunan Gini
0.056

Dengan satu split, root mengajukan satu pertanyaan terbaik yang ditemukannya. Kedua anaknya adalah leaf, dan masing-masing masih mencampur kedua kelas.

Naikkan max depth satu tingkat demi satu tingkat, lalu ikuti diagram tree di kiri sambil melihat ruang data di kanan. Algoritmanya greedy: di setiap node, ia mencoba setiap feature dan setiap titik tengah di antara nilai yang sudah diurutkan, menyimpan split terbaik, dan tidak pernah meninjaunya lagi. Cara ini membuat training cepat, tetapi tree yang dihasilkan belum tentu yang terbaik. Tree ini memilih split berdasarkan information gain, dan kartu penurunan Gini mengukur hasilnya. Implementasi sungguhan juga berhenti berdasarkan aturan seperti jumlah minimum sampel per leaf.

Langkah 4 dari 6: Overfitting pada Tree

Saat tree menghafal noise

traintest
Depth
2
Akurasi train
79%
Akurasi test
92%
Selisih
-13%

Tree yang dangkal: train 79%, test 92%. Satu garis batas mengabaikan 8 titik training yang salah label, jadi akurasi test mengalahkan train.

Geser max depth dari 1 ke 8 dan lihat kartu akurasi train dan test saling menjauh. Training set berisi 38 titik, dengan 8 di antaranya ditempatkan jauh di wilayah kelas lain sebagai label noise, dan test set (bentuk wajik) berisi 26 titik bersih. Setiap tingkat tambahan membuat tree bisa membungkus lebih banyak titik noise dalam area kecilnya sendiri. Tree yang dalam punya bias rendah dan variance tinggi: perubahan kecil pada data training bisa menghasilkan tree yang sangat berbeda. Random forest dirancang untuk mengatasi kelemahan ini.

Langkah 5 dari 6: Pruning

Menyederhanakan tree demi generalisasi

traintest
Alpha
0.000
Leaf
18/18
Akurasi train
92%
Akurasi test
77%

Tanpa pruning: ini tree overfit dengan depth 8 dari langkah 4, dengan 18 leaf. Train 92%, tetapi test hanya 77%. Naikkan alpha untuk mulai membuang branch yang mengikuti noise.

Geser alpha naik dari 0 pada skala log-nya dan lihat jumlah leaf turun. Cost-complexity pruning pada CART meminimalkan R(T) + α·|T|. R(T) adalah error training tree, dan |T| adalah jumlah leaf-nya, jadi setiap leaf harus sepadan dengan biayanya. Demo ini menjalankan prosedur weakest-link CART: terus meruntuhkan subtree yang menambah error training paling sedikit per leaf yang dibuang, sampai biaya itu melebihi alpha. Pada alpha = 0.01, tree turun dari 18 leaf menjadi 6 dan akurasi test naik dari 77% ke 85%. Setelah sekitar 0,013, hanya split di root yang tersisa, dengan akurasi train 79% dan test 92%. Dalam praktik, alpha dipilih dengan cross-validation, misalnya lewat parameter ccp_alpha di scikit-learn.

Langkah 6 dari 6: Decision Boundary

Area yang sejajar sumbu

traintest
Depth
3
Area
7
Akurasi train
97%
Akurasi test
90%

Depth yang lebih besar menghasilkan persegi panjang sejajar sumbu yang lebih halus. Berbeda dari SVM atau neural network, tree tidak bisa menggambar garis batas diagonal atau melengkung, jadi ia butuh banyak split untuk mendekatinya.

Ubah max depth dan perhatikan bentuk grid berwarnanya. Setiap segmen garis batas pasti horizontal atau vertikal karena setiap split menguji satu feature. Garis batas diagonal seperti x = y butuh tangga dari banyak split, sedangkan logistic regression atau SVM linear menggambarnya dengan satu garis. Oblique tree, yang melakukan split pada kombinasi berbobot beberapa feature, menghindari bentuk tangga itu, tetapi lebih mahal untuk di-train. Ensemble juga menghaluskannya: merata-ratakan ratusan tree dalam random forest menghasilkan garis batas yang jauh lebih halus daripada tree tunggal.

Apa itu decision tree?

Decision tree adalah model yang membuat prediksi dengan mengajukan serangkaian pertanyaan ya/tidak tentang input, misalnya "apakah x ≤ 0.4?". Setiap internal node berisi satu pertanyaan, setiap branch adalah satu jawaban, dan setiap leaf berisi satu prediksi: kelas mayoritas untuk klasifikasi atau rata-rata target untuk regresi. Training menumbuhkan tree secara greedy: di setiap node, ia memilih pertanyaan yang paling baik memisahkan label training.

Tree bisa menangani feature numerik maupun kategorikal, tidak butuh feature scaling, dan bisa dibaca sebagai kumpulan aturan if-then. Karena itu, tree populer untuk penilaian kredit, triase medis, dan situasi lain yang keputusannya harus bisa dijelaskan. Satu tree yang dalam mudah overfit, jadi tree lebih sering dipakai sebagai komponen model yang lebih besar. Random forest merata-ratakan ratusan tree, sedangkan library gradient boosting seperti XGBoost dan LightGBM menjumlahkannya satu per satu. Ensemble seperti ini masih termasuk model terkuat untuk data tabular.

Ide utama

  • Decision tree membuat prediksi dengan mengarahkan input melewati serangkaian pertanyaan feature dan threshold sampai ke leaf.
  • Setiap split dipilih secara greedy untuk memberi penurunan impurity terbesar, yang diukur dengan Gini atau entropy.
  • Setiap split menguji satu feature, jadi area keputusannya berupa persegi panjang yang sejajar sumbu.
  • Tree yang lebih dalam makin mendekati data training dan makin mudah menghafal noise.
  • Pruning serta batas depth atau ukuran leaf mengorbankan sedikit akurasi training demi akurasi test yang lebih baik.
  • Tree tidak butuh feature scaling dan menjadi base learner pada random forest dan gradient boosting.

Pertanyaan umum

Apakah decision tree bisa dipakai untuk regresi?

Bisa. Regression tree memprediksi rata-rata target dari titik training di setiap leaf dan memilih split yang paling menurunkan squared error. Prediksinya berupa fungsi tangga yang nilainya konstan di setiap area. CART menangani klasifikasi dan regresi dengan algoritma yang sama.

Apakah decision tree butuh feature scaling?

Tidak. Split membandingkan satu feature dengan threshold, jadi transformasi monoton pada feature itu, seperti standardisasi atau mengambil log-nya, tidak mengubah himpunan split yang mungkin. Metode berbasis jarak seperti k-nearest neighbors dan SVM berbeda: keduanya butuh feature yang sudah di-scale.

Bagaimana decision tree menangani feature kategorikal?

Tree bisa melakukan split pada feature kategorikal dengan mengirim sebagian kategori ke kiri dan sisanya ke kanan. Banyak library mengharapkan input numerik, jadi kategori sering diubah dulu dengan one-hot encoding atau ordinal encoding. LightGBM dan CatBoost bisa melakukan split langsung pada feature kategorikal.

Bagaimana feature importance dihitung pada decision tree?

Ukuran yang umum menjumlahkan penurunan impurity dari setiap split yang memakai suatu feature, diberi bobot sesuai jumlah sampel yang sampai ke split itu, lalu menormalkan totalnya. Hitungannya murah, tetapi cenderung memihak feature dengan banyak nilai berbeda. Permutation importance, yang mengukur seberapa jauh akurasi turun ketika nilai satu feature diacak, sering dipakai sebagai pembanding.

Penjelasan terkait

Referensi

  1. James, Witten, Hastie & Tibshirani, "An Introduction to Statistical Learning", chapter 8: Tree-Based Methods
  2. Quinlan (1986), "Induction of Decision Trees", Machine Learning
  3. Breiman, Friedman, Olshen & Stone (1984), "Classification and Regression Trees"

Terakhir diperbarui