Choosing a split
Section of Classification trees, part of Statistical learning
Choosing a split
| Type | Section |
| Taught in | Classification trees |
| Part | Statistical learning |
The value of \Delta I(m) depends on which cases go left. The split is a variable j_m and a threshold on that variable. If predictor j is continuous, the threshold is a number \lambda_m, and x goes left when x_{j_m}<\lambda_m. A discrete or ordinal predictor uses the same rule with \lambda_m restricted to the observed values, from the second through the last. A binary predictor sends x_{j_m}=0 left and x_{j_m}=1 right. A nominal predictor has no order to cut. One candidate is to peel off a single category and leave the rest together. Another is to search subsets of categories, which is feasible when the number of subsets is moderate, say 100 or fewer. Both are still binary questions.
The tree’s readability comes from refusing to cut on a linear combination of coordinates, which is exactly the cut that linear discriminant analysis and logistic regression are willing to make. A diagonal boundary has to be approximated by a staircase of axis-aligned cuts.
When the variable is discrete or categorical, every legal split can be scored and the best kept. For a continuous variable there is no analytic maximiser of \Delta I(m), because the class distributions are not known. The criterion is an average over the cases at the node, not an integral against a class density. The search runs through the ordered observed values, from the second smallest to the largest, and places the cut between a value and the one before it. Any cut strictly between two consecutive training values a<b sends the same training cases left and right, so it has the same estimated impurity. The training criterion does not say where in (a,b) the cut should sit. The midpoint is a convention for extending that partition to future observations. The training impurity does not identify a special threshold within the gap. Report the fitted cutoff as part of a predictive rule, with this finite resolution in mind.
Invariance to a change of units
Main article: Invariance to a change of units
Nearest neighbours changed their minds when a coordinate was rescaled, because Euclidean distance mixes the units. A tree never mixes units inside a split. Replacing predictor j by ax_j+b with a\ne 0 transforms every candidate cut on that variable and leaves \Delta I unchanged, so the sequence of variables and the order of splits stay the same. If a>0, the observations with x_j<\lambda are exactly the observations with ax_j+b<a\lambda+b. Every split partitions the data identically and has the same child compositions, hence the same \Delta I, at the transformed cut. If a<0, the left and right children swap. The reduction is symmetric in the two children, because replacing \hat p_L by 1-\hat p_L exchanges the two weighted terms, so \Delta I is unchanged. After the transformation the published cut-points transform with the data. The predictors do not need to be standardised before the fit.
A rotation is a different matter. The tree can cut only on coordinate axes, and a rotation moves those axes. A split on a single coordinate after rotation is a split on a linear combination before the rotation, which an axis-aligned tree cannot reproduce. The invariance is to strictly monotone affine changes of single coordinates, not to linear combinations. Training partitions are preserved by those coordinate transformations, up to ties and equivalent cuts. Predictions between observed values can differ when a nonlinear transformation changes the midpoint convention.
Multi-way splits and missing values
Main article: Multi-way splits and missing values
Allowing more children can reduce weighted impurity simply by refining the partition. The improvement need not be strict. A comparison across different numbers of children therefore needs a complexity adjustment. The gain ratio divides the impurity reduction by the entropy of the split allocation:
\Delta I(m) =\frac{I(m)-\sum_{k=1}^K \hat p_{km}\,I(m_k)} {-\sum_{k=1}^K \hat p_{km}\log\hat p_{km}}.
Here \hat p_{km} is the proportion sent to child k. The denominator is the entropy of the allocation, and it is positive for a nontrivial split. Dividing by it adjusts for the split’s allocation pattern, and it can also favour highly unbalanced splits with a small denominator. It is not a universal correction for selection bias, and it is not a guarantee of balanced children.
Missing-value handling is part of the algorithm and differs between implementations. CART can use surrogate splits: questions on other observed variables chosen to mimic the primary split’s left/right allocation. Sending a case to the majority branch is a fallback, not the definition of a surrogate. In rpart the choices are controlled by usesurrogate and maxsurrogate. State the settings when they affect predictions.
Example 1 (Building a tree in one dimension) Question. Two classes, five observations of a single variable: class 1 has x=1 and 6; class 2 has x=2, 5, and 11. What tree is built using cross-entropy?
Solution. The root node has proportions (2/5,3/5), so it would be labelled class 2 if the tree stopped. With the natural logarithm,
\begin{align*} I_C(\mathrm{root}) &=-\Bigl(\tfrac25\log\tfrac25+\tfrac35\log\tfrac35\Bigr)\\ &=0.3665+0.3065=0.673. \end{align*}
The ordered observations are 1,2,5,6,11, with classes 1,2,2,1,2, so there are n-1=4 candidate splits. The cut is taken at the midpoint, and \hat p_L is the fraction of the five observations on the left. The notation a:b is the number of class-1 and class-2 observations in a child.
| split | cut | \hat p_L | left | I_C(m_L) | right | I_C(m_R) | \Delta I |
|---|---|---|---|---|---|---|---|
| 1\mid 2,5,6,11 | 1.5 | 0.2 | \{1\} pure | 0 | 1:3 | 0.562 | 0.223 |
| 1,2\mid 5,6,11 | 3.5 | 0.4 | 1:1 | 0.693 | 1:2 | 0.637 | 0.014 |
| 1,2,5\mid 6,11 | 5.5 | 0.6 | 1:2 | 0.637 | 1:1 | 0.693 | 0.014 |
| 1,2,5,6\mid 11 | 8.5 | 0.8 | 2:2 | 0.693 | \{11\} pure | 0 | 0.118 |
The first split has
\Delta I=0.673-0.2\times 0-0.8\times 0.562=0.223,
the largest. The right-hand entropy 0.562 is -\bigl((1/4)\log(1/4)+(3/4)\log(3/4)\bigr). The balanced child has entropy \log 2=0.693, and a 1:2 child has entropy 0.637.
The left child \{1\} is pure, hence a leaf of class 1. Repeat on the right node \{2,5,6,11\}, with classes 2,2,1,2 and impurity 0.562. Cutting at 3.5 gives
\Delta I=0.562-0.25(0)-0.75(0.637)=0.085.
Cutting at 5.5 gives \Delta I=0.562-0.5(0)-0.5(0.693)=0.216. Cutting at 8.5 gives 0.085. The next split is at 5.5, producing the pure leaf \{2,5\} of class 2 and the node \{6,11\}. That node contains one observation of each class and is split at 8.5 into two pure leaves.
The tree is: if x<1.5, predict class 1 (the point 1); otherwise if x<5.5, predict class 2 (the points 2 and 5); otherwise if x<8.5, predict class 1 (the point 6); otherwise predict class 2 (the point 11). It classifies all five training observations correctly, with four leaves for five points.
With the Gini index the same first split wins. The root Gini index is 2(2/5)(3/5)=0.48. The four reductions are 0.180, 0.013, 0.013, and 0.080. The first of these is 0.48-0.8\times 2(1/4)(3/4)=0.48-0.30=0.180.
Used in
See also
Node impurity · Building a classification tree · Invariance to a change of units · Multi-way splits and missing values · Tree size and pruning · What a fitted tree can be trusted to mean · Laboratory: prune using training cross-validation · Decision tree