# Random forest algorithm

I have a question about Random Forest 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).

I think I understand the most steps, except step 3. How do we in practice predict the classes? Does anyone have a simple explanation? Because I cant find any explanation online... I understand that :

Finally a response class is predicted in each terminal node of the tree (or each rectangular section in the partition respectively) by means of deriving from all observations in this node either the average response value in regression or the most frequent response class in classification trees. Note that this means that a regression tree creates a piecewise (or rectangle-wise for two dimensions and cuboid-wise in higher dimensions) constant prediction function.

But I am trying to understand How do we use Out Of Bag data later for finding prediction error?

For example I am trying to understand In an ensemble of trees the predictions of all individual trees need to be combined. This is usually accomplished by means of (weighted or unweighted) averaging in regression or voting in classification. The term “voting” can be taken literally here: Each subject with given values of the predictor variables is “dropped through” every tree in the ensemble, so that each single tree returns a predicted class for the subject. The class that most trees “vote” for is returned as the prediction of the ensemble. This democratic voting process is the reason why ensemble methods are also called “committee” methods. Note, however, that there is no diagnostic for the unanimity of the vote. For regression and for predicting probabilities, i.e. relative class frequencies, the results of the single trees are averaged; some algorithms also employ weighted averages.

Best Regards!

I might not fully understand the question - but for what it is worth:

1. The random forest is a collection of individual trees.
2. Each tree uses a subset of parameters, and (critically) a subset of the observations. It then "fits" a tree on this subset of the observations (of which you know the class).
3. THe prediction error is calculated by making a prediction using the fitted model on the "rest" of the observations, and comparing the predicted classes with the actual classes.
4. the final prediction error of the forest is the average error across all the trees in the random forest.

The book "The Elements of Statistical Learning" might explain this more clearly.

• The error is the median, not the mean. Jun 12 '13 at 17:02
• @Wouter Yes, but if I have a continious response variable (regression task,not classification) how is the averaging done? Say I have 5 terminal nodes in a tree. Do I average the observations in every terminal node of the tree first? Do I then average those averages over all terminal nodes of the tree? Or then over the forest? Or not?:) Jun 12 '13 at 17:42
• Yes. A new observation enters each tree in the ensemble, follows its rules. Ends up in a terminal node in each tree. The prediction for each tree for that new observation is the average of the 5 labeled observations (the default in the vanilla rf implementation for regression) of the corresponding terminal node. You then average the prediction of each tree. Jun 13 '13 at 8:49
• @JEquihua Ok! Do I understand correctly if I say: Observations of Out Of Bag data for each single tree is "run" down that specific tree and falls in specific different "bins", aka terminal nodes. Then we first: 1. average the data in each single terminal node first. And then: 2. We average the averages of each single terminal node over the single tree. And then: 3. Take the average from each single tree from step 2 and average over the forest?  Thanks for your help! Jun 13 '13 at 11:43
• Yes, that seems correct. Jun 13 '13 at 13:25