2022-08-03

Ikhtisar XGBoost

Apa itu XGBoost

XGBoost, singkatan dari eXtreme Gradient Boosting, adalah pustaka pembelajaran mesin sumber terbuka yang menyediakan implementasi yang sangat efisien dan scalable dari gradient boosted decision trees. XGBoost telah menjadi pilihan populer di kalangan ilmuwan data dan praktisi pembelajaran mesin karena kinerja yang unggul, fleksibilitas, dan kemudahan penggunaannya.

Asal-Usul dan Evolusi

XGBoost muncul dari proyek penelitian yang dipimpin oleh Tianqi Chen di Universitas Washington, dengan implementasi awal yang dirilis pada tahun 2014. Pengembangan pustaka ini dipicu oleh keinginan untuk membuat implementasi gradient boosted trees yang scalable, efisien, dan mudah digunakan. Proyek ini cepat mendapatkan momentum di komunitas pembelajaran mesin, berkat kinerja impresifnya dalam berbagai kompetisi ilmu data, seperti platform prestisius Kaggle.

Keberhasilan XGBoost disebabkan oleh kombinasi unik kinerja yang tinggi, fleksibilitas, dan kemudahan penggunaannya. Pustaka ini terus berkembang selama bertahun-tahun, dengan fitur, perbaikan, dan optimasi baru yang ditambahkan untuk meningkatkan kemampuannya.

Mengapa Memilih XGBoost

Ada beberapa alasan untuk memilih XGBoost dibandingkan dengan pustaka dan algoritma pembelajaran mesin lainnya, di antaranya:

Kinerja unggul
XGBoost secara konsisten mengungguli algoritma lain dalam hal akurasi dan kecepatan, menjadikannya pilihan utama bagi banyak praktisi.
Scalability
Pustaka ini dirancang untuk menangani dataset berukuran besar dan dapat dilakukan skalabilitas linear dengan jumlah titik data, sehingga cocok untuk aplikasi big data.
Fleksibilitas
XGBoost menawarkan berbagai hyperparameter dan opsi kustomisasi, memungkinkan pengguna untuk menyesuaikan model mereka untuk tugas dan dataset tertentu.
Interpretabilitas
Penggunaan decision tree sebagai pembelajar dasar membuat model XGBoost relatif mudah diinterpretasikan dan visualisasikan, dibandingkan dengan model yang lebih kompleks seperti deep neural network.
Kompatibilitas lintas platform
XGBoost tersedia dalam beberapa bahasa pemrograman, termasuk Python, R, dan Java, menjadikannya mudah diakses oleh berbagai pengguna.

Algoritma XGBoost

Gradient Boosted Trees

Gradient boosting adalah teknik pembelajaran mesin yang menggabungkan beberapa pembelajar lemah untuk membuat model yang lebih akurat dan kuat. Dalam konteks XGBoost, pembelajar lemah ini adalah decision tree. Proses boosting melibatkan secara iteratif menambahkan pohon ke ensemble, di mana setiap pohon dirancang untuk memperbaiki kesalahan residu yang dibuat oleh pohon sebelumnya. Prediksi akhir adalah hasil penjumlahan dari prediksi yang dibuat oleh semua pohon individu dalam ensemble.

Ide kunci di balik gradient boosting adalah memperlakukan masalah sebagai tugas optimisasi gradient descent. Pada setiap iterasi, algoritma menghitung gradien negatif dari fungsi kerugian terhadap nilai prediksi ensemble sebelumnya, lalu menyesuaikan pohon baru dengan nilai gradien negatif ini. Pendekatan ini memastikan bahwa prediksi pohon baru sejalan dengan gradien tercuram dari fungsi kerugian, efektif mendorong prediksi model lebih dekat ke nilai target yang sebenarnya.

Proses gradient boosting dalam XGBoost dapat dibagi menjadi langkah-langkah berikut:

Inisialisasi model dengan nilai prediksi konstan yang meminimalkan fungsi kerugian. Ini berfungsi sebagai model dasar untuk ensemble.
Untuk setiap iterasi dalam proses boosting:
1. Hitung gradien negatif dari fungsi kerugian terhadap prediksi ensemble saat ini untuk setiap contoh pelatihan. Nilai gradien negatif ini mewakili kesalahan residu yang harus diperbaiki oleh pohon baru.
2. Pasang pohon keputusan baru ke nilai gradien negatif. Pohon ini dibangun menggunakan algoritma rakus, di mana setiap split dipilih berdasarkan gradien tercuram dari fungsi kerugian. Algoritma memilih fitur dan titik split yang menghasilkan penurunan terbesar pada fungsi kerugian.
3. Tentukan ukuran langkah optimal (learning rate) untuk pohon baru. Ini dicapai dengan meminimalkan fungsi kerugian menggunakan pencarian garis, yang melibatkan mencari ukuran langkah yang menghasilkan nilai terendah pada fungsi kerugian saat prediksi pohon baru digabungkan dengan ensemble saat ini.
4. Perbarui ensemble dengan menambahkan pohon baru, dilipatgandakan dengan ukuran langkah optimal. Ensemble yang diperbarui ini sekarang mencakup kontribusi pohon baru, yang dirancang untuk memperbaiki kesalahan residu yang dibuat oleh pohon sebelumnya.
Setelah mencapai jumlah iterasi maksimum atau kriteria berhenti yang ditentukan sebelumnya, ensemble akhir digunakan untuk membuat prediksi.

Proses iteratif gradient boosting dalam XGBoost memungkinkan algoritma untuk belajar secara adaptif dari kesalahan residu yang dibuat oleh pohon sebelumnya, efektif meningkatkan akurasi model seiring waktu. Dengan menyesuaikan pohon baru ke gradien tercuram dari fungsi kerugian, XGBoost memastikan bahwa setiap pohon yang ditambahkan memberikan kontribusi terbesar dalam mengurangi kerugian secara keseluruhan, menghasilkan model yang kuat dan andal.

Teknik Regularisasi

Untuk mencegah overfitting dan meningkatkan kinerja generalisasi, XGBoost menggabungkan teknik regularisasi yang mencegah model menjadi terlalu kompleks. Regularisasi menambahkan istilah penalti ke fungsi kerugian, yang membatasi bobot model dan mencegah mereka menjadi terlalu besar.

Ada dua jenis regularisasi utama yang digunakan dalam XGBoost:

Regularisasi L1 (Lasso)
Regularisasi L1 menambahkan nilai mutlak dari bobot ke fungsi kerugian. Efek dari metode regularisasi ini adalah mendorong beberapa bobot menjadi tepat nol, mengarah pada model sparse. Dalam konteks XGBoost, regularisasi L1 diterapkan pada bobot daun dari pohon keputusan, yang dapat mendorong beberapa simpul daun memiliki bobot nol, secara efektif memangkas pohon.
Regularisasi L2 (Ridge)
Regularisasi L2 menambahkan nilai kuadrat dari bobot ke fungsi kerugian. Metode ini tidak menghasilkan model sparse seperti regularisasi L1, tetapi memperkecil bobot, mencegah mereka menjadi terlalu besar. Dalam XGBoost, regularisasi L2 diterapkan pada bobot daun dari pohon keputusan, yang membantu meratakan model dan mengurangi overfitting.
Baik regularisasi L1 dan L2 dalam XGBoost dikendalikan oleh hiperparameter:

Konstruksi dan Penyempurnaan Pohon

Salah satu aspek kritis dari XGBoost yang membedakannya dari algoritma berbasis pohon keputusan lainnya adalah pendekatan efisien dalam konstruksi dan penyempurnaan pohon. Bagian ini akan memberikan penjelasan terperinci tentang teknik yang digunakan dalam XGBoost untuk membangun dan memangkas pohon keputusan, menghasilkan model yang lebih efektif dan akurat.

Konstruksi Pohon yang Rakus

XGBoost menggunakan strategi depth-first untuk membangun pohon keputusan, memungkinkan konstruksi pohon yang lebih efisien. Proses konstruksi pohon melibatkan pemilihan fitur dan titik pemotongan yang menghasilkan pengurangan terbesar dalam fungsi kerugian untuk setiap simpul. Pendekatan ini dikenal sebagai algoritma rakus karena membuat keputusan terbaik pada setiap langkah, hanya mempertimbangkan konsekuensi langsung.

Selama konstruksi pohon, XGBoost mengevaluasi pemisahan potensial dengan menghitung metrik keuntungan (gain), yang mengukur peningkatan dalam fungsi kerugian akibat pemisahan. Untuk setiap simpul, algoritma mengulang semua fitur dan titik pemotongan yang mungkin, memilih satu yang memaksimalkan gain. Pendekatan rakus ini memastikan bahwa struktur pohon dioptimalkan untuk mengurangi kerugian secara keseluruhan.

Penyempurnaan Pohon

Meskipun pendekatan rakus dalam konstruksi pohon efektif dalam menemukan struktur yang optimal, hal itu juga dapat menyebabkan overfitting jika pohon menjadi terlalu kompleks. Untuk mencegah overfitting, XGBoost menggunakan teknik yang disebut "penyempurnaan" (pruning), yang menghapus pemisahan yang tidak memberikan kontribusi cukup pada keuntungan keseluruhan.

XGBoost menggunakan pendekatan depth-first untuk penyempurnaan pohon, yang dilakukan selama proses konstruksi pohon itu sendiri. Algoritma menggabungkan istilah regularisasi untuk mengontrol proses penyempurnaan. Strategi penyempurnaan depth-first dalam XGBoost memiliki beberapa keuntungan. Dengan memangkas pohon selama konstruksi, XGBoost menghindari membangun cabang yang tidak perlu dan mengurangi waktu dan memori yang diperlukan untuk konstruksi pohon. Pendekatan ini juga memungkinkan algoritma untuk menemukan struktur pohon yang optimal secara lebih efisien, karena tidak perlu mundur dan mengevaluasi kembali keputusan sebelumnya.

Blok Kolom dan Paralelisasi

Selain teknik konstruksi dan penyempurnaan pohon yang efisien, XGBoost juga menggunakan struktur data blok kolom dan paralelisasi untuk mempercepat proses pelatihan. Struktur data blok kolom menyimpan dataset di memori dengan mengelompokkan fitur ke dalam blok, memungkinkan akses yang lebih cepat ke data selama konstruksi pohon.

XGBoost memanfaatkan prosesor multi-core modern dengan memparallelkan proses konstruksi pohon. Algoritma dapat mengevaluasi beberapa fitur dan titik pemotongan secara simultan, mengurangi waktu yang dibutuhkan untuk membangun setiap pohon secara signifikan. Paralelisasi ini sangat bermanfaat saat menangani dataset yang besar, karena memungkinkan XGBoost untuk skala dengan efektif dan menangani jumlah data yang sangat besar.

Menangani Nilai Hilang dan Fitur Kategori

Salah satu tantangan dalam bekerja dengan dataset dunia nyata adalah menangani nilai yang hilang dan fitur kategori. XGBoost mengatasi tantangan ini dengan teknik khusus untuk memproses nilai yang hilang dan menangani fitur kategori, menjadikannya algoritma pembelajaran mesin yang lebih serbaguna dan kuat.

Menangani Nilai Hilang

Nilai yang hilang dapat terjadi pada dataset karena berbagai alasan, seperti kegagalan sensor, kesalahan pengisian data, atau pengamatan yang hilang. XGBoost memiliki mekanisme bawaan untuk menangani nilai yang hilang secara efektif tanpa perlu imputasi, yang kadang-kadang dapat memperkenalkan bias atau mengurangi efisiensi algoritma.

Selama proses pembangunan pohon, ketika XGBoost menemukan nilai yang hilang untuk fitur tertentu, ia menetapkan nilai yang hilang ke arah default, baik kiri atau kanan. Arah default dipilih berdasarkan pengurangan dalam fungsi kerugian yang akan dicapai dengan mengirim nilai yang hilang ke setiap arah. Pendekatan ini memungkinkan algoritma membuat keputusan yang optimal bahkan ketika data tidak lengkap.

Setelah pohon dibangun, XGBoost dapat menangani nilai yang hilang dalam fase prediksi dengan mengikuti arah default yang ditentukan selama pembangunan pohon. Ini memungkinkan algoritma untuk membuat prediksi yang akurat bahkan ketika beberapa nilai fitur hilang.

Menangani Fitur Kategori

XGBoost awalnya dirancang untuk menangani fitur numerik, tetapi dapat diperluas untuk menangani fitur kategori secara efektif. Ada beberapa cara untuk menangani fitur kategori di XGBoost:

One-hot encoding
Salah satu metode paling sederhana untuk menangani fitur kategori adalah dengan mengubahnya menjadi fitur biner menggunakan one-hot encoding. Setiap nilai kategori yang unik direpresentasikan oleh fitur biner terpisah, yang mengambil nilai 1 jika kategori hadir dan 0 sebaliknya. Meskipun pendekatan ini dapat efektif untuk fitur kategori dengan jumlah nilai yang sedikit, ini dapat menyebabkan ruang fitur yang memiliki dimensi yang tinggi untuk fitur dengan banyak kategori.
Label encoding
Pendekatan lain untuk menangani fitur kategori adalah dengan memberi label numerik untuk setiap nilai kategori yang unik. Metode ini dapat secara signifikan mengurangi dimensi ruang fitur dibandingkan dengan one-hot encoding. Namun, label encoding memperkenalkan pengurutan acak dari kategori, yang kadang-kadang dapat menghasilkan hasil yang tidak optimal.
Target encoding
Target encoding melibatkan penggantian setiap nilai kategori dengan rata-rata variabel target untuk kategori tersebut. Pendekatan ini dapat menangkap hubungan antara fitur kategori dan variabel target secara lebih efektif dibandingkan dengan label encoding. Namun, target encoding dapat memperkenalkan kebocoran jika tidak dilakukan dengan benar, sehingga penting untuk melakukan encoding secara terpisah untuk set pelatihan dan validasi.

Shrinkage

Shrinkage adalah teknik yang digunakan dalam algoritma penguatan (boosting), termasuk XGBoost, untuk mencegah overfitting dengan mengurangi dampak dari setiap pohon individual yang ditambahkan ke model. Hal ini dicapai dengan memperkenalkan tingkat pembelajaran, yang juga dikenal sebagai faktor Shrinkage, yang menyesuaikan kontribusi dari setiap pohon ke dalam model akhir. Dengan cara ini, model belajar lebih lambat dan mengeneralisasi lebih baik terhadap data yang tidak terlihat.

Dalam konteks XGBoost, Shrinkage memainkan peran penting dalam mengurangi overfitting, yang merupakan masalah umum dalam model pembelajaran mesin, terutama yang mengandalkan pohon keputusan. Ketika sebuah model overfit, ia berperforma sangat baik pada data latihan tetapi buruk pada data yang baru dan tidak terlihat. Shrinkage membantu mengurangi masalah ini dengan mengendalikan bobot yang diberikan pada setiap pohon keputusan.