In the R randomForest package for random forest feature selection, how is the dataset split for training and testing?

Question

I'm using the randomForest R package to perform a random forest feature selection. I undestand that, after the execution of the randomForest function, I have to check the importance field, and study the importance measured throudh mean square error accuracy reduction and Gini purity reduction.

For example, by using this R code:

data(iris)
library("randomForest")
set.seed(71)
iris.rf <- randomForest(Species ~ ., data=iris, importance=TRUE,
proximity=TRUE)
print(iris.rf)

It will print out:

                     MeanDecreaseAccuracy  MeanDecreaseGini
        Sepal.Width  0.007962441             2.625413
        Sepal.Length 0.031901722            10.714741
        Petal.Length 0.304760304            42.104241
        Petal.Width  0.300907912            43.767952

Then, I see that I can rank these features by the MeanDecreaseAccuracy or MeanDecreaseGini field to understand what are the most important ones. Even if I understand the output of the method, I cannot understand how the method obtains its results.

The questions are:

1. How does the method compute the accuracy?
2. How does the method split the dataset into training set and test set to compute the accuracy?

Answer 1

It does not use a separate training and testing set. Instead, standard accuracy estimation in random forests takes advantage of an important feature: bagging, or bootstrap aggregation.

To construct a random forest, a large number of data subsets are generated by sampling with replacement from the full dataset. A separate decision tree is fit to each bootstrap data subset, the trees jointly forming the random forest. Each data point from the full dataset is present in approximately 2/3 of the bootstrap data subsets, and absent from the remaining 1/3. You can therefore use the 1/3 of trees that do not contain a point to predict what their value would be; these are called out-of-bag (OOB) estimates. This process avoids the overfitting problem (and arguably makes crossvalidation redundant for this purpose) since the points were not present in the trees used to predict them. By repeating this for every point in the full dataset and comparing the OOB predictions against the true values, you can calculate the accuracy of the random forest.

The mean decrease in accuracy metric (generally recommended) for a variable is calculated by permuting the values of this variable across the entire dataset and estimating how the accuracy of the random forest changes.

The mean decrease in Gini metric is explained this way by Breiman & Cutler (which I took from this helpful answer):

Every time a split of a node is made on variable m the gini impurity criterion for the two descendent nodes is less than the parent node. Adding up the gini decreases for each individual variable over all trees in the forest gives a fast variable importance that is often very consistent with the permutation importance measure.

Answer 2

In order to calculate mean decrease in accuracy randomForest doesn't use train and test sets per se it uses something called the out of bag sample. Since each tree is built using a bootstrap sample (a sample of the same size as your dataset sampled with replacement) there will be records that are in your dataset that are not used to build the tree, these records are called the out of bag (OOB) sample. You run these records down the tree and calculate their accuracy (you could think of the OOB records as your test set). In order to determine the mean decrease in accuracy you randomly permute one of the explanatory variables in your OOB sample and then rerun the OOB sample down the tree and recalculate the accuracy, the decrease you see in the accuracy is what the importance measure refers to.

Answer 3

If you want to have a more detailed description you can read the Wikipedia article that answers your questions: https://en.wikipedia.org/wiki/Random_forest

and this post: this is a nice post for a more detailed explanation: https://www.quora.com/What-is-the-out-of-bag-error-in-random-forests-What-does-it-mean-Whats-a-typical-value-if-any-Why-would-it-be-higher-or-lower-than-a-typical-value

But in short and just to start you up:

1) the random forest algorithm generates a set of decision trees

2) each tree is trained on a different, randomly chosen subset of the data (ca. 2/3) and using a different, randomly chosen subset of the features. so each decision tree in the random forest has a different test and training sets (answers your second question)

3) for each element X_i of the data you can then compute an out of bag error (OOB error). briefly you consider all the trees in the RF that are trained on a set not containing X_i. you compute an OOB error counting the percentage of those trees that fail classifying X_i. averaging this error on all data you get the OOB. Accuracy = 1-OOB