机器学习

A random forest is an ensemble learning method where multiple decision trees are constructed
and then they are merged to get a more accurate prediction.
If there is one method in machine learning that has grown in popularity over the last few years,
then it is the idea of random forests. The concept has been around for longer than that, with several
different people inventing variations, but the name that is most strongly attached to it is that of
Breiman, who also described the CART algorithm in unit 2.
Figure 3: Example of random forest with majority voting
The idea is largely that if one tree is good, then many trees (a forest) should be better, provided
that there is enough variety between them. The most interesting thing about a random forest is the
ways that it creates randomness from a standard dataset. The first of the methods that it uses is the
one that we have just seen: bagging. If we wish to create a forest then we can make the trees different
by training them on slightly different data, so we take bootstrap samples from the dataset for each tree.
However, this isn’t enough randomness yet. The other obvious place where it is possible to add
randomness is to limit the choices that the decision tree can make. At each node, a random subset of
the features is given to the tree, and it can only pick from that subset rather than from the whole set.
As well as increasing the randomness in the training of each tree, it also speeds up the training,
since there are fewer features to search over at each stage. Of course, it does introduce a new
parameter (how many features to consider), but the random forest does not seem to be very sensitive
to this parameter; in practice, a subset size that is the square root of the number of features seems to
be common. The effect of these two forms of randomness is to reduce the variance without effecting
the bias. Another benefit of this is that there is no need to prune the trees. There is another parameter
that we don’t know how to choose yet, which is the number of trees to put into the forest. However,
this is fairly easy to pick if we want optimal results: we can keep on building trees until the error stops
decreasing.
Once the set of trees are trained, the output of the forest is the majority vote for classification,
as with the other committee methods that we have seen, or the mean response for regression. And
those are pretty much the main features needed for creating a random forest. The algorithm is given
next before we see some results of using the random forest.
Algorithm
Here is an outline of the random forest algorithm.
1. The random forests algorithm generates many classification trees. Each tree is generated as
follows:
a) If the number of examples in the training set is N, take a sample of N examples at
random - but with replacement, from the original data. This sample will be the training
set for generating the tree.
b) If there are M input variables, a number m is specified such that at each node, m
variables are selected at random out of the M and the best split on these m is used to
68
2.split the node. The value of m is held constant during the generation of the various
trees in the forest.
c) Each tree is grown to the largest extent possible.
To classify a new object from an input vector, put the input vector down each of the trees in the
forest. Each tree gives a classification, and we say the tree “votes” for that class. The forest
chooses the classification
The implementation of this is very easy: we modify the decision to take an extra parameter, which is m,
the number of features that should be used in the selection set at each stage. We will look at an
example of using it shortly as a comparison to boosting.
Looking at the algorithm you might be able to see that it is a very unusual machine learning
method because it is embarrassingly parallel: since the trees do not depend upon each other, you can
both create and get decisions from different trees on different individual processors if you have them.
This means that the random forest can run on as many processors as you have available with nearly
linear speedup.
There is one more nice thing to mention about random forests, which is that with a little bit of
programming effort they come with built-in test data: the bootstrap sample will miss out about 35% of
the data on average, the so-called out-of-bootstrap examples. If we keep track of these datapoints then
they can be used as novel samples for that particular tree, giving an estimated test error that we get
without having to use any extra datapoints.
This avoids the need for cross-validation.
As a brief example of using the random forest, we start by demonstrating that the random
forest gets the correct results on the Party example that has been used in both this and the previous
chapters, based on 10 trees, each trained on 7 samples, and with just two levels allowed in each tree:
As a rather more involved example, the car evaluation dataset in the UCI Repository contains 1,728
examples aiming to classify whether or not a car is a good purchase based on six attributes. The
following results compare a single decision tree, bagging, and a random forest with 50 trees, each based
on 100 samples, and with a maximum depth of five for each tree. It can be seen that the random forest
is the most accurate of the three methods.
69
Strengths and weaknesses
Strengths
The following are some of the important strengths of random forests.
• 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 has an effective method for estimating missing data and maintains accuracy when a large
proportion of the data are missing.
• 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.
• 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.
• Random forest run times are quite fast, and they are able to deal with unbalanced and missing
data.
• They can handle binary features, categorical features, numerical features without any need for
scaling.
Weaknesses
•
 A weakness of random forest algorithms is that when used for regression they cannot predict
beyond the range in the training data, and that they may over-fit data sets that are particularly
noisy.
70
•
•
The sizes of the models created by random forests may be very large. It may take hundreds of
megabytes of memory and may be slow to evaluate.
Random forest models are black boxes that are very hard to interpret.