Bagging Predictors

By

Leo Breiman*

Technical Report No. 421
September 1994
*Partially supported by NSF grant DMS-9212419

Department of Statistics
University of California
Berkeley, California 94720

Bagging Predictors
Leo Breiman1
Department of Statistics
University of California at Berkeley

Abstract
Bagging predictors is a method for generating multiple versions of a predictor and using these to get an aggregated predictor. The aggregation averages over the versions when predicting a numerical outcome and does aplurality vote when predicting a class. The multiple versions are formedby making bootstrap replicates of the learning set and using these as newlearning sets. Tests on real and simulated data sets using classi cation andregression trees and subset selection in linear regression show that bagging
can give substantial gains in accuracy. The vital element is the instability ofthe prediction method. If perturbing the learning set can cause signi cantchanges in the predictor constructed, then bagging can improve accuracy.

1. Introduction

A learning set of L consists of data f(yn; xn), n = 1; : : : ; N g where the y's
are either class labels or a numerical response. We have a procedure for using
this learning set to form a predictor '(x; L) | if the input is x we predicty by '(x; L). Now, suppose we are given a sequence of learnings sets fLk geach consisting of N independent observations from the same underlying
distribution as L. Our mission is to use the fLk g to get a better predictor
than the single learning set predictor '(x; L). The restriction is that all weare allowed to work with is the sequence of predictors f'(x; Lk )g.
If y is numerical, an obvious procedure is to replace '(x; L) by the averageof '(x; Lk ) over k. i.e. by 'A (x) = EL '(x; L) where EL denotes the
expectation over L, and the subscript A in 'A denotes aggregation. If '(x; L)
1 partially supported by NSF grant DMS-9212419.

1

predicts a class j 2 f1; : : : ; J g, then one method of aggregating the '(x; Lk )is by voting. Let Nj = #fk; '(x; Lk ) = j g and take 'A(x) = argmaxj Nj .
Usually, though, we have a single learning set L without the luxury of
replicates of L. Still, an imitation of the process leading to 'A can be done.
Take repeated bootstrap samples fL B g from L, and form f'(x; L B )g. If
y is numerical, take 'B as'B (x) = avB'(x; L B ):If y is a class label, let the f'(x; L B )g vote to form 'B (x). We call thisprocedure \bootstrap aggregating" and use the acronym bagging.
The fL B g form replicate data sets, each consisting of N cases, drawn at
random, but with replacement, from L. Each (yn; xn) may appear repeatedtimes or not at all in any particular L B . The fL B g are replicate data
set drawn from the bootstrap distribution approximating the distribution
underlying L. For background on bootstrapping, see Efron and Tibshirani[1993]. A critical factor in whether bagging will improve accuracy is thestability of the procedure for constructing '. If changes in L, i.e. a replicate
L, produces small changes in ', then 'B will be close to '. Improvement will
occur for unstable procedures where a small change in L can result in largechanges in '. Unstability was studied in Breiman [1994] where it was pointed
out that neural nets, classi cation and regression trees, and subset selection
in linear regression were unstable, while k-nearest neighbor methods werestable.
For unstable procedures bagging works well. In Section 2 we bag classi cation trees on a variety of real and simulated data sets. The reductionin test set missclassi cation rates ranges from 20% to 47%. In section 3 regression trees are bagged with reduction in test set mean squared error on
data sets ranging from 22% to 46%. Section 4 goes over some theoreticaljusti cation for bagging and attempts to understand when it will or will notwork well. This is illustrated by the results of Section 5 on subset selection in
linear regression using simulated data. Section 6 gives concluding remarks.
These discuss how many bootstrap replications are useful, bagging nearest
neighbor classi ers and bagging class probability estimates.
The evidence, both experimental and theoretical, is that bagging canpush a good but unstable procedure a signi cant step towards optimality.
On the other hand, it can slightly degrade the performance of stable procedures. There has been recent work in the literature with some of the avor
(

)

(

(

(

(

)

)

)

(

2

)

(

)

)

of bagging. In particular, there has been some work on averaging and voting
over multiple trees. Buntine [1991] gave a Bayesian approach, Kwok andCarter [1990] used voting over multiple trees generated by using alternative
splits, and Heath et. al. [1993] used voting over multiple trees generated byalternative oblique splits. Dieterrich [1991] showed that a method for coding many class problems into a large number of two class problems increases
accuracy. There is some commonality of this idea with bagging.

2. Bagging Classi cation Trees
2.1. Results
Bagging was applied to classi cation trees using the following data sets:
waveform (simulated)heart
breast cancer (Wisconsin)
ionospherediabetesglass
soybeanAll of these except the heart data are in the UCI repository (ftp ics.uci.edu/pub/machine-learning-databases). The data are brie y described in Section
2.2.
Testing was done using random divisions of each data set into a learningand test set, constructing the usual tree classi er using the learning set, andbagging this tree using 50 bootstrap replicates. This was repeated 100 times
for each data set (speci cs are given in Section 2.3). The average test set
missclassi cation rate using a single tree is denoted by eS and the bagging
rate by eB . The results are:3

Table 1 Missclassi cation Rates (Percent)
Data SeteS eB Decrease

waveformheart
breast cancer
ionospherediabetesglass
soybean

29.0
10.0
6.0
11.2
23.4
32.0
14.5

19.4
5.3
4.2
8.6
18.8
24.9
10.6

33%
47%
30%
23%
20%
22%
27%

For the waveform data it's known that the minimal attainable rate (Bayes
Rate) is 14.0%. Using this as a base, the excess error drops from 15.0% to
5.4%.
2.2. Data Sets
Table 2 gives a summary of the data sets and the test set sizes used.

Data Set

Table 2
Data Set Summary# Samples # Variables # Classes # Test Set
waveform
300
21
3
1500
heart
1395(823)
16(18)
2250
breast cancer 699
92100
ionosphere
351
34
2
25
diabetes
1036(768)
8
2
250
glass
214
9
6
20
soybean
307
35
19
25
The gures in parentheses are for the original data sets. These were modi ed
for reasons described below to give the as-used numbers. In all but thesimulated waveform data, the data set was randomly divided into a test set
and learning set. So, for instance, in the glass data, the size of the learning
set in each iteration was 194 = 214 20. For the simulated waveform data,
a learning set of 300 and a test set of 1500 were generated for each iteration.
Brief descriptions of the data sets follows. More extended background isavailable in the UCI repository.
4

Waveform This is simulated 21 variable data with 300 cases and 3 classes
each having probability 1=3. It is described in Breiman et al [1984] (a C
subroutine for generating the data is in the UCI repository subdirectory/waveform).
Heart This is data from the study referred to in the opening paragraphs of
the CART book (Breiman et. al. [1984]). To quote:At the University of California, San Diego Medical Center, when aheart attack patient is admitted, 19 variables are measured during
the rst 24 hours. These include blood pressure, age, and 17 otherordered and binary variables summarizing the medical symptoms
considered as important indicators of the patient's condition.
The goal of a recent medical study (see Chapter 6) was the development of a method to identify high risk patients (those who will
not survive at least 30 days) on the basis of the initial 24-hourdata.
The data base has also been studied in Olshen et al [1985]. It was gathered on a project (SCOR) headed by John Ross Jr. Elizabeth Gilpin andRichard Olshen were instrumental in my obtaining the data. The data used
had 18 variables. Two variables with high proportions of missing data weredeleted, together with a few other cases that had missing values. This left
779 complete cases | 77 deaths and 702 survivors. To equalize class sizes,
each case of death was replicated 9 times giving 693 deaths for a total of1395 cases.
Breast Cancer This is data given to the UCI repository by William H. Wolberg, University of Wisconsin Hospitals, Madison (see Wolberg and Mangasariam [1990]). It is two class data with 699 cases, (458 benign and 241
malignant). It has 9 variables consisting of cellular characteristics. (subdirectory /breast-cancer-wisconsin)
Ionosphere This is radar data gathered by the Space Physics Group at Johns
Hopkins University (see Sigillito et. al. [1989]). There are 351 cases with 34
variables, consisting of 2 attributes for each at 17 pulse numbers. There are
two classes: good = some type of structure in the ionosphere (226); bad =no structure (125). (subdirectory /ionosphere)5

Diabetes This is a data base gathered among the Pima Indians by the National Institute of Diabetes and Digestive and Kidney Diseases. (See Smithet. al. [1988]). The data base consists of 768 cases, 8 variables and twoclasses. The variables are medical measurements on the patient plus age andpregnancy information. The classes are: tested positive for diabetes (268)or negative (500). To equalize class sizes, the diabetes cases were duplicatedgiving a total sample size of 1036. (subdirectory /pima-indians-diabetes)
Glass This data base was created in the Central Research Establishment,
Home Oce Forensic Science Service Aldermaston, Reading, Berkshire. Eachcase consists of 9 chemical measurements on one of 6 types of glass. Thereare 214 cases.
Soybean The soybean learning set consists of 307 cases, 35 variables and
19 classes. The classes are various types of soybean diseases. The variables are observation on the plants together with some climatic variables.
All are categorical. Some missing values were lled in. (subdirectory /soybean/soybean large.data)(subdirectory /glass)2.2. Computations
In all runs, the following procedure was used:i). The data set was randomly divided into a test set T and learning set L.
The test sets sizes selected in the real data sets are ad hoc, mostly chosen sothat L would be reasonably large. In simulated data, test set size was chosen
comfortably large.
ii). A classi cation tree was constructed from L, with selection done by
10-fold cross-validation. Running the test set T down this tree gives the
missclassi cation rate eS (L; T )iii). A bootstrap sample LB is selected from L, and a tree grown using LB
and 10-fold cross-validation. This is repeated 50 times giving tree classi ers' (x); : : : ; ' (x).
iv). If (jn ; xn ) 2 T , then the estimated class of xn is that class having theplurality in ' (xn); : : :; ' (xn ). The proportion of times the estimated class
1

50

1

50

6

di ers from the true class is the bagging missclassi cation rate eB (L; T ).
v) The random division of the data is repeated 100 times and the reportedeS , eB are the averages over the 100 iterations.

3. Bagging Regression Trees
3.1. Results
Bagging trees was used on 5 data sets with numerical responses.
Boston Housing
Ozone
Friedman #1(simulated)
Friedman #2(simulated)
Friedman #3(simulated)
The computing scheme was similar to that used in classi cation. Learningand test sets were randomly selected, 25 bootstrap replications used, and 100
iterations. The results are:Table 3
Mean Squared Test Set Error

Data SeteSeB Decrease
Boston Housing 19.1 11.7
39%
Ozone
23.1 18.0
22%Friedman #1
11.4
6.2
46%
Friedman #2
30,800 21,700 30%
Friedman #3.0403 .0249 38%
3.2. Data Sets

Data Set

Boston Housing
Ozone
Friedman #1
Friedman #2
Friedman #3

Table 4
Summary of Data Sets
#Cases # Variables # Test Set
506
330(366)
200
200
200
7

12
8(9)
10
4
4

25
15
1000
1000
1000

Boston Housing This data became well-known through its use in the bookby Belsley, Kuh, and Welsch [1980]. It has 506 cases corresponding to census
tracts in the greater Boston area. The y-variable is median housing price inthe tract. There are 12 predictor variables, mainly socio-economic. The data
has since been used in many studies. (UCI repository/housing).
Ozone The ozone data consists of 366 readings of maximum daily ozone at a
hot spot in the Los Angeles basin and 9 predictor variables | all meteorlogical, i.e. temperature, humidity, etc. It is described in Breiman and Friedman[1985] and has also been used in many subsequent studies. Eliminating one
variable with many missing values and a few other cases leaves a data set
with 330 complete cases and 8 variables.
Friedman #1 All three Friedman data sets are simulated data that appear in
the MARS paper (Friedman [1991]). In the rst data set, there are ten independent predictor variables x1; : : : ; x10 each of which is uniformly distributed
over [0; 1]. The response is given by

y = 10 sin(x x ) + 20(x123:5) + 10x + 5x + 2

45

where  is N (0; 1). Friedman gives results for this model for sample sizes 50,
100, 200. We use sample size 200.
Friedman #2, #3 These two examples are taken to simulate the impedance
and phase shift in an alternating current circuit. They are 4 variable datawith#2y = (x21 + (x2x3 (1=x2 x4))2)1=2 + 2



(1
=x
x
)
#3
y = tan+xwhere x , x , x , x are uniformly distributed over the ranges
1

1

2

3

xx
2

3

2

4

1

4

0  x  100
20  (x =2)  280
0  x 1
1  x  11
1

2

3

4

8

3

The noise  ,  are distributed as N (0;  ), N (0;  ) with  ,  selected togive 3:1 signal/noise ratios. In each example, the sample sizes are 200.
3.2. Computations
The two real data sets were divided at random in a learning set L andtest set T . For each of the simulated data sets, a learning set L of 200 cases
was generated and a test set of 1000 cases. A regression tree was grownusing L and 10-fold cross-validation. The test set T was run down L andgave mean-squared-error eS (L; T ).
Then 25 bootstrap replicates L B of L were generated. For each one,a regression tree was grown using L B and 10-fold cross-validation. This
gave 25 predictors ' (x); : : :; ' (x). For each (yn; xn ) 2 T , the predictedy^B value was taken as avk 'k (xn). Then eB (L; T ) is the mean-squared-error
between the y^B and the true y-values in T . This procedure was repeated 100
times and the errors averaged to give the single tree error eS and the bagged
error eB .
2

2
2

3

(

2

3

)

(

1

2
3

)

25

4. Why Bagging Works
Let each (y; x) case in L be independently drawn from the probability
distribution P . Suppose y is numerical and '(x; L) the predictor. Then theaggregated predictor is'A (x; P ) = EL '(x; L):

Take Y , X to be random variables having the distribution P and independentof L. The average prediction error e in '(x; L) is

e = EL EY;X(Y'(X ; L)) :eA = EY;X(Y'A (X ; P )) :2

De ne the error in the aggregated predictor 'A to be
2

Using the inequality (EZ )  EZ gives22

e = EY E (Y2

2EY 'A + EY;X EL' (X ; L)'A ) = eA22

9Thus, 'A has lower mean-squared prediction error than '. How much
lower depends on how unequal the two sides of[EL '(x; L)]  EL ' (x; L)
are. The e ect of instability is clear. If '(x; L) does not change too muchwith replicate L the two sides will be nearly equal, and aggregation will
not help. The more highly variable the '(x; L) are, the more improvement
aggregation may produce. But 'A always improves on '.
Now, the bagged estimate is not 'A (x; P ), but rather'B (x) = 'A(x; PL);
where PL is the distribution that concentrates mass 1=N at each point(yn; xn) 2 L, (PL is called the bootstrap approximation to P ). Then 'B
is caught in two currents: on the one hand, if the procedure is unstable, it
can give improvement through aggregation. On the other side, if the procedure is stable, then 'B = 'A(x; PL ) will not be as accurate for data drawn
from P as 'A (x; P ) ' '(x; L).
There is a cross-over point between instability and stability at which 'B
stops improving on '(x; L) and does worse. This has a vivid illustration in
the linear regression subset selection example in the next section. There isanother obvious limitation of bagging. For some data sets, it may happen
that '(x; L) is close to the limits of accuracy attainable on that data. Thenno amount of bagging will do much improving. This is also illustrated in thenext section.
In classi cation, a predictor '(x; L) predicts a class label j 2 f1; : : : ; J g.
If L is drawn from the distribution P , and Y , X are from P independent ofL, then the probability of correct classi cation for L xed is;r(L) = PX(Y = '(X ; L))P ( '( X ; L ) = j j Y = j ) P ( Y = j ) :=2

Denote2j

Q(j jx) = PL ('(x; L) = j ):Then, averaged over L, the probability of correct classi cation isX
E (Q(j jX )jY = j )P (Y = j )
r =
j

10

=

XZ
j

Q(j jx)P (j jx)PX (dx)where PX (dx) is the overall x distribution.
Since 'A (x) = arg maxi Q(ijx),

rA =

XZ
j

I (arg max
Q(ijx) = j )P (j jx)PX (dx)iwhere I () is the indicator function. Consider the set
For x 2 C

C = fx; arg max
P (j jx) = arg max
Q(j jx)g:jjXjso that

rA =

Z

x2C

I (arg max
Q(ijx) = j )P (j jx) = max
P (j jx)ijmax
P (j jx)PX (dx) +j

ZX

x2C j I ('A(x) = j )P (j jx)PX (dx):0The highest attainable correct classi cation rate is given by the predictor

Q(x) = arg max
P (j jx)jand has the correct classi cation rateZr = max
P (j jx)PX (dx):j

If x 2 C , the sum Pj Q(j jx)P (j jx) can be less than maxj P (j jx). Thus,
even if PX (C ) ' 1, the unaggregated predictor ' can be far from optimal.
But 'A is nearly optimal. Aggregating can therefore transform good predictors into nearly optimal ones. On the other hand, unlike the numericaly situation, poor predictors can be transformed into worse ones. The same
behavior regarding stability holds. Bagging unstable classi ers usually improves them. Bagging stable classi ers is not a good idea.
11

5. A Linear Regression Illustration
5.1. Forward Variable Selection
Subset selection in linear regression gives an illustration of the points
made in the previous section. With data of the form L = f(yn; xn), n =1; : : : ; N g where x = (x ; : : :; xM ) consists of M predictor variables, a popular prediction method consists of forming predictors ' (x); : : :; 'M (x) where
each 'm is linear in x and depends on only m of the M x-variables. Then
one of the f'mg is chosen as the designated predictor. For more background,see Breiman and Spector [1993].
A common method for constructing the f'mg, and one that is used inour simulation, is forward variable entry. If the variables used in 'k are
xm1 ; : : : ; xmk , then for each m 62 fm ; : : :; mk g form the linear regression of yon (xm1 ; : : :; xmk ; xm), compute the residual sum-of-squares RSS(m) and takexmk+1 such that mk minimizes RSS(m) and 'k (x) the linear regression
based on (xm1 ; : : :; xmk+1 ).
There are other forms of variable selection i.e. best subsets, backwards
and variants thereof. What is clear about all of them is that they are unstableprocedures (see Breiman [1994]). The variables are competing for inclusionin the f'mg and small changes in the data can cause large changes in thef'mg.
5.2. Simulation Structure
The simulated data used in this section are drawn from the model.
Xy=m xm + 
1

1

1

+1

+1

m

where  is N (0; 1). The number of variables M = 30 and the sample size is
60. The fxmg are drawn from a mean-zero joint normal distribution with
EXi Xj = ji jj and at each iteration,  is selected from a uniform distribution
on [0; 1].
It is known that subset selection is nearly optimal if there are only a few
large non-zero m, and that its performance is poor if there are many small
but non-zero m. To bridge the spectrum, three sets of coecients are used.
Each set of coecients consists of three clusters; one is centered at m = 5,
one at m = 15 and the other at m = 25. Each cluster is of the formm = c[(h jm k j) ] ; m = 1; : : : ; 30
+ 212

where k is the cluster center, and h = 1; 3; 5 for the rst, second and third
set of coecients respectively. The normalizing constant C is taken so that
the R for the data is ' :75. Thus, for h = 1, there are only three non-zerof mg. For h = 3 there are 15 non-zero f mg, and for h = 5, there are 27
non-zero f mg, all relatively small.
For each set of coecients, the following procedure was replicated 250
times:i). Data L = f(yn; xn), n = 1; : : : ; g was drawn from the model
2

y=

X

m xm + 

where the fxmg were drawn from the joint normal distribution describedabove.
ii). Forward entry of variables was done using L to get the predictors' (x); : : : ; 'M (x). The mean-squared prediction error of each of these wascomputed giving e ; : : : ; eM .
iii). Fifty bootstrap replicates fL B g of L were generated. For each of these,forward stepwise regression was applied to construct predictors
f' (x; L B ); : : : ; 'M (x; L B )g. These were averaged over the L B to givethe bagged sequence ' B (x); : : :; 'MB (x). The prediction errors e B ; : : : ; eMB
for this sequence was computed.
These computed mean-squared-errors were averaged over the 250 repetitions to give two sequences femS g, femB g. For each set of coecients, these
two sequences are plotted vs. m in Figure 1a,b,c.
5.3. Discussion of Simulation Results
First and most obvious is that the best bagged predictor is always at least
as good as the best subset predictor. When h = 1 and subset selection isnearly optimal, there is no improvement. For h = 3 and 5 there is substantial
improvement. This illustrates the obvious: bagging can improve only if theunbagged is not optimal.
The second point is less obvious. Note that in all three graphs there is apoint past which the bagged predictors have larger prediction error than theunbagged. The explanation is this: linear regression using all variables is afairly stable procedure. The stability decreases as the number of variables
used in the predictor decreases. As noted in section 4, for a stable procedure'B = 'A (x; PL ) is not as accurate as ' ' '(x; P ). The higher values of
1

1

1

(

(

)

(

)

)

(

( )
1

(

( )

)

( )
1

(

13

)

)

(

)

14

'mB for large m re ect this fact. As m decreases, the instability increases
and there is a cross-over point of which 'mB becomes more accurate than 'm
(

)

(

)

6. Concluding Remarks
6.1. Bagging Class Probability Estimates
Some classi cation methods estimate probabilities p^(j jx) that an object
with prediction vector x belongs to class j . Then the class corresponding to
x is estimated as arg maxj p^(j jx). For such methods, a natural competitor
to bagging by voting is to average the p^(j jx) over all bootstrap replications,
getting p^B (j jx) and then use the estimated class arg maxj p^B (j jx). Thisestimate was computed in every classi cation example we worked on. The
resulting missclassi cation rate was always virtually identical to the voting
missclassi cation rate. In some applications, estimates of class probabilities
are required, instead of, or along with, the classi cations. The evidence so far
indicates that bagged estimates are likely to be more accurate than the single
estimates. To verify this, it would be necessary to compare both estimateswith the true values p(j jx) over the x in the test set. For real data the true
values are unknown. But they can be computed for the simulated waveform
data, where they reduce to computing an expression involving error functions.
Using the waveform data, we did a simulation similar to that in Section
2 with learning and test sets both of size 300, and 25 bootstrap replications.
In each iteration, we computed the average over the test set and classes ofjp^(j jx) p (j jx)j and jp^B (j jx) p(j jx)j. This was repeated 50 times andthe results averaged. The single tree estimates had an error of .189. The
error of the bagged estimates was .124, a decrease of 34%.
6.2. How Many Bootstrap Replicates Are Enough?
In our experiments, 50 bootstrap replicates was used for classi cationand 25 for regression. This does not mean that 50 or 25 were necessaryor sucient, but simply that they seemed reasonable. My sense of it isthat fewer are required when y is numerical and more are required with anincreasing number of classes.
The answer is not too important when procedures like CART are used,because running times, even for a large number of bootstraps, are very nominal. But neural nets progress much slower and replications may require many15

days of computing. Still, bagging is almost a dream procedure for parallel
computing. The construction of a predictor on each L B proceeds with nocommunication necessary from the other CPU's.
To give some ideas of what the results are as connected with the numberof bootstrap replicates we ran the waveform data using 10, 25, 50 and 100
replicates using the same simulation scheme as in Section 2. The results are:()

Table 5.1
Bagged Missclassi cation Rates (%)

No. Bootstrap Replicates Missclassi cation Rate
10
21.8
25
19.5
50
19.4
100
19.4
The unbagged rate is 29.0, so its clear that we are getting most of the improvement using only 10 bootstrap replicates. More than 25 bootstrap replicates
is love's labor lost.
6.3. Bagging Nearest Neighbor Classi ers
Nearest neighbor classi ers were run on all the data sets described in
section 2 except for the soybean data whose variables were categorical. The
same random division into learning and test sets was used with 100 bootstrap
replicates, and 100 iterations in each run. A Euclidean metric was used witheach coordinate standardized by dividing by its standard deviation over thelearning set. See Table 5 for the results:

Table 5
Missclassi cation Rates for Nearest Neighbor
Data SeteSeB
waveform
26.1
heart
6.3
breast cancer 4.9
ionosphere35.7
diabetes
16.4
glass
21.6

26.1
6.3
4.9
35.7
16.4
21.6

16

Nearest neighbor is more accurate than single trees in 5 of the 6 data sets,
but bagged trees are more accurate in 5 of the 6 data sets.
Cycles did not have to be expended to nd that bagging nearest neighbors
does not change things. Some simple computations show why. Given N
possible outcomes of a trial (the N cases (yn; xn) in the learning set) andN trials, the probability that the nth outcome is selected 0; 1; 2; : : : times isapproximately Poisson distributed with  = 1 for large N . The probability
that the nth outcome will occur at least once is 1 (1=e) ' :632.
If there are NB bootstrap repetitions in a 2-class problem, then a test
case may change classi cation only if its nearest neighbor in the learning set
is not in the bootstrap sample in at least half of the NB replications. This
probability is given by the probability that the number of heads in NB tosses
of a coin with probability .632 of heads is less than :5NB . As NB gets larger,
this probability gets very small. Analogous results hold for J -class problems.
The stability of nearest neighbor classi cation methods with respect toperturbations of the data distinguishes them from competitors such as trees
and neural nets.
6.4. Conclusions
Bagging goes a ways toward making a silk purse out of a sow's ear, especially if the sow's ear is twitchy. It is a relatively easy way to improve an
existing method, since all that needs adding is a loop in front that selects thebootstrap sample and sends it to the procedure and back end that does theaggregation. What one loses, with the trees, is a simple and interpretablestructure. What one gains is increased accuracy.

References
Belsley, D., Kuh, E., and Welsch, R. (1980) \Regression Diagnostics", John
Wiley and Sons.
Breiman, L. (1994) Heuristics of instability in model selection, Technical
Report, Statistics Department, University of California at Berkeley.
Breiman, L., Friedman, J., Olshen, R., and Stone, C. (1984) \Classi cation
and Regression Trees", Wadsworth.
17

Breiman, L. and Friedman, J. (1985) Estimating optimal transformations in
multiple regression and correlation (with discussion), Journal of the American Statistical Association, 80, 580-619 .
Breiman, L. and Spector, P (1992) Submodel Selection and Evaluation in
Regression { the X-Random Case, International Review of Statistics, 3, 291319
Buntine, W. (1991) \Learning classi cation trees", Arti cial Intelligence
Frontiers in Statistics, ed D.J. Hand, Chapman and Hall, London, 182-201.
Dietterich, T.G. and Bakiri, G. (1991) Error-correcting output codes: A general method for improving multiclass inductive learning programs, Proceedings of the Ninth National Conference on Arti cial Intelligence (AAAI-91),
Anaheim, CA: AAAI Press.
Efron, B., and Tibshirani, R. (1993) \An Introduction to the Bootstrap".
Chapman and Hall.
Friedman, J. (1991) Multivariate adaptive regression splines (with discussion), Annals of Statistics, 19, 1-141.
Heath, D., Kasif, S., and Salzberg, S. (1993) k-dt: a multi-tree learning
method. Proceedings of the Second International Workshop on Multistrategy
Learning, 1002-1007, Chambery, France, Morgan Kaufman.
Kwok, S., and Carter, C. (1990) Multiple decision trees, Uncertainty in Arti cial Intelligence 4, ed. Shachter, R., Levitt, T., Kanal, L., and Lemmer,J., North-Holland, 327-335.
Olshen, R., Gilpin, A., Henning, H., LeWinter, M., Collins, D., and Ross, J.
(1985) Twelve-month prognosis following myocardial infarction: Classi cation trees, logistic regression, and stepwise linear discrimination, Proceedingsof the Berkeley conference in honor of Jerzy Neyman and Jack Kiefer, L. Le
Cam;R. Olshen, (Ed), Wadsworth, 245-267.
Smith, J., Everhart, J., Dickson, W., Knowler, W., and Johannes, R. (1988)
Using the ADAP learning algorithm to forecast the onset of diabetes mellitus.
In Proceedings of the Symposium on Computer Applications and Medical
18

Care 261{265. IEEE Computer Society Press.
Sigillito, V. G., Wing, S. P., Hutton, L. V.,and Baker, K. B. (1989) Classication of radar returns from the ionosphere using neural networks. Johns
Hopkins APL Technical Digest, 10, 262-266.
Wolberg, W. and Mangasarian, O (1990) Multisurface method of patternseparation for medical diagnosis applied to breast cytology, Proceedings of
the National Academy of Sciences, U.S.A., Volume 87, December 1990, pp
9193-9196.

19