Implémentations optimisées de l'algorithme Random Forest

43

J'ai remarqué qu'il existe quelques implémentations de forêt aléatoire telles que ALGLIB, Waffles et certains packages R tels que randomForest. Quelqu'un peut-il me dire si ces bibliothèques sont hautement optimisées? Sont-ils fondamentalement équivalents aux forêts aléatoires décrites dans Les éléments de l’apprentissage statistique ou ont-ils été complétés de nombreuses astuces?

J'espère que cette question est assez spécifique. Pour illustrer le type de réponse que je recherche, si quelqu'un me demandait si le progiciel d'algèbre linéaire BLAS était hautement optimisé, je dirais qu'il était extrêmement optimisé et qu'il ne valait surtout pas la peine d'être amélioré, sauf dans des applications très spécialisées.

random-forest algorithms model-evaluation Henry B.
la source
Random Jungle peut fonctionner sur de nombreux serveurs de manière parallèle. Voir: Schwarz et al (2010). Safari to Random Jungle: une implémentation rapide de Random Forests pour des données de grande dimension. Bioinformatics, 26 , 14, pp 1752–18, doi.org/10.1093/bioinformatics/btq257 . code: 1 ; 2 ; 3 ; 4 .
User128525

Réponses:

31

(Mise à jour du 6 IX 2015 avec les suggestions des commentaires, également faite en CW)

Il existe deux nouveaux packages intéressants pour R qui sont plutôt bien optimisés pour certaines conditions:

  • ranger - C ++, package R, optimisé pour problèmes, en parallèle, un traitement spécial des données GWAS.p>>n
  • Arboriculteur - C ++, R et liaisons Python, optimisés pour à grande problèmes, semble - t - plans pour GPGPU.n

Autres implémentations RF:

  • The Original One - Code Fortran autonome, pas parallèle, assez difficile à utiliser.
  • randomForest - Le package C, R, probablement le plus populaire, pas parallèle, est en fait assez rapide par rapport à la vitesse sur un cœur, en particulier pour les petites données.
  • package randomForestSRC - C, R, clone de randomForest prenant en charge le traitement parallèle et les problèmes de survie.
  • party - C, R package, assez lent, mais conçu comme un avion pour expérimenter avec RF.
  • bigrf - package C + / R, R, conçu pour fonctionner sur le Big Data dans le cadre BigMemory ; assez loin d'être complet.
  • scikit learn Ensemble Forest - Python, une partie du framework scikit-learn, parallèle, implémente de nombreuses variantes de RF.
  • lait RF - Python, une partie de la structure du lait.
  • Gaufres - C ++, faisant partie d’un ensemble d’outils plus vaste, parallèle et assez rapide.
  • WEKA rf - Java / WEKA, parallèle.
  • ALGLIB
  • Random Jungle - abandonné?
  • rt-rank - abandonné?
  • PARF - abandonné?

Le papier Ranger présente certaines comparaisons vitesse / mémoire, mais il n’existe pas de référence complète.

utilisateur88
la source
6
On peut maintenant ajouter sklearn.ensemble à partir de la boîte à outils Python scikit-learn.
chl
1
Milk in Python a également une implémentation Random Forest.
JEquihua
3
Random Jungle a été remplacé par Ranger. J'ai essayé le ver (il y a un autre ver C ++) et il est nettement plus rapide que randomForest (je ne l'ai pas chronométré cependant). L'auteur a effectué des tests dans un document séparé ( arxiv.org/abs/1508.04409 ).
NoviceProg
11

Autant que je sache, la version R de randomForest appelle le même code Fortran que la version d'origine. De plus, il est trivial de paralléliser la fonction randomForest. C'est en fait l'un des exemples fournis dans la documentation foreach .

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

Étant donné que les forêts aléatoires sont embarrassantes en parallèle, la plus grande optimisation que vous puissiez faire est de les exécuter en parallèle. Après cela, je ne pense pas que l'algorithme ait un fruit à portée de main, mais je peux me tromper.

Le seul problème est que vous perdez l'estimation d'erreur hors du sac dans la forêt combinée, mais il existe probablement un moyen simple de la calculer (j'aimerais en fait savoir comment faire cela).

Zach
la source
7

Le ELSII utilisé forêt d'arbres décisionnels (voir par exemple référence 3 p.591), qui est une implémentation R du Breiman et Cutler Code Fortran de Salford. Le code de Andy Liaw est en C.

Il existe une autre implémentation de RF proposée dans le package de parti (en C), qui repose sur R / Lapack, qui dépend de BLAS (voir /include/R_ext/Lapack.hdans votre répertoire de base R).

En ce qui concerne l'ensachage, il ne devrait pas être trop difficile de le mettre en parallèle, mais je laisserai aux utilisateurs plus spécialisés le soin de répondre à cet aspect.

chl
la source
5

L'équipe à l'origine de randomJungle affirme que l'ordre de grandeur est plus rapide que l'implémentation de R randomForest et qu'il utilise moins de mémoire en ordre. Un paquet pour randomJungle est en cours de développement pour R mais je ne peux pas encore le construire.

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

gpr
la source
Je ne sais pas si cela vous intéresse toujours après 4 ans, mais le ou les auteurs de randomJungle l’ont remplacé avec Ranger. J'ai essayé le ver et il est en effet sensiblement plus rapide que randomForest avec quelques exemples de données (je ne l'ai pas chronométré cependant).
NoviceProg