Combining Classifiers with Meta Decision Trees.
The paper introduces meta decision trees (MDTs), a novel method for combining multiple classifiers. Instead of giving a prediction, MDT leaves specify which classifier should be used to obtain a prediction. We present an algorithm for learning MDTs based on the C4.5 algorithm for learning ordinary decision trees (ODTs). An extensive experimental evaluation of the new algorithm is performed on twenty-one data sets, combining classifiers generated by five learning algorithms: two algorithms for learning decision trees, a rule learning algorithm, a nearest neighbor algorithm and a naive Bayes algorithm. In terms of performance, stacking with MDTs combines classifiers better than voting and stacking with ODTs. In addition, the MDTs are much more concise than the ODTs and are thus a step towards comprehensible combination of multiple classifiers. MDTs also perform better than several other approaches to stacking.
Introduction
The task of constructing ensembles of classiers [8] can be broken down into two sub-tasks.
We rst have to generate a diverse set of base-level classiers. Once the base-level classiers
have been generated, the issue of how to combine their predictions arises.
Several approaches to generating base-level classiers are possible. One approach is to
generate classiers by applying dierent learning algorithms (with heterogeneous model
representations) to a single data set (see, e.g., Merz [14]). Another possibility is to apply
a single learning algorithm with dierent parameters settings to a single data set. Finally,
methods like bagging [5] and boosting [9] generate multiple classies by applying a single
learning algorithm to dierent versions of a given data set. Two dierent methods for manipulating
the data set are used: random sampling with replacement (also called bootstrap
sampling) in bagging and re-weighting of the misclassied training examples in boosting.
Techniques for combining the predictions obtained from the multiple base-level classiers
can be clustered in three combining frameworks: voting (used in bagging and boost-
ing), stacked generalization or stacking [22] and cascading [10]. In voting, each base-level
classier gives a vote for its prediction. The prediction receiving the most votes is the
nal prediction. In stacking, a learning algorithm is used to learn how to combine the
predictions of the base-level classiers. The induced meta-level classier is then used to
obtain the nal prediction from the predictions of the base-level classiers. Cascading
is an iterative process of combining classiers: at each iteration, the training data set is
extended with the predictions obtained in the previous iteration.
The work presented here focuses on combining the predictions of base-level classiers
induced by applying dierent learning algorithms to a single data set. It adopts the stacking
framework, where we have to learn how to combine the base-level classiers. To this end,
it introduces the notion of meta decision trees (MDTs), proposes an algorithm for learning
them and evaluates MDTs in comparison to other methods for combining classiers.
Meta decision trees (MDTs) are a novel method for combining multiple classiers. The
dierence between meta and ordinary decision trees (ODTs) is that MDT leaves specify
which base-level classier should be used, instead of predicting the class value directly. The
attributes used by MDTs are derived from the class probability distributions predicted by
the base-level classiers for a given example. We have developed MLC4.5, a modication of
C4.5 [17], for inducing meta decision trees. MDTs and MLC4.5 are described in Section 3.
The performance of MDTs is evaluated on a collection of twenty-one data sets. MDTs
are used to combine classiers generated by ve base-level learning algorithms: two tree-
learning algorithms C4.5 [17] and LTree [11], the rule-learning algorithm CN2 [7], the
k-nearest neighbor (k-NN) algorithm [20] and a modication of the naive Bayes algorithm
[12]. In the experiments, we compare the performance of stacking with MDTs to the
performance of stacking with ODTs. We also compare MDTs with two voting schemes
and two other stacking approaches. Finally, we compare MDTs to boosting and bagging
of decision trees as state of the art methods for constructing ensembles of classiers.
Section 4 reports on the experimental methodology and results. The experimental
results are analyzed and discussed in Section 5. The presented work is put in the context of
previous work on combining multiple classiers in Section 6. Section 7 presents conclusions
based on the empirical evaluation along with directions for further work.
Combining Multiple Classiers
In this paper, we focus on combining multiple classiers generated by using dierent learning
algorithms on a single data set. In the rst phase, depicted on the left hand side of

Figure

1, a set of N base-level classiers is generated by applying the
learning algorithms A 1 ; A to a single training data set L.
training
set
"!
"!
A
A
A
A
A
A
A A
AN
CN
A
A
A
A
A
A
A A
x
new
example
CN
CML

Figure

1: Constructing and using an ensemble of classiers. Left hand side: generation of
the base-level classiers by applying N dierent learning algorithms
to a single training data set L. Right hand side: classication of a new example x using
the base-level classiers in C and the combining method CML .
We assume that each base-level classier from C predicts a probability distribution over
the possible class values. Thus, the prediction of the base-level classier C when applied
to example x is a probability distribution vector:
is a set of possible class values and p C (c i jx) denotes the probability
that example x belongs to class c i as estimated (and predicted) by classier C. The class
c j with the highest class probability p C (c j jx) is predicted by classier C.
The classication of a new example x at the meta-level is depicted on the right hand
side of Figure 1. First, the N predictions fp C1 (x); p C2 of the base-level
classiers in C on x are generated. The obtained predictions are then combined using
the combining method CML . Dierent combining methods are used in dierent combining
frameworks. In the following subsections, the combining frameworks of voting and stacking
are presented.
2.1 Voting
In the voting framework for combining classiers, the predictions of the base-level classiers
are combined according to a static voting scheme, which does not change with training data
set L. The voting scheme remains the same for all dierent training sets and sets of learning
algorithms (or base-level classiers).
The simplest voting scheme is the plurality vote. According to this voting scheme, each
base-level classier casts a vote for its prediction. The example is classied in the class
that collects the most votes.
There is a renement of the plurality vote algorithm for the case where class probability
distributions are predicted by the base-level classiers [8]. Let p C (x) be the class probability
distribution predicted by the base-level classier C on example x. The probability
distribution vectors returned by the base-level classiers can be summed to obtain the class
probability distribution of the meta-level voting classier:
The predicted class for x is the class c j with the highest class probability p CML
2.2 Stacking
In contrast to voting, where CML is static, stacking induces a combiner method CML
from the meta-level training set, based on L, in addition to the base-level classiers. CML
is induced by using a learning algorithm at the meta-level: the meta-level examples are
constructed from the predictions of the base-level classiers on the examples in L and the
correct classications of the latter. As the combiner is intended to combine the predictions
of the base-level classiers (induced on the entire training set L) for unseen examples,
special care has to be taken when constructing the meta-level data set. To this end, the
cross-validation procedure presented in Table 1 is applied.

Table

1: The algorithm for building the meta-level data set used to induce the combiner
CML in the stacking framework.
function build combiner(L, fA
stratified partition(L; m)
do
to N do
Let C j;i be the classier obtained by applying A j to L n L i
Let CV j;i be class values predicted by C j;i on examples in L i
Let CD j;i be class distributions predicted by C j;i on examples in L i
endfor
endfor
Apply AML to LML in order to induce the combiner CML
return CML
endfunction
First, the training set L is partitioned into m disjoint sets
equal size. The partitioning is stratied in the sense that each set L i roughly preserves the
class probability distribution in L. In order to obtain the base-level predictions on unseen
examples, the learning algorithm A j is used to train base-level classier C j;i on the training
set L n L i . The trained classier C j;i is then used to obtain the predictions for examples
in L i . The predictions of the base-level classiers include the predicted class values CV j;i
as well as the class probability distributions CD j;i . These are then used to calculate the
meta-level attributes for the examples in L i .
The meta-level attributes are calculated for all N learning algorithms and joined together
into set of meta-level examples. This set is one of the m parts of the meta-level
data set LML . Repeating this procedure m times (once for each set L i ), we obtain the
whole meta-level data set. Finally, the learning algorithm AML is applied to it in order to
induce the combiner CML .
The framework for combining multiple classiers used in this paper is based on the
combiner methodology described in [6] and the stacking framework of [22]. In these two ap-
proaches, only the class values predicted by the base-level classiers are used as meta-level
attributes. Therefore, the meta level attributes procedure used in these frameworks
is trivial: it returns only the class values predicted by the base-level classiers. In our
approach, we use the class probability distributions predicted by the base-level classiers
in addition to the predicted class values for calculating the set of meta-level attributes.
The meta-level attributes used in our study are discussed in detail in Section 3.
3 Meta Decision Trees
In this section, we rst introduce meta decision trees (MDTs). We then discuss the possible
sets of meta-level attributes used to induce MDTs. Finally, we present an algorithm for
inducing MDTs, named MLC4.5.
3.1 What are Meta Decision Trees
The structure of a meta decision tree is identical to the structure of an ordinary decision
tree. A decision (inner) node species a test to be carried out on a single attribute value
and each outcome of the test has its own branch leading to the appropriate subtree. In a
leaf node, a MDT predicts which classier is to be used for classication of an example,
instead of predicting the class value of the example directly (as an ODT would do).
The dierence between ordinary and meta decision trees is illustrated with the example
presented in Tables 2 and 3. First, the predictions of the base-level classiers (Table 2a)
are obtained on the given data set. These include predicted class probability distributions
as well as class values themselves. In the meta-level data set M (Table 2b), the meta-level
attributes C 1 and C 2 are the class value predictions of two base-level classiers C 1
and C 2 for a given example. The two additional meta-level attributes Conf 1 and Conf 2
measure the condence of the predictions of C 1 and C 2 for a given example. The highest
class probability, predicted by a base-level classier, is used as a measure of its prediction
condence.

Table

2: Building the meta-level data set. a) Predictions of the base-level classiers. b)
The meta-level data set M .
a) Predictions of the base-level classiers
Base-level attributes (x) p C1 (0jx) p C1 (1jx) pred. p C2 (0jx) p C2 (1jx) pred.
. 0.875 0.125 0 0.875 0.125 0
.
.
.
.
.
.
.
b) Meta-level data set M
The meta decision tree induced using the meta-level data set M is given in Table 3a).
The MDT is interpreted as follows: if the condence Conf 1 of the base-level classier C 1 is
high, then C 1 should be used for classifying the example, otherwise the base-level classier
should be used. The ordinary decision tree induced using the same meta-level data
set M (given in Table 3b) is much less comprehensible, despite the fact that it re
ects
the same rule for choosing among the base-level predictions. Note that both the MDT
and the ODT need the predictions of the base-level classiers in order to make their own
predictions.

Table

3: The dierence between ordinary and meta decision trees. a) The meta decision
tree induced from the meta-level data set M (by MLC4.5). b) The ODT induced from the
same meta-level data set M (by C4.5). c) The MDT written as a logic program.
a) The MDT induced from M
Conf1 <= 0.625: C2
Conf1 > 0.625: C1
b) The ODT induced from M
| Conf1 > 0.625
| Conf1 <= 0.625:
| |
| |
| Conf1 > 0.625: 1
| Conf1 <= 0.625:
| |
| |
c) The MDT written as a logic program
The comprehensibility of the MDT from Table 3a) is entirely due to the extended
expressiveness of the MDT leaves. Both the MDT and the ODT in Table 3a) and b) are
induced from the propositional data set M . While the ODT induced from M is purely
propositional, the MDT is not. A (rst order) logic program equivalent to the MDT
is presented in Table 3c). The predicate combine(Conf 1 , C 1 , Conf 2 , C 2 , C) is used to
combine the predictions of the base-level classiers C 1 and C 2 into class C according to
the values of the attributes (variables) Conf 1 and Conf 2 . Each clause of the program
corresponds to one leaf node of the MDT and includes a non-propositional class value
assignment in the rst and in the second clause). In the propositional
framework, the only possible assignments are one for each class value.
There is another way of interpreting meta decision trees. A meta decision tree selects an
appropriate classier for a given example in the domain. Consider the subset of examples
falling in one leaf of the MDT. It identies a subset of the data where one of the base-level
classiers performs better than the others. Thus, the MDT identify subsets that are
relative areas of expertise of the base-level classiers. An area of expertise of a base-level
classier is relative in the sense that its predictive performance in that area is better as
compared to the performances of the other base-level classiers. This is dierent from an
area of expertise of an individual base-level classier [15], which is a subset of the data
where the predictions of a single base-level classier are correct.
Note that in the process of inducing meta decision trees two types of attributes are used.
Ordinary attributes are used in the decision (inner) nodes of the MDT (e.g., attributes
Conf 1 and Conf 2 in the example meta-level data set M ). The role of these attributes is
identical to the role of attributes used for inducing ordinary decision trees. Class attributes
(e.g., C 1 and C 2 in M ), on the other hand, are used in the leaf nodes only. Each base-level
classier has its class attribute: the values of this attribute are the predictions of the
base-level classier. Thus, the class attribute assigned to the leaf node of the MDT decides
which base-level classier will be used for prediction. When inducing ODTs for combining
classiers, the class attributes are used in the same way as ordinary attributes.
The partitioning of the data set into relative areas of expertise is based on the values of
the ordinary meta-level attributes used to induce MDTs. In existing studies about areas
of expertise of individual classiers [15], the original base-level attributes from the domain
at hand are used. We use a dierent set of ordinary attributes for inducing MDTs. These
are properties of the class probability distributions predicted by the base-level classiers
and re
ect the certainty and condence of the predictions. However, the original base-level
attributes can be also used to induce MDTs. Details about each of the two sets of
meta-level attributes are given in the following subsection.
3.2 Meta-Level Attributes
As meta-level attributes, we calculate the properties of the class probability (CDP) distributions
predicted by the base-level classiers that re
ect the certainty and condence of
the predictions.
First, maxprob(x; C) is the highest class probability (i.e. the probability of the predicted
class) predicted by the base-level classier C for example x:
Next, entropy(x; C) is the entropy of the class probability distribution predicted by
the classier C for example x:
Finally, weight(x; C) is the fraction of the training examples used by the classier C
to estimate the class distribution for example x. For decision trees, it is the weight of
the examples in the leaf node used to classify the example. For rules, it is the weight of
the examples covered by the rule(s) which has been used to classify the example. This
property has not been used for the nearest neighbor and naive Bayes classiers, as it does
not apply to them in a straightforward fashion.
The entropy and the maximum probability of a probability distribution re
ect the certainty
of the classier in the predicted class value. If the probability distribution returned
is highly spread, the maximum probability will be low and the entropy will be high, indicating
that the classier is not very certain in its prediction of the class value. On the other
hand, if the probability distribution returned is highly focused, the maximum probability is
high and the entropy low, thus indicating that the classier is certain in the predicted class
value. The weight quanties how reliable is the predicted class probability distribution.
Intuitively, the weight corresponds to the number of training examples used to estimate
the probability distribution: the higher the weight, the more reliable the estimate.
An example MDT, induced on the image domain from the UCI repository [3], is given in

Table

4. The leaf denoted by an asterisk (*) species that the C4.5 classier is to be used
to classify an example, if (1) the maximum probability in the class probability distribution
predicted by k-NN is smaller than 0.77; (2) the fraction of the examples in the leaf of the
tree used for prediction is larger than 0.4% of all the examples in the training set;
and (3) the entropy of the class distribution predicted by C4.5 is less then 0.14. In sum, if
the k-NN classier is not very condent in its prediction (1) and the C4.5 classier is very

Table

4: A meta decision tree induced on the image domain using class distribution properties
as ordinary attributes.
knn maxprob <= 0.77147:
| c45 weight <= 0.00385: KNN
| c45 weight > 0.00385:
| | c45 entropy <= 0.14144: C4.5 (*)
| | c45 entropy > 0.14144: LTREE
condent in its prediction (3 and 2), the leaf recommends using the C4.5 prediction; this
is consistent with common-sense knowledge in the domain of classier combination.
Another set of ordinary attributes used for inducing meta decision trees is the set of
original domain (base-level) attributes (BLA). In this case, the relative areas of expertise
of the base-level classiers are described in terms of the original domain attributes as in
the example MDT in Table 5.

Table

5: A meta decision tree induced on the image domain using base-level attributes as
ordinary attributes.
short-line-density-5 <= 0:
| short-line-density-2 <= 0: KNN
| short-line-density-2 > 0: LTREE
short-line-density-5 > 0:
| short-line-density-5 <= 0.111111: LTREE
| short-line-density-5 > 0.111111: C45 (*)
The leaf denoted by an asterisk (*) in Table 5 species that C4.5 should be used to
classify examples with short-line-density-5 values larger than 0.11. MDTs based on
the base-level ordinary attributes can provide new insight into the applicability of the base-level
classiers to the domain of use. However, only a human expert from the domain of
use can interpret an MDT induced using these attributes. It cannot be interpreted directly
from the point of view of classier combination.
Note here another important property of MDTs induced using the CDP set of meta-level
attributes. They are domain independent in the sense that the same language for
expressing meta decision trees is used in all domains once we x the set of base-level
classiers to be used. This means that a MDT induced on one domain can be used in
any other domain for combining the same set of base-level classiers (although it may not
perform very well). In part, this is due to the fact that the CDP set of meta-level attributes
is domain independent. It depends only on the set of base-level classiers C. However, an
ODT built from the same set of meta-level attributes is still domain dependent for two
reasons. First, it uses tests on the class values predicted by the base-level classiers (e.g.,
the tests in the root node of the ODT from Table 3b). Second, an ODT
predicts the class value itself, which is clearly domain dependent.
In sum, there are three reasons for the domain independence of MDTs: (1) the CDP
set of meta-level attributes; (2) not using class attributes in the decision (inner) nodes and
(3) predicting the base-level classier to be used instead of predicting the class value itself.
3.3 MLC4.5 - a Modication of C4.5 for Learning MDTs
In this subsection, we present MLC4.5 1 , an algorithm for learning MDTs based on Quinlan's
C4.5 [17] system for inducing ODTs. MLC4.5 takes as input a meta-level data set as
generated by the algorithm in Table 1. Note that this data set consists of ordinary and
class attributes. There are four dierences between MLC4.5 and C4.5:
1. Only ordinary attributes are used in internal nodes;
2. Assignments of the form class attribute) are made by MLC4.5
in leaf nodes, as opposed to assignments of the form is a class value);
3. The goodness-of-split for internal nodes is calculated dierently (as described below);
4. MLC4.5 does not post-prune the induced MDTs.
The rest of the MLC4.5 algorithm is identical to the original C4.5 algorithm. Below we
describe C4.5's and MLC4.5's measures for selecting attributes in internal nodes.
patch that can be used to transform the source code of C4.5 into MLC4.5 is available at
http://ai.ijs.si/bernard/mdts/
C4.5 is a greedy divide and conquer algorithm for building classication trees [17]. At
each step, the best split according to the gain (or gain ratio) criterion is chosen from the set
of all possible splits for all attributes. According to this criterion, the split is chosen that
maximizes the decrease of the impurity of the subsets obtained after the split as compared
to the impurity of the current subset of examples. The impurity criterion is based on the
entropy of the class probability distribution of the examples in the current subset S of
training examples:
denotes the relative frequency of examples in S that belong to class c i . The
gain criterion selects the split that maximizes the decrement of the info measure.
In MLC4.5, we are interested in the accuracies of each of the base-level classiers C
from C on the examples in S, i.e., the proportion of examples in S that have a class equal
to the class attribute C. The newly introduced measure, used in MLC4.5, is dened as:
where accuracy(C; S) denotes the relative frequency of examples in S that are correctly
classied by the base-level classier C. The vector of accuracies does not have probability
distribution properties (its elements do not sum to 1), so the entropy can not be calculated.
This is the reason for replacing the entropy based measure with an accuracy based one.
As in C4.5, the splitting process stops when at least one of the following two criteria
is satised: (1) the accuracy of one of the classiers on a current subset is 100% (leading
to info ML or (2) a user dened minimal number of examples is achieved in the
current subset. In each case, a leaf node is being constructed. The classier with the
maximal accuracy is being predicted by a leaf node of a MDT.
In order to compare MDTs with ODTs in a principled fashion, we also developed a
intermediate version of C4.5 (called AC4.5) that induces ODTs using the accuracy based
info A measure:
4 Experimental Methodology and Results
The main goal of the experiments we performed was to evaluate the performance of meta
decision trees, especially in comparison to other methods for combining classiers, such as
voting and stacking with ordinary decision trees, as well as other methods for constructing
ensembles of classiers, such as boosting and bagging. We also investigate the use of
dierent meta-level attributes in MDTs. We performed experiments on a collection of
twenty-one data sets from the UCI Repository of Machine Learning Databases and Domain
Theories [3]. These data sets have been widely used in other comparative studies.
In the remainder of this section, we rst describe how classication error rates were
estimated and compared. We then list all the base-level and meta-level learning algorithms
used in this study. Finally, we describe a measure of the diversity of the base-level classiers
that we use in comparing the performance of meta-level learning algorithms.
4.1 Estimating and Comparing Classication Error Rates
In all the experiments presented here, classication errors are estimated using 10-fold
stratied cross validation. Cross validation is repeated ten times using a dierent random
reordering of the examples in the data set. The same set of re-orderings have been used
for all experiments.
For pair-wise comparison of classication algorithms, we calculated the relative improvement
and the paired t-test, as described below. In order to evaluate the accuracy
improvement achieved in a given domain by using classier C 1 as compared to using clas-
sier C 2 , we calculate the relative improvement: 1 error(C 1 )=error(C 2 ). In the analysis
presented in Section 5, we compare the performance of meta decision trees induced
using CDP as ordinary meta-level attributes to other approaches: C 1 will thus refer to
combiners induced by MLC4.5 using CDP. The average relative improvement across all
domains is calculated using the geometric mean of error reduction in individual domains:
The classication errors of C 1 and C 2 averaged over the ten runs of 10-fold cross validation
are compared for each data set (error(C 1 ) and error(C 2 ) refer to these averages).
The statistical signicance of the dierence in performance is tested using the paired t-test
(exactly the same folds are used for C 1 and C 2 ) with signicance level of 95%: += to
the right of a gure in the tables with results means that the classier C 1 is signicantly
better/worse than C 2 .
Another aspect of tree induction performance is the simplicity of the induced decision
trees. In the experiments presented here, we used the size of the decision trees, measured
as the number of (internal and leaf) nodes, as a measure of simplicity: the smaller the tree,
the simpler it is.
4.2 Base-Level Algorithms
Five learning algorithms have been used in the base-level experiments: two tree-learning
algorithms C4.5 [17] and LTree [11], the rule-learning algorithm CN2 [7], the k-nearest
neighbor (k-NN) algorithm [20] and a modication of the naive Bayes algorithm [12].
All algorithms have been used with their default parameters' settings. The output of
each base-level classier for each example in the test set consist of at least two components:
the predicted class and the class probability distribution. All the base-level algorithms
used in this study calculate the class probability distribution for classied examples, but
two of them (k-NN and naive Bayes) do not calculate the weight of the examples used
for classication (see Section 3). The code of the other three of them (C4.5, CN2 and
was adapted to output the class probability distribution as well as the weight of
the examples used for classication.
The classication errors of the base-level classiers on the twenty-one data sets are presented
in Table 7 in Appendix A. The smallest overall classication error is achieved using
linear discriminant trees induced with LTree. However, on dierent data sets, dierent
base-level classiers achieve the smallest classication error.
4.3 Meta-Level Algorithms
At the meta-level, we evaluate the performances of eleven dierent algorithms for constructing
ensembles of classiers (listed below). Nine of these make use of exactly the same set of
ve base-level classiers induced by the ve algorithms from the previous section. In brief,
two perform stacking with ODTs, using the algorithms C4.5 and AC4.5 (see previous sec-
three perform stacking with MDTs using the algorithm MLC4.5 and three dierent
sets of meta-level attributes (CDP, BLA, CDP+BLA); two are voting schemes; Select-Best
chooses the best base-level classier, and SCANN performs stacking with nearest neighbor
after analyzing dependencies among the base-level classiers. In addition, boosting and
bagging of decision trees are considered, which create larger ensembles (200 trees).
uses ordinary decision trees induced with C4.5 for combining base-level classiers.
uses ODTs induced with AC4.5 for combining base-level classiers.
MDT-CDP uses meta decision trees induced with MLC4.5 on a set of class distribution
properties (CDP) as meta-level attributes.
MDT-BLA uses MDTs induced with MLC4.5 on a set of base-level attributes (BLA) as
meta-level attributes.
MDT-CDP+BLA uses MDTs induced with MLC4.5 on a union of two alternative sets
of meta-level attributes (CDP and BLA).
P-VOTE is a simple plurality vote algorithm (see Section 2.1).
CD-VOTE is a renement of the plurality vote algorithm for the case where class probability
distributions are predicted by the base-level classiers (see Section 2.1).
Select-Best selects the base-level classier that performs best on the training set (as
estimated by 10-fold stratied cross-validation). This is equivalent to building a
single leaf MDT.
SCANN [14] performs Stacking with Correspodence Analysis and Nearest Neighbours.
Correspondence analysis is used to deal with the highly correlated predictions of
the base-level classiers: SCANN transforms the original set of potentially highly
correlated meta-level attributes (i.e., predictions of the base-level classiers), into a
new (smaller) set of uncorrelated meta-level attributes. A nearest neighbor classier
is then used for classication with the new set of meta-level attributes.
Boosting of decision trees. Two hundred iterations were used for boosting. Decision trees
were induced using J48 2 , (C4.5) with default parameters' settings for pre- and post-
pruning. The WEKA [21] data mining suite implements the AdaBoost [9] boosting
method with re-weighting of the training examples.
Bagging of decision trees. Two hundred iterations (decision trees), were used for bagging,
using J4.8 with default settings.
A detailed report on the performance of the above methods can be found in Appendix A.
Their classication errors can be found in Table 9. The sizes of (ordinary and meta) decision
trees induced with dierent meta-level combining algorithms are given in Table 8. Finally,
a comparison of the classication errors of each method to those of MDT-CDP (in terms of
average relative accuracy improvement and number of signicant wins and losses) is given
in

Table

10. A summary of this detailed report is given in Table 6.
4.4 Diversity of Base-Level Classiers
Empirical studies performed in [1, 2] show that the classication error of meta-level learning
methods as well as the improvement of accuracy achieved using them is highly correlated
to the degree of diversity of the predictions of the base-level classiers. The measure of the
diversity of two classiers used in these studies is error correlation. The smaller the error
correlation, the greater the diversity of the base-level classiers.
2 The experiments with bagging and boosting have been performed using the WEKA data mining suite
which includes J48, a Java re-implementation of C4.5. The dierences between the J48 results and
the C4.5 results are negligible: an average of 0.01% with a maximum relative dierence of 4%.
correlation is dened by [1, 2] as the probability that both classiers make the
same error. This denition of error correlation is not \normalized": its maximum value
is the lower of the two classication errors. An alternative denition of error correlation,
proposed in [11], is used in this paper. Error correlation is dened as the conditional
probability that both classiers make the same error, given that one of them makes an
error:
are predictions of classiers C i and C j for a given example x and
c(x) is the true class of x. The error correlation for a set of multiple classiers C is dened
as the average of the pairwise error correlations:
relative
improvement
over
LTree
(base-level)
degree of the error correlation between base-level classifiers
australian
balance
breast-w
bridges-td
car
chess
diabetes
echocardiogram
german
glass
heart
hepatitis
hypothyroid
image
ionosphere iris
soya
tic-tac-toe
vote
waveform
wine
insignificant
significant
relative
improvement
over
k-NN
(base-level)
degree of the error correlation between base-level classifiers
australian
balance
breast-w
bridges-td
car
chess
diabetes echocardiogram
german
glass
heart
hepatitis
hypothyroid
image
ionosphere
iris
soya
tic-tac-toe
vote
waveform
wine
insignificant
significant

Figure

2: Relative accuracy improvement achieved with MDTs when compared to two
base-level classiers (LTree and k-NN) in dependence of the error correlation among the
ve base-level classiers.
The graphs in Figure 2 conrm these results for meta decision trees. The relative accuracy
improvement achieved with MDTs over LTree and k-NN (two base-level classiers
with highest overall accuracies) decreases as the error correlation of the base-level clas-
siers increases. The linear regression line interpolated through the points conrms this
trend, which shows that performance improvement achieved with MDTs is correlated to
the diversity of errors of the base-level classiers.

Table

Summary performance of the meta-level learning algorithms as compared to MDTs
induced using class distribution properties (MDT-CDP) as meta-level attributes: average
relative accuracy improvement (in %), number of signicant wins/losses and average tree
size (where applicable). Details in Tables 10 and 8 in Appendix A.
Meta-level algorithm Ave. rel. acc. imp. (in
MDT-BLA 14.47 8/0 66.94
MDT-CDP+BLA 13.91 8/0 73.73
Select-Best 7.81 5/2 1
SCANN 13.95 9/6 NA
Boosting 9.36 13/6 NA
Bagging 22.26 10/4 NA
5 Analysis of the Experimental Results
The results of the experiments are summarized in Table 6. In brief, the following main
conclusions that can be drawn from these results:
1. The properties of the class probability distributions predicted by the base-level clas-
siers (CDP) are better meta-level attributes for inducing MDTs than the base-level
attributes (BLA). Using BLA in addition to CDP worsens the performance.
2. Meta decision trees (MDTs) induced using CDP outperform ordinary decision trees
and voting for combining classiers.
3. MDTs perform slightly better than the SCANN and Select-Best methods.
4. The performance improvement achieved with MDTs is correlated to the diversity of
errors of the base-level classiers: the higher the diversity, the better the relative
performance as compared to other methods.
5. Using MDTs to combine classiers induced with dierent learning algorithms outperforms
ensemble learning methods based on bagging and boosting of decision trees.
Below we look into these claims and the experimental results in some more detail.
5.1 MDTs with Dierent Sets of Meta-Level Attributes
We analyzed the dependence of MDTs performance on the set of ordinary meta-level
attributes used to induce them. We used three sets of attributes: the properties of the
class distributions predicted by the base-level classiers (CDP), the original (base-level)
domain attributes (BLA) and their union (CDP+BLA).
The average relative improvement achieved by MDTs induced using CDP over MDTs
induced using BLA and CDP+BLA is about 14% with CDP being signicantly better in 8
domains (see Table 6 and Table 10 in Appendix A). MDTs induced using CDP are about
times smaller on average than MDTs induced using BLA and CDP+BLA (see Table 8).
These results show that the CDP set of meta-level attributes is better than the BLA set.
Furthermore, using BLA in addition to CDP decreases performance. In the remainder of
this Section, we only consider MDTs induced using CDP.
An analysis of the results for ordinary decision trees induced using CDP, BLA and
CDP+BLA (only the results for CDP are actually presented in the paper) shows that the
claim holds also for ODTs. This result is especially important because it highlights the
importance of using the class probability distributions predicted by the base-level classiers
for identifying their (relative) areas of expertise. So far, base-level attributes from the
original domain have typically been used to identify the areas of expertise of base-level
classiers.
5.2 Meta Decision Trees vs. Ordinary Decision Trees
To compare combining classiers with MDTs and ODTs, we rst look at the relative
improvement of using MLC4.5 over C-C4.5 (see Table 6, column C-C4.5 of Table 10 in


Appendix

A and left hand side of Figure 3).
performs signicantly better in 15 and signicantly worse in 2 data sets. There
is a 4% overall decrease of accuracy (this is a geometric mean), but this is entirely due to
the result in the tic-tac-toe domain, where all combining methods perform very well. If we
exclude the tic-tac-toe domain, a 7% overall relative increase is obtained. We can thus say
that MLC4.5 performs slightly better in terms of accuracy. However, the MDTs are much
smaller, the size reduction factor being over 16 (see Table 8), despite the fact that ODTs
induced with C4.5 are post-pruned and MDTs are not.
relative
improvement
over
(in
tic-tac-toe balance breast-w hypothyroid soya heart image vote hepatitis glass
echocardiogram waveform iris
german australian chess diabetes car
bridges-td wine
ionosphere
avg.
insignificant
significant
relative
improvement
over
(in
iris
bridges-td image heart soya waveform vote breast-w hepatitis german balance diabetes echocardiogram glass
ionosphere australian hypothyroid chess wine car
tic-tac-toe
avg.
insignificant
significant

Figure

3: Relative improvement of the accuracy when using MDTs induced with MLC4.5
when compared to the accuracy of ODTs induced with AC4.5 and C4.5.
To get a clearer picture of the performance dierences due to the extended expressive
power of MDT leaves (as compared to ODT leaves), we compare MLC4.5 and C-AC4.5 (see

Table

6, column C-AC4.5 in Table 10 and right hand side of Figure 3). Both MLC4.5 and
AC4.5 use the same learning algorithm. The only dierence between them is the types of
trees they induce: MLC4.5 induces meta decision trees and AC4.5 induces ordinary ones.
The comparison clearly shows that MDTs outperform ODTs for combining classiers. The
overall relative accuracy improvement is about 8% and MLC4.5 is signicantly better than
C-AC4.5 in 12 out of 21 data sets and is signicantly worse in only one (ionosphere).
Consider also the graph on the right hand side of Figure 3. MDTs perform better than
ODTs in all but two domains, with the performance gains being much larger than the
losses.
Furthermore, the MDTs are, on average, more than 34 times smaller than the ODTs
induced with AC4.5 (see Table 8). The reduction of the tree size improves the comprehensibility
of meta decision trees. For example, we were able to interpret and comment on the
MDT in

Table

4.
In sum, meta decision trees performs better than ordinary decision trees for combining
classiers: MDTs are more accurate and much more concise. The comparison of MLC4.5
and AC4.5 shows that the performance improvement is due to the extended expressive
power of MDT leaves.
5.3 Meta Decision Trees vs. Voting
Combining classiers with MDTs is signicantly better than plurality vote in 10 domains
and signicantly worse in 6. However, the signicant improvements are much higher than
the signicant drops of accuracy, giving an overall accuracy improvement of 22%. Since
performs slightly better than plurality vote, a smaller overall improvement of
20% is achieved with MDTs. MLC4.5 is signicantly better in 10 data sets and signicantly
worse in 5. These results show that MDTs outperform the voting schemes for combining
classiers (see Table 6 and Table 10 in Appendix A).
-0.4
relative
improvement
over
degree of the error correlation between base-level classifiers
australian
balance
breast-w
bridges-td
car
chess
diabetes
echocardiogram
german
glass
heart
hepatitis
hypothyroid
image
ionosphere
iris
soya
tic-tac-toe
vote
waveform
wine
insignificant
significant
-0.4
relative
improvement
over
degree of the error correlation between base-level classifiers
australian
balance
breast-w
bridges-td
car
chess
diabetes
echocardiogram
german
glass
heart hepatitis
hypothyroid
image
ionosphere
iris
soya
tic-tac-toe
vote
waveform
wine
insignificant
significant

Figure

4: Relative improvement of the accuracy of MDTs over two voting schemes in
dependence of the degree of error correlation between the base-level classiers.
We explored the dependence of accuracy improvement by MDTs over voting on the
diversity of the base-level classiers. The graphs in Figure 4 show that MDTs can make
better use of the diversity of errors of the base-level classiers than the voting schemes.
Namely, for the domains with low error correlation (and therefore higher diversity) of the
base-level classiers, the relative improvement of MDTs over the voting schemes is higher.
However, the slope of the linear regression line is smaller than the one for the improvement
over the base-level classiers. Still, the trend clearly shows that MDTs make better use of
the error diversity of the base-level predictions than voting.
5.4 Meta Decision Trees vs. Select-Best
Combining classiers with MDTs is signicantly better than Select-Best in 5 domains and
signicantly worse in 2, giving an overall accuracy improvement of almost 8% (see Table 6
and

Table

in Appendix A).
relative
improvement
over
Select-Best
degree of the error correlation between base-level classifiers
australian
balance breast-w bridges-td
car
chess
diabetes
echocardiogram
german
glass heart hepatitis
hypothyroid
image
ionosphere iris
soya
tic-tac-toe
vote
waveform
wine
insignificant
significant

Figure

5: Relative improvement of the accuracy of MDTs over Select-Best method in
dependence of the degree of error correlation between the base-level classiers.
The results of the dependence analysis of accuracy improvement by MDTs over Select-
Best on the diversity of the base-level classiers is given in Figure 5. MDTs can make
slightly better use of the diversity of errors of the base-level classiers than Select-Best.
The slope of the linear regression line is smaller than the one for the improvement over the
voting methods.
5.5 Meta Decision Trees vs. SCANN
Combining classiers with MDTs is signicantly better than SCANN in 9 domains and
signicantly worse in 6 (see Table 6 and Table 10 in Appendix A). However, the signicant
improvements are much higher than the signicant drops of accuracy, giving an overall
accuracy improvement of almost 14%. These results show that MDTs outperform the
SCANN method for combining classiers.
-0.4
relative
improvement
over
degree of the error correlation between base-level classifiers
australian
balance breast-w
bridges-td
car
chess
diabetes
echocardiogram
german
glass
heart
hepatitis
hypothyroid
image
ionosphere
iris
soya
tic-tac-toe
vote
waveform
wine
insignificant
significant

Figure

Relative improvement of the accuracy of MDTs over SCANN method in dependence
of the degree of error correlation between the base-level classiers.
We explored the dependence of accuracy improvement by MDTs over SCANN on the
diversity of the base-level classiers. The graph in Figure 6 shows that MDTs can make a
slightly better use of the diversity of errors of the base-level classiers than SCANN. The
slope of the linear regression line is smaller than the one for the improvement over the
voting methods.
5.6 Meta Decision Trees vs. Boosting and Bagging
Finally, we compare the performance of MDTs with the performance of two state of the
art ensemble learning methods: bagging and boosting of decision trees.
performs signicantly better than boosting in 13 and signicantly better than
bagging in 10 out of the 21 data sets. MLC4.5 performed signicantly worse than boosting
in 6 domains and signicantly worse than bagging in 4 domains only. The overall relative
improvement of performance is 9% over boosting and 22% over bagging (see Table 6 and

Table

in Appendix A).
It is clear that MDTs outperform bagging and boosting of decision trees. This comparison
is not fair in the sense that MDTs use base-level classiers induced by decision trees
and four other learning methods, while boosting and bagging use only decision trees as a
base-level learning algorithm. However, it does show that our approach to constructing
ensembles of classiers is competitive to existing state of the art approaches.
6 Related Work
An overview of methods for constructing ensembles of classiers can be found in [8]. Several
meta-level learning studies are closely related to our work.
Let us rst mention the study of using SCANN [14] for combining base-level classiers.
As mentioned above, SCANN performs stacking by using correspondence analysis of the
classications of the base-level classiers. The author shows that SCANN outperforms the
plurality vote scheme, also in the case when the base-level classiers are highly correlated.
SCANN does not use any class probability distribution properties of the predictions by the
base-level classiers (although the possibility of extending the method in that direction
is mentioned). Therefore, no comparison with the CD voting scheme is included in their
study. Our study shows that MDTs using CDP attributes are slightly better than SCANN
in terms of performance. Also, the concept induced by SCANN at the meta-level is not
directly interpretable and can not be used for identifying the relative areas of expertise of
the base-level classiers.
In cascading, base-level classiers are induced using the examples in a current node of
the decision tree (or each step of the divide and conquer algorithm for building decision
trees). New attributes, based on the class probability distributions predicted by the base-level
classiers, are generated and added to the set of the original attributes in the domain.
The base-level classiers used in this study are naive Bayes and Linear Discriminant. The
integration of these two base-level classiers within decision trees is much tighter than in
our combining/stacking framework. The similarity to our approach is that class probability
distributions are used.
A version of stacked generalization, using the class probability distributions predicted
by the base-level classiers, is implemented in the data mining suite WEKA [21]. However,
class probability distributions are used there directly and not through their properties, such
as maximal probability and entropy. This makes them domain dependent in the sense
discussed in Section 3. The indirect use of class probability distributions through their
properties makes MDTs domain independent.
Ordinary decision trees have already been used for combining multiple classiers in
[6]. However, the emphasis of their study is more on partitioning techniques for massive
data sets and combining multiple classiers trained on dierent subsets of massive data
sets. Our study focuses on combining multiple classiers generated on the same data set.
Therefore, the obtained results are not directly comparable to theirs.
Combining classiers by identifying their areas of expertise has already been explored
in [15] and [13]. In their studies, a description of the area of expertise in the form of an
ordinary decision tree, called arbiter, is induced for each individual base-level classier.
For a single data set, as many arbiters are needed as there are base-level classiers. When
combining multiple classiers, a voting scheme is used to combine the decisions of the
arbiters. However, a single MDT, identifying relative areas of expertise of all base-level
classiers at once is much more comprehensible. Another improvement presented in our
study is the possibility to use the certainty and condence of the base-level predictions for
identifying the classiers expertise areas and not only the original (base-level) attributes
of the data set.
The present study is also related to our previous work on the topic of meta-level learning
[18]. There we introduced an inductive logic programming [16] (ILP) framework for learning
the relation between data set characteristics and the performance of dierent (base-
level) classiers. A more expressive (non-propositional) formulation is used to represent
the meta-level examples (data set characteristics), e.g., properties of individual attributes.
The induced meta-level concepts are also non-propositional. While MDT leaves are more
expressive than ODT leaves, the language of MDTs is still much less expressive than the
language of logic programs used in ILP.
7 Conclusions and Further Work
We have presented a new technique for combining classiers based on meta decision trees
(MDTs). MDTs make the language of decision trees more suitable for combining classiers:
they select the most appropriate base-level classier for a given example. Each leaf of the
MDT represents a part of the data set, which is a relative area of expertise of the base-level
classier in that leaf. The relative areas of expertise can be identied on the basis of the
values of the original (base-level) attributes (BLA) of the data set, but also on the basis
of the properties of the class probability distributions (CDP) predicted by the base-level
classiers. The latter re
ect the certainty and condence of the class value predictions by
the individual base-level classiers.
The extensive empirical evaluation shows that MDTs induced from CDPs perform much
better and are much more concise than MDTs induced from BLAs. Due to the extended
expressiveness of MDT leaves, they also outperform ordinary decision trees (ODTs), both
in terms of accuracy and conciseness. MDTs are usually so small that they can easily be
interpreted: we regard this as a step towards a comprehensible model of combining clas-
siers by explicitly identifying their relative areas of expertise. In contrast, most existing
work uses non-symbolic learning methods (e.g., neural networks) to combine classiers [14].
MDTs can use the diversity of the base-level classiers better than voting: they out-perform
voting schemes in terms of accuracy, especially in domains with high diversity of
the errors made by the base-level classiers. MDTs also perform slightly better than the
SCANN method for combining classiers and the Select-Best method, which simply takes
the best single classier. Finally, MDTs induced from CDPs perform better than boosting
and bagging of decision trees and are thus competitive with state of the art methods for
learning ensembles.
MDTs built by using CDPs are domain independent and are, in principle, transferable
across domains once we x the set of base-level learning algorithms. This in the sense that
a MDT built on one data set can be used on any other data set (since it uses the same set
of attributes). There are several potential benets of the domain independence of MDTs.
First, machine learning experts can use MDTs for domain independent analysis of relative
areas of expertise of dierent base-level classiers, without having knowledge about the
particular domain of use. Furthermore, an MDT induced on one data set can be used for
combining classiers induced by the same set of base-level learning algorithms on other
data sets. Finally, MDTs can be induced using data sets that contain examples originating
from dierent domains.
Exploring the above options already gives us some topics for further work. Combining
data from dierent domains for learning MDTs is an especially interesting avenue for
further work that would bring together the present study with meta-level learning work on
selecting appropriate classiers for a given domain [4]. In this case, attributes describing
individual data set properties can be added to the class distribution properties in the meta-level
learning data set. Preliminary investigations along these lines have been already made
[19].
There are several other obvious directions for further work. For ordinary decision trees,
it is already known that post-pruning gives better results than pre-pruning. Preliminary
experiments show that pre-pruning degrades the classication accuracy of MDTs. Thus,
one of the priorities for further work is the development of a post-pruning method for meta
decision trees and its implementation in MLC4.5.
An interesting aspect of our work is that we use class-distribution properties for meta-level
learning. Most of the work on combining classiers only uses the predicted classes and
not the corresponding probability distributions. It would be interesting to use other learning
algorithms (neural networks, Bayesian classication and SCANN) to combine classiers
based on the probability distributions returned by them. A comparison of combining clas-
siers using class predictions only vs. with class predictions along with class probability
distributions would be also worthwhile.
The consistency of meta decision trees with common sense classiers combination
knowledge, as brie
y discussed in Section 3, opens another question for further research.
The process of inducing meta-level classiers can be biased to produce only meta-level
classiers consistent with existing knowledge. This can be achieved using strong language
bias within MLC4.5 or, probably more easily, within a framework of meta decision rules,
where rule templates could be used.

Acknowledgments

The work reported was supported in part by the Slovenian Ministry of Education, Science
and Sport and by the EU-funded project Data Mining and Decision Support for
Business Competitiveness: A European Virtual Enterprise (IST-1999-11495). We thank
Jo~ao Gama for many insightful and inspirational discussions about combining multiple
classiers. Many thanks to Marko Bohanec, Thomas Dietterich, Nada Lavrac and three
anonymous reviewers for their comments on earlier versions of the manuscript.



--R

On explaining degree of error reduction due to combining multiple decision trees.
reduction through learning multiple descriptions.
UCI repository of machine learning databases.

Analysis of Results.
Bagging Predictors.
On the Accuracy of Meta-learning for Scalable Data Mining
Rule induction with CN2: Some recent improvements.

Experiments with a New Boosting Algorithm.
Combining Classi
Discriminant trees.
A Linear-Bayes Classi er
Integrating multiple classi
Using Correspondence Analysis to Combine Classi
Exploiting Multiple Existing Models and Learning Algorithms.
Learning logical de



A study of distance-based machine learning algorithms
Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations.
Stacked Generalization.
--TR

--CTR
Michael Gamon, Sentiment classification on customer feedback data: noisy data, large feature vectors, and the role of linguistic analysis, Proceedings of the 20th international conference on Computational Linguistics, p.841-es, August 23-27, 2004, Geneva, Switzerland
Saso Deroski , Bernard enko, Is Combining Classifiers with Stacking Better than Selecting the Best One?, Machine Learning, v.54 n.3, p.255-273, March 2004
Efstathios Stamatatos , Gerhard Widmer, Automatic identification of music performers with learning ensembles, Artificial Intelligence, v.165 n.1, p.37-56, June 2005
Christophe Giraud-Carrier , Ricardo Vilalta , Pavel Brazdil, Introduction to the Special Issue on Meta-Learning, Machine Learning, v.54 n.3, p.187-193, March 2004
Joo Gama, Functional Trees, Machine Learning, v.55 n.3, p.219-250, June 2004
Pavel B. Brazdil , Carlos Soares , Joaquim Pinto Da Costa, Ranking Learning Algorithms: Using IBL and Meta-Learning on Accuracy and Time Results, Machine Learning, v.50 n.3, p.251-277, March
Nicols Garca-Pedrajas , Domingo Ortiz-Boyer, A cooperative constructive method for neural networks for pattern recognition, Pattern Recognition, v.40 n.1, p.80-98, January, 2007
S. B. Kotsiantis , I. D. Zaharakis , P. E. Pintelas, Machine learning: a review of classification and combining techniques, Artificial Intelligence Review, v.26 n.3, p.159-190, November  2006
stacking;meta-level learning;decision trees;ensembles of classifiers;combining classifiers