To choose a tree’s questions, a computer needs a number for how mixed a node is. Meet the misclassification rate, the Gini impurity and entropy, score a split by the drop in size-weighted impurity, and find the best first question for the twelve points by hand.
ML02.1.2L2 Intermediate30 minIn review (what this means)
The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.
Compute the misclassification rate, the Gini impurity and the entropy of a node from its class counts.
Score a split by the decrease in size-weighted impurity, and call the entropy decrease information gain.
Score every threshold of both features of the twelve points and find the best first split by hand.
Explain, with the picture of a curve and a chord, why Gini and entropy can reward a split that the misclassification rate ignores.
The question
The tree of the last lesson began with the question \(x_1 \le 3.5\). Why that one, out of every feature and every threshold? To let a computer choose, we need a number that says how mixed a group of points is, so that a good question is one that makes the groups less mixed. Which number?
From the last lesson
1. What shape is the region of a leaf of a decision tree?
Show answer
An axis-aligned rectangle (a box in higher dimensions), because each test on the way down keeps one side of a cut on a single feature.
2. What should a leaf of a classification tree predict, and why?
Show answer
Its majority class. Answering class \(k\) gets \({n_m - n_{mk}}\) of its points wrong, which is smallest when \(n_{mk}\) is largest.
Intuition
A node of a tree holds some training points. If they are all of one class, the node is pure and there is nothing left to ask. If they are half and half, the node is as mixed as it can be. An impurity measure turns this into a number: zero for a pure node, largest for an even mix. For two classes it depends only on \(p\), the share of class 1 in the node.
ML02.1.2-F1
Three impurity measures for two classes. All are zero for a pure node and largest for an even mix. At the 5 : 1 node of the twelve points (\(p = 1/6\)) they read \(0.167\), \(0.278\) and \(0.650\).
The three curves agree on the ends and on where the peak is. They differ in shape: the misclassification rate is a tent of straight lines, while Gini and entropy are rounded. That small difference in shape turns out to matter, as the pitfalls section shows.
Build it up
Step 1. The misclassification rate. If a node answers with its majority class, the share of its points it gets wrong is its misclassification rate. For the 5 : 1 node that is \(1/6\).
Step 2. The Gini impurity. Pick two points from the node at random, with replacement. The Gini impurity is the chance that they belong to different classes. For the 5 : 1 node, the chance of “class 0 then class 1” is \({(5/6)(1/6)}\) and the chance of “class 1 then class 0” is the same, so \({G = 2 \cdot 5/36} = 5/18 \approx 0.278\).
Step 3. Entropy. Seeing a class with probability \(p\) carries a surprise of \(-\log_2 p\) bits: a sure thing carries none, a fair coin carries 1 bit, a rare class carries a lot. Entropy is the average surprise over the points of the node.
ML02.1.2-F5
Surprise, in bits, against the probability of what you see. In the 5 : 1 node, five points in six carry a small surprise and one carries a large one. Their average is the entropy, \(0.650\) bits.
Step 4. Score a split. A question sends the points of a node into two children. Measure each child’s impurity and average them, weighting each child by its share of the points: a child with more points matters more. The split’s score is how far this weighted average falls below the parent’s impurity.
ML02.1.2-F2
Scoring the question \(x_1 \le 3.5\) at the root. The weighted Gini of the children is \(5/18\), so the question lowers the impurity by \(2/9\).
The formal statement
A node holds \(n\) points, a share \(p_k\) of them in class \(k\), for \(k = 1, \dots, K\).
NoteDefinition: three impurity measures
\[
\begin{aligned}
E &= 1 - \max_k p_k \\
G &= \sum_{k=1}^{K} p_k (1 - p_k) \\
H &= -\sum_{k=1}^{K} p_k \log_2 p_k
\end{aligned}
\]
with \(0 \log_2 0\) taken as \(0\). For two classes, with \(p\) the share of class 1:
\[
\begin{aligned}
E &= \min(p,\, 1 - p) \\
G &= 2p(1 - p) \\
H &= -p \log_2 p - (1 - p) \log_2 (1 - p)
\end{aligned}
\]
The second form of \(G\) comes from the first. With two classes, \(p_1 = 1 - p\) and \(p_2 = p\), so each of the two terms \({p_k(1 - p_k)}\) equals \({p(1 - p)}\), and their sum is \({2p(1 - p)}\). Another useful form: expand the product and use \(\sum_k p_k = 1\),
NoteDefinition: impurity decrease and information gain
A split sends \(n_L\) of the node’s \(n\) points to the left child and \(n_R\) to the right. For an impurity measure \(I\), the split’s impurity decrease is
With entropy as \(I\), the decrease is called the information gain. The best split is the one with the largest decrease.
Why the decrease is never negative. The parent’s share of class 1 is the weighted average of its children’s shares:
\[
p = \tfrac{n_L}{n}\, p_L + \tfrac{n_R}{n}\, p_R .
\]
Draw the curve \(I(p)\), mark the two children on it, and join them with a straight segment, a chord. The point of the chord above \(p\) is exactly the weighted impurity of the children. Gini and entropy are curves that bend downwards (concave), so the chord lies below the curve, and the parent sits at or above the chord. The gap is the decrease. It is zero only when the two children have the same share, \(p_L = p_R\).
Go deeper: the concavity argument, line by line
Write \(w = n_L/n\), so that \(n_R/n = 1 - w\) and \(p = {w p_L} + {(1 - w) p_R}\). A function \(I\) is concave when, for every \(w\) between 0 and 1,
The left side is the parent’s impurity and the right side is the weighted impurity of the children, so \(\Delta I \ge 0\) for any concave \(I\). A twice-differentiable function is concave when its second derivative is never positive. For Gini, \(G(p) = 2p - 2p^2\) gives \(G'(p) = 2 - 4p\) and \(G''(p) = -4\). For entropy, \(H'(p) = \log_2 \frac{1 - p}{p}\) and
\[
H''(p) = -\frac{1}{p(1 - p)\ln 2},
\]
which is negative for every \(p\) strictly between 0 and 1. Both are strictly concave, so the inequality is strict unless \(p_L = p_R\). The misclassification rate is concave too, but it is made of two straight pieces. When both children sit on the same piece, the chord lies along the curve and the decrease is exactly zero.
Worked example
Score every first question for the twelve points. Sort the values of each feature and put a threshold halfway between neighbouring values. Feature \(x_1\) takes the values 1 to 6, giving five thresholds; \(x_2\) takes 1 to 5, giving four.
Take \(x_1 \le 3.5\) in full. The left side holds \((1, 1)\), \((2, 1)\), \((1, 2)\), \((2, 3)\), \((3, 2)\) of class 0 and \((2, 5)\) of class 1: counts 5 : 1. The right side holds 1 : 5. Each child has Gini \({1 - (5/6)^2 - (1/6)^2} = 10/36 = 5/18\). Each holds half the points, so the weighted Gini is \(5/18\), and the decrease is \({1/2 - 5/18} = 4/18 = 2/9 \approx 0.222\).
For entropy, the root is an even mix, so \(H = 1\) bit. Each child has
so the information gain is \({1 - 0.650} = 0.350\) bits.
A second one, \(x_1 \le 2.5\), to see unequal sizes. The children are 4 : 1 (five points) and 2 : 5 (seven points), with Gini \({1 - 16/25 - 1/25} = 8/25\) and \({1 - 4/49 - 25/49} = 20/49\). Weighted: \({(5/12)(8/25)} + {(7/12)(20/49)} = {2/15 + 5/21} = 13/35\), a decrease of \({1/2 - 13/35} = 9/70 \approx 0.129\).
The table has all nine. The counts are class 0 : class 1 on the left, then on the right.
Split
Counts
Gini drop
Gain (bits)
\(x_1 \le 1.5\)
2:0, 4:6
0.100
0.191
\(x_1 \le 2.5\)
4:1, 2:5
0.129
0.196
\(x_1 \le 3.5\)
5:1, 1:5
0.222
0.350
\(x_1 \le 4.5\)
5:3, 1:3
0.062
0.093
\(x_1 \le 5.5\)
6:5, 0:1
0.045
0.089
\(x_2 \le 1.5\)
2:1, 4:5
0.019
0.027
\(x_2 \le 2.5\)
4:2, 2:4
0.056
0.082
\(x_2 \le 3.5\)
5:3, 1:3
0.062
0.093
\(x_2 \le 4.5\)
5:4, 1:2
0.019
0.027
ML02.1.2-F3
The nine candidate first questions. Both measures pick \(x_1 \le 3.5\), by a clear margin.
Both measures choose \(x_1 \le 3.5\). They often agree: the two curves have nearly the same shape, and here they rank the nine splits in almost the same order.
Now score every threshold of every feature with the impurity decrease.
def counts(y):return [int((y ==0).sum()), int((y ==1).sum())]def decrease(X, y, feature, s, impurity): left = X[:, feature] <= s n, n_left =len(y), int(left.sum()) after = (n_left * impurity(counts(y[left]))+ (n - n_left) * impurity(counts(y[~left]))) / nreturn impurity(counts(y)) - afterrows = []for j inrange(points.shape[1]): values = np.unique(points[:, j])for s in (values[:-1] + values[1:]) /2: rows.append((j, s, decrease(points, labels, j, s, gini), decrease(points, labels, j, s, entropy)))print(f"x{j +1} <= {s}: Gini drop {rows[-1][2]:.3f} gain {rows[-1][3]:.3f}")best =max(rows, key=lambda r: r[2])print("best:", f"x{best[0] +1} <= {best[1]}")
x1 <= 1.5: Gini drop 0.100 gain 0.191
x1 <= 2.5: Gini drop 0.129 gain 0.196
x1 <= 3.5: Gini drop 0.222 gain 0.350
x1 <= 4.5: Gini drop 0.062 gain 0.093
x1 <= 5.5: Gini drop 0.045 gain 0.089
x2 <= 1.5: Gini drop 0.019 gain 0.027
x2 <= 2.5: Gini drop 0.056 gain 0.082
x2 <= 3.5: Gini drop 0.062 gain 0.093
x2 <= 4.5: Gini drop 0.019 gain 0.027
best: x1 <= 3.5
scikit-learn agrees. A tree with one question, max_depth=1, picks the same split under either criterion, and tree_.impurity holds each node’s impurity. Its "entropy" criterion uses logarithms to base 2, so the root has entropy 1.
from sklearn.tree import DecisionTreeClassifierfor criterion in ["gini", "entropy"]: stump = DecisionTreeClassifier(max_depth=1, criterion=criterion).fit(points, labels) t = stump.tree_print(criterion, " split: x%d <= %.1f"% (t.feature[0] +1, t.threshold[0])," impurities:", t.impurity.round(3))
The tree grower of lesson 3 switches between Gini and entropy and shows each node’s counts and impurity. Drag a point and watch which question wins the root.
Pitfalls
The right child of the root, the 1 : 5 node, holds \((5, 5)\) of class 0 and five points of class 1. Every split of this node leaves class 1 in the majority on both sides, so the misclassification rate never moves. The split \(x_2 \le 4.5\) is the useful one: it peels off four class-1 points into a pure leaf.
ML02.1.2-F4
Wrong beside right, for the split \(x_2 \le 4.5\) of the 1 : 5 node. The parent (ring) is the curve above \(p = 5/6\); the weighted children (dot) are the chord. The misclassification rate is straight there, so the chord lies on it and the decrease is 0. Gini is curved, so it rewards the split with a decrease of \(1/9\).
“Grow the tree with the error rate, since the error rate is what I care about.”
A split can make a node much purer without changing any majority, and then the error rate cannot see it. In the figure, every split of the 1 : 5 node leaves its misclassification rate at \(1/6\), so a grower using it would stop, yet the next question down separates the node completely. Hastie, Tibshirani and Friedman give a larger example: from a \((400, 400)\) node, the splits into \((300, 100)\) and \((100, 300)\), or into \((200, 400)\) and \((200, 0)\), both have error rate 0.25, but only the second makes a pure node, and Gini and entropy both prefer it. Grow with Gini or entropy. The error rate is still a fine measure for judging the finished tree.
“Entropy and Gini give different trees, so the choice matters a lot.”
They are rarely far apart. The two curves have nearly the same shape, and on the twelve points they choose the same question at every node. Entropy is slower to compute because of the logarithm. Try both; if they differ, treat the choice like any other setting and compare the trees by cross-validation (ML01.9).
“Add the children’s impurities to score a split.”
Without weights a tiny child counts as much as a large one. Split a single point off a mixed node: the one-point child has impurity 0, and the large child is almost as mixed as the parent. A plain average of the two halves the parent’s impurity, so this useless split looks excellent. Weighted by size, the one-point child counts for \(1/n\) and the split scores close to zero. Always weight each child by its share of the points.
Check yourself
Recall
1. Give the Gini impurity and the entropy of a node with counts 3 : 1.
The chance that two points drawn at random, with replacement, from the node belong to different classes.
3. How is a split scored?
Show answer
By the impurity decrease: the parent’s impurity minus the children’s impurities, each weighted by its share of the parent’s points.
4. What is information gain?
Show answer
The impurity decrease of a split when entropy is the impurity measure.
5. Why can the impurity decrease of Gini or entropy never be negative?
Show answer
Both are concave, so the weighted average of the children’s impurities (the chord) lies on or below the curve at the parent’s share. It is zero only if the children have the same share.
Exercises
1.★ Verify the row \(x_2 \le 2.5\) of the table: the counts, the Gini decrease and the information gain.
Show solution
Points with \(x_2 \le 2.5\): \((1, 1)\), \((2, 1)\), \((1, 2)\), \((3, 2)\) of class 0 and \((4, 1)\), \((5, 2)\) of class 1, so 4 : 2; the other six are 2 : 4. Each child has \({G = 1 - 4/9 - 1/9} = 4/9\), so the weighted Gini is \(4/9\) and the decrease is \({1/2 - 4/9} = 1/18 \approx 0.056\). Each child has \({H = -\tfrac23\log_2\tfrac23 - \tfrac13\log_2\tfrac13} = 0.918\) bits, so the gain is \({1 - 0.918} = 0.082\) bits.
2.★★ Show that for two classes the Gini impurity is largest at \(p = 1/2\), and find its value there. Do the same for entropy.
Show solution
\(G(p) = 2p - 2p^2\), so \(G'(p) = 2 - 4p\), which is zero at \(p = 1/2\); since \(G''(p) = -4 < 0\) this is a maximum, \(G(1/2) = 1/2\). For entropy,
which is zero when \({1 - p} = p\), at \(p = 1/2\). The second derivative is negative, so this is a maximum, \(H(1/2) = 1\) bit.
3.★★★ ESL’s example: a node with counts \((400, 400)\) is split either into \((300, 100)\) and \((100, 300)\), or into \((200, 400)\) and \((200, 0)\). Compute the error rate, the weighted Gini and the weighted entropy after each split, and say which split each measure prefers.
Show solution
First split: each child has 400 points and error rate \(1/4\), so the weighted error is \(0.25\). Each child has \({G = 2 \cdot \tfrac34 \cdot \tfrac14} = 0.375\) and \({H = 0.811}\) bits, so the weighted values are \(0.375\) and \(0.811\).
Second split: the children have 600 and 200 points, weights \(3/4\) and \(1/4\). The error rates are \(1/3\) and 0, weighted \({\tfrac34 \cdot \tfrac13} = 0.25\), the same as before. Gini: \({2 \cdot \tfrac13 \cdot \tfrac23} = 4/9\) and 0, weighted \({\tfrac34 \cdot \tfrac49} = 1/3 \approx 0.333\). Entropy: \({H(1/3)} = 0.918\) and 0, weighted \({\tfrac34 \cdot 0.918} = 0.689\) bits.
The error rate cannot tell the splits apart. Gini (\(0.333 < 0.375\)) and entropy (\(0.689 < 0.811\)) both prefer the second split, the one that makes a pure node.
Summary card
A good question makes the children purer, weighted by their size.
Entropy.\(H = -\sum_k p_k \log_2 p_k\) bits; the average surprise.
Score. Decrease \(= I(\text{parent})\) minus the size-weighted child impurities.
Twelve points. Best root split \(x_1 \le 3.5\): Gini drop \(2/9\), gain \(0.350\) bits.
Sources and next steps
Sources. Each was opened and checked against this lesson on 15 November 2026.
T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning, 2nd edition, 12th printing. Section 9.2.3: the three impurity measures (9.17), their two-class forms and Figure 9.3; the \((400, 400)\) example used in exercise 3; the interpretation of Gini as the error of a random rule.
G. James, D. Witten, T. Hastie, R. Tibshirani and J. Taylor, An Introduction to Statistical Learning, 2nd edition. Section 8.1.2: the classification error rate (8.5), the Gini index (8.6), entropy (8.7), and the remark that error rate is not sensitive enough for growing trees.
