Random forest

Random forests or random decision forests is an ensemble learning method for classification, regression and other tasks that works by creating a multitude of decision trees during training. For classification tasks, the output of the random forest is the class selected by most trees. For regression tasks, the output is the average of the predictions of the trees. Random forests correct for decision trees' habit of overfitting to their training set. The first algorithm for random decision forests was created in 1995 by Tin Kam Ho using the random subspace method, which, in Ho's formulation, is a way to implement the "stochastic discrimination" approach to classification proposed by Eugene Kleinberg. An extension of the algorithm was developed by Leo Breiman and Adele Cutler, who registered "Random Forests" as a trademark in 2006 ( , owned by Minitab, Inc.). The extension combines Breiman's "bagging" idea and random selection of features, introduced first by Ho and later independently by Amit and Geman in order to construct a collection of decision trees with controlled variance.

Random forests or random decision forests is an ensemble learning method for classification, regression and other tasks that works by creating a multitude of decision trees during training. For classification tasks, the output of the random forest is the class selected by most trees. For regression tasks, the output is the average of the predictions of the trees. Random forests correct for decision trees' habit of overfitting to their training set. The first algorithm for random decision forests was created in 1995 by Tin Kam Ho using the random subspace method, which, in Ho's formulation, is a way to implement the "stochastic discrimination" approach to classification proposed by Eugene Kleinberg. An extension of the algorithm was developed by Leo Breiman and Adele Cutler, who registered "Random Forests" as a trademark in 2006 ( , owned by Minitab, Inc.). The extension combines Breiman's "bagging" idea and random selection of features, introduced first by Ho and later independently by Amit and Geman in order to construct a collection of decision trees with controlled variance. ==Algorithm== ===Preliminaries: decision tree learning=== Decision trees are a popular method for various machine learning tasks. Tree learning is almost "an off-the-shelf procedure for data mining", say Hastie et al., "because it is invariant under scaling and various other transformations of feature values, is robust to inclusion of irrelevant features, and produces inspectable models. However, they are seldom accurate". In particular, trees that are grown very deep tend to learn highly irregular patterns: they overfit their training sets, i.e. have low bias, but very high variance. Random forests are a way of averaging multiple deep decision trees, trained on different parts of the same training set, with the goal of reducing the variance. This comes at the expense of a small increase in the bias and some loss of interpretability, but generally greatly boosts the performance in the final model. ===Bagging=== The training algorithm for random forests applies the general technique of bootstrap aggregating, or bagging, to tree learners. Given a training set = , ..., with responses = , ..., , bagging repeatedly (B times) selects a random sample with replacement of the training set and fits trees to these samples: After training, predictions for unseen samples can be made by averaging the predictions from all the individual regression trees on : \hat{f} = \frac{1}{B} \sum_{b=1}^Bf_b (x') or by taking the plurality vote in the case of classification trees. This bootstrapping procedure leads to better model performance because it decreases the variance of the model, without increasing the bias. This means that while the predictions of a single tree are highly sensitive to noise in its training set, the average of many trees is not, as long as the trees are not correlated. Simply training many trees on a single training set would give strongly correlated trees (or even the same tree many times, if the training algorithm is deterministic); bootstrap sampling is a way of de-correlating the trees by showing them different training sets. Additionally, an estimate of the uncertainty of the prediction can be made as the standard deviation of the predictions from all the individual regression trees on : \sigma = \sqrt{\frac{\sum_{b=1}^B (f_b(x') - \hat{f})^2}{B-1} }. The number of samples (equivalently, of trees) is a free parameter. Typically, a few hundred to several thousand trees are used, depending on the size and nature of the training set. can be optimized using cross-validation, or by observing the out-of-bag error: the mean prediction error on each training sample , using only the trees that did not have in their bootstrap sample. The training and test error tend to level off after some number of trees have been fit. ===From bagging to random forests=== The above procedure describes the original bagging algorithm for trees. Random forests also include another type of bagging scheme: they use a modified tree learning algorithm that selects, at each candidate split in the learning process, a random subset of the features. This process is sometimes called "feature bagging". The reason for doing this is the correlation of the trees in an ordinary bootstrap sample: if one or a few features are very strong predictors for the response variable (target output), these features will be selected in many of the trees, causing them to become correlated. An analysis of how bagging and random subspace projection contribute to accuracy gains under different conditions is given by Ho. Typically, for a classification problem with p features, \sqrt{p} (rounded down) features are used in each split. For regression problems the inventors recommend p/3 (rounded down) with a minimum node size of 5 as the default. In practice, the best values for these parameters should be tuned on a case-to-case basis for every problem. ===ExtraTrees=== Adding one further step of randomization yields extremely randomized trees, or ExtraTrees. As with ordinary random forests, they are an ensemble of individual trees, but there are two main differences: (1) each tree is trained using the whole learning sample (rather than a bootstrap sample), and (2) the top-down splitting is randomized: for each feature under consideration, a number of random cut-points are selected, instead of computing the locally optimal cut-point (based on, e.g., information gain or the Gini impurity). The values are chosen from a uniform distribution within the feature's empirical range (in the tree's training set). Then, of all the randomly chosen splits, the split that yields the highest score is chosen to split the node. Similar to ordinary random forests, the number of randomly selected features to be considered at each node can be specified. Default values for this parameter are \sqrt{p} for classification and p for regression, where p is the number of features in the model. ===Random forests for high-dimensional data=== The basic random forest procedure may not work well in situations where there are a large number of features but only a small proportion of these features are informative with respect to sample classification. This can be addressed by encouraging the procedure to focus mainly on features and trees that are informative. Some methods for accomplishing this are: Prefiltering: Eliminate features that are mostly just noise. Enriched Random Forest (ERF): Use weighted random sampling instead of simple random sampling at each node of each tree, giving greater weight to features that appear to be more informative. Tree-weighted random forest (TWRF): Give more weight to more accurate trees. ==Properties== To measure a feature's importance in a data set \mathcal{D}_n =\{(X_i, Y_i)\}_{i=1}^n , first a random forest is trained on the data. During training, the out-of-bag error for each data point is recorded and averaged over the forest. (If bagging is not used during training, we can instead compute errors on an independent test set.) After training, the values of the feature are permuted in the out-of-bag samples and the out-of-bag error is again computed on this perturbed data set. The importance for the feature is computed by averaging the difference in out-of-bag error before and after the permutation over all trees. The score is normalized by the standard deviation of these differences. Features which produce large values for this score are ranked as more important than features which produce small values. The statistical definition of the variable importance measure was given and analyzed by Zhu et al. This method of determining variable importance has some drawbacks: When features have different numbers of values, random forests favor features with more values. Solutions to this problem include partial permutations and growing unbiased trees. If the data contain groups of correlated features of similar relevance, then smaller groups are favored over large groups. If there are collinear features, the procedure may fail to identify important features. A solution is to permute groups of correlated features together. This approach to feature importance for random forests considers as important the variables which decrease a lot the impurity during splitting. It is described in the book Classification and Regression Trees by Leo Breiman and is the default implementation in scikit learn and R. The definition is: \text{unormalized average importance}(x)=\frac{1}{n_T} \sum_{i=1}^{n_T} \sum_{\text{node }j \in T_i | \text{split variable}(j) = x} p_{T_i}(j)\Delta i_{T_i}(j), where x is a feature n_T is the number of trees in the forest T_i is tree i p_{T_i}(j)=\frac{n_j}{n} is the fraction of samples reaching node j \Delta i_{T_i}(j) is the change in impurity in tree i at node j . As impurity measure for samples falling in a node e.g. the following statistics can be used: Entropy Gini coefficient Mean squared error The normalized importance is then obtained by normalizing over all features, so that the sum of normalized feature importances is 1. The scikit learn default implementation can report misleading feature importance: it favors high cardinality features it uses training statistics and so does not reflect a feature's usefulness for predictions on a test set A relationship between random forests and the -nearest neighbor algorithm ( -NN) was pointed out by Lin and Jeon in 2002. Both can be viewed as so-called weighted neighborhoods schemes. These are models built from a training set \{(x_i, y_i)\}_{i=1}^n that make predictions \hat{y} for new points by looking at the "neighborhood" of the point, formalized by a weight function : \hat{y} = \sum_{i=1}^n W(x_i, x') \, y_i. Here, W(x_i, x') is the non-negative weight of the 'th training point relative to the new point in the same tree. For any , the weights for points x_i must sum to 1. Weight functions are as follows: In -NN, W(x_i, x') = \frac{1}{k} if is one of the points closest to , and zero otherwise. In a tree, W(x_i, x') = \frac{1}{k'} if is one of the points in the same leaf as , and zero otherwise. Since a forest averages the predictions of a set of trees with individual weight functions W_j , its predictions are \hat{y} = \frac{1}{m}\sum_{j=1}^m\sum_{i=1}^n W_{j}(x_i, x') \, y_i = \sum_{i=1}^n\left(\frac{1}{m}\sum_{j=1}^m W_{j}(x_i, x')\right) \, y_i. This shows that the whole forest is again a weighted neighborhood scheme, with weights that average those of the individual trees. The neighbors of in this interpretation are the points x_i sharing the same leaf in any tree j . In this way, the neighborhood of depends in a complex way on the structure of the trees, and thus on the structure of the training set. Lin and Jeon show that the shape of the neighborhood used by a random forest adapts to the local importance of each feature. ==Kernel random forest== In machine learning, kernel random forests (KeRF) establish the connection between random forests and kernel methods. By slightly modifying their definition, random forests can be rewritten as kernel methods, which are more interpretable and easier to analyze. Given a training sample \mathcal{D}_n =\{(\mathbf{X}_i, Y_i)\}_{i=1}^n of [0,1]^p\times\mathbb{R} -valued independent random variables distributed as the independent prototype pair (\mathbf{X}, Y) , where \operatorname{E}[Y^2] . We aim at predicting the response Y , associated with the random variable \mathbf{X} , by estimating the regression function m(\mathbf{x})=\operatorname{E}[Y \mid \mathbf{X} = \mathbf{x}] . A random regression forest is an ensemble of M randomized regression trees. Denote m_n(\mathbf{x},\mathbf{\Theta}_j) the predicted value at point \mathbf{x} by the j -th tree, where \mathbf{\Theta}_1,\ldots,\mathbf{\Theta}_M are independent random variables, distributed as a generic random variable \mathbf{\Theta} , independent of the sample \mathcal{D}_n . This random variable can be used to describe the randomness induced by node splitting and the sampling procedure for tree construction. The trees are combined to form the finite forest estimate m_{M, n}(\mathbf{x},\Theta_1,\ldots,\Theta_M) = \frac{1}{M}\sum_{j=1}^M m_n(\mathbf{x},\Theta_j) . For regression trees, we have m_n = \sum_{i=1}^n\frac{Y_i\mathbf{1}_{\mathbf{X}_i\in A_n(\mathbf{x},\Theta_j)}}{N_n(\mathbf{x}, \Theta_j)} , where A_n(\mathbf{x},\Theta_j) is the cell containing \mathbf{x} , designed with randomness \Theta_j and dataset \mathcal{D}_n , and N_n(\mathbf{x}, \Theta_j) = \sum_{i=1}^n \mathbf{1}_{\mathbf{X}_i\in A_n(\mathbf{x}, \Theta_j)} . Thus random forest estimates satisfy, for all \mathbf{x}\in[0,1]^d , m_{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) =\frac{1}{M}\sum_{j=1}^M \left(\sum_{i=1}^n\frac{Y_i\mathbf{1}_{\mathbf{X}_i\in A_n(\mathbf{x},\Theta_j)}}{N_n(\mathbf{x}, \Theta_j)}\right) . Random regression forest has two levels of averaging, first over the samples in the target cell of a tree, then over all trees. Thus the contributions of observations that are in cells with a high density of data points are smaller than that of observations which belong to less populated cells. In order to improve the random forest methods and compensate the misestimation, Scornet defined KeRF by \tilde{m}_{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) = \frac{1}{\sum_{j=1}^M N_n(\mathbf{x}, \Theta_j)}\sum_{j=1}^M\sum_{i=1}^n Y_i\mathbf{1}_{\mathbf{X}_i\in A_n(\mathbf{x}, \Theta_j)}, which is equal to the mean of the Y_i 's falling in the cells containing \mathbf{x} in the forest. If we define the connection function of the M finite forest as K_{M,n}(\mathbf{x}, \mathbf{z}) = \frac{1}{M} \sum_{j=1}^M \mathbf{1}_{\mathbf{z} \in A_n (\mathbf{x}, \Theta_j)} , i.e. the proportion of cells shared between \mathbf{x} and \mathbf{z} , then almost surely we have \tilde{m}_{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) = \frac{\sum_{i=1}^n Y_i K_{M,n}(\mathbf{x}, \mathbf{x}_i)}{\sum_{\ell=1}^n K_{M,n}(\mathbf{x}, \mathbf{x}_{\ell})} , which defines the KeRF. K_k^{cc}(\mathbf{x},\mathbf{z}) = \sum_{k_1,\ldots,k_d, \sum_{j=1}^d k_j=k} \frac{k!}{k_1!\cdots k_d!} \left(\frac 1 d \right)^k \prod_{j=1}^d\mathbf{1}_{\lceil2^{k_j}x_j\rceil=\lceil2^{k_j}z_j\rceil}, \qquad \text{ for all } \mathbf{x},\mathbf{z}\in[0,1]^d. K_k^{uf}(\mathbf{0},\mathbf{x}) = \sum_{k_1,\ldots,k_d, \sum_{j=1}^d k_j=k} \frac{k!}{k_1!\ldots k_d!}\left(\frac{1}{d}\right)^k \prod_{m=1}^d\left(1-|x_m|\sum_{j=0}^{k_m-1}\frac{\left(-\ln|x_m|\right)^j}{j!}\right) \text{ for all } \mathbf{x}\in[0,1]^d. a_n\leq N_n(\mathbf{x},\Theta)\leq b_n \text{ and } a_n\leq \frac 1 M \sum_{m=1}^M N_n {\mathbf{x},\Theta_m}\leq b_n. Then almost surely, |m_{M,n}(\mathbf{x}) - \tilde{m}_{M,n}(\mathbf{x})| \le\frac{b_n-a_n}{a_n} \tilde{m}_{M,n}(\mathbf{x}). |m_{\infty,n}(\mathbf{x})-\tilde{m}_{\infty,n}(\mathbf{x})| \le \frac{b_n-a_n}{a_n}\tilde{m}_{\infty,n}(\mathbf{x}) + n \varepsilon_n \left( \max_{1\le i\le n} Y_i \right). Assume that Y = m(\mathbf{X}) + \varepsilon , where \varepsilon is a centered Gaussian noise, independent of \mathbf{X} , with finite variance \sigma^2 . Moreover, \mathbf{X} is uniformly distributed on [0,1]^d and m is Lipschitz. Scornet proved upper bounds on the rates of consistency for centered KeRF and uniform KeRF.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373673788 under CC BY-SA 4.0; modifications have been made.