Optimierte Implementierungen des Random Forest-Algorithmus

44

Mir ist aufgefallen, dass es einige Implementierungen von Random Forest wie ALGLIB, Waffles und einige R-Pakete gibt randomForest. Kann mir jemand sagen, ob diese Bibliotheken hoch optimiert sind? Entsprechen sie im Wesentlichen den Zufallsforsten, wie in den Elementen des statistischen Lernens beschrieben, oder wurden viele zusätzliche Tricks hinzugefügt?

Ich hoffe, diese Frage ist spezifisch genug. Als Beispiel für die Art der Antwort, nach der ich suche, würde ich sagen, wenn mich jemand fragte, ob das BLAS-Paket für lineare Algebra in hohem Maße optimiert ist, dass es in höchstem Maße optimiert ist und es meistens nicht wert ist, verbessert zu werden, außer in sehr speziellen Anwendungen.

random-forest algorithms model-evaluation Henry B.
quelle
Random Jungle kann auf vielen Servern parallel ausgeführt werden. Siehe: Schwarz et al. (2010). Auf Safari zu Random Jungle: eine schnelle Implementierung von Random Forests für hochdimensionale Daten. Bioinformatics, 26 , 14, S. 1752–8, doi.org/10.1093/bioinformatics/btq257 . Code: 1 ; 2 ; 3 ; 4 .
User128525

Antworten:

31

(Aktualisiert 6 IX 2015 mit Vorschlägen aus Kommentaren, auch CW gemacht)

Es gibt zwei neue, nette Pakete für R, die für bestimmte Bedingungen ziemlich gut optimiert sind:

  • Ranger - C ++, R Paket, optimiert für Probleme, parallel, eine besondere Behandlung von GWAS Daten.p>>n
  • Arborist - C ++ -, R- und Python-Bindungen, optimiert für Probleme, planen offenbar GPGPU.n

Andere RF-Implementierungen:

  • Der Original One - eigenständiger Fortran-Code, nicht parallel, ziemlich schwer zu benutzen.
  • randomForest - C, R-Paket, wahrscheinlich das beliebteste, nicht parallele, im Vergleich zu Single-Core-Geschwindigkeit sogar recht schnell, insbesondere für kleine Datenmengen.
  • randomForestSRC - C, R-Paket, Klon von randomForest, der Parallelverarbeitungs- und Überlebensprobleme unterstützt.
  • Party- C, R-Paket, ziemlich langsam, aber als Flugzeug zum Experimentieren mit RF konzipiert.
  • bigrf - C + / R, R-Paket, das für die Arbeit mit Big Data innerhalb des BigMemory-Frameworks entwickelt wurde ; bei weitem nicht vollständig.
  • scikit learn Ensemble forest - Python, Teil des scikit learn-Frameworks, implementiert viele RF-Varianten.
  • Milch RF - Python, Teil des Milchgerüsts.
  • Waffeln - C ++, Teil eines größeren ML-Toolkits, parallel und recht schnell.
  • so genannte WEKA rf - Java / WEKA, parallel.
  • ALGLIB
  • Zufälliger Dschungel - verlassen?
  • RT-Rang - aufgegeben?
  • PARF - aufgegeben?

Ranger-Papier hat einige Geschwindigkeits- / Speichervergleiche, aber es gibt keinen gründlichen Benchmark.

user88
quelle
6
Man kann jetzt sklearn.ensemble aus der Python-Toolbox für Scikit-Learn hinzufügen .
chl
1
Milk in Python hat auch eine Random Forest-Implementierung.
JEquihua
3
Random Jungle wurde von Ranger abgelöst. Ich habe die R-Version ausprobiert (es gibt eine andere C ++ - Version) und sie ist merklich schneller als randomForest (ich habe sie jedoch nicht zeitlich festgelegt). Der Autor hat einige Tests in einem separaten Artikel durchgeführt ( arxiv.org/abs/1508.04409 ).
NoviceProg
11

Soweit ich weiß, nennt die R-Version von randomForest denselben Fortran-Code wie die Originalversion. Darüber hinaus ist es trivial, die randomForest-Funktion zu parallelisieren. Tatsächlich ist es eines der Beispiele in der Dokumentation zu foreach .

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

Da zufällige Gesamtstrukturen peinlich parallel sind, können Sie sie am besten parallel ausführen. Danach glaube ich, dass der Algorithmus keine anderen niedrig hängenden Früchte enthält, aber ich könnte mich irren.

Das einzige Problem ist, dass Sie die Out-of-Bag-Fehlerabschätzung in der kombinierten Gesamtstruktur verlieren, aber es gibt wahrscheinlich einen einfachen Weg, sie zu berechnen (ich würde gerne herausfinden, wie das geht).

Zach
quelle
7

Das ELSII verwendete randomForest (siehe z. B. Fußnote 3, S. 591), eine R-Implementierung des Breiman and Cutler's Fortran-Codes von Salford. Andy Liaws Code ist in C.

Es gibt eine weitere Implementierung von RFs, die im Party- Paket (in C) vorgeschlagen wird und auf R / Lapack basiert, das einige Abhängigkeiten von BLAS aufweist (siehe /include/R_ext/Lapack.hin Ihrem Basis-R-Verzeichnis).

Was das Absacken betrifft, sollte es nicht zu schwierig sein, es zu parallelisieren, aber ich werde spezialisiertere Benutzer auf diesen Aspekt antworten lassen.

chl
quelle
5

Das Team hinter randomJungle behauptet, dass dies eine Größenordnung schneller ist als die Implementierung von R randomForest und eine Größenordnung weniger Speicherplatz benötigt. Ein Paket für randomJungle wird für R entwickelt, aber ich kann es noch nicht erstellen.

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

gpr
quelle
Ich bin mir nicht sicher, ob dies nach 4 Jahren noch für Sie von Interesse ist, aber der / die Autor (en) von randomJungle hat / haben es mit Ranger abgelöst. Ich habe das R ver ausprobiert und es ist in der Tat mit einigen Beispieldaten merklich schneller als randomForest (ich habe es jedoch nicht zeitlich festgelegt).
NoviceProg