Data mining criteria for tree-based regression and classification.
This paper is concerned with the construction of regression and classification trees that are more adapted to data mining applications than conventional trees. To this end, we propose new splitting criteria for growing trees. Conventional splitting criteria attempt to perform well on both sides of a split by attempting a compromise in the quality of fit between the left and the right side. By contrast, we adopt a data mining point of view by proposing criteria that search for interesting subsets of the data, as opposed to modeling all of the data equally well. The new criteria do not split based on a compromise between the left and the right bucket; they effectively pick the more interesting bucket and ignore the other.As expected, the result is often a simpler characterization of interesting subsets of the data. Less expected is that the new criteria often yield whole trees that provide more interpretable data descriptions. Surprisingly, it is a "flaw" that works to their advantage: The new criteria have an increased tendency to accept splits near the boundaries of the predictor ranges. This so-called "end-cut problem" leads to the repeated peeling of small layers of data and results in very unbalanced but highly expressive and interpretable trees.
Introduction
Tree methods can be applied to two kinds of predictive problems. Regression trees
are used to predict a continuous response, while classification trees are used to
predict a class label.
The goal of tree methods is to partition data into small buckets such that a
response value (regression tree) or a class label (classification tree) can be well
predicted in each subset. Figure 1 shows partitions in a regression tree in the
left panel and a classification tree in the right panel. In the left panel, data are
partitioned into two subsets in order to explain the response (vertical axis) as best
as possible with means in the subsets. In the right panel, data are partitioned into
two subsets in order to explain the class labels "1","2","3" as best as possible.
Andreas Buja is Technology Consultant, AT&T Labs - Research, 180 Park Ave, P.O. Box 971,
Florham Park, NJ 07932-0971.
andreas@research.att.com, http://www.research.att.com/~andreas/
Yung-Seop Lee is graduate student, Department of Statistics, Rutgers University, Hill Center
for the Mathematical Sciences - Busch Campus, Piscataway, NJ 08855.
Regression Tree
x
Classification Tree
x
class
Figure

1: Partitions in Regression and Classification Tree
1.1 Structure of trees
Data are repeatedly partitioned into even smaller subsets by means of binary splits.
Thus a tree can be described by a diagram such as Figure 2 (a). Each node represents
a subset of data, each pair of daughter nodes represents a binary split of the subset
corresponding to the parent node.2
(a)
(b)

Figure

2: Two predictors example
Standard trees partition the data with binary splits along predictor variables,
that is, two daughter subsets of a parent subset are obtained by splitting a fixed
value at a fixed threshold; for example, x goes to left daughter and x (1) - t 1
goes to right daughter, and so on . Figure 2 (a) illustrates a tree with repeated
splits at x (1) with respect to t 1 , x (2) with respect to t 2 , and x (1) again with respect
to t 3 . The geometry of the resulting partitions is illustrated in Figure 2 (b).
1.2 Tree construction: greedy optimization of splits
One repeatedly searches for the best possible split of a subset by searching all possible
threshold values for all variables.
Optimization is according to an impurity measure, which will be discussed in
detail in Sections 3 and 4. For regression trees, impurity can be measured by variants
of RSS, while for classification trees, impurity can be measured for example by
misclassification rate, entropy, Gini index, .
One stops splitting a subset when no significant gain in impurity can be obtained.
The subset then forms a terminal node or "leaf" in the tree.
Since CART (Breiman et al., 1984), the sizing of trees is somewhat more complex:
One tends to grow first an overly large tree, and then to prune it back in a second
stage. The reason for this is the greediness of tree construction which does not look
ahead more than one step, and may hence miss out on successful splits further down
the line. Overgrowing and pruning trees may therefore find more optimal trees than
growing alone.
1.3 Splitting criteria for data mining
A tree growing strategy is specified by defining a measure of impurity for a split.
This is done by defining a measure of impurity for the left and the right bucket of
a split, and by combining these two measures into an overall impurity measure for
the split.
In conventional splitting criteria, the left and the right are combined by a
weighted sum of the two sides. In effect, one compromises between left and right
buckets by taking their sizes into account.
In our new data mining criteria, however, we are not interested in modeling all
of the data equally well; rather, we are content as long as we find subsets of the
data that are interesting. We therefore propose combining the impurities of the left
and right buckets of split in such a way that a split occurs when one bucket alone is
of low impurity, regardless of the other bucket. That is, low impurity of one bucket
alone causes a low value for the impurity measure of the split.
These data mining criteria for splits need to be developed for regression and
classification trees separately. Section 3 deals with regression, and Section 4 with
classification.
2 Data for Trees
2.1 When To Grow Trees, and When Not
Recently tree methods have been applied to many areas in data mining, sometimes
even with data that are not suitable for tree methods. In general, growing trees
is most useful when dependence on predictors is heterogeneous, complex and interactions
are present. If the dependency is heterogeneous or complex, multiple local
structures can be handled by tree methods, while other models can only handle
a single prominent structure. The strength of trees for detecting interactions was
effectively advertized by the names of the first tree methods:
Interaction Detection (Morgan & Sonquist, 1963), and Chi-square-based
AID (Hartigan, 1975).
Prediction accuracy of trees will suffer in the following situations:
ffl Regression trees may fail when a dose response is present. The term "dose re-
sponse", borrowed from biostatistics, refers to gradual monotone dependence;
the opposite is dependence with threshold effects.
ffl Classification trees may fail when the optimal decision boundaries are not
aligned in some way with the variable axes, and hence splits on variables are
not able to make full use of the information contained in the predictors.
Interpretability of trees, on the other hand, may suffer in the presence of highly
correlated predictors: Correlated predictors can substitute for each other and appear
in more or less random alternation, when in fact one of the predictors would suffice.
The effect is added complexity for the interpreting data analyst and, even worse, the
possibility of misleading conclusions when separate and distinct effects are attributed
to the predictors, even though they share the "effects" due to their correlations.
2.2 An Example of When Not to Grow Trees
The waveform data (Breiman et al., 1984, p. 49 and 134) is an example of unsuitable
data for tree growing. This data was generated artificially with 21-dimensional
predictors. It has three classes whose distribution in predictor space is analytically
described as follows:
where the numbers u and ffl m are independently distributed according to the uniform
distribution on [0; 1], and the Gaussian with zero mean and unit variance, respec-
tively. The three 21-dimensional vectors h are irrelevant, except
for the fact that they form an obliquely placed triangle with sides of length roughly
11.5, 11.5 and 16.5. The shape of the resulting pointcloud is that of three sausages
with their ends linked together. This is reflected in the projection onto the first two
principal components, shown in figure 3 .
The reason why tree methods are not successful in this data is that the optimal
classification boundaries are not aligned with any of the coordinate axes, as the
authors mention on p. 55. From the geometry of the data it is immediate that
linear discriminant analysis outperforms trees. Thus, before applying tree methods
blindly, one should perform a preliminary exploratory analysis to determine what
type of classification procedure will make best use of the available information in
the data.
Figure

3: Distribution of Class of Waveform Data
2.3 Uses of Trees
There are two principles which must be balanced in using tree growing algorithms;
accuracy for prediction, and 2) interpretation.
In prediction problems, one wants to grow trees which produce accurate classifiers
based on training samples and which generalize well to test samples.
Often, one also wants to grow interpretable trees, that is, trees whose nodes
represent potentially useful and meaningful subsets. For interpretation, the top of
a tree is usually the most valuable part because the top nodes can be described
using few conditions: In general, each step down a tree adds a new inequality to
the description of a node (for exceptions, see below). It is also helpful, although not
essential for interpretation, that the top nodes of a tree tend to be statistically less
variable than lower level nodes.
2.4 Simplicity and Interpretability of Trees
In the present work, we are concerned with the construction of methods that favor
interpretable trees. That is, we attempt to find methods that search for meaningful
nodes as close to the top of the tree as possible. By emphasizing the interpretability
of nodes near the top, we de-emphasize the precise calibration of the tree depth
for prediction: Stopping criteria for growing and pruning trees are of low priority
for our purposes because the interpreting data analyst can always ignore the lower
nodes of a tree that was grown too deeply. This is harmless as long as the analyst
does not interpret statistical flukes in the lower nodes. By de-emphasizing the lower
parts of trees, we may sacrifice some global accuracy for prediction.
A remark about simplicity and interpretability of trees is in order: Although
the literature has a bias in favor of balanced trees, balance and interpretability are
very different concepts: There exists a type of extremely unbalanced trees that are
highly interpretable, namely, those that use the same variable repeatedly down a
cascade of splits. See Figure 4 for an example. The simplicity of this tree stems
from the fact that all nodes can be described by one or two conditions, regardless
of tree depth.
Tree fragments similar to this example appear often in trees fitted to data that
exhibit dose response. In the example of Figure 4, it is apparent from the mean
values in the nodes that the response shows monotone increasing dependence on
the predictor x. If this kind of tree structure is found, a data analyst may want to
consider linear or additive models that describe the monotone dependence in a more
direct way. On the other hand, dose response may be present only locally, in which
case a tree may still be a more successful description of the data than a linear or
an additive model. Below we will illustrate with the Boston Housing data how our
new data mining criteria can uncover local dose response.
Our new criteria for splitting sometimes generate trees that are less balanced and
yet more interpretable than conventional balanced trees. This is not a contradiction,
as the preceding considerations show.
x < 7x < 4

Figure

4: An artificial example of a simple and interpretable yet unbalanced tree
3 Regression Trees
3.1 Conventional Criteria for Regression Trees
As mentioned in Section 1.1, trees are grown by recursively splitting the data based
on minimization of a splitting criterion.
Conventional splitting criteria are compromises of the impurities of left and right
buckets. The impurity measure of choice for buckets is simply the variance. The
compromise for the splitting criterion is a weighted average of the variances or a
function thereof in the left and right buckets.
We need some notation: The means and variances in the left and right buckets
are denoted by
-R =NR
R =NR
The compromise for the split can be derived with maximum likelihood estimation in
a combined Gaussian model for the two buckets: i.i.d. N(-L ; oe 2
L ) in the left bucket
and i.i.d. N(-R ; oe 2
R ) in the right bucket. In CART, equal variances are assumed,
but there is no necessity to this assumption. We give the criteria for both equal and
non-equal variances. After minimizing the negative log Likelihood of these models,
the following splitting criteria result:
equal variance model (CART) : crit LR =NL +NR [N L - oe 2
[N L log -
L +N R log - oe 2
This makes precise the sense in which conventional criteria compromise between the
left and right bucket.
Minimization of the negative log Likelihood is straightforward, but here it is
anyway: In the equal variance case, we have
min -L ;- R ;oe [\Gammalog likelihood(L;
oe L
2 ) is the pooled variance estimate. Thus, minimizing
yields the same splits as minimizing the negative log Likelihood.
For the non-equal variance case, we get
min -L ;oe L ;- R ;oe R
[\Gammalog likelihood(L;
R +1+log
where the constants can be dropped because they do not affect the minimization
over all splits.
3.2 Data Mining Criteria for Regression Trees
Under some circumstances, conventional criteria for tree growing are unable to immediately
identify single interesting buckets, where "interesting" could mean buckets
with high mean value of the response, or high purity in terms of small variance of
the response. The kind of situations we have in mind are depicted in Figure 5. The
left hand plot shows a response that has a subset with small variance on the right,
while the right hand plot has a subset with extreme mean on the right. It is plain
that the CART criterion will not deal properly with the left hand situation as it
assumes equal variances. In the right hand situation CART will find a split in the
middle at around x = 300 whereas we may have an interest in finding the small
bucket with extremely high mean on the right.
Our approach is to identify pure buckets (-oe 2 small) or extreme buckets (- ex-
treme) as quickly as possible.
For example, we will ignore the left bucket if the right side is interesting, that
R is very small or if -
-R is very high (or low). Thus we are not compromising
anymore between left and right buckets. In order to generate this type of tree, we
use two new criteria for splitting.
x
y
-55x
y
-226
Figure

5: Examples of Pure or Extreme Buckets. Left : Around x=200, we find a
pure bucket with small -
oe 2 . Right: Around x=600, we find an extreme bucket with
large mean.
With this criterion we are searching for one pure bucket as early as possible. To
this end, rather than using a weighted average of two variances, the criterion
is:
crit
By minimizing this criterion over all possible splits, we are finding a split whose
left or right side is the single bucket with smallest variance (purity). Note that
for the subsequent split, both the high-purity bucket AND the ignored bucket
are candidates for further splitting. Thus, ignored buckets get a chance to have
further high-purity buckets split off later on. Typically, a high-purity bucket
is unlikely to be split again. As a result, the trees grown with this criterion
tend to be purposely unbalanced.
ffl New Criterion 2: One-sided extremes (high or low value response)
This criterion is searching for a high mean on the response variable as early as
possible. dual criterion would be searching for low means.) The criterion is
a more radical departure from conventional approaches because the notion of
"purity" has never been questioned so far. Means have never been thought of
as splitting criteria, although they are often of greater interest than variances.
From our point of view, minimizing a variance-based criterion is a circuitous
route when searching for interesting means. The mean criterion we propose
maximizes the larger of the means of the left and right bucket:
crit
Implicitly the bucket with the smaller mean is ignored. By maximizing this
criterion over all possible splits, we are finding a split whose left or right side
is the single bucket with the highest mean.
At this point, a natural criticism of the above criteria may arise: their potentially
excessive greediness, that is, trees built with these criteria may miss the most
important splitting variables and they may instead capture spurious groups on the
periphery of the variable ranges, thus exacerbating the so-called "end cut problem."
This criticism has a grain of truth, but it paints the situation bleaker than it is.
It is not true that important splitting variables are generally missed; it depends
on the data at hand whether the conventional or the newly proposed criteria are
more successful. The criterion that searches for one-sided extremes, for example,
can be successful because extreme response values are often found on the periphery
of the variable ranges, if for no other reason than monotonicity of many response
surfaces. The "end cut problem," that is the preference of cuts near the extremes
of the variable ranges, is shared by most tree-building strategies [see Breiman et al.,
1984, p.313], so this is nothing peculiar to the new criteria.
A second criticism is the lack of balance in the trees constructed with the above
criteria. Superficially, one might expect balanced trees to be more interpretable than
unbalanced ones, defeating the rationale for the criteria. This concern is unfounded,
though, as we will show with real data examples below. In those cases where the
above criteria succeed, they produce more interpretable trees due to the simple
rationale that underlies them.
Finally, recall that the present goal is not to devise methods that produce superior
fit, but methods that enhance interpretability. Therefore, we are not concerned
with the usual problems of tuning tree-depth for fit with stopping and pruning
strategies. In the course of interpretation of a tree, a user simply ignores lower level
nodes when they are no longer interpretable.
4 Classification Trees
4.1 Conventional Criteria for Classification Trees
We consider here only the two-class situation. The class labels are denoted 0 and
1. Given a split into left and right buckets, let p 0
be the
probabilities of 0 and 1 on the left and on the right, respectively. Here are some of
the conventional loss or impurity notions for buckets:
ffl Misclassification rate in the left bucket: min(p 0
(Breiman et al., 1984,
p.98). Implicitly one assigns a class to the bucket by majority vote and estimates
the misclassification rate by the proportion of the other class.
ffl Entropy (information): \Gammap 0
L . If the probabilities are estimated
by relative frequencies (denoted the same by abuse of notation), the
entropy can also be interpreted as min[\Gammalog likelihood=N L ] of the multinomial
model in the left bucket, where NL is the size of the left bucket (Breiman
et al., 1984, p.103).
ffl The Gini index: p 0
L . In terms of estimates, this is essentially the Mean
Square fitting a mean to y n 2 f0; 1g; n 2 L, as a short
calculation shows:
L is the number of 0's and N 1
L is the number of 1's
in the left bucket.0.20.60.0 0.5 1.0
Misclassification
the
Gini
index

Figure

Impurity Functions for buckets, from left to right: misclassification rate,
entropy, and the Gini index (as a function of p 0
L , for example).
The above impurity criteria for buckets are conventionally blended into impurity
criteria for splits by forming weighted sums from the left and right buckets, thus
compromising between left and right. Denoting with pL the marginal
probabilities of the left and the right bucket, the compromise takes the following
form for misclassification rate:
for entropy:
R log
R log
and for the Gini index:
The impurity functions for buckets are depicted in Figure 6. They have several
desirable properties: In a given node, they take the maximum value when the classes
are in equal proportions, and the minimum value when all bucket members are in
the same class. Also, these functions are symmetric, and hence the two classes are
treated equally (assuming equal priors).
Among the three impurity functions, misclassification rate is the most problematic
because it may lead to many indistinguishable splits, some of which may be
intuitively more preferable than others. The problem is illustrated, for example, in
Breiman et al. (1984, p.96). The general reason is linearity of misclassification rate
on either half of the unit interval(see the left plot of Figure 6). Linearity implies that
data can be shifted (within limits) between left and right buckets without changing
the combined misclassification rate of a split. The following consideration gives an
idea of the large number of potential splits that are equivalent under misclassification
rate: Consider the misclassification count NLmin(p 0
of rate) on training data, and estimate the probabilities by relative frequencies:
Denote by N l
L and N l
R the counts of the minority class - the "losers" - on the left
and right, and correspondingly by N w
L and N w
R the counts of the majority class -
the "winners" - on the left and right:
l
R - N w
R (1)
where l 6= w 2 f0; 1g. Note that
R (2)
is the misclassification count. Because
L and
R +N w
R are the
counts of the left and right bucket, respectively, we have
R +N w
R (3)
for the count of the parent bucket.
For a fixed value of the misclassification count M , there exist many combinations
(N l
R ) satisfying the above conditions 1, 2 and 3. For example, for
fixed there exist a large number of combinations, such as
In general, there exist
combinations for fixed N and M . For this amounts to 1281
possibilities. For fixed N, the maximum number of combinations is (N
is attained for misclassification count Figure 7 shows the number
of combinations for as a functions of M .
missclassification count
number
of
combinations
parent bucket size = 100

Figure

7: Number of combinations of misclassification count for fixed N=100
These considerations suggest that misclassification rate, when used as a splitting
criterion, can suffer from considerable non-uniqueness of minimizing splits. When
considering two examples of equivalent splits, however, one observes quickly that
one of the two splits is usually preferable for reasons other than misclassification
rate. For example, among the two equivalent splits resulting in the combinations
(N l
respectively, the latter
is clearly preferable because it provides one large bucket (R) that is completely pure.
The root of the problem is the piecewise linearity of the misclassification rate
such as min(p 0
R ) in the right bucket. We therefore need an impurity function
that accelerates toward zero, that is, decreases faster than linearly, as the proportion
of the dominant class in a bucket moves closer to 1. This is the rationale for using
concave impurity functions such as entropy and the Gini index. CART (Breiman
et al., 1984 and Salford Systems, 1995) uses the Gini index, while C4.5 (Quinlan,
1993) and S-Plus (Venables and Ripley, 1994) use entropy.
In the two-class case, there does not seem to exist a clear difference in performance
between entropy and the Gini index. In the multiclass case, however, recent
work by Breiman (1996) has brought to light a difference between the Gini and entropy
criterion. The Gini index tends to assign the majority class to one pure bucket
(if it exists) and the rest of the classes to the other bucket, that is, it tends to form
unbalanced, well distinguishable buckets. Entropy, on the other hand, tries to balance
the size of the two buckets. According to Breiman, this results in deficiencies
of entropy that are not shared by the Gini index.
4.2 Data Mining Criteria for Classification Trees
As mentioned in Section 3.2, our approach tries to identify pure or extreme buckets
as quickly as possible. While the criteria for regression trees are based on variances
or means, the ones for classification trees are only based on the probabilities of
class 0 or 1. Our goal can therefore be restated as searching for buckets where one
of the class probabilities (p 0 or either in the left or the right bucket, but
not necessarily both.
Another approach is to select one of the two classes, 1, say, and look for buckets
that are very purely class 1. For example, in a medical context, one might want to
quickly find buckets that show high rates of mortality, or high rates of treatment
effect.
As before in Section 3.2, we use two criteria for splitting, corresponding to the
two approaches just described:
This criterion searches for a pure bucket, regardless of its class, as early as
possible:
crit
which is equivalent to
crit (a)
because min(p 0
(for example) are monotone transformations of
each other. The criteria are also equivalent to
crit (b)
because if one of p 0
L is maximum, the other is minimum. This latter
criterion expresses the idea of pure buckets more directly.
ffl New Criterion 2: One-sided extremes
Having chosen class 1 as the class of interest, the criterion that searches for a
pure class 1 bucket among L and R is
crit
which is identical to
crit
because of p 0
L , for example.
Note that these criteria are direct analogs of the new data mining criteria for re-
gression, as shown in the following table:
Regression Trees Classification Trees
One-sided purity min(-oe 2
One-sided extreme max(-
5 The End-Cut Problem
High variability in small buckets can lead to chance capitalization (Breiman et al.,
p.313 ff), that is, optimization of splits can take advantage of randomly occurring
purity of small buckets. As an implication, splitting methods can lead to extremely
unbalanced splits. This problem is even greater for our data mining criteria because
they look at buckets individually without combining them in a size-weighted average
as in CART. In the usual CART criterion, small buckets with higher variability are
downweighted according to their size.
As an illustration of the end-cut problem, we simulated a simple case of unstructured
regression data, which is the same case that was theoretically examined in
Breiman et al. (1984). Theoretically, all cuts have equal merit, but empirically the
end-cut preference for finite samples emerges for all known figures of merit. Simulation
is necessary because the theoretical consideration for the CART criterion do
not carry over to the new data mining criteria.
We thus generated a set of 200 observations from a Gaussian distribution with
zero mean and unit variance. We computed for each split with buckets of size
- 5 the CART criterion (RSSL
R ) and the new one-sided
purity criterion min(-oe L ; - oe R ). We then computed the optimal split locations for both
criteria. This scheme was repeated 10,000 times, and optimality of each split location
was tallied in a histogram. The first histogram in Figure 8 shows the frequency with
which each split location was minimum under the CART criterion. The second
histogram shows the same for the one-sided purity criterion.
The two figures show the extent to which the criteria prefer cut locations closer
to either extreme. Clearly this effect is more pronounced for the one-sided purity
criterion. While both criteria require measures to counteract this effect, the one-sided
purity criterion does more so.
split location of minimum of total RSS
data mining criterion 1
split location of minimum of purity criterion

Figure

8: Illustration of end-cut problem
An approach to solving the end-cut problem is penalization of buckets for small
size by the criterion with penalty terms so as to make small buckets less viable.
Penalization is best understood if the criterion can be interpreted as negative log
Likelihoods of a suitable model. In this case, the literature offers a large number of
additive penalty terms such as C P (Mallows' C P statistic), AIC (Akaike's information
criterion), BIC (Schwarz' Bayesian information criterion), MDL (the minimum
description length criterion), among others. In the present paper, we work with the
AIC and the BIC criteria, if for no other reasons than their popularity. The AIC
penalty adds the (effective) number of estimated parameters to the negative log
Likelihood, whereas the BIC adds the number of estimated parameters multiplied
by log(N)=2.
Applying these penalties to an individual bucket, we obtain for the constant
Gaussian and multinomial models that underlie regression and classification trees:
Model -log Likelihood AIC BIC
Regression: Gaussian N(log -
Classification: Multinomial N Entropy
At this stage, we have to raise an important point about our intended use of
the AIC and BIC penalties: Conventionally, these penalties are used in a model
selection context, where one applies multiple models to a fixed dataset. In our
unconventional situation, however, we apply one fixed model to multiple datasets,
namely, variable-sized (NR , NL ) buckets of data that are part of a larger dataset.
The ensuing problem is that -log Likelihood is not comparable across different
bucket sizes: -log Likelihood is an unbiased estimate of bucket size times the divergence
of the model with respect to the actual distribution. Therefore, comparability
across bucket sizes is gained if one uses the average -log Likelihood, which is an
unbiased estimate of the divergence across bucket sizes.
log P
Z
log P (x))dQ(x)
[In the rest of this section, N denotes a generic sample size or bucket size in order
to avoid the subscripts of NL and NR .]
As a consequence, a penalized average -log Likelihood has a penalty term that
is also divided by the bucket size:
Model ave -log Likelihood 1
Regression: Gaussian 1log -
Classification: Multinomial Entropy
The penalty terms ( 2
N , log N
N and 1log N
N ) are monotone decreasing for N - 3 and
converge to zero as N !1. These behaviors are obvious requirements for additive
penalties.
The penalized value associated with the BIC is bigger than that associated with
the AIC except small buckets, as illustrated in Figure 9.
Unfortunately, even though this approach produces intuitively pleasing penalties,
their performance in our experiments has been somewhat disappointing. We expect,
however, that the approach will perform better if some recent results by Jianming
Ye (1998) are taken into account. In light of Ye's insights, it is plausible that
in the penalties the number of parameters of the model should be replaced with
Ye's ``generalized degrees of freedom'' (gdf) which take into consideration the fact
that extensive searching implicitly consumes degrees of freedom. Gdfs tend to be
considerably higher than the conventional dfs.
In the examples of the following sections, we counteract the end-cut problem by
imposing a minimum bucket size of roughly 5% of the overall sample size.
6 An Example of Regression Trees: Boston Housing
Data
Following Breiman et al. (1984), we demonstrate the application of the new data
mining criteria on the Boston Housing data. These well-known data were originally
Bucket Size
Penalized
Value
AIC penalty
BIC penalty

Figure

9: The plot of 1
and 1log N
except small size of N
created by Harrison and Rubinfeld (1978), and they were also exploited by Belsley,
Kuh and Welsch (1980) and Quinlan (1993). Harrison and Rubinfeld's main interest
in the data was to investigate how air pollution concentration (NOX) affects the
value of single family homes in the suburbs of Boston. Although NOX turned out
to be a minor factor if any, the data have been frequently used to demonstrate new
regression methods.
The Boston Housing data are available from the UC Irvine Machine Learning
Repository (http://www.ics.uci.edu/~mlearn/MLRepository.html).
The data contain the median housing values as a response, and 13 predictor
variables for 506 census tracts in the Boston area. The predictors are displayed in

Table

1.
6.1 Comparison of Criteria for Regression Trees
We constructed several trees based on both CART and the new data mining cri-
teria. To facilitate comparisons, all trees were generated with equal size, namely,
terminal nodes. A minimum bucket size of 23 was chosen, which is about 5%
of the overall sample size (506). No pruning was applied because our interest was
in interpretation as opposed to prediction. The results are displayed in Figures 10
Variable description
CRIM crime rate
ZN proportion of residential land zoned for lots over 25,000 sq. ft
INDUS proportion of non-retail business acres
CHAS Charles River dummy variable (=1 if tract bounds river; 0 otherwise)
NOX nitric oxides concentration, pphm
RM average number of rooms per dwelling
AGE proportion of owner-occupied units built prior to 1940
DIS weighted distances to five Boston employment centers
RAD index of accessibility to radial highways
TAX full-value property tax rate per $10,000
PTRATIO pupil teacher ratio
is the proportion of blacks
LSTAT percent lower status population
response median value of owner occupied homes in $1000's

Table

1: Predictor Variables for the Boston Housing Data.
through 15 and summarized in Table 2. In the figures, the mean response (m) and
the size (sz) is given for each node.
After perusing the six trees and their summaries in sequence, it is worthwhile
to return to the CART tree of Figure 10 at the beginning, and apply the lessons of
the extreme means trees of the last two Figures, 14 and 15. We recognize from the
CART tree that RM is the dominant variable, in particular for RM ? 7, indicating
a monotone dependence on RM for large values of RM. For RM! 7, LSTAT takes
over. As we learnt from the high means tree, for RM! 7 there exists a monotone
decreasing dependence on LSTAT. The CART tree tries to tell the same story, but
because of its prejudice in favor of balanced splits, it is incapable of successively
layering the data according to ascending values of LSTAT: The split on LSTAT at
the second level divides into buckets of size 51% and 34%, of which only the left
bucket further divides on LSTAT. By comparison, the high means criterion creates
at level 3 a split on LSTAT with buckets of sizes 9% and 77%, clearly indicating
that the left bucket is only the first of a half dozen "tree rings" in ascending order
of LSTAT and descending order of housing price.
In summary, it appears to us that the least interpretable trees are the first two,
corresponding to the CART criterion and the separate-variances criterion, although
0:8 is the highest among the six trees. Greater interpretability is gained
with the one-sided purity criterion, partly due to the fact that it successively peels off
many small buckets, resulting in a less balanced yet more telling tree. The greatest
|
LSTAT<5.36
B<380.4
CRIM<7.48
5.7%
8.9%
m=21,
4.7%
m=24,
8.7%
6.7%
4.9%
6.5%
m=21,
4.7%
4.5%
m=17,
8.7%
m=15,
7.1%
5.5%
8.1%
m=35,
4.5%
4.5%
m=45,
5.9%
m=23,
sz=100.0%
85.0%
m=23,
51.0%
m=25,
28.1% m=24,
13.4%
m=21,
m=15,
34.0%
m=17,
20.4% m=16,
15.8%
13.6%
m=37,
15.0%
9.1%
Boston
Housing
pooled
variance
model
(CART)
Figure

10: The Boston Housing Data, Tree 1, CART Criterion.
|
DIS<3.36
RM<7.06
AGE<93.2
4.7% m=22.0,
10.5% m=26.0,
8.5%
5.7% m=34.0,
4.5%
6.1% m=23.0,
8.1% m=20.0,
5.7% m=21.0,
7.1%
5.9% m=20.0,
5.5% m=17.0,
4.5%
8.1% m=14.0,
5.1% m=12.0,
4.9% m=
9.9,
4.7%
sz=100.0%
40.1%
34.0%
19.0%
10.3%
59.9%
26.9% m=20.0,
13.0%
33.0%
10.1%
14.8% m=11.0,
9.7%
Boston
Housing
separate
variance
model
Figure

11: The Boston Housing Data, Tree 2, Separate Variance Criterion.
AGE<22.1
5.1%
m=27,
14.6%
5.3%
m=34,
4.5%
m=46,
5.3%
6.1%
5.1%
6.1%
5.5%
m=11,
5.3%
4.7%
6.7%
4.7%
7.1%
4.5%
m=17,
8.9%
m=23,
sz=100.0%
m=23,
91.1%
m=24,
86.6%
m=25,
74.7%
41.1%
m=31,
m=28,
29.6%
m=27,
20.0%
28.5%
m=18,
m=17,
15.6%
m=15,
10.9%
m=16,
Boston
Housing
raw
one-sided
purity
Figure

12: The Boston Housing Data, Tree 3, One-Sided Purity Criterion.
m=24,
6.5%
7.9%
m=23,
6.1%
5.5%
m=35,
4.9%
m=28,
4.9%
m=46,
5.1%
m=21,
6.7%
8.9%
4.9%
8.5%
m=11,
4.5%
4.7%
7.1%
4.5%
m=17,
8.9%
m=23,
sz=100.0%
m=23,
91.1%
m=24,
86.6%
m=25,
74.7%
41.1%
m=24,
20.6%
m=25,
14.4%
m=35,
20.6%
15.4% m=32,
9.9%
m=18,
26.9%
13.8%
m=16,
13.0%
m=16,
Boston
Housing
data:
penalized
one-sided
purity
Figure

13: The Boston Housing Data, Tree 4, Penalized One-Sided Purity Criterion.
|
LSTAT<6.22
m=36,
4.7%
m=27,
8.7%
m=25,
7.9%
4.7%
m=21,
5.7%
5.9%
m=21,
5.3%
m=21,
5.5%
8.5%
m=18,
5.1%
m=18,
5.7%
m=15,
4.7%
m=16,
4.5%
m=11,
13.0%
m=33,
4.5%
m=45,
5.1%
m=23,
sz=100.0%
m=21,
94.9%
m=21,
90.1%
85.6%
76.9%
m=18,
69.0%
m=24,
10.5%
m=17,
58.5%
m=17,
52.6% m=16,
m=16,
41.7% m=15,
28.1% m=13,
Boston
Housing
one-sided
extremes
(high
Figure

14: The Boston Housing Data, Tree 5, High Means Criterion.
|
LSTAT<14.1
PTRATIO<20.2
m=13,
4.7%
m=23,
6.3%
m=25,
5.7%
m=24,
4.7%
4.9%
5.9%
m=34,
4.7%
m=41,
8.9%
7.3%
m=21,
8.7%
5.3%
6.7%
m=17,
7.7%
m=15,
8.5%
4.5%
5.1%
m=23,
sz=100.0%
m=23,
94.9%
m=24,
90.1%
m=24,
85.6%
m=25,
77.1%
69.4%
m=27,
62.6%
m=27,
57.3%
48.6%
41.3%
m=31,
m=24,
10.5%
m=34,
19.6% m=39,
13.6%
Boston
Housing
one-sided
extremes
(low
Figure

15: The Boston Housing Data, Tree 6, Low Means Criterion.
R CART: pooled variance model
Somewhat balanced tree of depth 6. The major variables are
RM (3x) and LSTAT (6x). Minor variables appearing once each
are NOX, CRIM, B, PTRATIO, DIS, INDUS, with splits mostly
in the expected directions. Means in the terminal nodes vary from
45.10 to 10.20.
Tree 2 NL log -
R separate variance model
More balanced tree than the CART tree, of depth 5. The major
variables are again RM (4x) and LSTAT (3x). Minor variables are
doesn't appear. The splits are in the expected directions. Means in
the terminal nodes vary from 45.10 to 9.94.
Tree 3 min(-oe 2
R ) Data Mining criterion 1: raw one-sided
purity
Unbalanced tree of depth 9. PTRATIO (1x) appears at the top
but cannot be judged of top importance because it splits off a
small bucket of only size 9%. Apparently a cluster of school districts
has significantly worse pupil-to-teacher ratios than the ma-
jority. Crime-infested neighborhoods are peeled off next in a small
bucket of size 5% (CRIM, 1x). NOX makes surprisingly 3 appear-
ances, which would have made Harrison and Rubinfeld happy. In
the third split from the top, NOX breaks off 12% of highly polluted
areas with a low bucket mean of 16, as compared to 25 for the rest.
The most powerful variable is LSTAT (3x), which creates next a
powerful split into buckets of size 41% and 34%, with means of
and 19, respectively. Noticeable is the ambiguous role of DIS (3x),
which correlates negatively with housing values for low values of
LSTAT (! 10:15, "high-status"), but positively for high values of
LSTAT ("low-status") and high values of NOX (? 0:52, "polluted").
RM (2x) plays a role only in "high-status" neighborhoods. "Crime-
neighborhoods are peeled off early on as singular areas with
extremely low housing values (CRIM, 1x). The splits on AGE (1x)
and ZN (1x) are irrelevant due to low mean-differences.
log - oe 2
Data Mining criterion 2: penalized one-sided
purity (AIC)
Qualitatively, this tree is surprisingly similar to the previous one,
with some differences in the lower levels of the tree. Penalization
does not seem to affect the splits till further down in the tree.
Mining criterion 3: One-sided ex-
tremes: high mean
The search of high response values creates a very unbalanced tree.
There are no single powerful splits, only peeling splits with small
buckets on one side. The repeated appearance of just two variables,
RM (2x, levels 1 and 3) and LSTAT (8x), however, tells a powerful
story: For highest housing prices (bucket mean 45), average size of
homes as measured by RM (? 7:59) is the only variable that mat-
ters. For RM ! 7:08, a persistent monotone decreasing dependence
on LSTAT takes over, down to a median housing value of about 17.
This simple interplay between RM and LSTAT lends striking interpretability
to the tree and tells a simple but convincing story. At
the bottom, crime (CRIM, 2x) and pollution (NOX, 1x) show some
remaining smaller effects in the expected directions. Smaller effects
of DIS and TAX are also seen half-way down the tree.
-R ) Data Mining criterion 4: One-sided ex-
tremes: low mean
This tree tells a similar story as the previous one, but greater precision
is achieved for low housing values, because this is where the
criterion looks first. Again the tree is very unbalanced. The first
peeling split is on CRIM (1x) which sets aside a 5% bucket of crime-
infested neighborhoods with lowest housing values around 10. The
second lowest mean bucket consists of 5% census tracts with low B
(! 100), corresponding to 63%\Sigma32% of African-American popula-
tion, due to the quadratic transformation. Thereafter, monotone
decreasing dependence on LSTAT takes over in the form of six peeling
splits, followed by monotone increasing dependence on RM in
the form of five peeling splits. These two successive dose response
effects are essentially the same as in the previous tree, which found
them in reverse order due to peeling from high to low housing values.

Table

2: The result of regression trees in Boston Housing Data.
interpretability is achieved for the one-sided extreme means criteria, partly due to
their extreme imbalance.
Interpretability, as we found it in the above examples, has two sides to it:
ffl Buckets with extremely high or low means near the top of the trees: Such buckets
are desirable for interpretation because they describe extreme response behavior
in terms of simple clauses. Finding such buckets is exactly the purpose
of the extreme means criteria.
In the Boston Housing Data, the high-mean criterion, for example, immediately
finds a bucket of well-off areas with very large homes: RM? 7:59. The
low-mean criterion, by comparison, immediately finds a high-crime bucket:
CRIM? 15:79. While CART also finds the areas with large homes at the
second level, it does not find the high crime bucket at all.
ffl Dose response effects or monotone dependencies: The iterative peeling behavior
of the data mining criteria allows detection of gradual increases or decreases
in the response as a function of individual predictors. For iterative peeling on
a predictor to become apparent, it is essential that the peeling layers form a
series of small dangling terminal buckets and hence form highly unbalanced
trees. CART, by comparison, is handicapped in this regard because of it favors
balanced splits more than the data mining criteria.
The last point is ironic because it implies that the greater end-cut problem of the
data mining criteria compared to CART works in our favor. Conversely, CART's
end-cut problem is not sufficiently strong to allow it to clearly detect monotone
dependencies with highly unbalanced trees.
Once monotone dependencies are detected, it is plausible to switch from tree
modeling to additive or even linear modeling that include suitable interaction terms.
Interaction terms may be necessary to localize monotone dependence. For example,
the above tree generated with the low means criterion might suggest a linear model
of the following form:
6.2 Graphical Diagnostics for Regression Trees
Although tree-based methods are in some sense more flexible than many conventional
parametric methods, it is still necessary to guard against artifacts. The best
techniques for diagnosing artifacts and missfit are graphical. In contrast to linear
regression, basic diagnostics for regression trees can be straightforward because
they do not require additional computations. In a first cut, it may be sufficient to
graphically render the effect of each split in turn. This may be achieved by plotting
the response variable against the predictor of the split for the points in the parent
bucket. One should then graphically differentiate the points in the two child buckets
by plotting them with different glyphs or colors.
We created a series of such diagnostic plots for the tree generated with the low
mean criterion. Figure 16 shows how buckets with ascending housing values are
being split off:
ffl high crime areas,
strongly African-American neighborhoods,
ffl a segment with decreasing fraction of lower status people,
ffl communities with unfavorable pupil-teacher ratios in their schools,
ffl another segment with decreasing fraction of lower status people, and finally
ffl the segment in which increasing size of the homes matters.
These plots confirm that most of these splits are plausible: High crime is the factor
that depresses housing values the most; there does exist a cluster of neighborhoods
whose pupil-teacher ratio is clearly worse and well separated from the majority.
Finally, the monotone dependencies are clearly visible for decreasing percentage of
lower status people and increasing number of rooms. Also visible are some "outliers,"
namely, the desirable areas of Beacon Hill and Back Bay near Boston downtown,
with top housing values yet limited size of homes.
14

Figure

Graphical view of the major splits applied to the Boston Housing data,
using the low means criterion.
7 An Example of Classification Trees: Pima Indians
Diabetes
We demonstrate the application of the new data mining criteria for classification
trees with the Pima Indians Diabetes data (Pima data, for short). These data
were originally owned by the "National Institute of Diabetes and Digestive and
Kidney Diseases," but they are now available from the UC Irvine Machine Learning
Repository (http://www.ics.uci.edu/~mlearn/MLRepository.html).
The class labels of the Pima data are 1 for diabetes and 0 otherwise. There
are 8 predictor variables for 768 patients, all females, at least 21 years of age, and
of Pima Indian heritage near Phoenix, AZ. Among the 768 patients, 268 tested
positive for diabetes (class 1). For details about the data, see the documentation at
the UC Irvine Repository. The predictor variables and their definitions are shown
in

Table

3.
Variable description
PRGN number of times pregnant
PLASMA plasma glucose concentration at two hours in an oral
glucose tolerance test
BP diastolic blood pressure (mm Hg)
THICK Triceps skin fold thickness (mm)
INSULIN two hour serum insulin (- U/ml)
BODY body mass index (weight in kg=(height in m) 2 )
diabetes pedigree function
AGE age (years)
RESPONSE class variable (=1 if diabetes; 0 otherwise)

Table

3: Predictor Variables for the Pima Indians Diabetes Data.
Using the Pima data, we constructed four trees based on both CART and our
new data mining criteria. A minimum bucket size of 35 was imposed, which is
about 5% of the overall sample size (768), as for the regression trees of the Boston
Housing data. Since we are concerned with interpretability, we again did not use
pruning. The resulting trees are shown in Figures 20 through 23. For each node, the
proportion (p) of each class and the size (sz) are given. Tables 4 and 5 summarizes
the trees.
From the trees and the summary, it becomes clear that PLASMA is the most
powerful predictor, followed by BODY. In particular the third tree is almost completely
dominated by these two variables. Their interleaved appearance down this
tree suggests a combined monotone dependence which should be studied more care-
0: No Diabetes
50 100 150 200305070
PLASMA
Class 1: Diabetes

Figure

17: The Distribution of the Two Classes of the Pima Diabetes Data, BODY
against PLASMA.
fully.

Figure

17 shows the distribution of the two classes in the PLASMA-BODY
plane. We switched to another fitting method that is more natural for describing
monotone dependencies, namely, nearest-neighbor fitting. For every point we estimated
the conditional class 1 probability p 1 (PLASMA, BODY) by the fraction of
class 1 samples among the 20 nearest neighbors in terms of Euclidean distance in
PLASMA-BODY coordinates after standardizing both variables to unit variance.

Figure

shows a sequence of plots of the data in the (PLASMA, BODY) plane
and a rendition of p 1 (PLASMA, BODY) in terms of highlighted slices
for an increasing sequence of six values of c. The plots make it clear that the response
behavior is quite complex: The first plot shows a slice that is best described as a
cut on a low value of BODY. The following four slices veer 90 clockwise, and the
last slice is best described as a cut on a high value of PLASMA. There is one more
feature worth of note, though: In the third plot we notice a hole in the center of the
highlighted slice. This hole is being filled in by a blob of data in the fourth plot.
From this feature we infer the existence of a mild hump in the p 1 -surface in the
center of the data. In summary, the function p 1 (PLASMA, BODY) has the shape
of a clockwise ascending spiral rule surface with a hump in the middle.
Obviously, trees are quite suboptimal for fitting a response with these charac-
teristics. Figure 19 shows how the third tree in Figure 22 tries to approximate this
surface with a step function on axes-aligned rectangular tiles.
PLASMA PLASMA

Figure

18: The Pima Indian Diabetes Data, BODY against PLASMA. The highlights
represent slices with near-constant p 1 ffl). The values of p 1 in the
slices increase left to right and top to bottom. Open squares: no diabetes (class 0),
A

Figure

19: The Pima Diabetes Data, BODY against PLASMA. The plain is tiled
according to the buckets of the tree in Figure 22. Open squares: no diabetes (class 0),
AGE<28
PLASMA<105.1
PEDIGREE<0.26
INSULIN<00000101p=1.00:0.00,
13.2% p=0.93:0.07,
7.0% p=0.82:0.18,
4.9% p=0.92:0.08,
4.9%
p=0.73:0.27,
6.6%
p=0.93:0.07,
6.0% p=0.87:0.13,
5.1% p=0.70:0.30,
4.8%
p=0.53:0.47,
6.6%
p=0.36:0.64,
7.2%
p=0.67:0.33,
8.6% p=0.53:0.47,
5.9% p=0.28:0.72,
7.9% p=0.08:0.92,
4.8% p=0.16:0.84,
6.4%
p=0.65:0.35,
sz=100.0%
p=0.79:0.21,
36.7%
p=0.97:0.03,
20.2%
16.5%
p=0.87:0.13,
9.9%
p=0.66:0.34,
29.7%
p=0.59:0.41,
p=0.69:0.31,
16.5%
p=0.79:0.21,
9.9%
p=0.37:0.63,
p=0.27:0.73,
p=0.39:0.61,
13.8%
p=0.13:0.87,
Pima
misclass.
error

Figure

20: The Pima Indian Diabetes Data, Tree 1, CART Criterion.
PLASMA<99.3
BODY<25.2
PLASMA<166.2
PEDIGREE<0.2
AGE<28
p=0.95:0.05,
5.6% p=1.00:0.00,
4.9% p=0.84:0.16,
4.9% p=0.91:0.09,
4.6% p=0.89:0.11,
8.1% p=0.86:0.14,
7.7% p=0.92:0.08,
5.1% p=0.72:0.28,
7.4% p=0.71:0.29,
6.4% p=0.71:0.29,
4.9% p=0.46:0.54,
14.6%
p=0.76:0.24,
4.8%
p=0.28:0.72,
6.1%
p=0.25:0.75,
5.2%
p=0.19:0.81,
4.8% p=0.08:0.92,
4.8%
p=0.65:0.35,
sz=100.0%
p=0.63:0.37,
94.4%
p=0.92:0.08,
9.9%
84.5%
p=0.58:0.42,
79.9%
p=0.55:0.45,
71.9%
64.2%
p=0.58:0.42,
54.6%
p=0.80:0.20,
12.5%
42.1%
p=0.47:0.53,
30.5%
p=0.57:0.43,
p=0.52:0.48,
19.5%
p=0.14:0.86,
9.6%
Pima
one-sided
purity
misclass.
error

Figure

21: The Pima Indian Diabetes Data, Tree 2, One-Sided Purity.
PLASMA<99.3
BODY<25.2
THICK<28
|
PLASMA<122
THICK<34.1
THICK<28
Typical balanced tree of depth 6. The strongest variable is PLASMA
(5x), which creates a very successful split at the top. BODY (3x)
is the next important variable, but much less so, followed by PEDIGREE
(3x) and AGE (2x). The class ratios in the terminal buckets
range from 1.00:0.00 on the left to 0.16:0.84 on the right. All splits
are in the right direction. Overall, the tree is plausible but does not
have a simple interpretation.
R ) Data Mining criterion 1: one-sided pu-
rity
Extremely unbalanced tree of depth 12. In spite of the depth of the
tree, its overall structure is simple: As the tree moves to the right,
layers high in class 0 (no diabetes) are being shaved off, and, con-
versely, as the tree steps left, a layers high in class 1 (diabetes)
is shaved off. The top of the tree is dominated by BODY and
while AGE and PEDIGREE play a role in the lower parts
of the tree, where the large rest bucket gets harder and harder to
classify.
Tree 3 max(p 0
R ) Data Mining criterion 2: one-sided ex-
tremes, high class 0
Extremely unbalanced tree with simple structure: Because the criterion
searches for layers high in class 0 (no diabetes), the tree keeps
stepping to the right. In order to describe conditions under which
class 0 is prevalent, it appears that only BODY and PLASMA mat-
ter. The tree shows a sequence of interleaved splits on these two
variables, indicating a combined monotone dependence on them. See
below for an investigation of this behavior. For interpretability, this
tree is the most successful one.

Table

4: The Result of Classification Trees in the Pima Indians Diabetes Data.
Tree 4 max(p 1
R ) Data Mining criterion 2: one-sided ex-
tremes, high class 1
Another extremely unbalanced tree with simple structure: The criterion
searches for layers high in class 1 (diabetes), which causes the
tree to step to the left. In order to describe conditions under which
class 1 is prevalent, PLASMA (6x) matters by far the most, followed
by PRGN (2x).

Table

5: The Result of Classification Trees in Pima Indians Diabetes Data.

Summary

The following are a few messages from our investigations and experiments:
ffl If trees are grown for interpretation, global measures of goodness of fit are not
always desirable.
ffl Hyper-greedy data mining criteria can give very different insights.
ffl Highly unbalanced trees can reveal monotone dependence and dose-response
effects. The end-cut problem turns into a virtue.
ffl To really understand data & algorithms, extensive visualization is necessary.
The following are a few topics that would merit further research:
Assess when the end-cut "problem" hurts and when it helps.
ffl Extend the new 2-class criteria to the multiclass problem.
ffl Develop more sophisticated rules for stopping and pruning.
ffl Increase accuracy with a limited 2-step look-ahead procedure for the new cri-
teria, adopting a suggestion of Breiman's (1996).



--R

"A New Look at the Statistical Model
Regression Diagnostics
"Technical Note: Some Properties of Splitting Criteria,"
Classification and Regression Trees
"Tree-Based Models,"
"A Statistical Perspective on Knowledge Discovery in Databases,"
"From Data Mining to Knowledge Discovery: An Overview,"
"Model Selection and the Principle of Minimum Description Length,"
"Hedonic Prices and the Demand for Clean Air,"
Clustering Algorithms
"Some Comments on C p ,"
UCI repository of machine learning data bases (http://www.
"Problems in the Analysis of Survey Data, and a Proposal,"

"Estimating the Dimension of a Model,"

CART: A Supplementary Module for SYS- TAT
"XGobi: Interactive Data Visualization in the X Window System,"
Modern Applied Statistics with S-Plus
"On Measuring and Correcting the Effects of Data Mining and Model Selection,"
--TR
C4.5: programs for machine learning
Technical note
A simple, fast, and effective rule learner

--CTR
Xiaoming Huo , Seoung Bum Kim , Kwok-Leung Tsui , Shuchun Wang, FBP: A Frontier-Based Tree-Pruning Algorithm, INFORMS Journal on Computing, v.18 n.4, p.494-505, January 2006
Soon Tee Teoh , Kwan-Liu Ma, PaintingClass: interactive construction, visualization and exploration of decision trees, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Owen Carmichael , Martial Hebert, Shape-Based Recognition of Wiry Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.12, p.1537-1552, December 2004
Vasilis Aggelis , Panagiotis Anagnostou, e-banking prediction using data mining methods, Proceedings of the 4th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering Data Bases, p.1-6, February 13-15, 2005, Salzburg, Austria
CART;boston housing data;splitting criteria;Pima Indians Diabetes data