berikut penjelasan langkah-demi-langkah (step-by-step) bagaimana Decision Tree bekerja, disertai contoh perhitungan entropi / information gain, pseudocode singkat, tips hyperparameter, dan contoh kode Python kecil.

Inti singkat

Decision Tree membagi data berulang-ulang menjadi subset dengan aturan kondisi (mis. fitur ≤ t) sehingga setiap node menjadi “lebih murni” (hanya berisi satu kelas atau proporsi kelas serupa). Pemilihan pemisahan dibuat dengan mengukur penurunan impurity (mis. information gain berbasis entropi atau Gini impurity).

Langkah-langkah training (root → leaf)

1. Mulai di root node dengan seluruh data. Hitung impurity awal (contoh: entropi atau Gini).

2. Untuk setiap fitur, cari calon pemisahan terbaik:

   • Jika fitur kontinu: urutkan nilai unik, coba ambang (threshold) di titik tengah antara nilai berturut-turut.

   • Jika fitur kategorikal: coba pemisahan satu-per-satu atau penggabungan kategori (tergantung implementasi).

3. Untuk setiap calon split, bagi data menjadi dua (kiri/kanan) dan hitung impurity anak (entropy/Gini).

4. Hitung weighted impurity anak:
   Isplit=nLnI(L)+nRnI(R)I_{split} = \frac{n_{L}}{n} I(L) + \frac{n_{R}}{n} I(R)Isplit​=nnL​​I(L)+nnR​​I(R).
   Kemudian hitung penurunan impurity (mis. Information Gain):
   ΔI=I(parent)−Isplit\Delta I = I(parent) - I_{split}ΔI=I(parent)−Isplit​.
   
   

5. Pilih split dengan ΔI\Delta IΔI terbesar (atau Gini decrease terbesar). Buat node internal dengan aturan tersebut.

6. Bagi subset ke child node dan ulangi rekursif untuk masing-masing child sampai memenuhi kriteria berhenti:

   • Semua contoh di node punya kelas sama, atau

   • depth maksimum tercapai, atau

   • jumlah sampel di node < min_samples_split, atau

   • impurity sudah sangat rendah.

7. Atur leaf: jika berhenti, tetapkan label (mayoritas) atau probabilitas kelas di leaf.

8. (Opsional) Pruning: potong cabang yang overfit (pre-prune dengan batasan di langkah berhenti, atau post-prune menggunakan data validasi).
   Formula impurity (yang umum dipakai)

• Entropy (untuk kelas-k):
  H=−∑i=1kpilog⁡2piH = -\sum_{i=1}^k p_i \log_2 p_iH=−∑i=1k​pi​log2​pi​

• Gini impurity:
  G=1−∑i=1kpi2G = 1 - \sum_{i=1}^k p_i^2G=1−∑i=1k​pi2​

• Information Gain (IG):
  IG=H(parent)−∑c∈{L,R}ncnH(c)IG = H(parent) - \sum_{c \in \{L,R\}} \frac{n_c}{n} H(c)IG=H(parent)−∑c∈{L,R}​nnc​​H(c)

Contoh perhitungan (toy) —
hitung entropi dan information gain

Misal dataset 10 contoh, 2 kelas: Positif (P) = 6, Negatif (N) = 4.

1. Entropi parent:
   pP=6/10=0.6p_P = 6/10 = 0.6pP​=6/10=0.6, pN=4/10=0.4p_N = 4/10 = 0.4pN​=4/10=0.4.
   Hitung log₂:

   • log⁡2(0.6)=ln⁡0.6ln⁡2≈−0.736965594\log_2(0.6) = \dfrac{\ln 0.6}{\ln 2} \approx -0.736965594log2​(0.6)=ln2ln0.6​≈−0.736965594.
     kontribusi =−0.6×(−0.736965594)=0.4421793564= -0.6 \times (-0.736965594) = 0.4421793564=−0.6×(−0.736965594)=0.4421793564.

   • log⁡2(0.4)≈−1.321928095\log_2(0.4) \approx -1.321928095log2​(0.4)≈−1.321928095.
     kontribusi =−0.4×(−1.321928095)=0.5287712380= -0.4 \times (-1.321928095) = 0.5287712380=−0.4×(−1.321928095)=0.5287712380.
     Jadi H(parent)≈0.4421793564+0.5287712380=0.9709505944H(parent) \approx 0.4421793564 + 0.5287712380 = 0.9709505944H(parent)≈0.4421793564+0.5287712380=0.9709505944 (≈ 0.971 bit).

2. Misal sebuah split membagi jadi: kiri = 4 P, 0 N (size 4); kanan = 2 P, 4 N (size 6).

   • Entropi kiri: semua P → H(L)=0H(L)=0H(L)=0.

   • Entropi kanan: pP=2/6≈0.3333333, pN=4/6≈0.6666667p_P=2/6\approx 0.3333333,\ p_N=4/6\approx 0.6666667pP​=2/6≈0.3333333, pN​=4/6≈0.6666667.

     • log⁡2(1/3)≈−1.5849625\log_2(1/3)\approx -1.5849625log2​(1/3)≈−1.5849625 → kontribusi =−13×(−1.5849625)≈0.5283208333= -\tfrac{1}{3}\times(-1.5849625)\approx 0.5283208333=−31​×(−1.5849625)≈0.5283208333.

     • log⁡2(2/3)≈−0.5849625\log_2(2/3)\approx -0.5849625log2​(2/3)≈−0.5849625 → kontribusi =−23×(−0.5849625)≈0.389975= -\tfrac{2}{3}\times(-0.5849625)\approx 0.389975=−32​×(−0.5849625)≈0.389975.
       Jadi H(R)≈0.5283208333+0.389975=0.9182958333H(R)\approx 0.5283208333 + 0.389975 = 0.9182958333H(R)≈0.5283208333+0.389975=0.9182958333.
       
       

   • Weighted child entropy: 410⋅0+610⋅0.9182958333≈0.5509775\frac{4}{10}\cdot0 + \frac{6}{10}\cdot0.9182958333 \approx 0.5509775104​⋅0+106​⋅0.9182958333≈0.5509775.

   • Information Gain = 0.9709505944−0.5509775≈0.41997309440.9709505944 - 0.5509775 \approx 0.41997309440.9709505944−0.5509775≈0.4199730944.

Split ini meningkatkan “kemurnian” sebesar ≈ 0.420 bit; Decision Tree akan membandingkan IG untuk semua calon split dan memilih yang terbesar.

Prediksi (inference)

Untuk sampel baru: mulai di root → cek aturan fitur_i ≤ threshold → turun ke child kiri/kanan sesuai aturan → ulang sampai mencapai leaf → keluarkan prediksi (label mayoritas di leaf) atau probabilitas (proporsi kelas di leaf).

Hyperparameter penting & tips praktis

• criterion: 'gini' (CART, cepat) atau 'entropy' (ID3-style/info gain). Hasil mirip biasanya.
  
  

• max_depth: mencegah overfitting (pre-prune).

• min_samples_split, min_samples_leaf: batasi split pada node kecil.

• max_features: mengurangi variance (serupa idea random forest).

• class_weight: untuk data tidak seimbang.
  Tips: tidak perlu feature scaling (tree invariant terhadap skala), tapi raw outliers bisa memengaruhi thresholding. Untuk performa dan generalisasi, sering gunakan ensemble (Random Forest / Gradient Boosting).
  
  Kelebihan & Kekurangan (ringkas)

• Kelebihan: mudah diinterpretasi (visualisasi), menangani fitur kategorikal dan kontinu, tidak perlu scaling.

• Kekurangan: mudah overfit, sensitif pada variasi data (variance tinggi), pembagian greedy lokal (tidak global optimal).