Random forest

This article is about the machine learning technique. For other kinds of random tree, see Random tree (disambiguation).

Random forest (or random forests) is an ensemble classifier that consists of many decision trees and outputs the class that is the mode of the class's output by individual trees. The algorithm for inducing a random forest was developed by Leo Breiman and Adele Cutler, and "Random Forests" is their trademark. The term came from random decision forests that was first proposed by Tin Kam Ho of Bell Labs in 1995. The method combines Breiman's "bagging" idea and the random selection of features, introduced independently by Ho and Amit and Geman in order to construct a collection of decision trees with controlled variation.

The selection of a random subset of features is an example of the random subspace method, which, in Ho's formulation, is a way to implement stochastic discrimination proposed by Eugene Kleinberg.

Learning algorithm

Each tree is constructed using the following algorithm:

1. Let the number of training cases be N, and the number of variables in the classifier be M.
2. We are told the number m of input variables to be used to determine the decision at a node of the tree; m should be much less than M.
3. Choose a training set for this tree by choosing N times with replacement from all N available training cases (i.e. take a bootstrap sample). Use the rest of the cases to estimate the error of the tree, by predicting their classes.
4. For each node of the tree, randomly choose m variables on which to base the decision at that node. Calculate the best split based on these m variables in the training set.
5. Each tree is fully grown and not pruned (as may be done in constructing a normal tree classifier).

Features and Advantages

The advantages of random forest are:

• It is unexcelled in accuracy among current algorithms. For many data sets, it produces a highly accurate classifier
• It runs efficiently on large data bases.
• It can handle thousands of input variables without variable deletion.
• It gives estimates of what variables are important in the classification.
• It generates an internal unbiased estimate of the generalization error as the forest building progresses.
• It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing.
• It has methods for balancing error in class population unbalanced data sets.
• Generated forests can be saved for future use on other data.
• Prototypes are computed that give information about the relation between the variables and the classification.
• It computes proximities between pairs of cases that can be used in clustering, locating outliers, or (by scaling) give interesting views of the data.
• The capabilities of the above can be extended to unlabeled data, leading to unsupervised clustering, data views and outlier detection.
• It offers an experimental method for detecting variable interactions.
• Learning is fast

Disadvantages

• Random forests are prone to overfitting for some datasets. This is even more pronounced in noisy classification/regression tasks.
• Random forests do not handle large numbers of irrelevant features as well as ensembles of entropy-reducing decision trees.
• It is more efficient to select a random decision boundary than an entropy-reducing decision boundary, thus making larger ensembles more feasible. Although this may seem to be an advantage at first, it has the effect of shifting the computation from training time to evaluation time, which is actually a disadvantage for most applications.

See also

• Random multinomial logit
• Random naive Bayes

Commercial implementation

• [1] Random Forests.

Open source implementations

• The Original RF by Breiman and Cutler. Written in Fortran 77. May be difficult to configure.
• ALGLIB contains implementation of modified random forest algorithm in C#, C++, Pascal, VBA.
• FastRandomForest Efficient implementation in Java, utilitizes multiple cores. Integrates into the Weka environment.
• orngEnsemble module within Orange data mining software suite
• PARF Written in Fortran 90. Can distribute work over a cluster of computers using MPI.
• party an implementation of Breiman's random forests based on conditional inference trees for R
• randomForest for R
• TMVA Toolkit for Multivariate Data Analysis implements random forests.
• milk for Python implements random forests.
• Waffles A C++ library of machine learning algorithms, including RF.
• [2] Matlab version.
• Apache Mahout

External links

• Random Forests classifier description (Site of Leo Breiman)
• Liaw, Andy & Wiener, Matthew "Classification and Regression by randomForest" R News (2002) Vol. 2/3 p. 18 (Discussion of the use of the random forest package for R)
• Ho, Tin Kam (2002). "A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors". Pattern Analysis and Applications 5, p. 102-112 (Comparison of bagging and random subspace method)
• Prinzie, A., Van den Poel, D. (2007). Random Multiclass Classification: Generalizing Random Forests to Random MNL and Random NB, Dexa 2007, Lecture Notes in Computer Science, 4653, 349-358. Generalizing Random Forests framework to other methods. The paper introduces Random MNL and Random NB as two generalizations of Random Forests.
• Prinzie, A., Van den Poel, D. (2008). Random Forests for multiclass classification: Random MultiNomial Logit, Expert Systems with Applications, 34(3), 1721-1732. Generalization of Random Forests to choice models like the Multinomial Logit Model (MNL): Random Multinomial Logit.
• Stochastic Discrimination and Its Implementation (Site of Eugene Kleinberg).