Pohon Keputusan – Kekuatan Mengejutkan dari Aturan Keputusan Bertingkat

 (mlu-explain.github.io)
3 poin oleh GN⁺ 2026-03-02 | 1 komentar | Bagikan ke WhatsApp
  • Struktur yang membagi ruang fitur secara berulang untuk mengklasifikasikan data, dengan memilih pemisahan yang memberi information gain terbesar di setiap tahap
  • Menggunakan entropy untuk mengukur kemurnian (purity) data, lalu menghitung information gain berdasarkan nilai tersebut
  • Algoritma ID3 mencari titik pemisahan optimal dengan menghitung selisih entropy antara node induk dan node anak, lalu memperluas pohon secara rekursif
  • Selain entropy, Gini impurity juga dapat digunakan; keduanya umumnya memberi hasil yang serupa, tetapi berbeda dalam efisiensi komputasi
  • Pemisahan yang berlebihan dapat menyebabkan overfitting dan ketidakstabilan, sehingga hal ini dikurangi dengan pruning atau Random Forest

Konsep dasar pohon keputusan

  • Pohon keputusan membagi data dari atas ke bawah, dan di setiap tahap menerapkan aturan kondisi untuk memisahkan data ke dalam area yang lebih mudah dibedakan
    • Setiap pemisahan ditentukan oleh fitur (feature) tertentu dan nilai ambang (cutoff value)
    • Tujuannya adalah membentuk node yang murni sehingga kelas dapat dipisahkan dengan baik dalam tugas klasifikasi

Definisi dan sifat entropy

  • Entropy adalah metrik untuk mengukur ketidakpastian informasi, yang untuk probabilitas (p_i) didefinisikan sebagai (H = -\sum p_i \log_2(p_i))
  • Sifat utama
    1. Jika hanya satu kejadian yang memiliki probabilitas 1 dan sisanya 0, maka (H=0), artinya tidak ada ketidakpastian
    2. Jika probabilitas semua kejadian sama, entropy mencapai nilai maksimum dan menunjukkan keadaan paling tidak murni
    3. Semakin merata probabilitasnya, semakin besar entropy
  • Karena itu, node murni memiliki entropy 0, sedangkan node campuran memiliki nilai entropy yang tinggi

Information gain dan algoritma ID3

  • Information gain dihitung sebagai selisih entropy sebelum dan sesudah pemisahan, dan menunjukkan efisiensi pemisahan data
    • Rumus: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
  • Tahapan algoritma ID3
    1. Menghitung entropy untuk setiap fitur
    2. Membagi dataset dengan berbagai kriteria pemisahan dan menghitung information gain
    3. Memilih pemisahan dengan information gain terbesar untuk membentuk node keputusan
    4. Membentuk node daun ketika data tidak bisa lagi dipisahkan
    5. Menjalankan proses ini secara rekursif untuk semua subset, tetapi berhenti jika semua elemen berada pada kelas yang sama
  • Sebagai contoh, kondisi Diameter ≤ 0.45 dipilih sebagai pemisahan pertama karena memiliki information gain tertinggi, yaitu 0.574

Gini impurity dan ukuran alternatif

  • Gini impurity adalah alternatif dari entropy, yakni cara lain untuk mengukur ketidakmurnian informasi
    • Tidak memerlukan perhitungan log sehingga lebih cepat secara komputasi
    • Pada dataset yang tidak seimbang, entropy bisa menjadi pilihan yang lebih hati-hati
  • Keduanya umumnya menghasilkan hasil yang serupa

Masalah overfitting dan ketidakstabilan

  • Algoritma ID3 terus melakukan pemisahan untuk meminimalkan entropy, sehingga pohon bisa menjadi terlalu dalam
    • Hal ini memicu overfitting, yang menurunkan kemampuan generalisasi pada data baru
  • Ada juga masalah ketidakstabilan (high variance), di mana perubahan kecil pada data dapat sangat mengubah struktur pohon
    • Contoh: menambahkan Gaussian noise kecil pada 5% data pelatihan saja dapat menghasilkan pohon yang sepenuhnya berbeda
  • Sebagai solusi, pruning dapat digunakan untuk membatasi kedalaman pohon, jumlah daun, jumlah sampel minimum, dan sebagainya

Ekstensi ke Random Forest

  • Untuk mengurangi ketidakstabilan pada satu pohon keputusan, digunakan pendekatan menggabungkan prediksi dari banyak pohon yang dilatih pada sampel data yang berbeda
    • Pendekatan ini disebut Random Forest, yang menawarkan stabilitas tinggi dan kemampuan generalisasi yang baik
  • Ini melengkapi kekurangan pohon keputusan, dan hingga kini dinilai sebagai salah satu algoritma machine learning paling sukses

Kesimpulan dan pembelajaran lanjutan

  • Pohon keputusan adalah model yang mudah diinterpretasikan, cepat dilatih, dan sederhana dalam prapemrosesan
  • Namun, untuk mengatasi overfitting dan ketidakstabilan, diperlukan pruning atau teknik ensemble
  • Tulisan ini tidak membahas pohon untuk regresi, end-cut preference, hyperparameter, dan topik terkait lainnya, sehingga pembelajaran lanjutan melalui materi terkait disarankan

Bacaan terkait

1 komentar

 
GN⁺ 2026-03-02
Komentar Hacker News

  • Saat mempelajari classifier, senjata rahasia yang sangat efektif bagi saya adalah melatih classifier linear yang bagus terlebih dahulu
    Lalu melatih decision tree dengan memakai nilai output non-threshold dari classifier linear itu sebagai satu dimensi fitur tambahan, dan membungkusnya dengan sistem boosted tree
    Dengan begitu, kelemahan decision tree ditutup oleh model linear, dan sebaliknya bagian yang sulit bagi model linear ditangani oleh tree
    Rotasi data atau normalisasi sumbu juga bisa dipertimbangkan, tetapi kebanyakan tidak diperlukan
    Namun, saat fitur sangat sparse, tree kesulitan menemukan titik split

    • Jika dipikir-pikir, ini pendekatan yang mirip dengan yang dipakai dalam reinforcement learning
      Kita menambahkan komputasi ekstra ke state mentah (raw state) untuk membentuk observed state, lalu belajar dari sana
      Misalnya pada game Snake, model dilatih bukan hanya dengan koordinat ular, tetapi juga fitur turunan seperti jumlah jalur pelarian
    • Titik lemah fatal decision tree pada akhirnya adalah feature engineering
      Jika data tidak dibersihkan dan fitur tidak dirancang dengan baik, hasilnya bisa jauh lebih buruk daripada model black-box seperti neural network
      Ironisnya, neural network bisa menemukan fitur laten semacam ini sendiri, tetapi sulit menafsirkan mengapa ia bekerja seperti itu
    • Ada berbagai varian tree untuk tujuan yang berbeda
      Contohnya Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT), dan Hierarchical Mixture of Experts (HME)
    • Saya penasaran apa sebenarnya maksud dari ungkapan “wilayah equi-label memiliki struktur yang terpartisi”
    • Ide ini juga mirip dengan inti dari makalah IRM yang ditulis Arjovsky, Bottou, dan lainnya

  • Sekitar tahun 2010 saat bekerja di CERN, Boosted Decision Tree adalah classifier yang paling populer
    Alasannya keseimbangan antara explainability dan daya ekspresi, dan pada saat itu secara budaya orang enggan memakai neural network untuk analisis fisika
    Sekarang zamannya sudah banyak berubah

    • Perubahan seperti ini agak mengkhawatirkan
      Dalam fisika, yang penting bukan sekadar menyesuaikan kurva dengan baik, tetapi memahami mekanisme kausal
      Sama seperti sistem epicycle milik Ptolemaios yang lebih akurat mencocokkan gerak benda langit, tetapi tidak menjelaskan penyebabnya
    • Saya juga berlatar belakang fisika (teori), dan setelah mencoba decision tree di bidang lain, saya merasa “explainability” agak terlalu dibesar-besarkan
      Begitu depth-nya sedikit lebih dalam, model itu hampir menjadi rimba yang mustahil ditafsirkan
      Neural network juga sama; kita bisa mengikuti operasi internalnya, tetapi tetap tidak tahu mengapa ia mengambil keputusan itu
    • Saya penasaran apakah Boosted Decision Tree dan Boosted Random Forest itu hal yang sama

  • Di situs yang sama juga ada penjelasan tentang Random Forest → mlu-explain/random-forest

  • Fakta menarik: single-bit neural network pada dasarnya adalah decision tree
    Secara teori, sebagian besar neural network bisa “dikompilasi” menjadi rantai if-else, tetapi kapan itu bekerja dengan baik masih belum jelas

    • Saya pernah membaca makalah “neural network adalah decision tree” (arXiv:2210.05189), tetapi pada praktiknya tree-nya menjadi sangat besar
      Ini lebih seperti perluasan konsep, jadi sulit dianggap sebagai pemetaan langsung
      Karena itu akan menarik jika dijelaskan lebih lanjut maksud konkretnya
    • Saya penasaran apakah ada software atau makalah yang benar-benar melakukan transformasi seperti ini. Sepertinya seru untuk proyek akhir pekan

  • Kelebihan terbesar decision tree adalah kecepatannya
    Dalam lingkungan low-latency, saya pernah mencoba mengganti classifier berbasis tree dengan neural network kecil, tetapi walaupun akurasinya sedikit lebih tinggi, latency inferensi neural network lebih dari 100 kali lebih tinggi

    • Selain itu, single decision tree juga mudah di-port langsung ke edge device
      Sebaliknya, tree hasil boosting atau bagging lebih kompleks, dan algoritme ML klasik lain juga kurang portabel

  • Di salah satu buku teks ML (mungkin ESL), decision tree digambarkan seperti ini
    “Dapat ditafsirkan, cepat, bekerja baik pada beragam data, tidak terlalu sensitif terhadap scaling, dan parameter tuning-nya sedikit... tetapi tidak bekerja dengan baik”
    Memang bagging atau boosting bisa menutupi kekurangan ini, tetapi dalam prosesnya sebagian keunggulan aslinya ikut hilang

  • Saya sangat menyukai decision tree. Ini adalah algoritme ML klasik favorit saya
    Saya pernah membuat implementasi paralel fungsional murni dengan GNU Guile → tautan kode
    Namun, di Guile tidak ada hal seperti NumPy atau DataFrame, jadi representasi datanya tidak efisien

    • Saya penasaran dalam hal apa NumPy atau DataFrame lebih unggul dibanding Guile
      Guile cocok untuk manipulasi tree, jadi terasa alami untuk implementasi decision tree
      Namun, jika dikompilasi ke machine code, seharusnya bisa lebih efisien
      Sebagai referensi, Lush(https://lush.sourceforge.net/) atau aiscm(https://wedesoft.github.io/aiscm/) juga layak dilihat

  • Pengambilan keputusan yang samar oleh pakar pun sering kali bisa dimodelkan dengan decision tree sederhana atau decision chain
    Pakarnya sendiri mungkin merasa prosesnya rumit, tetapi dalam kenyataannya tree sederhana sering menjelaskannya dengan lebih baik
    Dulu regresi atau clustering berbasis jarak terlihat lebih canggih, tetapi tree jauh lebih efektif
    Pembahasan terkait ada secara rinci di bab 7 Oxford Handbook of Expertise

    • Dalam visualisasi yang pernah saya lihat, keputusan direpresentasikan sebagai partisi ruang pada bidang 2D
      Pada akhirnya, decision tree adalah struktur yang membagi ruang kemungkinan seperti kD-Tree dan menetapkan tindakan pada tiap wilayah
      Penilaian halus seorang pakar muncul dari detail permukaan batas, tetapi tree tetap memberi pendekatan yang cukup baik

  • Situsnya menarik dan presentasinya bagus
    Hanya saja, kontras warna beberapa teks rendah sehingga sulit dibaca

    • Saya juga berpikir begitu. Firefox Reader View sangat membantu
      Aksesibilitas bukan hanya untuk penyandang disabilitas, tetapi elemen dasar untuk meningkatkan keterbacaan

  • Di era deep learning sekarang, decision tree sedang diremehkan
    Padahal model ini masih dapat ditafsirkan, cepat, dan cukup praktis
    Saya membuat sistem penilaian untuk analisis situs web berbasis tree,
    yang mengevaluasi kondisi seperti “apakah ada meta description?”, “apakah dimuat dalam 3 detik?”, dan “apakah ramah seluler?”
    Pengguna bisa langsung memahami mengapa mereka mendapat skor seperti itu
    Mustahil menjelaskan alasan neural network memberi nilai 73, tetapi tree memudahkannya