Zoptymalizowane implementacje algorytmu Random Forest

44

Zauważyłem, że istnieje kilka implementacje losowej lasu, takich jak ALGLIB, gofry i kilka pakietów, takich jak R randomForest. Czy ktoś może mi powiedzieć, czy te biblioteki są wysoce zoptymalizowane? Czy są one w zasadzie równoważne losowym lasom opisanym w Elementach statystycznego uczenia się, czy też dodano wiele dodatkowych sztuczek?

Mam nadzieję, że to pytanie jest wystarczająco szczegółowe. Jako ilustrację rodzaju odpowiedzi, której szukam, gdyby ktoś zapytał mnie, czy pakiet algebry liniowej BLAS był wysoce zoptymalizowany, powiedziałbym, że był bardzo wysoce zoptymalizowany i przeważnie nie warto próbować go ulepszać, z wyjątkiem bardzo wyspecjalizowanych aplikacji.

random-forest algorithms model-evaluation Henry B.
źródło
Random Jungle może działać równolegle na wielu serwerach. Patrz: Schwarz i in. (2010). Na safari do Losowej Dżungli: szybka implementacja Losowych Lasów dla danych wielowymiarowych. Bioinformatics, 26 , 14, s. 1752–8, doi.org/10.1093/bioinformatics/btq257 . kod: 1 ; 2 ; 3 ; 4 .
128525

Odpowiedzi:

31

(Zaktualizowano 6 IX 2015 z sugestiami z komentarzy, również CW)

Dostępne są dwa nowe, ładne pakiety dla R, które są dość dobrze zoptymalizowane do określonych warunków:

  • ranger - pakiet C ++, R, zoptymalizowany pod kątem problemów , równoległe, specjalne traktowanie danych GWAS.p>>n
  • Arborist - C ++, R Python wiązania, zoptymalizowanych dla wielkoskalowymi problemów, jak widać planów GPGPU.n

Inne wdrożenia RF:

  • Pierwotny - samodzielny kod Fortran, nie równoległy, bardzo trudny w użyciu.
  • randomForest - pakiet C, R, prawdopodobnie najpopularniejszy, nie równoległy, w rzeczywistości dość szybki w porównaniu z szybkością jednordzeniową, szczególnie w przypadku małych danych.
  • randomForestSRC - pakiet C, R, klon randomForest wspierający równoległe problemy przetwarzania i przetrwania.
  • party - pakiet C, R, dość wolny, ale zaprojektowany jako samolot do eksperymentowania z RF.
  • bigrf - pakiet C + / R, R, zbudowany do pracy z dużymi danymi w ramach bigmemory ; całkiem dalekie od ukończenia.
  • scikit learn Ensemble forest - Python, część frameworku scikit-learn, równolegle, implementuje wiele wariantów RF.
  • mleko RF - Python, część frameworka mleka.
  • Gofry - C ++, część większego zestawu narzędzi ML, równoległe i dość szybkie.
  • tak zwana WEKA rf - Java / WEKA, równolegle.
  • ALGLIB
  • Losowa dżungla - porzucona?
  • rt-rank - porzucony?
  • PARF - porzucony?

Papier Ranger ma pewne porównania prędkości / pamięci, ale nie ma dokładnego testu porównawczego.

użytkowników88
źródło
6
Można teraz dodać sklearn.ensemble z przybornika Python scikit-learn.
chl
1
Milk in Python ma również implementację Random Forest.
JEquihua
3
Losowa dżungla została zastąpiona przez Komandosa. Wypróbowałem wersję R (istnieje inna wersja C ++) i jest zauważalnie szybsza niż randomForest (chociaż tego nie czas). Autor przeprowadził pewne testy w osobnym artykule ( arxiv.org/abs/1508.04409 ).
NoviceProg,
11

O ile mi wiadomo, wersja R randomForest wywołuje ten sam kod Fortran, co wersja oryginalna. Co więcej, zrównoleglenie funkcji randomForest jest banalne. To właściwie jeden z przykładów podanych w dokumentacji Foreach .

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

Biorąc pod uwagę, że losowe lasy są żenująco równoległe, największą optymalizacją, jaką możesz zrobić, jest ich równoległe uruchamianie. Po tym nie sądzę, że w algorytmie są inne nisko wiszące owoce, ale mogę się mylić.

Jedynym problemem jest to, że tracisz oszacowanie błędu braku torby w połączonym lesie, ale prawdopodobnie istnieje prosty sposób, aby go obliczyć (naprawdę chciałbym dowiedzieć się, jak to zrobić).

Zach
źródło
7

W ELSII zastosowano randomForest (patrz np. Przypis 3, s. 591), który jest implementacją R kodu Breiman i Cutlera Fortrana z Salford. Kod Andy'ego Liawa znajduje się w C.

Istnieje kolejna implementacja RF zaproponowana w pakiecie partyjnym (w C), który opiera się na R / Lapack, który ma pewne zależności od BLAS (patrz /include/R_ext/Lapack.hw twoim podstawowym katalogu R).

Jeśli chodzi o pakowanie, to nie powinno być zbyt trudne do zrównoleglenia go, ale pozwolę bardziej wyspecjalizowanym użytkownikom odpowiedzieć na ten temat.

chl
źródło
5

Zespół stojący za randomJungle twierdzi, że jest o rząd wielkości szybszy niż implementacja random random R i używa o rząd wielkości mniej pamięci. Pakiet dla randomJungle jest opracowywany dla R, ale nie mogę go jeszcze skompilować.

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

gpr
źródło
Nie jestem pewien, czy to Cię interesuje po 4 latach, ale autor (autorzy) randomJungle zastąpił go Rangerem. Wypróbowałem wersję R i jest ona rzeczywiście zauważalnie szybsza niż randomForest z pewnymi przykładowymi danymi (chociaż tego nie czas).
NoviceProg,