Implementaciones optimizadas del algoritmo Random Forest

43

Me he dado cuenta de que hay algunas implementaciones de bosque aleatorio como ALGLIB, Waffles y algunos paquetes R como randomForest. ¿Alguien puede decirme si estas bibliotecas están altamente optimizadas? ¿Son básicamente equivalentes a los bosques aleatorios como se detalla en Los elementos del aprendizaje estadístico o se han agregado muchos trucos adicionales?

Espero que esta pregunta sea lo suficientemente específica. Como ilustración del tipo de respuesta que estoy buscando, si alguien me preguntara si el paquete de álgebra lineal BLAS estaba altamente optimizado, diría que estaba extremadamente optimizado y no vale la pena intentar mejorarlo, excepto en aplicaciones muy especializadas.

random-forest algorithms model-evaluation Henry B.
fuente
Random Jungle puede ejecutarse en muchos servidores de forma paralela. Ver: Schwarz, et al (2010). De safari a Random Jungle: una implementación rápida de Random Forests para datos de alta dimensión. Bioinformática, 26 , 14, págs. 1752–8, doi.org/10.1093/bioinformatics/btq257 . código: 1 ; 2 ; 3 ; 4 .
Usuario128525

Respuestas:

31

(Actualizado 6 IX 2015 con sugerencias de comentarios, también hecho CW)

Hay dos paquetes nuevos y agradables disponibles para R que están bastante bien optimizados para ciertas condiciones:

  • ranger - C ++, el paquete de R, optimizado para problemas, paralelo, tratamiento especial de datos GWAS.p>>n
  • Arborist - Los enlaces de C ++, Python, R y optimizados para a gran problemas, al parecer los planes para GPGPU.n

Otras implementaciones de RF:

  • The Original One : código Fortran independiente, no paralelo, bastante difícil de usar.
  • randomForest : paquete C, R, probablemente el más popular, no paralelo, en realidad bastante rápido en comparación con una velocidad de un solo núcleo, especialmente para datos pequeños.
  • randomForestSRC - Paquete C, R, clon de randomForest que admite problemas de procesamiento y supervivencia paralelos.
  • party - paquete C, R, bastante lento, pero diseñado como un avión para experimentar con RF.
  • bigrf - C + / R, paquete R, creado para trabajar en big data dentro del marco bigmemory ; bastante lejos de estar completo.
  • scikit learn Ensemble forest - Python, parte del marco scikit-learn, paralelo, implementa muchas variantes de RF.
  • RF de leche - Python, parte del marco de la leche.
  • Waffles : C ++, parte de un kit de herramientas ML más grande, paralelo y bastante rápido.
  • llamado WEKA rf - Java / WEKA, paralelo.
  • ALGLIB
  • Random Jungle - abandonado?
  • rt-rank - abandonado?
  • PARF : ¿abandonado?

El papel de guardabosques tiene algunas comparaciones de velocidad / memoria, pero no hay un punto de referencia exhaustivo.

usuario88
fuente
66
Ahora se puede agregar sklearn.ensemble de la caja de herramientas de Python scikit-learn.
chl
1
Milk in Python también tiene una implementación de Random Forest.
JEquihua
3
Random Jungle ha sido reemplazado por Ranger. He probado el R ver (hay otro C ++ ver) y es notablemente más rápido que randomForest (aunque no lo cronometré). El autor ha realizado algunas pruebas en un documento separado ( arxiv.org/abs/1508.04409 ).
NovicioProg
11

Hasta donde yo sé, la versión R de randomForest llama al mismo código Fortran que la versión original. Además, es trivial paralelizar la función randomForest. En realidad, es uno de los ejemplos proporcionados en la documentación foreach .

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

Dado que los bosques aleatorios son vergonzosamente paralelos, la mayor optimización que puede hacer es ejecutarlos en paralelo. Después de eso, no creo que haya ninguna otra fruta baja en el algoritmo, pero podría estar equivocado.

El único problema es que pierdes la estimación de error fuera de la bolsa en el bosque combinado, pero probablemente haya una forma simple de calcularlo (en realidad me encantaría saber cómo hacer esto).

Zach
fuente
7

El ELSII usó randomForest (ver, por ejemplo, nota al pie 3 p.591), que es una implementación R del código Fortran de Breiman y Cutler de Salford. El código de Andy Liaw está en C.

Hay otra implementación de RFs propuesta en el paquete de fiesta (en C), que se basa en R / Lapack, que tiene algunas dependencias en BLAS (consulte /include/R_ext/Lapack.hen su directorio base R).

En lo que respecta al embolsado, no debería ser demasiado difícil paralelizarlo, pero dejaré que usuarios más especializados respondan sobre este aspecto.

chl
fuente
5

El equipo detrás de randomJungle afirma que es un orden de magnitud más rápido que la implementación R randomForest y usa una magnitud de orden menos memoria. Se está desarrollando un paquete para randomJungle para R, pero todavía no puedo construirlo.

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

gpr
fuente
No estoy seguro si esto sigue siendo de su interés después de 4 años, pero el (los) autor (es) de randomJungle lo ha reemplazado con Ranger. He probado el R ver y de hecho es notablemente más rápido que randomForest con algunos datos de muestra (aunque no lo cronometré).
NoviceProg