Implementations of the Random Forest algorithm

Question

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

Answer 1

I must admit I'm only using R implementations, so I can at least say that party is few times slower than randomForest (yet offers greater control over the algorithm).

Non-R implementations I have heard of are The Original One, ALGLIB, Waffles, so-called WEKA rf, Random Jungle, rt-rank and PARF. Only two of them are parallel, PARF via MPI and Weka via multithreading. And well, judging from the source none of them was really written with performance in mind, so I don't expect than any of them would be rocket faster than randomForest (or at least fast enough to make me switch from R). Also note they differ in the tree building algorithm they use, so they are not all compatible with the original.

Reassuming, the answer is no, there is no highly-optimized RF implementation, however this is not a burning issue as in case of heavy-BLAS-using algorithms like SVM; RF is already quite fast, scales well, and even though it is trivially parallelizable it is usually easier to parallelize the analysis on higher level (CV, feature selection, repetitions, datasets, etc.).

Answer 2

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

Answer 3

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.

Answer 4

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/