Mata Kuliah: Machine Learning

Tree-Based Algorithms

Pendahuluan

Dalam pembelajaran mesin, algoritma yang berbasis pohon disebut algoritma berbasis pohon. Algoritma ini menggunakan struktur seperti pohon untuk membuat keputusan atau prediksi. Beberapa algoritma berbasis pohon yang paling umum adalah:

• Decision Tree: Struktur pohon sederhana di mana setiap node internal mewakili keputusan berdasarkan fitur, dan setiap node daun mewakili hasil (klasifikasi atau regresi).

• Random Forest: Metode ensemble yang membuat kumpulan pohon keputusan dan menggabungkan hasilnya (biasanya dengan rata-rata atau pemungutan suara mayoritas) untuk meningkatkan akurasi dan mengurangi overfitting.

• Gradient Boosting Machines (GBM): Algoritma boosting yang membangun pohon secara berurutan, di mana setiap pohon mencoba memperbaiki kesalahan yang dibuat oleh pohon sebelumnya. Implementasi populer termasuk XGBoost, LightGBM, dan CatBoost.

Algoritma ini banyak digunakan karena kemampuannya untuk menangani tugas klasifikasi dan regresi secara efektif serta interpretabilitasnya.

Decision Tree

Decision tree membagi dataset menjadi beberapa wilayah (berbentuk kotak). Algoritma ini memilih fitur dan ambang batas yang dapat membagi target dengan baik. Langkah ini diulangi hingga kedalaman maksimum yang diinginkan tercapai, yang akan membuat batasan untuk mengklasifikasikan data berdasarkan wilayah yang telah dibuat sebelumnya.

Sumber: medium.com/@axelivandatanjung

Decision Tree untuk Regresi

Algoritma decision tree mirip dengan regresi piecewise-linear. Decision tree membagi ruang input menjadi beberapa wilayah, dan menghitung nilai rata-rata target pada set

Komponen Decision Tree

Decision tree terdiri dari beberapa komponen utama:

• Decision tree seperti pohon, namun terbalik. Root ada di atas.
• Decision/internal node: uji nilai dari salah satu atribut/fitur input.
• Kumpulan edges/branches dari node: label dengan nilai atribut/fitur yang mungkin.
• Leaf node: output value.

Sumber: Pacmann Academy

Cara Split Node (Partisi)

1. Cari batas partisi/sekat terbaik untuk masing-masing variabel prediktor.
2. Bandingkan partisi terbaik dari semua variabel prediktor… pilih yang paling baik.
3. Lakukan penyekatan/spliting berdasarkan variabel yang dihasilkan pada langkah ke-2.
4. Lakukan langkah 1-2-3 untuk setiap node, sampai tercapai kriteria penghentian algoritma.

Contoh, asumsikan kita memiliki variabel income untuk memprediksi debt.

Sumber: Pacmann Academy

Cara Split Node (Partisi)

Hitung mean squared error (MSE) untuk setiap partisi (feature space) pada variabel income. Pilih partisi dengan nilai MSE terendah.

Sumber: Pacmann Academy

Aturan Penghentian

• Kedalaman Maksimum: Pohon berhenti tumbuh ketika kedalaman maksimum tercapai.
• Jumlah Sampel Minimum: Pohon berhenti tumbuh ketika jumlah sampel minimum di node daun tercapai.

Overfitting

Sumber: Pacmann Academy

Materi Tambahan Click Here

Aplikasi Decision Tree untuk Regresi dengan Scikit-Learn

Berikut adalah contoh penerapan algoritma Decision Tree untuk regresi menggunakan pustaka Scikit-Learn di Python:

DecisionTreeRegressor

class sklearn.tree.DecisionTreeRegressor(*, criterion='squared_error', splitter='best', 
max_depth=None, min_samples_split=2, min_samples_leaf=1, 
min_weight_fraction_leaf=0.0, max_features=None, random_state=None, 
max_leaf_nodes=None, min_impurity_decrease=0.0, ccp_alpha=0.0, 
monotonic_cst=None)                              

Contoh:

from sklearn.datasets import load_diabetes
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeRegressor
X, y = load_diabetes(return_X_y=True)
regressor = DecisionTreeRegressor(random_state=0)
cross_val_score(regressor, X, y, cv=10)                               

Code Exercise

Random Forest

Breiman, L. 2001. Random Forests. Machine Learning 45: 5–32.

Banyaknya Artikel Ilmiah di Google Scholar dengan kata pencarian “random forest breiman”

Algoritme Random Forest

Sumber: Wang et al. (2019)

Algoritme Random Forest

Ide Dasar:

• Ensemble dari ratusan/ribuan pohon
• korelasi prediksi antar pohon diusahakan minimal → diversity

Algoritme:

Algoritme Random Forest

1. Ambil Sampel Data: Pilih sebagian data secara acak dari kumpulan data utama dengan teknik bootstrapping resampling (replacement - Artinya setelah satu data dipilih, data itu tetap bisa dipilih lagi), sehingga setiap pohon mendapatkan kombinasi data yang sedikit berbeda.
2. Bangun Banyak Pohon Keputusan: Buat beberapa pohon keputusan secara paralel. Setiap pohon dibangun menggunakan sampel data yang telah dipilih, dan pada setiap percabangan, hanya sebagian kecil fitur (variabel) yang dipilih secara acak untuk dipertimbangkan.
3. Latih Setiap Pohon: Ajarkan setiap pohon keputusan untuk membuat keputusan berdasarkan pola dalam data sampelnya, tanpa memengaruhi pohon lain.
4. Kumpulkan Hasil dari Semua Pohon: Setelah semua pohon selesai dilatih, masukkan data baru ke setiap pohon untuk mendapatkan prediksi dari masing-masing pohon.
5. Gabungkan Prediksi (Voting): Untuk tugas klasifikasi, hitung suara terbanyak (majority voting) dari semua pohon untuk menentukan hasil akhir. Untuk tugas regresi, ambil rata-rata dari prediksi semua pohon.
6. Hasil Akhir: Berikan output berupa kelas (untuk klasifikasi) atau nilai (untuk regresi) sebagai hasil prediksi Random Forest.

Hyperparameter Utama Random Forest di Sklearn

1. n_estimators
   • Apa itu: Jumlah pohon keputusan yang dibuat di dalam Random Forest.
     
   • Default: 100
     
   • Contoh: n_estimators=50 berarti ada 50 pohon.
     
   • Efek: Semakin banyak pohon, biasanya semakin akurat, tapi prosesnya jadi lebih lambat.
2. max_depth
   • Apa itu: Kedalaman maksimum setiap pohon (berapa banyak tingkat keputusan).
     
   • Default: None (pohon tumbuh sampai semua daun murni atau batas lain tercapai).
     
   • Contoh: max_depth=10 batasi pohon sampai 10 tingkat.
     
   • Efek: Membatasi kedalaman bisa mencegah overfitting (pohon terlalu hafal data).

Hyperparameter Utama Random Forest di Sklearn

3. min_samples_split
   • Apa itu: Jumlah minimum sampel yang dibutuhkan untuk membagi sebuah simpul (node) di pohon.
     
   • Default: 2
     
   • Contoh: min_samples_split=5 berarti simpul baru dibagi jika ada minimal 5 sampel.
     
   • Efek: Nilai lebih besar mencegah pohon terlalu rumit (overfitting).
4. min_samples_leaf
   • Apa itu: Jumlah minimum sampel yang harus ada di daun (leaf node).
     
   • Default: 1
     
   • Contoh: min_samples_leaf=2 berarti setiap daun harus punya minimal 2 sampel.
     
   • Efek: Membantu mengontrol ukuran pohon dan mencegah daun dengan sedikit data.

Hyperparameter Utama Random Forest di Sklearn

5. max_features
   • Apa itu: Jumlah maksimum fitur (kolom data) yang dipertimbangkan saat mencari pemisahan terbaik di setiap simpul.
     
   • Default: “sqrt” (akar kuadrat dari total fitur).
     
   • Contoh: max_features='log2' atau max_features=0.5 (50% dari fitur).
     
   • Efek: Membatasi fitur membuat pohon lebih beragam dan mengurangi korelasi antar pohon.
6. bootstrap
   • Apa itu: Menentukan apakah bootstrapping resampling digunakan untuk membuat sampel data.
     
   • Default: True
     
   • Contoh: bootstrap=False berarti semua pohon pakai seluruh data (tanpa sampling).
     
   • Efek: Jika True, model lebih tahan overfitting karena ada keacakan.

Hyperparameter Utama Random Forest di Sklearn

7. random_state
   • Apa itu: Angka untuk mengatur keacakan agar hasil bisa direproduksi.
     
   • Default: None
     
   • Contoh: random_state=42 untuk hasil yang konsisten setiap kali dijalankan.
     
   • Efek: Berguna untuk debugging atau membandingkan hasil.