Boosted Random Forest
Yohei Mishina, Masamitsu Tsuchiya and Hironobu Fujiyoshi
Department of Computer Science, Chubu University, 1200 Matsumoto-cho, Kasugai, Aichi, Japan{mishi, mtdoll}@vision.cs.chubu.ac.jp, hf@cs.chubu.ac.jp

Keywords:

Boosting, Random Forest, Machine Learning, Pattern Recognition.

Abstract:

The ability of generalization by random forests is higher than that by other multi-class classifiers because of
the effect of bagging and feature selection. Since random forests based on ensemble learning requires a lot ofdecision trees to obtain high performance, it is not suitable for implementing the algorithm on the small-scale
hardware such as embedded system. In this paper, we propose a boosted random forests in which boostingalgorithm is introduced into random forests. Experimental results show that the proposed method, which
consists of fewer decision trees, has higher generalization ability comparing to the conventional method.

1INTRODUCTION

Random forest(Breiman, 2001) is a multi-class classifier that is robust against noise, has high discrimination performance, and is capable of training and classifying at high speed. It is therefore attracting attention in many fields, including computer vision, patternrecognition, and machine learning(Amit and Geman,1997), (Lepetit and p. Fua, 2006), (J. Shotton andCipolla, 2008), (J. Shotton et al., 2011), (Gall et al.,2011). Random forest controls loss of generalizationin training due to overfitting by introducing randomness in bagging and feature selection(Ho, 1998) whenconstructing an ensemble of decision trees. Eachdecision tree in random forest is independent, sohigh speed can be attained by parallel processing intree training and classification. Boosting(Freund andSchapire, 1995) is a typical ensemble training algorithm that is used to sequentially construct classifiers
for random forest that involve independent decision
trees. Boosting is an ensemble training algorithm thatcombines weak learners, which individually have low
discriminating performance, to construct a classifierof higher discriminating performance. Boosting generally attains high discrimination by sequential training of classifiers in which the training sample forwhich the previous classifier produced classification
errors is used to train the subsequent classifier to produce correct classification. However, boosting tends
to overfit the training sample. Random forest, on theother hand, uses randomness in the construction of thedecision trees, thus avoiding overfitting to the training
sample. For that reason, a large number of decisiontrees must be constructed to obtain high generality.
However, increasing the number of decision trees increases the memory requirements, so that approach is
not suited to implementation on small-scale hardware
such as embedded system. We therefore propose aboosted random forest method, in which a boostingalgorithm is introduced in random forest. The proposed method constructs complementary classifiers
by successive decision tree construction and can yieldclassifiers with smaller decision trees while maintaining discrimination performance.

2RANDOM FOREST

Random forest is an ensemble training algorithm thatconstructs multiple decision trees. It suppresses overfitting to the training samples by random selectionof training samples for tree construction in the same
way as is done in bagging(Breiman, 1996),(Breiman,1999), resulting in construction of a classifier that isrobust against noise. Also, random selection of features to be used at splitting nodes enables fast training, even if the dimensionality of the feature vector islarge.

2.1 Training Process
In the training of random forest, bagging is used tocreate sample sub sets by random sampling from thetraining sample. One sample set is used to construct
one decision tree. At splitting node n, sample set Sn
is split into sample sets Sl and Sr by comparing the%RRVWHG5DQGRP)RUHVW

value of feature quantity xi with a threshold value
τ. The splitting function of the splitting node selects combinations that can partition the most samples
from among randomly selected features {fk }Kk=1 andthreshold {τh }H
h=1 for each class. The recommended
number of feature selections, K, is the square root of
the feature dimensionality. The evaluation functionused for selecting the optimum combination is the information gain, ΔG. The splitting processing is repeated recursively until a certain depth is reached or
until the information gain is zero. A leaf node is thencreated and the class probability P(c|l) is stored.

2.2 Classification Process
An unknown sample is input to all of the decision
trees, and the class probabilities of the leaf nodes arrived at are output. The class that has the largest average of the class probabilities obtained from all of
the decision trees, Pt (c|x), according to Eq. (1) is theclassification decision.
P(c|x) =1 T
∑ Pt (c|x)
T t=1

(1)

2.3 Number of Decision Trees andDiscriminating Performance

Algorithm 1: Proposed method.
Require: Training samples {x1 , y1 , w1 }, . . ., {xN , yN , wN };xi ∈ X , yi ∈ {1, 2, . . ., M}, wi
Init: Initialize sample weight wi :(1)wi ⇐ N1 .
Run:for t = 1 : T do
Make subset St from training samples.
ΔGmax ⇐ −∞.
for k = 1 : K do
Random sampling from feature f k .
for h = 1 : H do
Random sampling from threshold τh .
Split Sn into Sl or Sr by f k and τh .
Compute information gain ΔG:ΔG = E(Sn ) − ||SSnl || E(Sl ) − ||SSnr| E(Sr ).
if ΔG > ΔGmax then
ΔGmax ⇐ ΔG
end ifend forend for
if ΔGmax = 0 or reach a maximum depth thenStore the probability distribution P(c|l) to leaf node.
elseGenerating a split node recursively.
end ifif Finished training of decision tree thenEstimate class label ŷi :ŷi = arg max Pt (c|l).
cCompute error rate of decision tree εt :N

Random forest achieves generality by using a large
number of decision trees for ensemble training. However, it is difficult to obtain the optimum number oftrees for training, so there are many redundant decision trees that consume a large amount of memory.

i:yi $=ŷi(t+1)

BOOSTED RANDOM FORESTN(t)i=1Compute weight of decision tree αt :t)αt = 21 log (M−1)(1−εεt
if α > 0 thenUpdate weight! of training sample wi,t+1 :wi3(t)εt = ∑ wi / ∑ wi .

(t)

=wi exp (αt ) if yi $= ŷi(t)wi exp (−αt ) otherwise.

else
Reject a tree
end ifend ifend forRandom forest is robust against noise and has highgenerality because of random training. However, it
requires many decision trees, as using fewer decision trees reduces performance. It therefore cannot
maintain generality when implemented on small-scale
hardware. For that reason, boosting is introduced torandom forest. The purpose of using boosting is tomaintain generality even with a small number of decision trees by using the fact that sequential training
constructs complementary decision trees for the training samples.

updating.
First, a training sample of size N,{x1 , y1 , w1 }, . . . , {xN , yN , wN }, that have a feature ofdimension d and class labels y ∈ M are prepared. Thetraining sample weight, w, is initialized to N1 . Samplesets are created by random sampling from the training sample. Decision trees are constructed using thesample sets in the same way as in random forest. Proposed algorithm 1 is described in above.

3.1 Training Process

3.1.1 Node Splitting

The proposed training algorithm involves one procedure for when the sample weighting is updated andanother procedure for when there is noThe flow of the proposed method is illustrated inFig. 1. The splitting function selects combinations ofrandomly-prepared features and thresholds that have9,6$33,QWHUQDWLRQDO&RQIHUHQFHRQ&RPSXWHU9LVLRQ7KHRU\DQG$SSOLFDWLRQVRound Learning Samples

SubsetDecisionTreeWeighttree is discarded. The training sample is classified by
the constructed decision trees and the error rate is calculated from the weights of the incorrectly classified
samples assample weight update

Nεt =(t)Figure 1: Training algorithm of the proposed method.

the highest information gain. The information gain
ΔG is computed by|S r ||S l |
E(S l ) −E(S r ),|S n ||S n |(2)

where Sn is sample set at node n, Sl is sample set atleft child node, Sr is sample set at right child node,and E(S ) is entropy computed byM

E(S ) = − ∑ P(c j ) log P(c j ).

(3)

j=1

In calculating the information gain, the samples areprioritized by largest weight and the probability ofclass c j , P(c j ), is calculated using the weight of sample i, wi computed using∑i∈S∧yi =c jwi / ∑ wi ,

(4)

i∈S

where, S is the sample set that arrived at node. A leaf
node is created when recursive splitting has developed
the decision tree to a certain depth or when the information gain of a sample set that has reached a node iszero. The leaf node stores the class probability P(c)obtained with Eq. (4).
3.1.2 Decision Tree Weighting

Decision trees that easily correct classification of thesamples that have been incorrectly classified in thenext step are constructed by making the weights ofincorrectly classified samples large as!
(t)
wi exp (αt ) if yi $= ŷi(t+1)
wi=(7)(t)wi exp (−αt ) otherwise,
where ŷi is estimated class label usingŷi = arg max Pt (c|l).

1(M − 1)(1 − εt )log,
2εt(5)

where, εt is the error rate of the decision tree and M
is the number of classes. The expected value for thesuccessful classification rate in random classificationis M1 . If the classification error rate exceeds 1 − M1 ,the value of α is negative in Eq. (5) and the decision(8)c

After updating the training sample weights, theweights are normalized to N. Constructing the decision trees and updating the training sample weights inthat way is repeated to obtain T decision trees and T
weighted decision trees. After all decision trees havebeen constructed, the decision tree weights are normalized.

3.2 Classification Process
An unknown sample is input to all of the decision
trees as shown in Fig. 1, and the class probabilities
that are stored in the arrived-at leaf nodes are output.
Than, the outputs of the decision trees, Pt (c|x), areweight-averaged using the decision tree weights asP(c|x) =1 T∑ αt Pt (c|x).
T t=1

(9)

The class that has the highest probability ŷ is output
as the classification result byŷ = arg max P(c|x).

In the same way as for multi-class boosting(Kim andCipolla, 2008), (Saberian and Vasconcelos, 2008), thedecision tree weight, αt , is calculated by
αt =(6)3.1.3 Updating Training Sample Weights

sample weight update

P(c j ) =(t)i=1i:yi $=ŷi

ΔG = E(S n ) −N∑ wi / ∑ wi .

(10)

c4

EXPERIMENTAL RESULTS

To show the effectiveness of the proposed method,
the number of nodes are compared for the proposed
method and the conventional method at the same levelof generalization ability. For the proposed method,
we investigated procedures with and without sequential sample weight updating.

%RRVWHG5DQGRP)RUHVW

4.1 Data Set

Table 4: Error rate by boosted random forest [%].

The evaluation experiments used four data sets,Pendigits, Letter, Satelite, and Spambase, from thosepublished by the UCI Machine Learning Repository
as a set of machine training algorithm benchmarks.
The data sets are described briefly in Table 1.

Depth5101520

Table 1: Data sets.

Training7,494
10,000
4,435
3,221

Tests
3,498
10,000
2,000
1,380

Class
1026
62Dim.
16
163657The error ratio for each dataset of the conventional random forest(RF) and for the proposed
method(boosted random forest with or without sample weight updating, BRF, BRF w/o updating) are
shown in Table 2, 3, and 4 respectively. The miss"",-""".,-"/01"2345678"

Spame
6.88
5.58
5.14
4.71

Ave.
12.82
6.69
6.13
5.92

Table 3: Error rate by boosted random forest w/o updating[%].

Depth
51015
20

Pen
8.183.92
3.66
3.72

Letter
22.75
7.50
6.20
6.10

Satelite
12.95
10.05
9.40
9.10

%!"

"".,-"

$#"
$!"

Spame
6.81
5.58
5.07
4.64

!" $!" %!" &!" '!" #!" (!" )!" *!" +!" $!!" $$!" $%!" $&!" $'!" $#!",-./(%$01$'%((#!

&!"
"",-"
%#"
!"##$%&'()*+!

"".,-"/01"2345678"%!""".,-"

$#"
$!"
#"
!"
!" $!" %!" &!" '!" #!" (!" )!" *!" +!" $!!" $$!" $%!" $&!" $'!" $#!",-./(%$01$'%((#!

Figure 2: Generalization error of pendigits.

Table 2: Error rate by random forest [%].

Satelite
13.05
9.95
9.30
9.10

Ave.
7.61
5.01
4.81
4.70

!"

4.3 Experimental Results

Letter
22.95
7.25
6.40
6.20

Spame
4.57
4.13
3.77
3.55

#"

In this experiment, the depth of the decision trees fortraining parameters was fixed at 5, 10, 15, and 20.
We compared the minimum value of the miss rate bychanging the number of decision trees. The numberof candidates for the split function was 10 times thesquare root of the number of feature dimensions.

Pen
8.38
3.97
3.66
3.69

Satelite
10.70
8.35
8.25
8.20

%#"

4.2 Training Parameter

Depth
510
1520

Letter
11.45
5.00
4.55
4.40

&!"

!"##$%&'()*+!

DatasetPendigits
LetterSatelite
Spamebase

Pen
3.72
2.55
2.69
2.66

Ave.
12.67
6.76
6.08
5.89

rate of the proposed method was lower than that of therandom forest when the number of depth for decision
trees was shallower. In contrast, when the number ofdepth for decision trees was deeper, the miss rate ofthe proposed method was equal to or lower than thatof the random forest. It is clear that the classification

performance of the boosted random forest with updating sample weight is superior. Figure 2 shows themiss rate for each depth in the case of the “Pendigits” dataset. From Fig. 2, we realized that the random forest requires more depth in order to obtain ahigher classification performance than the proposedmethod. In contrast, the proposed “boosted randomforest” method does not require more depth because
it has been trained by choosing the split function withdifficult training samples at upper nodes, which havea heavier sample weight.

4.4 Memory Usage for Decision Trees
For the implementation of decision trees on smallscale hardware, less memory is better. Therefore,
in this section we compare the amount of memory
needed for each method. For each node, the total
memory of a split function is 11 bytes, of which theselected feature dimension is 1 byte, the threshold is

9,6$33,QWHUQDWLRQDO&RQIHUHQFHRQ&RPSXWHU9LVLRQ7KHRU\DQG$SSOLFDWLRQV

2 bytes, and the pointer for a child node is 8 bytes.
For each leaf node, total memory is estimated by thenumber of class bytes. Thus, we estimate the amountof memory B required for decision trees byT

B = ∑ (Ns,t × 11 + Nl,t × M),

(11)

t=1

where the number of trees is T , number of split nodes
is Ns,t , number of leaf nodes is Nl,t and number ofclasses is M.
Figure 3 shows the amount of memory for eachmethod with minimum error rate and the reduction
ratio of the proposed method compared to the random forest. The amount of memory required by the(!!!#&%"!##""<=#""><=#?@A#B7,5C+.#$%!!#

3*,BDCA+#%!"!##!"#$%&'()*+,)-".'/0)*12,!

""><=#$!!!#'%!!#'!!!#$%"!##%!!#!#!"!##)*+,-.-/0#

1*2*3#

45/*6-/*#

4758*950*#:;*35.*#

Figure 3: Amount of memory and reduction rate.

proposed “boosted random forest” method is significantly reduced while maintaining the higher classification performance. Due to sequential training, theboosted random forest consists of complementary decision trees that enable the final classifier to be constructed in favor of those instances misclassified byprevious decision trees.

5CONCLUSIONS

We have proposed a boosted random forest in whicha boosting algorithm is introduced to a conventionalrandom forest. The boosted random forest maintains
a high classification performance, even with fewer
decision trees, because it constructs complementary
classifiers through sequential training by boosting.
Experimental results show that the total memory required by the boosted random forest is 47% lessthan that of the conventional random forest. It isthus suited to implementation in low-memory, smallscale hardware applications such as embedded systems. Our future work includes experimental evaluation for image recognition problems that are currently
difficult to classify.

REFERENCES
Amit, Y. and Geman, D. (1997). Shape quantization andrecognition with randomized trees. In Neural Computation. MIT Press.
Breiman, L. (1996). Bagging predictors. In Machine Learning. Springer.
Breiman, L. (1999). Using adaptive bagging to debias regressions. In Technical Report. Statistics Dept. UCB.
Breiman, L. (2001). Random forests. In Machine learning.
Springer.
Freund, Y. and Schapire, R. (1995). A decision-theoretic
generalization of on-line learning and an application to boosting. In Computational learning theory.
Springer.
Gall, J., Yao, A., Razavi, N., Van Gool, L., and Lempitsky,V. (2011). Hough forests for object detection, tracking, and action recognition. In Pattern Analysis andMachine Intelligence. IEEE.
Ho, T. K. (1998). The random subspace method for constructing decision forests. In Pattern Analysis and Machine Intelligence. IEEE.
J. Shotton, a. A. F., Cook, M., Sharp, T., Finocchio, M.,
Moore, R., Kipman, A., and Blake, A. (2011). Realtime human pose recognition in parts from single
depth images. In Computer Vision and Pattern Recognition. IEEE.
J. Shotton, M. J. and Cipolla, R. (2008). Semantic texton
forests for image categorization and segmentation. In
Computer Vision and Pattern Recognition. IEEE.
Kim, T.-K. and Cipolla, R. (2008). Mcboost: Multiple classifier boosting for perceptual co-clustering of images
and visual features. In Advances in Neural Information Processing Systems.
Lepetit, V. and p. Fua (2006). Keypoint recognition using
randomized trees. In Pattern Analysis and MachineIntelligence. IEEE.
Saberian, M. and Vasconcelos, N. (2008). Multiclass boosting: Theory and algorithms. In Advances in NeuralInformation Processing Systems.