Random Forest Daring
- Diperkenalkan oleh
- Saffari, A. et al.
- Tahun
- 2009
- Jenis
- Incremental ensemble (streaming decision trees)
- Keluarga
- Machine learning
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Random Forest Daring (ORF) memperluas Random Forest klasik ke pengaturan streaming, memperbarui setiap pohon secara inkremental saat observasi baru tiba tanpa menyimpan atau memutar ulang seluruh set pelatihan.
Algoritma seperti Adaptive Random Forests (ARF) menambahkan deteksi drift sehingga ansambel beradaptasi ketika distribusi data berubah seiring waktu.
Intuisi di balik metode
Random Forest Klasik memerlukan seluruh dataset di muka untuk menumbuhkan pohonnya. Random Forest Daring menggantikan pengambilan sampel bootstrap batch dengan trik bagging daring berbobot Poisson: setiap observasi yang masuk diteruskan ke setiap pohon, yang memutuskan — dengan menarik hitungan Poisson — berapa kali untuk memperlakukan contoh tersebut sebagai titik pelatihan baru. Pohon tumbuh secara inkremental menggunakan kriteria pencarian pemisahan daring (misalnya, batas Hoeffding), dan modul deteksi drift mengawasi drift konsep, mengganti pohon yang basi dengan pohon yang baru. Hasilnya adalah ansambel yang belajar terus menerus dari aliran sambil tetap menggabungkan beberapa pohon yang beragam untuk pengurangan varians.
Sejarah
Bagging daring diformalkan oleh Oza & Russell (2001) sebagai perkiraan berbobot Poisson untuk agregasi bootstrap. Saffari dkk. (2009) memperkenalkan Random Forests Daring yang menggabungkan bagging daring dengan pemilihan fitur acak dan kriteria pemisahan berbasis Hoeffding untuk aliran visi komputer. Gomes dkk. (2017) memperkenalkan Adaptive Random Forests (ARF), menambahkan deteksi drift per-pohon melalui ADWIN, dan menunjukkan akurasi negara-seni pada tugas klasifikasi aliran data benchmark. ARF menjadi baseline standar dalam kerangka kerja MOA (Massive Online Analysis).
Kapan digunakan
Gunakan Random Forest Daring ketika data tiba terus menerus atau dalam batch besar yang tidak dapat disimpan dalam memori, ketika drift konsep masuk akal (misalnya, aliran keuangan, jaringan sensor, log perilaku pengguna), atau ketika prediksi latensi rendah diperlukan sebelum seluruh dataset tersedia. Ini juga cocok secara alami untuk aplikasi di mana data berlabel masuk sedikit demi sedikit seiring waktu. Hindari jika seluruh dataset pas dengan nyaman di memori dan pelatihan ulang terjangkau — dalam kasus tersebut Random Forest standar yang dilatih secara luring biasanya akan lebih akurat dan lebih sederhana untuk divalidasi. Hindari juga jika Anda memerlukan peringkat kepentingan fitur yang stabil dan dapat direproduksi, karena hutan daring menghasilkan perkiraan kepentingan yang kurang stabil daripada rekan batch mereka.
Batasan dan pertimbangan
- Keputusan pemisahan yang dibuat lebih awal dengan data jarang bisa suboptimal dan sulit untuk direvisi.
- Perkiraan kepentingan fitur kurang stabil dibandingkan pada Random Forest batch.
- Penyetelan hyperparameter (jumlah pohon, ambang batas deteksi drift) lebih kompleks dalam konteks streaming.
- Evaluasi memerlukan protokol berbasis aliran khusus (prequential/test-then-train) yang berbeda dari validasi silang standar.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Belajar dari data streaming dengan memori konstan per pohon, independen dari panjang aliran.
- Beradaptasi dengan drift konsep ketika dipasangkan dengan mekanisme deteksi drift seperti ADWIN.
- Mewarisi manfaat pengurangan varians agregasi ansambel bahkan dalam pengaturan daring.
- Memberikan prediksi yang dapat digunakan dari beberapa observasi pertama, meningkat seiring waktu.
- Tidak perlu menyimpan atau memutar ulang seluruh dataset historis.
Penerapan
- Deteksi penipuan dan intrusi waktu nyata pada aliran jaringan atau transaksi.
- Pemeliharaan prediktif dari aliran sensor di mana distribusi bergeser dengan penuaan peralatan.
- Prediksi tingkat klik di periklanan di mana perilaku pengguna berkembang setiap hari.
- Pemantauan medis di mana keadaan pasien berubah terus menerus seiring waktu.
- Penginderaan lingkungan dan iklim dengan pola musiman non-stasioner.
Cara kerjanya
Cara kerjanya
Sekumpulan T pohon (atau pohon Hoeffding) diinisialisasi. Setiap pohon memelihara statistik yang cukup per-daun — hitungan kelas atau jumlah kuadrat untuk regresi — alih-alih menyimpan observasi mentah, membuat model konstan memori per pohon.
Untuk setiap observasi yang tiba, setiap pohon secara independen menarik k dari distribusi Poisson(1) dan memperlakukan observasi tersebut sebagai k replikasi virtual dari dirinya sendiri. Ketika k = 0 pohon melewati titik tersebut (bertindak sebagai sampel di luar kantongnya). Ini mendekati pengambilan sampel bootstrap tanpa memerlukan seluruh dataset.
Rumus
k \sim \text{Poisson}(\lambda),\; \lambda=1Setiap pohon memperbarui statistik yang cukup di daun aktifnya. Pemisahan dipicu ketika kriteria yang secara statistik kuat (seperti batas Hoeffding) menunjukkan bahwa pemisahan terbaik kemungkinan tidak akan berubah dengan lebih banyak data, setelah itu daun diperluas menjadi node internal dan daun baru diinisialisasi.
Modul deteksi drift opsional (misalnya, ADWIN) memantau kesalahan prediksi setiap pohon pada aliran di luar kantong. Ketika degradasi yang signifikan secara statistik terdeteksi, pohon yang terpengaruh direset atau diganti dengan pohon yang baru diinisialisasi, menjaga ansambel tetap terkini dengan distribusi yang berkembang.
Pada titik mana pun, semua pohon aktif memberikan suara: suara mayoritas untuk klasifikasi atau prediksi rata-rata untuk regresi. Pohon yang telah memproses sangat sedikit contoh mungkin diberi bobot lebih rendah atau dikecualikan sampai mereka mengumpulkan cukup data untuk memberikan suara yang andal.
Rumus
\hat{y} = \text{mode/mean of active trees}Kesalahan umum
- Mengevaluasi dengan validasi silang k-lipatan standar, yang mengasumsikan data i.i.d. dan mengabaikan urutan temporal.
- Mengabaikan drift konsep: gagal menyertakan komponen deteksi drift ketika distribusi data berubah seiring waktu.
- Membandingkan akurasi hutan daring secara langsung dengan Random Forest batch yang dilatih pada seluruh dataset historis — yang terakhir memiliki keuntungan informasi yang melekat.
- Menggunakan terlalu sedikit pohon di awal aliran sebelum setiap pohon melihat cukup data untuk membuat pemisahan yang andal.
- Lupa bahwa bagging berbobot Poisson mendekati bootstrap — itu tidak secara tepat mereproduksi sifat statistik bootstrap batch.
Pertanyaan yang sering diajukan
Bagaimana Online Random Forest berbeda dari Random Forest standar?
Random Forest Standar melatih semua pohon sekaligus pada seluruh dataset menggunakan pengambilan sampel bootstrap. Online Random Forest menggantikan bootstrap batch dengan bagging daring berbobot Poisson, memperbarui pemisahan pohon secara inkremental saat setiap observasi tiba, dan secara opsional mendeteksi dan beradaptasi dengan drift konsep — semua tanpa menyimpan data masa lalu.
Apa trik pembobotan Poisson?
Setiap contoh yang masuk ditampilkan ke setiap pohon k kali, di mana k ditarik dari Poisson(1). Karena nilai harapan k adalah 1, dan k = 0 dengan probabilitas ~37%, ini secara statistik mendekati proses bootstrap (pengambilan sampel dengan penggantian) tanpa memerlukan seluruh dataset dalam memori.
Bagaimana cara mengevaluasi random forest daring?
Gunakan protokol prequential (test-then-train): untuk setiap observasi yang masuk, pertama prediksi dengan model saat ini, catat kesalahannya, lalu perbarui model. Ini memberikan perkiraan kinerja prediktif yang tidak bias dan berurutan secara temporal tanpa kebocoran data.
Kapan saya harus menambahkan deteksi drift?
Kapan pun proses penghasil data kemungkinan akan berubah seiring waktu — misalnya, preferensi pengguna, pasar keuangan, atau sistem mekanis yang aus. Tanpa deteksi drift, pohon yang basi menumpuk dan menurunkan akurasi ansambel. ADWIN adalah pilihan yang umum dan teruji dengan baik.
Apakah Adaptive Random Forest sama?
ARF adalah varian Random Forest Daring yang paling banyak diadopsi. Ini menggabungkan bagging daring, pemilihan fitur acak, dan deteksi drift ADWIN per-pohon, dan tersedia di pustaka MOA dan scikit-multiflow/River. Istilah 'Online Random Forest' sering merujuk secara generik ke keluarga; ARF adalah implementasi spesifik yang sangat direkomendasikan.
Metode terkait
Sumber
Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.
Buka referensi publikasiDisalin.Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.
Buka referensi DOIDisalin.