Implementações otimizadas do algoritmo Random Forest

43

Notei que existem algumas implementações de floresta aleatória, como ALGLIB, Waffles e alguns pacotes R, como randomForest. Alguém pode me dizer se essas bibliotecas são altamente otimizadas? Eles são basicamente equivalentes às florestas aleatórias, conforme detalhado em Os elementos do aprendizado estatístico, ou foram adicionados muitos truques extras?

Espero que esta pergunta seja específica o suficiente. Como ilustração do tipo de resposta que estou procurando, se alguém me perguntasse se o pacote de álgebra linear BLAS era altamente otimizado, eu diria que ele era extremamente altamente otimizado e, principalmente, não vale a pena tentar melhorar, exceto em aplicações muito especializadas.

random-forest algorithms model-evaluation Henry B.
fonte
O Random Jungle pode ser executado em muitos servidores de maneira paralela. Ver: Schwarz, et al. (2010). No safari para Random Jungle: uma implementação rápida de Random Forests para dados de alta dimensão. Bioinformatics, 26 , 14, pp 1752–8, doi.org/10.1093/bioinformatics/btq257 . código: 1 ; 2 ; 3 ; 4 .
User128525

Respostas:

31

(Atualizado em 6 de IX de 2015, com sugestões de comentários, também feitas CW)

Existem dois pacotes novos e agradáveis ​​disponíveis para o R, que são bastante otimizados para determinadas condições:

  • ranger - C ++, pacote R, optimizado para problemas, em paralelo, um tratamento especial de dados GWAS.p>>n
  • Arborist - ligações C ++, R e Python, otimizados para de larga problemas, aparentemente planos para GPGPU.n

Outras implementações de RF:

  • O código Fortran original e autônomo, não paralelo, bastante difícil de usar.
  • randomForest - pacote C, R, provavelmente o mais popular, não paralelo, na verdade, bastante rápido quando comparado com base na velocidade de núcleo único, especialmente para dados pequenos.
  • randomForestSRC - pacote C, R, clone do randomForest que suporta problemas de processamento e sobrevivência paralelos.
  • party - pacote C, R, bastante lento, mas projetado como um plano para experimentar com RF.
  • bigrf - pacote C + / R, R, desenvolvido para trabalhar com big data dentro da estrutura de bigmemory ; longe de estar completo.
  • scikit learn Floresta de conjunto - Python, parte da estrutura scikit-learn, paralela, implementa muitas variantes de RF.
  • leite RF 's - Python, parte do quadro de leite.
  • Waffles - C ++, parte de um kit de ferramentas ML maior, paralelo e bastante rápido.
  • chamado WEKA rf - Java / WEKA, paralelo.
  • ALGLIB
  • Selva aleatória - abandonada?
  • rt-rank - abandonado?
  • PARF - abandonado?

O papel Ranger possui algumas comparações de velocidade / memória, mas não há um benchmark completo.

usuário88
fonte
6
Agora é possível adicionar sklearn.ensemble a partir da caixa de ferramentas Python scikit-learn.
chl
1
O Milk em Python também possui uma implementação de Floresta Aleatória.
JEquihua
3
A selva aleatória foi substituída pela guarda florestal. Eu tentei a versão R (existe outra versão em C ++) e é notavelmente mais rápida que randomForest (embora não tenha sido o tempo). O autor fez alguns testes em um artigo separado ( arxiv.org/abs/1508.04409 ).
precisa saber é o seguinte
11

Tanto quanto eu sei, a versão R do randomForest chama o mesmo código Fortran que a versão original. Além disso, é trivial paralelizar a função randomForest. Na verdade, é um dos exemplos fornecidos na documentação do foreach .

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

Dado que as florestas aleatórias são embaraçosamente paralelas, a maior otimização que você pode fazer é executá-las em paralelo. Depois disso, acho que não há outra fruta no algoritmo, mas posso estar errado.

O único problema é que você perde a estimativa de erro pronto para uso na floresta combinada, mas provavelmente existe uma maneira simples de calculá-la (eu adoraria descobrir como fazer isso).

Zach
fonte
7

O ELSII usou randomForest (veja, por exemplo, nota de rodapé 3 p.591), que é uma implementação R do código Fortran de Breiman e Cutler de Salford. O código de Andy Liaw está em C.

Há outra implementação de RFs proposta no pacote de partes (em C), que depende do R / Lapack, que possui algumas dependências do BLAS (consulte /include/R_ext/Lapack.ho diretório R básico).

No que diz respeito à ensacamento, não deve ser muito difícil paralelizá-la, mas deixarei que usuários mais especializados respondam sobre esse aspecto.

chl
fonte
5

A equipe por trás do randomJungle afirma que é uma ordem de magnitude mais rápida que a implementação R randomForest e usa uma magnitude de ordem menos memória. Um pacote para randomJungle está sendo desenvolvido para o R, mas ainda não consigo construir.

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

gpr
fonte
Não tenho certeza se isso ainda lhe interessa após 4 anos, mas o (s) autor (es) da randomJungle a substituíram pelo Ranger. Eu tentei o R ver e é realmente visivelmente mais rápido do que randomForest com alguns dados de amostra (eu não o cronometrei).
NoviceProg