Multi-way splits and missing values
Section of Classification trees, part of Statistical learning
Multi-way splits and missing values
| Type | Section |
| Taught in | Classification trees |
| Part | Statistical learning |
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 · Choosing a split · Invariance to a change of units · Tree size and pruning · What a fitted tree can be trusted to mean · Laboratory: prune using training cross-validation · Decision tree