Decision Tree Induction (Pohon Keputusan)

Capaian Pembelajaran

Setelah minggu ini kamu bisa:

1. Menjelaskan proses klasifikasi dua tahap: pelatihan (learning) dan prediksi.
2. Menghitung entropy, information gain, gain ratio, dan Gini impurity secara manual.
3. Membangun pohon keputusan (ID3) langkah demi langkah.
4. Menentukan titik split terbaik untuk atribut numerik.
5. Menjelaskan overfitting dan teknik pruning; melatih & memvisualisasikan pohon dengan scikit-learn.

1. Klasifikasi: Gambaran Umum

Klasifikasi = memprediksi label kategori (kelas) dari data berdasarkan contoh berlabel (supervised learning).

Data latih berlabel ──► [Algoritma pembelajaran] ──► Model (pohon/aturan)
Data baru tanpa label ──► [Model] ──► Prediksi kelas

Contoh: churn ya/tidak, email spam/bukan, kredit layak/tidak.

Bedakan dengan regresi (prediksi nilai numerik, mis. harga).

2. Struktur Pohon Keputusan

• Root node: atribut pertama yang diuji.
• Internal node: uji pada sebuah atribut.
• Cabang: hasil uji (nilai atribut / kondisi ≤ t).
• Leaf: label kelas.

Setiap jalur root → leaf = satu aturan IF-THEN, mis. IF outlook = Sunny AND humidity = High THEN play = No.

Kelebihan: mudah diinterpretasi, tidak perlu scaling, menangani data campuran. Kekurangan: mudah overfit, tidak stabil (data sedikit berubah → pohon berubah).

3. Algoritma Umum (Top-Down, Greedy, Rekursif — Hunt's algorithm)

BangunPohon(D, atribut):
    if semua data D berkelas sama c:   return Leaf(c)
    if atribut habis:                  return Leaf(kelas mayoritas D)
    A = atribut terbaik menurut ukuran seleksi (gain / gain ratio / gini)
    buat node uji A
    for setiap nilai v dari A:
        Dv = data D dengan A = v
        if Dv kosong: tambahkan Leaf(kelas mayoritas D)
        else: tambahkan BangunPohon(Dv, atribut − {A})

Inti algoritma: ukuran seleksi atribut — atribut mana yang paling "memurnikan" data?

4. Entropy & Information Gain (ID3)

Entropy mengukur ketidakmurnian (ketidakpastian) himpunan data D dengan m kelas:

Info(D) = − Σ pᵢ · log₂(pᵢ)

• Semua data satu kelas → entropy 0 (murni).
• Dua kelas 50:50 → entropy 1 (paling tidak pasti).

Setelah dipecah oleh atribut A menjadi v partisi:

Info_A(D) = Σⱼ (|Dⱼ| / |D|) · Info(Dⱼ)

Information Gain: Gain(A) = Info(D) − Info_A(D) → pilih atribut dengan gain terbesar.

Contoh: Play Tennis (14 data: 9 Yes, 5 No)

Info(D) = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = 0.410 + 0.530 = **0.940**

Atribut outlook:

Info_outlook(D) = (5/14)(0.971) + (4/14)(0) + (5/14)(0.971) = 0.694 Gain(outlook) = 0.940 − 0.694 = **0.246**

Hasil semua atribut:

→ outlook menjadi root. Cabang Overcast langsung murni (Yes). Rekursi pada Sunny (terpilih humidity) dan Rain (terpilih wind):

outlook
├── Sunny    → humidity
│              ├── High   → No
│              └── Normal → Yes
├── Overcast → Yes
└── Rain     → wind
               ├── Strong → No
               └── Weak   → Yes

5. Gain Ratio (C4.5)

Information gain bias ke atribut dengan banyak nilai (mis. id_pelanggan → setiap partisi murni → gain maksimal, tetapi tidak berguna).

C4.5 menormalisasi dengan split info:

SplitInfo_A(D) = − Σⱼ (|Dⱼ|/|D|) · log₂(|Dⱼ|/|D|)

GainRatio(A) = Gain(A) / SplitInfo_A(D)

Contoh outlook: SplitInfo = −2·(5/14)log₂(5/14) − (4/14)log₂(4/14) = 1.577 → GainRatio = 0.246/1.577 = 0.156.

C4.5 juga menangani atribut numerik, nilai hilang, dan melakukan pruning.

6. Gini Impurity (CART)

Gini(D) = 1 − Σ pᵢ²

Gini setelah split (CART selalu biner):

Gini_A(D) = (|D₁|/|D|)·Gini(D₁) + (|D₂|/|D|)·Gini(D₂)

Pilih split dengan Gini_A terkecil (penurunan impurity terbesar ΔGini = Gini(D) − Gini_A(D)).

Contoh: Gini(play) = 1 − (9/14)² − (5/14)² = **0.459**.

Split humidity (High: 3 Yes/4 No, Normal: 6 Yes/1 No):

• Gini(High) = 1 − (3/7)² − (4/7)² = 0.490
• Gini(Normal) = 1 − (6/7)² − (1/7)² = 0.245
• Gini_humidity = 0.5·0.490 + 0.5·0.245 = 0.367 → ΔGini = 0.092

7. Atribut Numerik

Untuk atribut kontinu (mis. umur), cari threshold t terbaik:

1. Urutkan nilai unik.
2. Kandidat t = titik tengah dua nilai berurutan: (aᵢ + aᵢ₊₁)/2.
3. Untuk tiap t, hitung gain/gini dari split A ≤ t vs A > t.
4. Pilih t terbaik.

Contoh: umur = [22, 25, 30, 35, 40, 50], beli = [N, N, Y, Y, Y, N]. Kandidat t = 23.5, 27.5, 32.5, 37.5, 45. Pada t = 27.5: kiri {N, N} murni, kanan {Y, Y, Y, N} entropy 0.811 → Info = (4/6)(0.811) = 0.541; Gain = 1 − 0.541 = 0.459 (terbaik).

8. Overfitting & Pruning

Pohon yang terlalu dalam menghafal noise data latih → akurasi latih tinggi, akurasi uji rendah.

9. Decision Tree di scikit-learn

from sklearn.tree import DecisionTreeClassifier, plot_tree, export_text

model = DecisionTreeClassifier(criterion="entropy", max_depth=4, random_state=0)
model.fit(X_train, y_train)
print(export_text(model, feature_names=list(X_train.columns)))
model.feature_importances_

Catatan: scikit-learn membutuhkan fitur numerik → gunakan one-hot / ordinal encoding untuk kategorikal.

Ringkasan

• Entropy 0 = murni, 1 = paling campur (2 kelas). Gain = penurunan entropy.
• ID3 → information gain; C4.5 → gain ratio (atasi bias banyak nilai); CART → Gini, split biner.
• Atribut numerik: uji threshold titik tengah.
• Kendalikan overfitting dengan pre-pruning (max_depth) atau post-pruning (ccp_alpha).

Bacaan

• Han, Kamber & Pei — Bab 8.2 (Decision Tree Induction).
• Quinlan (1986) — Induction of Decision Trees; Breiman dkk. (1984) — CART.

Tugas Minggu Ini

1. Kerjakan lab.ipynb (visualisasi pohon & evaluasi akurasi).
2. Kerjakan kuis (di web, atau baca quiz.json).
3. Isi exercise.py, lalu cek: python check.py 6