47

I have noticed that there are a few implementations of random forest such as ALGLIB, Waffles and some R packages like randomForest. Can anybody tell me whether these libraries are highly optimized? Are they basically equivalent to the random forests as detailed in The Elements of Statistical Learning or have a lot of extra tricks been added?

I hope this question is specific enough. As an illustration of the type of answer I am looking for, if somebody asked me whether the linear algebra package BLAS was highly optimized, I would say it was extremely highly optimized and mostly not worth trying to improve upon except in very specialized applications.

QuantIbex
  • 3,880
  • 1
  • 24
  • 42
Henry B.
  • 1,479
  • 1
  • 14
  • 19
  • Random Jungle can run on many servers in a parallel manner. See: Schwarz, et al (2010). On safari to Random Jungle: a fast implementation of Random Forests for high-dimensional data. *Bioinformatics, 26*, 14, pp 1752–8, https://doi.org/10.1093/bioinformatics/btq257. code: [1](https://sourceforge.net/p/randomjungle/code/HEAD/tree/trunk/); [2](https://github.com/gitpan/RandomJungle); [3](https://github.com/insilico/randomjungle); [4](https://github.com/texane/randomjungle). – User128525 Mar 14 '19 at 15:56

5 Answers5

32

(Updated 6 IX 2015 with suggestions from comments, also made CW)

There are two new, nice packages available for R which are pretty well optimised for a certain conditions:

  • ranger -- C++, R package, optimised for $p>>n$ problems, parallel, special treatment of GWAS data.
  • Arborist -- C++, R and Python bindings, optimised for large-$n$ problems, apparently plans for GPGPU.

Other RF implementations:

  • The Original One -- standalone Fortran code, not parallel, pretty hard to use.
  • randomForest -- C, R package, probably the most popular, not parallel, actually quite fast when compared on a single-core speed basis, especially for small data.
  • randomForestSRC -- C, R package, clone of randomForest supporting parallel processing and survival problems.
  • party -- C, R package, quite slow, but designed as a plane for experimenting with RF.
  • bigrf -- C+/R, R package, built to work on big data within bigmemory framework; quite far from being complete.
  • scikit learn Ensemble forest -- Python, part of scikit-learn framework, parallel, implements many variants of RF.
  • milk's RF -- Python, part of milk framework.
  • so-called WEKA rf -- Java/WEKA, parallel.
  • ALGLIB
  • rt-rank -- abandoned?

Ranger paper has some speed/memory comparisons, but there is no thorough benchmark.

Community
  • 1
  • 7
    One can now add [sklearn.ensemble](http://scikit-learn.org/stable/modules/ensemble.html) from the Python scikit-learn toolbox. – chl Jan 17 '12 at 20:32
  • 1
    Milk in Python also has a Random Forest implementation. – JEquihua Mar 26 '13 at 14:35
  • 3
    Random Jungle has been superseded by Ranger. I've tried the R ver (there is another C++ ver) and it is noticeably faster than randomForest (I didn't time it though). The author has done some testing in a separate paper (http://arxiv.org/abs/1508.04409). – NoviceProg Sep 04 '15 at 14:20
12

As far as I know, the R version of randomForest calls the same Fortran code as the original version. Furthermore, it's trivial to parallelize the randomForest function. It's actually one of the examples provided in the foreach documentation.

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

Given that random forests are embarrassingly parallel, the biggest optimization you can make is running them in parallel. After that, I don't think there's any other low-hanging fruit in the algorithm, but I could be wrong.

The only issue is that you lose the out-of-bag error estimate in the combined forest, but there's probably a simple way to calculate it (I'd actually love to find out how to do this).

chl
  • 50,972
  • 18
  • 205
  • 364
Zach
  • 22,308
  • 18
  • 114
  • 158
7

The ELSII used randomForest (see e.g., footnote 3 p.591), which is an R implementation of the Breiman and Cutler's Fortran code from Salford. Andy Liaw's code is in C.

There's another implementation of RFs proposed in the party package (in C), which relies on R/Lapack, which has some dependencies on BLAS (see/include/R_ext/Lapack.h in your base R directory).

As far as bagging is concerned, it should not be too hard to parallelize it, but I'll let more specialized users answer on this aspect.

chl
  • 50,972
  • 18
  • 205
  • 364
5

The team behind randomJungle claims that is an order of magnitude faster than the R randomForest implementation and uses an order magnitude less memory. A package for randomJungle is being developed for R but I can't get to build yet.

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

gpr
  • 51
  • 1
  • 1
  • Not sure if this is still of interest to you after 4 years but the author(s) of randomJungle has superseded it with Ranger. I've tried the R ver and it is indeed noticeably faster than randomForest with some sample data (I didn't time it though). – NoviceProg Sep 04 '15 at 14:26
3

For the Javascript Implementation go through this demo.

If you are like a child who is hungry for a chocolate, here is your chocolate of random forest http://cs.stanford.edu/people/karpathy/svmjs/demo/demoforest.html

madhu131313
  • 131
  • 4