🌳 Decision Tree

Model berupa rangkaian pertanyaan if-else — paling mudah dijelaskan ke manusia.

🎬 Animasi: Decision Tree: Membagi Data

Pohon memilih split (fitur + ambang) yang paling ‘murnikan’ data di tiap cabang; daun = keputusan akhir.

📌 1. Konsep: Rangkaian Pertanyaan

Contoh: "Apakah harus bawa payung?"

            [hujan di radar?]
           /              \
        ya                 tidak
        ↓                   ↓
    BAWA PAYUNG      [awan tebal?]
                        /        \
                     ya           tidak
                     ↓            ↓
               BAWA (siaga)   TIDAK BAWA

Setiap cabang = satu pertanyaan (fitur ≤ threshold?)
Setiap daun  = satu keputusan (label mayoritas di titik itu)

Keunggulan: interpretable (bisa ditunjukkan ke bos/pasien), bisa menangani fitur campuran, tidak butuh scaling. Kelemahan: rawan overfitting (pohon terlalu dalam menghafal data).

📌 2. Entropy & Information Gain: Cara Memilih Pertanyaan

Entropy = ukuran "kekacauan" (ketidakmurnian) sebuah himpunan:
    H = -Σ pᵢ · log2(pᵢ)

    H([0,0,0,0])     = 0.0   (murni — tidak perlu tanya lagi)
    H([0,1])         = 1.0   (maksimal kacau)
    H([0,0,0,1])     = 0.81

Information Gain = H(parent) - H rata-rata anak
    → pilih split yang paling MENURUNKAN entropy (paling "memurnikan")

Split yang bagus: anak-anaknya hampir murni (entropy ≈ 0).
Split buruk:    anak-anaknya tetap campur (entropy ≈ parent).

📌 3. Contoh: Membangun Decision Tree Sendiri

print("=== MEMBANGUN DECISION TREE ===\n")
random_seed(42)
X, y = make_classification(120, n_features=2, sep=1.5)

def entropy(y):
    n = len(y)
    h = 0.0
    for l in set(y):
        p = sum(1 for v in y if v == l) / n
        h -= p * math.log2(p)
    return h

def best_split(X, y):
    parent_h = entropy(y)
    n = len(y)
    best = None
    for f in range(len(X[0])):
        vals = sorted(set(row[f] for row in X))
        for a, b in zip(vals, vals[1:]):
            thr = (a + b) / 2.0
            yl = [y[i] for i in range(n) if X[i][f] <= thr]
            yr = [y[i] for i in range(n) if X[i][f] > thr]
            if not yl or not yr:
                continue
            h_child = (len(yl) * entropy(yl) + len(yr) * entropy(yr)) / n
            gain = parent_h - h_child
            if best is None or gain > best[0]:
                best = (gain, f, thr)
    return best

def build_tree(X, y, depth, max_depth):
    votes = {}
    for l in y:
        votes[l] = votes.get(l, 0) + 1
    maj = max(votes, key=votes.get)
    if depth >= max_depth or len(set(y)) == 1:
        return ("leaf", maj)
    s = best_split(X, y)
    if s is None or s[0] <= 1e-9:
        return ("leaf", maj)
    gain, f, thr = s
    li = [i for i in range(len(X)) if X[i][f] <= thr]
    ri = [i for i in range(len(X)) if X[i][f] > thr]
    return ("split", f, thr,
            build_tree([X[i] for i in li], [y[i] for i in li], depth + 1, max_depth),
            build_tree([X[i] for i in ri], [y[i] for i in ri], depth + 1, max_depth))

def predict(tree, x):
    if tree[0] == "leaf":
        return tree[1]
    _, f, thr, left, right = tree
    return predict(left if x[f] <= thr else right, x)

def print_tree(tree, indent=""):
    if tree[0] == "leaf":
        print(indent + "→ kelas %d" % tree[1])
    else:
        _, f, thr, left, right = tree
        print(indent + "fitur_%d <= %.2f ?" % (f, thr))
        print_tree(left, indent + "   [ya]    ")
        print_tree(right, indent + "   [tidak] ")

tree = build_tree(X, y, 0, 3)
print("Struktur pohon (max depth 3):")
print_tree(tree)

pred = [predict(tree, x) for x in X]
print("\nAkurasi (train): %.1f%%" % (accuracy(y, pred) * 100))

# Telusuri satu prediksi
x = X[0]
print("\nTelusuri titik %s:" % [round(v, 2) for v in x])
node = tree
while node[0] != "leaf":
    _, f, thr, left, right = node
    go_left = x[f] <= thr
    print("  fitur_%d=%.2f %s %.2f → ke %s" %
          (f, x[f], "<=" if go_left else ">", thr, "kiri" if go_left else "kanan"))
    node = left if go_left else right
print("  → hasil: kelas %d (aktual %d)" % (node[1], y[0]))

Output:

📌 4. Contoh: Overfitting — Kedalaman Pohon

Pohon tanpa batas kedalaman akan tumbuh sampai setiap daun berisi 1 titik (murni) → akurasi train 100%, tapi menyimpan noise, bukan pola.

print("=== KEDALAMAN POHON vs OVERFITTING ===\n")
random_seed(42)
X, y = make_moons(120, noise=0.25)   # data ber-noise

def entropy(y):
    n = len(y)
    h = 0.0
    for l in set(y):
        p = sum(1 for v in y if v == l) / n
        h -= p * math.log2(p)
    return h

def best_split(X, y):
    parent_h = entropy(y)
    n = len(y)
    best = None
    for f in range(len(X[0])):
        vals = sorted(set(row[f] for row in X))
        for a, b in zip(vals, vals[1:]):
            thr = (a + b) / 2.0
            yl = [y[i] for i in range(n) if X[i][f] <= thr]
            yr = [y[i] for i in range(n) if X[i][f] > thr]
            if not yl or not yr:
                continue
            h_child = (len(yl) * entropy(yl) + len(yr) * entropy(yr)) / n
            gain = parent_h - h_child
            if best is None or gain > best[0]:
                best = (gain, f, thr)
    return best

def build_tree(X, y, depth, max_depth):
    votes = {}
    for l in y:
        votes[l] = votes.get(l, 0) + 1
    maj = max(votes, key=votes.get)
    if depth >= max_depth or len(set(y)) == 1:
        return ("leaf", maj)
    s = best_split(X, y)
    if s is None or s[0] <= 1e-9:
        return ("leaf", maj)
    gain, f, thr = s
    li = [i for i in range(len(X)) if X[i][f] <= thr]
    ri = [i for i in range(len(X)) if X[i][f] > thr]
    return ("split", f, thr,
            build_tree([X[i] for i in li], [y[i] for i in li], depth + 1, max_depth),
            build_tree([X[i] for i in ri], [y[i] for i in ri], depth + 1, max_depth))

def predict(tree, x):
    if tree[0] == "leaf":
        return tree[1]
    _, f, thr, left, right = tree
    return predict(left if x[f] <= thr else right, x)

def count_nodes(tree):
    if tree[0] == "leaf":
        return 1
    return 1 + count_nodes(tree[3]) + count_nodes(tree[4])

print("max_depth │ node │ akurasi train")
print("-" * 40)
for md in [1, 2, 4, 8, 12]:
    t = build_tree(X, y, 0, md)
    pred = [predict(t, x) for x in X]
    print("    %d     │ %4d │   %.1f%%"
          % (md, count_nodes(t), accuracy(y, pred) * 100))

print("""
Interpretasi:
• Akurasi train naik terus sampai 100% — TAPI itu hafalan,
  karena daun dalam mengikat titik noise satu per satu.
• Pohon dalam = boundary bergerigi mengikuti noise.
• Solusi dunia nyata: batasi depth, minimal sampel per daun,
  atau pruning (potong cabang yang tidak berguna).""")

Output:

💡 Karena pohon tunggal rapuh, praktisi jarang memakainya sendirian — mereka menggabungkan banyak pohon: Random Forest & Gradient Boosting (bab 15).

🧠 Latihan

Hitung entropy manual untuk himpunan [0,0,1,1,1]. (Jawaban: 0.971.) Verifikasi dengan fungsi di kode.
Ubah max_depth contoh 1 menjadi 1 dan 5. Bandingkan struktur pohon dan akurasinya.
Tambahkan aturan berhenti: "berhenti jika gain < 0.05" — berapa node pohon yang tersisa?
Jelaskan kenapa decision tree tidak butuh normalisasi data. (Petunjuk: bentuk pertanyaannya apa?)