47
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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, doi.org/10.1093/bioinformatics/btq257. code: 1; 2; 3; 4. $\endgroup$
    – User128525
    Commented Mar 14, 2019 at 15:56

5 Answers 5

Reset to default
33
$\begingroup$

(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.

Improve this answer
$\endgroup$
4
  • 7
    $\begingroup$ One can now add sklearn.ensemble from the Python scikit-learn toolbox. $\endgroup$
    – chl
    Commented Jan 17, 2012 at 20:32
  • 1
    $\begingroup$ Milk in Python also has a Random Forest implementation. $\endgroup$
    – JEquihua
    Commented Mar 26, 2013 at 14:35
  • 3
    $\begingroup$ 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 (arxiv.org/abs/1508.04409). $\endgroup$
    – NoviceProg
    Commented Sep 4, 2015 at 14:20
  • $\begingroup$ isn't randomForest implemented in FORTRAN ? $\endgroup$
    – Qbik
    Commented Dec 10, 2022 at 14:12
14
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ but combined forests lose some functionality - summaries of errors are not combined (or rather recalculated) and so one $\endgroup$
    – Qbik
    Commented Dec 10, 2022 at 14:27
7
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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/

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – NoviceProg
    Commented Sep 4, 2015 at 14:26
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.