Decision Tree

Bayangkan Anda diminta menyaring spam tanpa rumus apa pun — hanya boleh mengajukan pertanyaan ya/tidak, satu per satu. Pertanyaan pertama yang mungkin terlintas: “apakah email memuat lebih dari lima tautan?” Lalu, jika masih ragu: “apakah kata promosinya banyak?” Decision tree mengotomatiskan proses berpikir tersebut: algoritme mencari pertanyaan paling informatif, membelah data berdasarkan jawabannya, lalu mengulanginya sampai keputusan bisa diambil. Hasilnya adalah model yang dibaca seperti diagram alur — alasan utama decision tree menjadi favorit saat interpretasi penting. Balikannya, pohon yang tumbuh tanpa batas sangat pandai menghafal data, dan chapter ini akan memperlihatkan tanda-tandanya secara terukur.

Pemecahan Rekursif Ruang Fitur #

Sebuah decision tree terdiri dari simpul keputusan (decision node) yang memuat satu pertanyaan tentang satu fitur, dan daun (leaf) yang memuat prediksi final. Pelatihan berlangsung rekursif: pada tiap simpul, algoritme mencoba semua pertanyaan kandidat — semua fitur, semua titik potong — lalu memilih yang menghasilkan belahan paling “murni”. Data terbelah dua, tiap belahan diproses ulang dengan cara yang sama, hingga berhenti pada daun yang isinya mayoritas satu kelas; label daun adalah kelas mayoritas tersebut.

Konsekuensi geometrinya penting dipahami: setiap pertanyaan membelah ruang fitur dengan bidang tegak lurus sumbu (axis-aligned). “Tautan <= 5” adalah garis vertikal pada peta dua fitur; pertanyaan kedua membelah lagi dengan garis horizontal. Batas keputusan pohon akhirnya berbentuk tangga — wilayah persegi sambung menyambung — berbeda dari garis miring pada regresi logistik. Sebuah garis diagonal 45 derajat, misalnya, harus didekati dengan banyak anak tangga.

Mengukur Kemurnian Simpul #

“Paling murni” perlu definisi kuantitatif. Dua ukuran standar: Gini impurity dan entropy. Untuk sebuah simpul berisi proporsi kelas p₁, p₂, …, pK:

Gini(node)  = 1 - Σk pk²
Entropy     = -Σk pk * log2(pk)

Ukuran Gini berpikir begini: ambil satu titik acak dari simpul, tebak kelasnya secara acak sesuai proporsi — peluang salah menebak adalah nilainya. Simpul murni (satu kelas saja) bernilai 0; simpul 50:50 bernilai maksimum 0,5 (binier). Entropy dari statistika informasi berperilaku serupa: 0 saat murni, 1 bit saat 50:50.

Mari hitung dengan tangan pada simpul akar data contoh kita: 10 email, 5 ham dan 5 spam, jadi p₁ = p₂ = 0,5.

Gini(akar) = 1 - (0.5)² - (0.5)² = 0.500

Algoritme lalu menemukan pertanyaan “tautan <= 5.00” sebagai belahan terbaik. Belahan kiri berisi 4 email, semuanya ham — simpul murni, Gini = 1 - 1² - 0² = 0. Belahan kanan berisi 6 email: 1 ham dan 5 spam, sehingga p₁ = 1/6 dan p₂ = 5/6:

Gini(kanan) = 1 - (1/6)² - (5/6)² = 1 - 0.028 - 0.694 = 0.278
Gini tertimbang = (4/10) * 0 + (6/10) * 0.278 = 0.167

Information gain adalah penurunan impurity: 0,500 - 0,167 = 0,333 — angka yang cukup besar untuk satu pertanyaan. Pilihan antara Gini dan entropy hampir tidak pernah mengubah struktur pohon secara berarti; Gini adalah bawaan scikit-learn karena sedikit lebih murah dihitung.

Pohon yang Tumbuh Tanpa Batas #

Kapan rekursi berhenti? Jawabannya menentukan karakter model. Tanpa batasan, pohon tumbuh sampai setiap daun murni — dan itulah definisi mekanis dari menghafal: dengan cukup banyak belahan, satu daun bisa khusus menampung satu titik data, termasuk titik bisingnya. Email nyata selalu punya pengecualian; pohon yang dalam akan menafsirkan setiap pengecualian sebagai aturan. Materi Overfitting dan Underfitting di Section Dasar Machine Learning membahas gejala umumnya; pada pohon, obatnya berupa hyperparameter pemberhenti: max_depth membatasi jumlah pertanyaan bertingkat, min_samples_leaf mewajibkan tiap daun memuat minimal N data. Kedua parameter ini membuat pohon berhenti lebih awal dan terpaksa membuat aturan yang lebih umum.

Sekarang mari kita buktikan cerita overfitting itu dengan eksperimen kecil yang dibaca langsung dari aturan pohonnya:

# Decision Tree: aturan bertingkat, tanda-tanda overfitting, dan export_text.
# Kisah: menyaring spam dari jumlah tautan dan jumlah kata promosi.

import numpy as np
from sklearn.tree import DecisionTreeClassifier, export_text

# Data latih: 10 email. Struktur sebenarnya sederhana:
# spam ketika jumlah tautan >= 6, TETAPI email (7, 1) adalah ham bising
# (pengecualian nyata di dunia nyata) yang berada di wilayah spam.
X_latih = np.array([
    [1, 2], [2, 5], [3, 1], [4, 4], [7, 1],    # ham
    [6, 5], [7, 8], [8, 3], [9, 6], [10, 4],   # spam
])
y_latih = np.array([0, 0, 0, 0, 0, 1, 1, 1, 1, 1])

# Data uji terpisah, mengikuti aturan sebenarnya (tautan >= 6 -> spam).
X_uji = np.array([[2, 3], [3, 5], [9, 1], [7, 6]])
y_uji = np.array([0, 0, 1, 1])

# Model A: pohon dangkal (hanya satu pertanyaan).
model_dangkal = DecisionTreeClassifier(max_depth=1, random_state=42)
model_dangkal.fit(X_latih, y_latih)

# Model B: pohon tumbuh bebas sampai setiap daun murni.
model_dalam = DecisionTreeClassifier(max_depth=None, random_state=42)
model_dalam.fit(X_latih, y_latih)

print("Perbandingan kedalaman pohon:")
print("  model           akurasi latih   akurasi uji")
for nama, model in [("max_depth=1", model_dangkal),
                    ("max_depth=None", model_dalam)]:
    print(f"  {nama:<16} {model.score(X_latih, y_latih):>11.2f}   "
          f"{model.score(X_uji, y_uji):>10.2f}")

print("\nAturan pohon max_depth=None (hasil export_text):")
print(export_text(model_dalam, feature_names=["tautan", "kata_promosi"]))

print("Pentingnya fitur (impurity-based, max_depth=None):")
for nama, skor in zip(["tautan", "kata_promosi"],
                      model_dalam.feature_importances_):
    print(f"  {nama:<12} {skor:.3f}")

Output yang Dihasilkan:

Perbandingan kedalaman pohon:
  model           akurasi latih   akurasi uji
  max_depth=1             0.90         1.00
  max_depth=None          1.00         0.75

Aturan pohon max_depth=None (hasil export_text):
|--- tautan <= 5.00
|   |--- class: 0
|--- tautan >  5.00
|   |--- kata_promosi <= 2.00
|   |   |--- class: 0
|   |--- kata_promosi >  2.00
|   |   |--- class: 1

Pentingnya fitur (impurity-based, max_depth=None):
  tautan       0.667
  kata_promosi 0.333

Mari kita telaah baris-baris kode di atas:

1. Baris 10–14 (X_latih, y_latih): sepuluh email dengan struktur yang kita ketahui pasti — spam ketika tautan >= 6 — ditambah satu email ham bising di (7, 1) yang menyusup ke wilayah spam. Derau semacam ini adalah bahan bakar overfitting.
2. Baris 17–18 (X_uji, y_uji): empat email uji mengikuti aturan sebenarnya, termasuk email spam (9, 1) yang kebetulan miskin kata promosi — email inilah nantinya yang menjadi ujian bagi pohon yang terlalu dalam.
3. Baris 21–22 (max_depth=1): pohon hanya boleh mengajukan satu pertanyaan — versi paling ringkas dari model.
4. Baris 25–26 (max_depth=None): pohon bebas tumbuh sampai seluruh daun murni; inilah pohon yang berpotensi menghafal.
5. Baris 30–33 (perbandingan skor): kedua model dievaluasi pada data latih dan data uji yang sama persis — hanya kedalaman yang berbeda.
6. Baris 35–36 (export_text): fungsi dari sklearn.tree ini mencetak seluruh aturan pohon sebagai teks menjorok — dokumentasi model yang bisa dibaca manusia tanpa alat bantu.
7. Baris 38–41 (feature_importances_): skor kepentingan fitur berbasis impurity dinormalisasi sehingga berjumlah 1.

Angka pada tabel adalah pola overfitting klasik dalam bentuk paling murni. Pohon dangkal mencetak akurasi latih 0,90 — satu galat, yaitu email bising (7, 1) yang ditebak spam — tetapi akurasi uji sempurna 1,00. Pohon dalam membalik keadaan: akurasi latih naik ke 1,00 (semua daun murni) sementara akurasi uji anjlok ke 0,75. Menukar satu galat latih dengan satu galat uji — itulah harga menghafal derau.

Aturan export_text menjelaskan mengapa. Pohon dangkal hanya bertanya tautan <= 5.00: di bawahnya ham, di atasnya spam — persis aturan sebenarnya. Pohon dalam menambah pertanyaan kedua, kata_promosi <= 2.00, semata-mata untuk mengakomodasi satu email bising: email dengan tautan banyak tetapi kata promosi sedikit dinyatakan ham. Aturan tambahan itu cocok untuk si pengecualian, tetapi salah menyangkal email uji (9, 1) — spam sungguhan yang juga miskin kata promosi. Satu pengecualian di data latih menjadi aturan bohong yang menghukum data baru.

Skor kepentingan fitur juga informatif: tautan 0,667 dan kata_promosi 0,333 — persis proporsi information gain yang kita hitung dengan tangan tadi (0,333 dari total 0,500 penurunan impurity pada simpul akar). Kedua angka itu bukan kebetulan; feature importance versi impurity memang menjumlahkan seluruh penurunan yang ditimbulkan tiap fitur.

Decision tree membelah ruang fitur dengan tangga tegak lurus sumbu. Algoritme penutup section ini mencari sesuatu yang lebih ambisius: satu bidang pemisah dengan margin terlebar, bahkan memproyeksikan data ke dimensi lebih tinggi demi menemukannya. Mari kita masuki Support Vector Machine.