Implementasi yang dioptimalkan dari algoritma Random Forest

43

Saya perhatikan ada beberapa implementasi dari hutan acak seperti ALGLIB, Waffles dan beberapa paket R seperti randomForest. Adakah yang bisa memberi tahu saya apakah perpustakaan ini sangat optimal? Apakah mereka pada dasarnya setara dengan hutan acak seperti yang dijelaskan dalam Elemen Pembelajaran Statistik atau apakah banyak trik tambahan telah ditambahkan?

Saya harap pertanyaan ini cukup spesifik. Sebagai ilustrasi dari jenis jawaban yang saya cari, jika seseorang bertanya kepada saya apakah paket aljabar linier BLAS sangat dioptimalkan, saya akan mengatakan itu sangat sangat dioptimalkan dan sebagian besar tidak layak untuk dicoba ditingkatkan kecuali dalam aplikasi yang sangat khusus.

random-forest algorithms model-evaluation Henry B.
sumber
Random Jungle dapat berjalan di banyak server secara paralel. Lihat: Schwarz, et al (2010). Di safari ke Random Jungle: implementasi acak dari Hutan Acak untuk data dimensi tinggi. Bioinformatika, 26 , 14, hlm 1752–8, doi.org/10.1093/bioinformatics/btq257 . kode: 1 ; 2 ; 3 ; 4 .
User128525

Jawaban:

31

(Diperbarui 6 IX 2015 dengan saran dari komentar, juga dibuat CW)

Ada dua paket baru yang bagus untuk R yang dioptimalkan dengan cukup baik untuk kondisi tertentu:

  • ranger - C ++, paket R, dioptimalkan untuk masalah, paralel, perlakuan khusus data GWAS.p>>n
  • Arborist - C ++, R dan Python binding, dioptimalkan untuk besar- masalah, tampaknya rencana untuk GPGPU.n

Implementasi RF lainnya:

  • The Original One - kode Fortran mandiri, tidak paralel, cukup sulit digunakan.
  • randomForest - C, paket R, mungkin yang paling populer, bukan paralel, sebenarnya cukup cepat jika dibandingkan dengan kecepatan single-core, terutama untuk data kecil.
  • randomForestSRC - C, paket R, klon randomForest mendukung pemrosesan paralel dan masalah kelangsungan hidup.
  • party - C, paket R, cukup lambat, tetapi dirancang sebagai pesawat untuk bereksperimen dengan RF.
  • paket bigrf - C + / R, R, dibangun untuk mengerjakan data besar dalam kerangka memori besar ; cukup jauh dari lengkap.
  • scikit belajar Ensemble forest - Python, bagian dari kerangka scikit-learning, paralel, mengimplementasikan banyak varian RF.
  • susu 's RF - Python, bagian dari kerangka susu.
  • Waffles - C ++, bagian dari toolkit ML yang lebih besar, paralel dan cukup cepat.
  • disebut WEKA rf - Java / WEKA, parallel.
  • ALGLIB
  • Hutan Acak - ditinggalkan?
  • rt-rank - ditinggalkan?
  • PARF - ditinggalkan?

Kertas Ranger memiliki perbandingan kecepatan / memori, tetapi tidak ada patokan menyeluruh.

pengguna88
sumber
6
Satu sekarang dapat menambahkan sklearn.ensemble dari Python scikit-learn toolbox.
chl
1
Milk in Python juga memiliki implementasi Random Forest.
JEquihua
3
Jungle Acak telah digantikan oleh Ranger. Saya sudah mencoba R ver (ada lagi C ++ ver) dan itu terasa lebih cepat daripada randomForest (saya tidak menghitung waktu sekalipun). Penulis telah melakukan beberapa pengujian dalam makalah yang terpisah ( arxiv.org/abs/1508.04409 ).
NoviceProg
11

Sejauh yang saya tahu, versi R dari randomForest memanggil kode Fortran yang sama dengan versi aslinya. Selain itu, itu sepele untuk memparalelkan fungsi randomForest. Ini sebenarnya salah satu contoh yang disediakan dalam dokumentasi foreach .

library(foreach)
library(randomForest)
rf <- foreach(ntree = rep(250, 4), .combine = combine, .packages = "randomForest") %dopar% 
randomForest(x, y, ntree = ntree)

Mengingat bahwa hutan acak paralel paralelnya, optimasi terbesar yang dapat Anda lakukan adalah menjalankannya secara paralel. Setelah itu, saya tidak berpikir ada buah lain yang menggantung rendah dalam algoritme, tapi saya bisa salah.

Satu-satunya masalah adalah Anda kehilangan perkiraan kesalahan out-of-bag di hutan gabungan, tetapi mungkin ada cara sederhana untuk menghitungnya (saya benar-benar ingin mengetahui bagaimana melakukan ini).

Zach
sumber
7

The ELSII digunakan randomForest (lihat misalnya, catatan kaki 3 p.591), yang merupakan implementasi R dari Breiman dan Cutler kode Fortran dari Salford. Kode Andy Liaw dalam C.

Ada implementasi RF lain yang diusulkan dalam paket partai (dalam C), yang bergantung pada R / Lapack, yang memiliki beberapa dependensi pada BLAS (lihat /include/R_ext/Lapack.hdi direktori R dasar Anda).

Sejauh menyangkut pengemasan, seharusnya tidak terlalu sulit untuk memparalelasinya, tetapi saya akan membiarkan lebih banyak pengguna khusus menjawab pada aspek ini.

chl
sumber
5

Tim di balik randomJungle mengklaim bahwa urutan besarnya lebih cepat dari implementasi R randomForest dan menggunakan urutan besarnya lebih sedikit memori. Paket untuk randomJungle sedang dikembangkan untuk R tapi saya belum bisa membuatnya.

https://r-forge.r-project.org/projects/rjungler/

gpr
sumber
Tidak yakin apakah ini masih menarik bagi Anda setelah 4 tahun tetapi penulis randomJungle telah menggantikannya dengan Ranger. Saya sudah mencoba R ver dan itu memang terasa lebih cepat daripada randomForest dengan beberapa data sampel (saya tidak menghitung waktu sekalipun).
NoviceProg