A classification tree predicts a category: malignant or benign, which cultivar a wine comes from, whether a launch will damage a seal. It is built exactly like a regression tree, by recursive binary splitting followed by pruning, and drawn the same way (see Introduction to Decision Trees). Two things change. A leaf predicts the most common class among its training cases rather than their mean, and it reports the class proportions as estimated probabilities. And the quality of a split can no longer be measured by the residual sum of squares, because the outcome is not a number. This article derives the measures that take its place, works them by hand on a small dataset, and applies them to a three-class problem.
Impurity
A node is pure if all its training cases belong to one class; it then predicts that class with no training error and with complete confidence. A node with classes evenly mixed is maximally impure. Write $\hat{p}_{mk}$ for the proportion of the training cases in node $m$ that belong to class $k$, for $k = 1, \dots, K$. An impurity measure is a function $i(\hat{p}_{m1}, \dots, \hat{p}_{mK})$ that is zero for a pure node and largest when the classes are equally represented. A split is chosen to make the children as pure as possible, measured by the impurity of the two children weighted by their sizes:
$$\frac{n_L}{n}\, i(\text{left}) + \frac{n_R}{n}\, i(\text{right}),$$
where $n$ is the number of cases in the node being split and $n_L$, $n_R$ the numbers sent left and right. The weights matter. Without them a split that isolated one case into a pure child would look excellent however mixed the other child remained. Three impurity measures are in common use (James, Witten, Hastie and Tibshirani, 2021, §8.1.2).
The misclassification rate is the fraction of the node's training cases that do not belong to its majority class,
$$E_m = 1 - \max_k \hat{p}_{mk}$$
(James et al., 2021, eq. 8.5). It is the training error the node would make on its own cases, and its weighted average over the leaves of a tree is the tree's training error rate.
The Gini index is
$$G_m = \sum_{k=1}^{K} \hat{p}_{mk}\bigl(1 - \hat{p}_{mk}\bigr) = 1 - \sum_{k=1}^{K} \hat{p}_{mk}^2$$
(James et al., 2021, eq. 8.6); the two forms agree because the proportions sum to 1. It is the impurity measure associated with CART (Breiman, Friedman, Olshen and Stone, 1984) and the default in scikit-learn.
The entropy is
$$D_m = -\sum_{k=1}^{K} \hat{p}_{mk} \log \hat{p}_{mk}$$
(James et al., 2021, eq. 8.7), with $0 \log 0$ taken as 0. With logarithms to base 2 it is measured in bits. The reduction in entropy produced by a split is the information gain, the criterion of Quinlan's ID3 (1986) and the same quantity that ranks terms in text feature selection. ID3, in its notation, chooses the attribute that maximizes $\text{gain}(A) = I(p, n) - E(A)$, the entropy before the split minus the expected entropy after it. Entropy is sometimes loosely called information gain or cross-entropy; strictly, the gain is a difference of entropies, and cross-entropy compares two distributions (see Logistic Regression).
For two classes with proportions $p$ and $1 - p$, the three measures are $\min(p, 1-p)$, $2p(1-p)$ and $-p \log_2 p - (1-p)\log_2(1-p)$. All three peak at $p = 0.5$, at 0.5, 0.5 and 1 bit respectively.
Three ways to read the Gini index
The Gini formula looks arbitrary until it is read in one of three equivalent ways. Hastie, Tibshirani and Friedman (2009, §9.2.3) give the second and third.
Two random draws. Draw two cases from the node at random, with replacement. They have the same class with probability $\sum_k \hat{p}_{mk}^2$, so they differ with probability $1 - \sum_k \hat{p}_{mk}^2 = G_m$. The Gini index is the chance that two random members of the node disagree.
A randomized classifier. Suppose that, instead of predicting the majority class, the node labels each case by drawing a class at random with probabilities $\hat{p}_{mk}$. A case of class $k$, which occurs with probability $\hat{p}_{mk}$, is then mislabeled with probability $1 - \hat{p}_{mk}$, so the expected error rate is $\sum_k \hat{p}_{mk}(1 - \hat{p}_{mk}) = G_m$.
The variance of class indicators. Code class membership as $K$ indicator variables, $z_{ik} = 1$ if case $i$ is in class $k$ and 0 otherwise. Within node $m$ the mean of $z_{ik}$ is $\hat{p}_{mk}$, and the sum of its squared deviations from that mean is $n_m \hat{p}_{mk}(1 - \hat{p}_{mk})$, the variance of a 0/1 variable times the count. Adding over classes,
$$n_m G_m = \sum_{k=1}^{K} \sum_{i \in m} \bigl(z_{ik} - \hat{p}_{mk}\bigr)^2.$$
So the weighted Gini index of a split, multiplied by $n$, is exactly the total residual sum of squares of the $K$ indicator variables, each predicted by its mean on its own side of the split. A classification tree grown with the Gini index is a regression tree for the one-hot class indicators, and everything derived for the RSS criterion in Regression Trees carries over. James et al. (2021, §8.1.2) describe the Gini index as "a measure of total variance across the K classes", and the indicator form shows the sense in which that is exact.
The largest possible value follows from any of these readings. For fixed $K$, $\sum_k \hat{p}_{mk}^2$ is smallest when all proportions are equal (by the Cauchy-Schwarz inequality, $\sum_k \hat{p}_{mk}^2 \ge (\sum_k \hat{p}_{mk})^2 / K = 1/K$), so $G_m \le 1 - 1/K$: 0.5 for two classes, 0.667 for three. The bound 0.5 often quoted for the Gini index is the two-class case.
Entropy and the likelihood
Entropy has its own interpretation as the average number of bits needed to record the class of a case drawn from the node, using the best code for the node's class distribution; it reaches its maximum, $\log_2 K$ bits, when the classes are equally likely. A more useful reading for modeling connects it to the likelihood. A tree that predicts class probabilities $\hat{p}_{mk}$ in leaf $m$ assigns each training case of class $k$ in that leaf the probability $\hat{p}_{mk}$. The log-likelihood of the node's cases is then $\sum_k n_{mk} \log \hat{p}_{mk}$, where $n_{mk}$ is the number of class-$k$ cases, and with the proportions estimated from the node itself, $n_{mk} = n_m \hat{p}_{mk}$, this is
$$\sum_{k} n_m \hat{p}_{mk} \log \hat{p}_{mk} = -\,n_m D_m$$
with natural logarithms. Minimizing the weighted entropy of a split therefore maximizes the likelihood of a model that gives each leaf its own class probabilities, the same principle that fits logistic regression. The negative log-likelihood per case is the log loss or cross-entropy that logistic regression minimizes, here evaluated with each leaf's own proportions as the predictions.
The Challenger flights by hand
The 23 space shuttle flights before the Challenger accident, used in Logistic Regression (Draper, 1993), are small enough to split by hand. Seven flights showed thermal distress in at least one of the six field-joint O-rings and 16 did not. At the root,
- misclassification: $7/23 = 0.3043$,
- Gini: $1 - (7/23)^2 - (16/23)^2 = 2 \times 7 \times 16 / 23^2 = 0.4234$,
- entropy: $-\tfrac{7}{23}\log_2\tfrac{7}{23} - \tfrac{16}{23}\log_2\tfrac{16}{23} = 0.8865$ bits.
Launch temperature takes 16 distinct values, so there are 15 thresholds to try. For each, the table gives the flights on each side as (no distress, distress) and the weighted impurity of the split.
| Temperature ≤ | Left | Right | Error | Gini | Entropy |
|---|---|---|---|---|---|
| 55.0 | (0, 1) | (16, 6) | 0.2609 | 0.3794 | 0.8086 |
| 57.5 | (0, 2) | (16, 5) | 0.2174 | 0.3313 | 0.7230 |
| 60.5 | (0, 3) | (16, 4) | 0.1739 | 0.2783 | 0.6278 |
| 64.5 | (0, 4) | (16, 3) | 0.1304 | 0.2197 | 0.5198 |
| 66.5 | (1, 4) | (15, 3) | 0.1739 | 0.2870 | 0.6657 |
| 67.5 | (4, 4) | (12, 3) | 0.3043 | 0.3826 | 0.8186 |
| 68.5 | (5, 4) | (11, 3) | 0.3043 | 0.3982 | 0.8441 |
| 69.5 | (6, 4) | (10, 3) | 0.3043 | 0.4094 | 0.8627 |
| 71.0 | (8, 6) | (8, 1) | 0.3043 | 0.3754 | 0.7966 |
| 72.5 | (9, 6) | (7, 1) | 0.3043 | 0.3891 | 0.8223 |
| 74.0 | (10, 6) | (6, 1) | 0.3043 | 0.4006 | 0.8440 |
| 75.5 | (11, 7) | (5, 0) | 0.3043 | 0.3720 | 0.7545 |
| 77.0 | (13, 7) | (3, 0) | 0.3043 | 0.3957 | 0.8122 |
| 78.5 | (14, 7) | (2, 0) | 0.3043 | 0.4058 | 0.8384 |
| 80.0 | (15, 7) | (1, 0) | 0.3043 | 0.4150 | 0.8632 |
All three measures pick the same split: temperature at most 64.5 °F. The four coldest flights (53, 57, 58 and 63 °F) all had distress, so the left child is pure, with all three impurities zero. The right child has 16 flights without distress and 3 with, so its Gini index is $2 \times 3 \times 16/19^2 = 0.2659$ and its entropy 0.6292 bits. Weighted by size, the split's Gini index is $\tfrac{4}{23} \times 0 + \tfrac{19}{23} \times 0.2659 = 0.2197$, a decrease of 0.2038 from the root, and its entropy is 0.5198 bits, an information gain of 0.3667 bits. The other input, leak-check pressure, has three values, and its better threshold reduces the Gini index only to 0.3891. The root asks about temperature.
The two identities derived above can be checked on this split. The four indicator variables (one per class, on each side) have squared deviations from their side means that add up to 5.0526, and $23 \times 0.2197 = 5.0526$. Two flights drawn at random with replacement from all 23 have different outcomes with probability 0.4234, the root Gini index.
Why the misclassification rate is not enough
The table already shows the misclassification rate's weakness: for every threshold above 67 °F it is stuck at $7/23 = 0.3043$, the root's own error, because each of those splits leaves "no distress" as the majority on both sides. The error rate cannot tell those splits apart, although some clearly separate the classes better than others.
The second level makes the point sharper. The warm branch holds 19 flights, 16 without distress and 3 with, and predicts "no distress", making 3 errors. Every possible split of these 19 flights, on temperature or pressure, leaves "no distress" as the majority in both children, so every split still makes exactly 3 errors and the misclassification rate sees no improvement anywhere. The Gini index does: the best split, temperature at most 69.5 °F, sends six flights without distress to the left, a pure child, and leaves 10 and 3 on the right, lowering the weighted Gini index from 0.2659 to 0.2429 and the entropy from 0.6292 to 0.5332 bits. The split does not change any prediction, but it isolates a group the tree can now be certain about, and a later split of the mixed child might separate its three distressed flights. James et al. (2021, §8.1.2) give the same reason: Gini and entropy are "more sensitive to node purity than is the classification error rate".
The underlying reason is curvature. The parent's class proportion is the weighted average of the children's: with $w_L = n_L / n$ and $w_R = n_R / n$,
$$p = w_L\, p_L + w_R\, p_R.$$
If an impurity $i$ is strictly concave, so that the curve lies strictly above every chord, then
$$i(p) = i\bigl(w_L p_L + w_R p_R\bigr) > w_L\, i(p_L) + w_R\, i(p_R)$$
whenever $p_L \ne p_R$, by Jensen's inequality. For the Gini index and entropy, any split that changes the class proportions at all therefore lowers the weighted impurity, and the amount reflects how much the proportions change. The misclassification rate, $\min(p, 1-p)$, is a straight line on each side of $p = 0.5$. When $p_L$, $p_R$ and $p$ all lie on the same side, the weighted error of the children equals the parent's exactly, however different the children are. The warm branch is precisely this case: all proportions of distress lie below 0.5.
The same argument says why the weights must be the case counts. With other weights, $p$ would not be the weighted average of $p_L$ and $p_R$, and a split could appear to increase impurity.
The misclassification rate still has a role. When a tree is pruned, the goal is usually the accuracy of the final tree, and James et al. (2021, §8.1.2) note that "the classification error rate is preferable if prediction accuracy of the final pruned tree is the goal". Growing with Gini or entropy and choosing the pruned size by cross-validated accuracy combines the two.
Three classes: the wine data
The wine data (Aeberhard and Forina, 1992) record 13 chemical measurements on 178 wines grown in one region of Italy, from three cultivars: 59 from the first, 71 from the second and 48 from the third. With three classes the root impurity is near its ceiling: Gini $1 - (59^2 + 71^2 + 48^2)/178^2 = 0.6583$ against a maximum of $0.6667$, and entropy 1.5668 bits against $\log_2 3 = 1.5850$. Predicting the most common cultivar for every wine would be right 39.9% of the time.
The best root split for each of the five strongest measurements, with the weighted Gini index after the split and the cultivar counts on each side:
| Measurement | Threshold | Weighted Gini | Left | Right |
|---|---|---|---|---|
| proline | 755 | 0.4065 | (2, 67, 42) | (57, 4, 6) |
| color intensity | 3.82 | 0.4140 | (4, 60, 0) | (55, 11, 48) |
| alcohol | 12.78 | 0.4310 | (0, 62, 11) | (59, 9, 37) |
| OD280/OD315 | 2.115 | 0.4377 | (0, 7, 45) | (59, 64, 3) |
| flavanoids | 1.4 | 0.4380 | (0, 10, 47) | (59, 61, 1) |
Each of these splits isolates one cultivar from the other two in a different way. Proline, an amino acid, separates most of cultivar 1 (high proline) from cultivars 2 and 3; color intensity separates cultivar 2; OD280/OD315, an absorbance ratio, and flavanoids separate cultivar 3. Proline wins narrowly. Splitting each child once more gives a depth-2 tree.
Every cultivar is the majority in at least one leaf, and the tree classifies 164 of the 178 wines correctly (0.921). The leaf proportions are its probability estimates: a wine with proline above 755 and flavanoids above 2.165 is assigned probability $57/59 = 0.966$ of cultivar 1. Nothing about the method needed to change for three classes. That is a real convenience compared with logistic regression, which needs a multinomial extension for more than two classes, but it has a cost: a rare class may never be the majority in any leaf, and then the tree never predicts it at all.
Each leaf is a rectangle in the space of the inputs. Restricted to two inputs, proline and OD280/OD315, a depth-3 tree divides the plane into regions that can be drawn directly.
This two-input tree is right on 0.921 of the training wines and on 0.859 of wines in 10-fold cross-validation, a reminder that training accuracy flatters any tree.
Gini or entropy?
James et al. (2021, §8.1.2) observe that the Gini index and entropy "are quite similar numerically", and the curves above show why: after scaling, they differ little anywhere. On the Challenger flights they agreed on every comparison. They do not always pick the same split, though. With entropy as the criterion, the depth-2 wine tree splits first on flavanoids at 1.575 rather than proline, then on color intensity and proline. Ten-fold stratified cross-validated accuracy, by maximum depth:
| Maximum depth | 1 | 2 | 3 | 4 | 5 | Unlimited |
|---|---|---|---|---|---|---|
| Gini | 0.635 | 0.814 | 0.888 | 0.888 | 0.888 | 0.882 |
| Entropy | 0.566 | 0.852 | 0.909 | 0.909 | 0.909 | 0.909 |
Entropy does slightly better here from depth 2 on, by 0.02 to 0.04, between four and seven wines in 178, a difference that a different random division into folds could easily change. Neither measure is better in general, and the depth matters much more than the criterion.
Pruning a classification tree
The overfitting described in the introduction is controlled the same way as for regression trees: grow a large tree, compute the cost-complexity pruning sequence (derived in Regression Trees), and choose its size by cross-validation. scikit-learn's pruning penalizes the total Gini impurity of the leaves (or entropy, matching the criterion used for growing), weighted by the fraction of cases in each, plus $\alpha$ per leaf. The size is then chosen by cross-validated accuracy, the quantity of interest.
For the breast cancer data of the introduction (Wolberg, Mangasarian, Street and Street, 1993), the fully grown tree has 22 leaves and depth 7, classifies all 569 training tumors correctly, and has a 10-fold cross-validated accuracy of 0.923.
Pruning to 13 leaves raises cross-validated accuracy to 0.937. As in Regression Trees, picking the best size on the same folds is slightly optimistic; repeating the choice of $\alpha$ by an inner cross-validation within each training fold gives an honest accuracy of 0.931. Pruning helps, but the gain is modest, and a random forest on the same data reaches 0.961.
Categorical inputs
A numerical input with $k$ distinct values offers $k - 1$ splits. A categorical input with $q$ unordered categories offers many more, because a binary split can send any subset of the categories left and the rest right. Counting each partition once (swapping left and right gives the same split) and excluding the empty set, there are $2^{q-1} - 1$ possible splits: 3 for three categories, 31 for six, 511 for ten and 524,287 for twenty. The number grows fast enough that a categorical input with many levels has a large advantage in the search simply by offering more chances to fit the training data, a bias Quinlan (1986) noted for information gain, which favors attributes with more values.
For two classes there is an exact shortcut: order the categories by the proportion of class 1 in each, and the best split, by Gini index or entropy, is one of the $q - 1$ splits of that ordered list, as if the input were numerical (Hastie, Tibshirani and Friedman, 2009, §9.2.4, who attribute the proof to Breiman et al., 1984). The script for this article checked the shortcut against a brute-force search on 1,000 random two-class problems with six categories, and it found the best Gini split in all 1,000 while examining 5 splits instead of 31.
scikit-learn's trees need numerical inputs, so categorical inputs are usually converted to one-hot indicator columns, one per category (or one fewer, dropping a reference category). A split on an indicator at 0.5 then separates one category from all the others, so a grouping such as "categories A and C versus the rest" takes several splits to express.
In Python
from sklearn.datasets import load_wine
from sklearn.model_selection import StratifiedKFold, cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text
wine = load_wine()
X, y = wine.data, wine.target # cultivars coded 0, 1, 2
tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X, y)
print(export_text(tree, feature_names=wine.feature_names, show_weights=True))
print(tree.score(X, y)) # 0.921 on the training data
print(tree.predict_proba(X[:1])) # the class proportions in wine 1's leaf
folds = StratifiedKFold(10, shuffle=True, random_state=0)
for criterion in ("gini", "entropy"):
model = DecisionTreeClassifier(criterion=criterion, max_depth=3, random_state=0)
print(criterion, cross_val_score(model, X, y, cv=folds).mean()) # 0.888 and 0.909
show_weights=True prints the class counts in each leaf. StratifiedKFold keeps the proportions of the three cultivars about the same in every fold, which matters for small datasets with unequal classes. The numbers in this article are computed by tools/experiments/data-science/classification-trees.py in the site's repository.
References
- Aeberhard, S., and Forina, M. (1992). Wine [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5PC7J record · 8 pages
- Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Wadsworth. record · 3 pages
- Draper, D. (1993). Challenger USA Space Shuttle O-Ring [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5PW2T record · 4 pages
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer. record · 23 pages
- James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
- Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106. record · 2 pages
- Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages