🌲 Ensemble: Random Forest & Gradient Boosting

"Hikmah banyak kepala" — menggabungkan banyak model lemah menjadi model kuat. Raja kompetisi data science.

🎬 Animasi: Ensemble: Banyak Pohon Voting

Setiap ‘pohon’ punya garis keputusan sendiri; voting mayoritas membuat hasil lebih stabil daripada satu pohon.

📌 1. Kenapa Ensemble?

Satu model bisa bias/rapuh. Banyak model yang berbeda-beda kesalahannya saling melengkapi — voting/averaging-nya lebih stabil. (Analogi: dewan juri lebih adil dari satu juri.)

Dua keluarga besar:

BAGGING (parallel) — RANDOM FOREST
┌─────────┬─────────┬─────────┐
│ Tree 1  │ Tree 2  │ Tree 3  │   ← dilatih PARALEL di bootstrap sample
└────┬────┴────┬────┴────┬────┘     (sampel ulang dengan pengembalian)
     └─────────┼─────────┘
            VOTING MAJORITAS
• Tujuannya: kurangi VARIANCE (overfitting)
• Tiap pohon "melihat" data sedikit berbeda → error saling meniadakan

BOOSTING (sequential) — GRADIENT BOOSTING
Tree 1 → sisa error → Tree 2 → sisa error → Tree 3 → ...
• Tiap model baru memperbaiki KESELAHAN model sebelumnya
• F = F lama + learning_rate · (model baru yang fit ke residual)
• Tujuannya: kurangi BIAS
• "Residual" di klasifikasi = gradien negatif loss (p - y)

📌 2. Contoh: Random Forest vs Pohon Tunggal

Pohon dalam (depth 8) menghafal noise → gap train-test lebar. Random forest (banyak pohon dangkal + voting) lebih stabil.

print("=== RANDOM FOREST vs POHON TUNGGAL ===\n")
random_seed(42)
X, y = make_moons(150, noise=0.35)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3)

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):
    ph = 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
            hc = (len(yl) * entropy(yl) + len(yr) * entropy(yr)) / n
            g = ph - hc
            if best is None or g > best[0]:
                best = (g, f, thr)
    return best

def build_tree(X, y, d, md):
    votes = {}
    for l in y:
        votes[l] = votes.get(l, 0) + 1
    maj = max(votes, key=votes.get)
    if d >= md 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)
    g, 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], d + 1, md),
            build_tree([X[i] for i in ri], [y[i] for i in ri], d + 1, md))

def predict(t, x):
    if t[0] == "leaf":
        return t[1]
    _, f, thr, l, r = t
    return predict(l if x[f] <= thr else r, x)

# ── Pohon tunggal DALAM (rawan overfit) ──
t1 = build_tree(Xtr, ytr, 0, 8)
tr1 = [predict(t1, x) for x in Xtr]
te1 = [predict(t1, x) for x in Xte]

# ── RANDOM FOREST: 15 pohon dangkal + bootstrap + voting ──
def random_forest(X, y, n_trees=15, max_depth=4, seed=42):
    random_seed(seed)
    trees = []
    n = len(X)
    for _ in range(n_trees):
        idx = [randint(0, n - 1) for _ in range(n)]   # bootstrap
        trees.append(build_tree([X[i] for i in idx],
                                [y[i] for i in idx], 0, max_depth))
    return trees

def rf_predict(trees, x):
    votes = {}
    for t in trees:
        p = predict(t, x)
        votes[p] = votes.get(p, 0) + 1
    return max(votes, key=votes.get)

forest = random_forest(Xtr, ytr, n_trees=15, max_depth=4)
tr2 = [rf_predict(forest, x) for x in Xtr]
te2 = [rf_predict(forest, x) for x in Xte]

print_table(["Model", "Train", "Test", "Gap (overfit)"],
            ["pohon dalam (d=8)",  "%.1f%%" % (accuracy(ytr, tr1) * 100),
             "%.1f%%" % (accuracy(yte, te1) * 100),
             "%.1f%%" % ((accuracy(ytr, tr1) - accuracy(yte, te1)) * 100)],
            ["random forest (15)", "%.1f%%" % (accuracy(ytr, tr2) * 100),
             "%.1f%%" % (accuracy(yte, te2) * 100),
             "%.1f%%" % ((accuracy(ytr, tr2) - accuracy(yte, te2)) * 100)])
print("""
Pesan: gap train-test forest JAUH lebih kecil →
model lebih STABIL, tidak menghafal noise.
Di dunia nyata (tabular data), random forest sering jadi
baseline terkuat sebelum neural network.""")

Output:

📌 3. Contoh: Gradient Boosting (Stump)

Tiap "stump" (pohon 1 level) memperbaiki residual model sebelumnya. Kita uji di data circles (boundary melingkar — sulit untuk satu garis).

print("=== GRADIENT BOOSTING: MEMBANGUN BOUNDARY MELINGKAR ===\n")
random_seed(42)
X, y = make_circles(150)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3)
n = len(Xtr)

def fit_stump(X, resid):
    # pohon 1 level: cari (fitur, threshold) yang paling kurangi Σresid²
    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
            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]
            if len(li) < 3 or len(ri) < 3:
                continue
            vl = mean([resid[i] for i in li])
            vr = mean([resid[i] for i in ri])
            err = sum(resid[i] ** 2 for i in li) + sum(resid[i] ** 2 for i in ri)
            if best is None or err < best[0]:
                best = (err, f, thr, vl, vr)
    return best

F = [0.0] * n          # model akumulator (mulai 0)
lr = 0.1
stumps = []
for m in range(40):
    p = [sigmoid(v) for v in F]
    resid = [p[i] - ytr[i] for i in range(n)]   # gradien negatif log-loss
    s = fit_stump(Xtr, resid)
    if s is None:
        break
    _, f, thr, vl, vr = s
    stumps.append((f, thr, vl, vr))
    for i in range(n):
        F[i] -= lr * (vl if Xtr[i][f] <= thr else vr)

def gb_predict(x):
    s = 0.0
    for f, thr, vl, vr in stumps:
        s -= lr * (vl if x[f] <= thr else vr)
    return 1 if sigmoid(s) >= 0.5 else 0

tr = [gb_predict(x) for x in Xtr]
te = [gb_predict(x) for x in Xte]
print("Jumlah stump: %d" % len(stumps))
print("Akurasi train = %.1f%%" % (accuracy(ytr, tr) * 100))
print("Akurasi test  = %.1f%%" % (accuracy(yte, te) * 100))
print("""
40 stump (masing-masing cuma 1 pertanyaan!) digabung
sudah mampu membentuk boundary melingkar — karena tiap
stump "menambal" kesalahan gabungan sebelumnya.
XGBoost/LightGBM/CatBoost = implementasi industrial dari ide ini.""")

Output:

💡 Ringkasan ensemble: bagging (paralel, kurangi variance) vs boosting (sekuensial, kurangi bias). Di kompetisi Kaggle, gradient boosting pada data tabel hampir selalu mengalahkan model tunggal.

🧠 Latihan

Tambahkan feature subsampling: tiap split pohon hanya mempertimbangkan 1 fitur acak. Apakah forest lebih baik?
Ubah jumlah pohon dari 15 menjadi 5 dan 50. Plot akurasi test vs jumlah pohon — kapan mulai "jenuh"?
Di gradient boosting, turunkan lr ke 0.05 dan naikkan stump ke 80. Apa efeknya? (Petunjuk: langkah kecil × banyak.)
Jelaskan dengan analogi: kenapa boosting mengurangi bias, sedangkan bagging mengurangi variance.