Why Classification Trees Measure Impurity
A classification tree predicts a class from the observations that reach a terminal node. The earlier material on class predictions and probabilities in terminal nodes established that the observed class proportions in a node can be used to describe its class probabilities. When a node contains a mixture of classes, however, its prediction may be uncertain. A tree needs a way to quantify that mixture when comparing candidate partitions.
Gini impurity is one such measure. It is zero when all observations in a node belong to one class, and it increases as the node’s class proportions become more evenly balanced. For a proposed split, the relevant comparison is not an unweighted average of the children’s impurity: each child is weighted by the fraction of the parent observations that it contains.
The class proportions are empirical proportions for the observations in the node. This calculation does not require a parametric probability model or a distributional assumption about a numeric response. It does require each observation in the node to have a class label, and the class categories must be defined consistently across the parent and its children.
Gini impurity is smallest at \(0\), when one class has proportion \(1\). With \(K\) classes, it is largest when all classes have equal proportions: then \(G=1-1/K\). For two classes, the maximum is \(1/2\), at proportions \(1/2\) and \(1/2\). These values help check calculations, but impurity is not itself the probability that the tree’s majority-class prediction is wrong.
Calculating the Reduction for a Candidate Split
A candidate split partitions the observations in a parent node into nonempty child nodes. If child \(j\) contains \(n_j\) observations and has Gini impurity \(G_j\), its weight is \(n_j/n\), where \(n\) is the number in the parent. The weighted child impurity and the reduction are defined as follows.
The weights matter because each child represents a different number of observations. A small, nearly pure child should not count as much as a large child containing most of the data. The reduction compares the parent with the weighted average across all of its children, not with whichever child looks most favorable.
Worked Example: Comparing Two Binary-Class Splits
A hypothetical insurer is examining a node of 12 policy records, classified as either “renewed” or “not renewed.” There are 7 renewed and 5 not renewed records. Candidate A partitions the records into children with counts (5 renewed, 1 not renewed) and (2 renewed, 4 not renewed). Candidate B gives children (4 renewed, 2 not renewed) and (3 renewed, 3 not renewed). Calculate each reduction and choose the better split by this criterion.
Method and parent impurity. Use the empirical class proportions. For the parent, the proportions are \(7/12\) and \(5/12\), so $$ G_{\mathrm{parent}}=1-\left(\frac{7}{12}\right)^2-\left(\frac{5}{12}\right)^2 =\frac{144-49-25}{144} =\frac{70}{144} =\frac{35}{72} \approx 0.4861. $$
Candidate A. Each child contains 6 records, so each weight is \(6/12=1/2\). The first child has impurity $$ 1-\left(\frac{5}{6}\right)^2-\left(\frac{1}{6}\right)^2 =\frac{10}{36} =\frac{5}{18}. $$ The second child has impurity $$ 1-\left(\frac{2}{6}\right)^2-\left(\frac{4}{6}\right)^2 =\frac{16}{36} =\frac{4}{9}. $$ Thus the weighted child impurity is $$ \frac{1}{2}\left(\frac{5}{18}\right)+\frac{1}{2}\left(\frac{4}{9}\right) =\frac{5}{36}+\frac{8}{36} =\frac{13}{36} =\frac{26}{72} \approx 0.3611. $$ The reduction is \(35/72-26/72=9/72=1/8=0.1250\).
Candidate B. The first child’s impurity is $$ 1-\left(\frac{4}{6}\right)^2-\left(\frac{2}{6}\right)^2 =\frac{16}{36} =\frac{4}{9}, $$ and the second child’s impurity is $$ 1-\left(\frac{3}{6}\right)^2-\left(\frac{3}{6}\right)^2 =\frac{18}{36} =\frac{1}{2}. $$ Both children again have weight \(1/2\), giving weighted impurity $$ \frac{1}{2}\left(\frac{4}{9}\right)+\frac{1}{2}\left(\frac{1}{2}\right) =\frac{2}{9}+\frac{1}{4} =\frac{17}{36} =\frac{34}{72} \approx 0.4722. $$ The reduction is \(35/72-34/72=1/72\approx 0.0139\).
Conclusion and check. Candidate A has the larger reduction, \(0.1250\) versus \(0.0139\). Both weighted child impurities are between 0 and the parent impurity, so both reductions are nonnegative and the arithmetic is consistent. The method avoids choosing a split simply because one of its children looks pure; the other child and its size also matter.
Why the Weighted Reduction Works
The weighting is not an arbitrary adjustment. It makes the children’s impurity a summary of the parent observations after the split. To see the connection directly, let \(p_{jk}\) be the proportion of class \(k\) in child \(j\). The parent proportion in class \(k\) is the size-weighted average of the child proportions: $$ p_k=\sum_{j=1}^{J}\frac{n_j}{n}p_{jk}. $$ The parent Gini impurity can be written as \(\sum_k p_k(1-p_k)\), because \(\sum_k p_k=1\). Applying the weighted-average identity gives $$ G_{\mathrm{parent}} =\sum_{j=1}^{J}\frac{n_j}{n}G_j +\sum_{j=1}^{J}\frac{n_j}{n}\sum_{k=1}^{K}(p_{jk}-p_k)^2. $$
For completeness, this identity follows by expanding the squared differences. For a fixed class \(k\), $$ \sum_j\frac{n_j}{n}(p_{jk}-p_k)^2 =\sum_j\frac{n_j}{n}p_{jk}^2-p_k^2, $$ because \(\sum_j(n_j/n)p_{jk}=p_k\) and \(\sum_j n_j/n=1\). Summing over classes, the right-hand side becomes the weighted sum of the children’s squared class proportions minus the parent’s squared class proportions. Since \(G=1-\sum_k p_k^2\), rearranging yields the displayed identity.
The final term in the identity is nonnegative because it is a weighted sum of squared differences. Therefore, for a partition of the same parent observations, $$ \Delta G =\sum_{j=1}^{J}\frac{n_j}{n}\sum_{k=1}^{K}(p_{jk}-p_k)^2 \geq 0. $$ A split has a positive reduction when at least one child’s class proportions differ from the parent’s. It has zero reduction when every child has the same class proportions as the parent.
Worked Example: A Multiclass Split With Unequal Composition
A hypothetical review dataset has 12 records in a parent node: 6 marked “routine,” 3 marked “urgent,” and 3 marked “follow-up.” A candidate split produces a left child with counts (5, 1, 0) and a right child with counts (1, 2, 3), in that class order. Calculate the parent and child impurities and the split’s reduction.
Parent. The three class proportions are \(6/12\), \(3/12\), and \(3/12\). Thus $$ G_{\mathrm{parent}} =1-\left(\frac{6}{12}\right)^2-\left(\frac{3}{12}\right)^2-\left(\frac{3}{12}\right)^2 =1-\frac{36+9+9}{144} =\frac{90}{144} =\frac{5}{8} =0.6250. $$
Left child. This child has 6 records and proportions \(5/6\), \(1/6\), and \(0\): $$ G_{\mathrm{left}} =1-\left(\frac{5}{6}\right)^2-\left(\frac{1}{6}\right)^2-0^2 =\frac{10}{36} =\frac{5}{18} \approx 0.2778. $$
Right child. This child also has 6 records, with proportions \(1/6\), \(2/6\), and \(3/6\): $$ G_{\mathrm{right}} =1-\left(\frac{1}{6}\right)^2-\left(\frac{2}{6}\right)^2-\left(\frac{3}{6}\right)^2 =\frac{22}{36} =\frac{11}{18} \approx 0.6111. $$ The two weights are each \(6/12=1/2\), so $$ G_{\mathrm{children}} =\frac{1}{2}\left(\frac{5}{18}\right)+\frac{1}{2}\left(\frac{11}{18}\right) =\frac{16}{36} =\frac{4}{9} \approx 0.4444. $$ The reduction is $$ \Delta G=\frac{5}{8}-\frac{4}{9} =\frac{45-32}{72} =\frac{13}{72} \approx 0.1806. $$
Check and interpretation. The class counts in the children sum back to the parent counts: (5+1, 1+2, 0+3) = (6, 3, 3). The weighted impurity is below the parent impurity, and the reduction is positive. This calculation uses all three classes; dropping a class merely because its count is zero in one child would change the class definition unnecessarily.
Unequal Child Sizes and a Common Exam Trap
The need for weights is especially clear when a split creates children of very different sizes. An unweighted average gives a small child the same influence as a large child. That does not describe the average impurity across the parent’s observations, because the large child contains more of those observations.
Worked Example: Avoiding an Unweighted Child Average
A hypothetical classification node contains 10 claims, 6 in class “standard” and 4 in class “review.” Candidate A creates a child with counts (5 standard, 3 review) and a second child with counts (1 standard, 1 review). Calculate the reduction correctly, then assess the tempting unweighted calculation.
Parent and child impurities. The parent impurity is $$ G_{\mathrm{parent}}=1-\left(\frac{6}{10}\right)^2-\left(\frac{4}{10}\right)^2 =1-0.36-0.16=0.48. $$ The first child has size 8 and impurity $$ G_1=1-\left(\frac{5}{8}\right)^2-\left(\frac{3}{8}\right)^2 =\frac{30}{64}=\frac{15}{32}=0.46875. $$ The second child has size 2 and impurity $$ G_2=1-\left(\frac{1}{2}\right)^2-\left(\frac{1}{2}\right)^2 =\frac{1}{2}. $$
Correct weighting. The child weights are \(8/10=4/5\) and \(2/10=1/5\). Therefore $$ G_{\mathrm{children}} =\frac{4}{5}\left(\frac{15}{32}\right)+\frac{1}{5}\left(\frac{1}{2}\right) =\frac{3}{8}+\frac{1}{10} =\frac{19}{40} =0.475. $$ The reduction is \(0.48-0.475=0.005\).
The tempting error. The unweighted average is $$ \frac{0.46875+0.5}{2}=0.484375, $$ which would suggest a negative reduction of \(0.48-0.484375=-0.004375\). This is not the split criterion: it gives the 2-observation child as much influence as the 8-observation child. Weighting by child size corrects that mistake. The proper reduction is small but positive.
How to Interpret the Criterion
For a set of candidate splits of the same node, the split with the largest Gini reduction has the greatest reduction in weighted training-node impurity. Equivalently, it has the smallest weighted child impurity, since the parent impurity is the same for every candidate under comparison. The calculation is local: it evaluates the proposed partition of this node, not the overall predictive performance of a completed tree on new data.
A tree may compare valid candidate partitions using this criterion, but a large local reduction does not by itself establish that the resulting model will generalize well. The criterion also does not determine how a numeric predictor’s candidate cut points are generated, how categorical predictor levels are grouped, or when tree growth should stop. Those are separate modeling decisions.
A useful calculation sequence is:
Check that the class counts add to the parent size, then calculate each parent class proportion and its Gini impurity.
Use the proportions within that child, not the proportions from the parent.
Multiply each child impurity by \(n_j/n\), and sum the weighted terms.
Compute parent impurity minus weighted child impurity for each candidate. Select the larger reduction when the decision is based on this criterion.
Common errors are using percentages from the parent to calculate a child’s impurity, forgetting a class when it has a zero count in one child, and averaging child impurities without weights. Another is reporting the weighted child impurity as though it were the reduction: the reduction is the parent value minus that weighted value. Keep the two quantities distinct, and retain exact fractions through the calculation when possible before rounding.
Check Your Understanding
For each problem, calculate with the stated class counts and round decimal results to four places where needed.
- A parent has 5 “approve” and 3 “decline” observations. A split gives children (4 approve, 1 decline) and (1 approve, 2 decline). Find the parent impurity, weighted child impurity, and reduction. (Answer: Parent \(15/32=0.4688\); weighted child impurity \(11/30=0.3667\); reduction \(49/480=0.1021\).)
- A parent has three classes with counts (4, 2, 2). A split produces children (3, 1, 0) and (1, 1, 2). Find the Gini reduction. (Answer: Parent \(5/8=0.6250\); weighted child impurity \(1/2=0.5000\); reduction \(1/8=0.1250\).)
- A parent has 8 positive and 4 negative cases. Candidate A gives children (6, 2) and (2, 2); Candidate B gives (7, 1) and (1, 3). Calculate both reductions and select the larger one. (Answer: Candidate A \(1/36=0.0278\); Candidate B \(25/144=0.1736\); choose Candidate B.)
- A parent has 7 “clear” and 3 “flagged” cases. A split gives children (6, 2) and (1, 1). A candidate calculation reports the unweighted child average, \(0.4375\), as the weighted impurity. Give the correct weighted impurity and reduction. (Answer: Weighted impurity \(0.4000\); reduction \(0.0200\).)
- A parent has class counts (5, 3, 2). Candidate X gives children (4, 1, 0) and (1, 2, 2); Candidate Y gives children (3, 0, 0) and (2, 3, 2). Calculate the reduction for each and choose the larger. (Answer: Candidate X \(0.1400\); Candidate Y \(57/350\approx0.1629\); choose Candidate Y.)