Gini, Entropy, and Why Misclassification Error Cannot Grow a Tree

At a classification node holding a mixture of $K$ classes, a split is judged by how much it reduces impurity, and impurity is a function of the class proportions alone. Three functions are in common use: the Gini index, the Shannon entropy, and the misclassification error. They agree on the two endpoints, zero for a pure node and a maximum for a uniform one, and they rank many splits identically. The disagreements are the interesting part, because one of the three cannot be used to grow a tree at all.

Three scores for the same proportions

Let $p_k$ be the fraction of samples at a node belonging to class $k$.

The Gini index is $1-\sum_k p_k^2$, the probability that two independent draws from the node land on different classes. For two classes it reduces to $2p(1-p)$, which is exactly twice the sample variance of an indicator target, a correspondence that explains why Gini behaves like a variance criterion.

The Shannon entropy is $-\sum_k p_k \log p_k$, measured in bits when the logarithm is base two. It is the expected code length for the class label under the node’s distribution.

The misclassification error is $1-\max_k p_k$, the error rate of the majority-class rule at that node. It is the quantity a finished classifier is actually scored on, which makes it the intuitive choice and the wrong one for growth.

All three are zero at a pure node. Their maxima differ: Gini and the error rate both reach $1-1/K$ for $K$ classes, while entropy reaches $\log_2 K$. That difference is scale, not disagreement, and it disappears once gains are compared within one criterion rather than across two.

What a split criterion must satisfy

A growing algorithm chooses the split maximizing the weighted decrease

$$ \Delta = I(\text{parent}) - \frac{n_L}{n} I(\text{left}) - \frac{n_R}{n} I(\text{right}) $$

Two properties of $I$ make this a sensible objective. It must be zero for pure nodes, and it must be strictly concave in the proportions. Concavity is the load-bearing one. If $I$ is strictly concave, any split that moves the children’s distributions apart raises the average purity, so $\Delta$ is strictly positive for every non-trivial division, and the criterion is sensitive to degree: a split that separates the classes more thoroughly scores strictly higher.

The Gini index and entropy are strictly concave. The misclassification error is concave but only weakly: it is piecewise linear, so it is flat along any segment where the identity of the majority class does not change. Along those segments the criterion cannot tell two partitions apart, and sometimes it assigns both exactly the same value as the parent.

A worked partition where the error rate is blind

Take a node with 1,000 samples, 900 of class A and 100 of class B. The error rate is 0.1, the Gini index is $1-(0.81+0.01)=0.18$, and the entropy is about 0.469 bits.

Now split it into a left child of 850 samples (800 A, 50 B) and a right child of 150 (100 A, 50 B).

	error	Gini	entropy (bits)
parent	0.100	0.180	0.469
left	0.0588	0.1107	0.322
right	0.333	0.444	0.918
weighted children	0.100	0.1608	0.412
decrease	0.000	0.0192	0.057

The left child is 94% pure and the right child is 67% pure, a real change in composition. The misclassification error reports no gain whatsoever. The reason is structural: in both children class A is the majority, so each child’s error is a linear function of its counts, and the weighted average of two linear functions evaluated on a partition of the same total lands back on the parent’s line. A greedy search driven by this criterion would reject the split and stop growing.

The same arithmetic also makes the error rate indifferent between partitions of genuinely different quality. Consider the 400/400 node from the standard treatment: splitting it into (300, 100) and (100, 300) and splitting it into (200, 400) and (200, 0) both reduce the error from 0.5 to 0.25, so the criterion cannot choose. Gini scores the first at 0.125 and the second at 0.167; entropy scores them at 0.189 and 0.311 bits. Both prefer the second, which is the split that produces a pure child.

The lesson generalizes: any criterion that is linear over a region will have that region as a plateau, and a greedy search on a plateau makes an arbitrary choice.

Gini as a local approximation of entropy

Expand both functions around $p = 1/2$ in the two-class case. Both have zero slope there, and both are locally parabolic: Gini is $2p(1-p)$ with second derivative $-4$, and entropy in bits has second derivative $-4/\ln 2$, about $-5.77$. The shapes are therefore similar, with entropy the steeper of the two and rescaled to a maximum of one bit rather than one half. That similarity is the practical reason the choice between them rarely changes accuracy much. They separate near the ends, where Gini’s slope is constant in magnitude and entropy’s is not.

Two consequences follow. Gini is cheaper: it needs no logarithm, and on modern hardware the difference is a few operations per candidate evaluation multiplied by every candidate at every node. Gini also tends to concentrate on the largest class, because its derivative with respect to a small $p_k$ is small; entropy’s derivative grows without bound as $p_k \to 0$, giving it more reason to carve out small classes. Empirically the two produce trees of similar accuracy but different shapes, and neither dominates.

The base of the logarithm changes only the units of entropy. Base two gives bits, the natural log gives nats, and since the conversion is a positive constant, the ranking of splits is unchanged. Gains are not comparable across criteria, however, so a threshold tuned on “entropy decrease” means nothing when the implementation switches to Gini.

One further criterion in this family is worth naming because it shows that impurity is not the only possible objective. The twoing rule scores a split by how evenly it divides the samples, weighted by how far apart the two children’s class distributions are: it maximizes roughly $p_L p_R (\sum_k |p_k^L - p_k^R|)^2$, where $p_L$ and $p_R$ are the children’s sample fractions. The rule has no node-level impurity interpretation at all, and it tends to produce balanced splits that keep all classes represented on both sides. CART suggests twoing can be preferable when the number of classes is large, since it does not favour the largest class the way Gini does, and notes that it costs more to evaluate because every candidate threshold needs the class distributions of both children rather than one.

Cost, scaling, and what the choice changes downstream

Every criterion in this family is computed from class counts, so the incremental scan described in the CART split search works for all three: maintain the left histogram, derive the right histogram by subtraction, evaluate. The per-candidate cost is $O(K)$ regardless of which is chosen; the constant differs by a handful of floating-point operations, and on nodes with large $K$ the logarithm is the visible part.

import math

def impurity(counts, kind):
    n = sum(counts)
    if n == 0:
        return 0.0
    p = [c / n for c in counts]
    if kind == "gini":
        return 1.0 - sum(x * x for x in p)
    if kind == "entropy":
        return -sum(x * math.log2(x) for x in p if x > 0.0)
    if kind == "error":
        return 1.0 - max(p)
    raise ValueError(kind)

Two scaling facts matter when trees are later combined. First, impurity values shrink as nodes get small: an impurity decrease computed on 20 samples is noisy and, in a bagged or boosted ensemble, is exactly the kind of quantity that produces unstable splits. Second, the criterion is scale-free in $n$ but not in $K$; adding a class that never appears at a node changes nothing, while adding one that appears three times barely moves the score.

For regression the analogue is the mean squared error at the node, and it is strictly concave by construction because it is a variance. That is why regression trees have no equivalent of the misclassification trap, and why the split search for regression reduces to the sum-of-squares identity rather than a scan of class histograms.

The impurity function also interacts with pruning. Cost-complexity pruning ranks subtrees by $R(T) + \alpha|T|$, where $R$ is the training error; the impurity used to grow the tree determines which subtrees exist to be pruned, but the pruning criterion itself is usually the misclassification or squared-error loss rather than the growth impurity. A tree grown with entropy and pruned on error is therefore consistent, in the narrow sense that it is not optimizing the same quantity twice. Misclassification error remains the right measure for evaluating a finished tree, even though it is the wrong one for choosing splits inside it.