Dr. Dudi Duta Akbar

Random Forests ala Breiman (2001): Formulasi Matematis

—

by

dudidutaakbar@gmail.com
in
Academic Notes • Modeling • Machine Learning

Random Forests ala Breiman (2001): Formulasi Matematis yang “Kebaca”

definisi ensemble, margin–generalization error, strength–correlation, Out-of-Bag (OOB), permutation importance, serta bound untuk klasifikasi dan regresi.

Sumber Utama
Breiman, L. (2001). Random Forests.
Machine Learning, 45, 5–32.
Kata kunci: Random Forests, Ensemble Trees, Margin, Generalization Error, Strength, Correlation, OOB, Variable Importance, Regression Bound.
1) Tidak overfit
Menambah jumlah pohon membuat error generalisasi cenderung stabil (konvergen), bukan memburuk.
2) Mesin akurasi
Akurasi forest digerakkan oleh dua tombol: strength (kekuatan) dan correlation (korelasi) antar pohon.
3) Evaluasi OOB
Out-of-Bag (OOB) memberi estimasi error dan metrik internal tanpa harus memisahkan test set khusus.
Daftar Isi
Klik untuk lompat

1) Definisi Random Forest

Random Forest adalah koleksi pohon keputusan yang dibentuk dari proses acak i.i.d. (independen dan identik terdistribusi). Secara ringkas, modelnya dapat ditulis sebagai himpunan fungsi prediktor pohon.

Rumus inti
{ h(x, θk) , k = 1, 2, … }
Keterangan: θk memuat randomness (bootstrap sample + pemilihan subset fitur acak per split).
Intuisi (untuk pembaca blog)
  • Setiap pohon itu “cukup baik”, tapi belum tentu paling akurat.
  • Forest mengambil keputusan dengan voting (klasifikasi) atau rata-rata (regresi).
  • Randomness dipakai untuk membuat pohon-pohon tidak terlalu mirip (diversity).

2) Margin Function & Generalization Error

Margin (versi voting)
Definisi
mg(X, Y) = avgk I(hk(X) = Y) − maxj ≠ Y avgk I(hk(X) = j)
I(·) adalah indikator (1 jika benar, 0 jika tidak). Margin mengukur “selisih dukungan” kelas benar vs pesaing terkuat.
Interpretasi cepat
  • mg > 0: prediksi benar dan “yakin”.
  • mg < 0: prediksi salah (kalah voting).
Margin membantu memahami bukan hanya benar/salah, tapi juga “seberapa jauh” forest menang/kalah.
Generalization Error
PE* = P( mg(X, Y) < 0 )
Ini adalah probabilitas margin negatif pada distribusi data sebenarnya (bukan sekadar error training).

3) Konvergensi: Mengapa Random Forest Tidak Overfit

Karena setiap pohon dibangun dari parameter acak θk yang i.i.d., maka voting forest berbasis rata-rata. Ketika jumlah pohon makin besar, rata-rata voting menjadi stabil (konvergen), sehingga error generalisasi cenderung mendekati nilai limit.

Bentuk limit (intuisi matematis)
P( Pθ(h(X,θ)=Y) − maxj ≠ Y Pθ(h(X,θ)=j) < 0 )
Intinya: menambah pohon memperkecil fluktuasi voting (varians), bukan membuat model makin “menghafal”.

4) Strength–Correlation & Bound Error

Breiman menjelaskan performa forest dengan dua komponen: strength (kekuatan rata-rata) dan correlation (korelasi antar pohon). Forest bagus jika pohonnya cukup kuat, namun tidak terlalu mirip satu sama lain.

(a) Strength
Margin forest
mr(X, Y) = Pθ(h(X,θ)=Y) − maxj ≠ Y Pθ(h(X,θ)=j)
Definisi strength
s = E[ mr(X, Y) ]
Strength besar berarti forest rata-rata memberi “selisih suara” yang besar pada kelas benar.
(b) Correlation
Korelasi antar pohon mencerminkan seberapa mirip pola kesalahan antar pohon. Jika pohon terlalu mirip, ensemble kehilangan manfaat “keragaman”.
Raw margin (intuisi)
rmg(θ,X,Y) = I(h(X,θ)=Y) − I(h(X,θ)=ĵ(X,Y))
ĵ(X,Y) adalah pesaing terkuat (kelas salah dengan probabilitas terbesar).
Bound error (pesan utama Breiman)
PE* ≤ ( ρ̄ (1 − s²) ) / s²
Agar error kecil: naikkan s (strength) dan tekan ρ̄ (korelasi rata-rata). Random features (mtry) membantu menurunkan korelasi.
Placeholder Visual
Letakkan gambar/diagram pendukung di sini (misal: kurva strength vs correlation saat jumlah fitur acak per split berubah).
Caption: “Strength cenderung plateau setelah titik tertentu, sementara correlation dapat meningkat ketika fitur acak per split diperbesar (Breiman, 2001).”

5) Out-of-Bag (OOB): Evaluasi Internal Tanpa Test Set

Karena bootstrap, tiap pohon hanya melihat sebagian data training. Observasi yang tidak terambil menjadi Out-of-Bag (OOB) untuk pohon tersebut. Dari voting OOB, kita memperoleh estimasi probabilitas kelas tanpa memerlukan pembagian data khusus.

Estimator vote OOB
Q(x,j) = [ Σ I( h(x,θk) = j ; (y,x) ∉ Tk,B ) ] / [ Σ I( (y,x) ∉ Tk,B ) ]
Q(x,j) mengaproksimasi P(h(x,θ)=j). Dari sini, OOB error dapat dihitung untuk memantau performa.

6) Variable Importance (Permutation)

Langkah inti
  1. Ambil data OOB untuk sebuah pohon.
  2. Acak (permutasi) fitur ke-m pada data OOB.
  3. Prediksi ulang dan hitung kenaikan error.
  4. Rata-rata kenaikan error di seluruh pohon.
ΔErrm = Errperm(m) − Errasli
Jika ΔErrm besar, fitur tersebut penting karena pengacakan merusak akurasi model.

7) Random Forest untuk Regresi

Untuk regresi, output setiap pohon bersifat numerik. Forest mengambil rata-rata prediksi pohon sehingga varians turun.

Prediksi forest
ĥRF(x) = avgk h(x,θk)
Ketika jumlah pohon besar, rata-rata prediksi cenderung stabil dan mengurangi error karena varians turun.
Bound penting (regresi)
PE*(forest) ≤ ρ̄ · PE*(tree)
Jika korelasi residual antar pohon (ρ̄) rendah, forest dapat jauh lebih baik daripada pohon tunggal.

8) Pseudocode Ringkas

Algoritme Random Forest (high-level)
Input: data D={(x_i,y_i)} i=1..N, jumlah pohon K, jumlah fitur acak per split F
Untuk k = 1..K:
1) Ambil bootstrap sample D_k dari D
2) Bangun pohon (tanpa pruning):
– di setiap node pilih subset fitur acak ukuran F
– cari split terbaik pada subset tersebut
3) Simpan pohon h(x,θ_k)
Klasifikasi: y_hat(x) = argmax_j Σ_k I(h(x,θ_k)=j)
Regresi: y_hat(x) = (1/K) Σ_k h(x,θ_k)
Takeaway Kunci
Random Forest kuat karena menggabungkan banyak pohon yang cukup kuat namun tidak terlalu berkorelasi. Secara praktis, desain yang efektif adalah menjaga strength tinggi dan menekan korelasi melalui bootstrap + random features.
Referensi
Breiman, L. (2001). Random Forests. Machine Learning, 45, 5–32.