Worked Classification Tree Split Comparison

From Class Counts to a Split Decision

A classification tree partitions the predictor space into cells and assigns a class to each cell. At a node, a candidate split is useful when its two child nodes are more homogeneous in their class labels than the parent node. This tutorial works through that comparison numerically: we calculate Gini impurity and entropy before and after candidate splits, choose a threshold, and evaluate the cellwise classifier it produces.

The calculations use empirical class proportions. They therefore describe impurity in the observed sample, not the unknown population distribution. In particular, the training error of a fitted tree is not automatically its population classification risk.

Definition: For a node containing observations from $K$ classes, let $p_k$ be the proportion in class $k$, where $k=1,\ldots,K$. Its Gini impurity is $G=1-\sum_{k=1}^{K}p_k^2$. Its entropy, measured in bits, is $H=-\sum_{k=1}^{K}p_k\log_2(p_k)$, with $0\log_2(0)=0$. If a proposed split sends proportions $w_L$ and $w_R$ of the node’s observations to its left and right children, its weighted child impurity is $w_L I_L+w_R I_R$, where $I$ is the chosen impurity measure. The impurity decrease is the parent impurity minus this weighted child impurity.

A split is preferred by a specified impurity criterion when it gives the largest impurity decrease, equivalently the smallest weighted child impurity. The weights matter: a small, pure child should not count as much as a large, impure child. Gini and entropy are different measures, so their numerical decreases are not directly comparable to each other; compare candidate splits within the same measure.

Worked Data and Parent Impurity

Consider eight observations with one ordered predictor $x$ and a binary class label. The observations are listed in increasing order of $x$; a threshold $t$ sends $x\leq t$ left and $x>t$ right.

$x$	1	2	3	4	5	6	7	8
Class	A	B	A	B	A	B	A	B

Worked Example: Impurity at the Parent Node

There are four observations in class A and four in class B, so the parent proportions are $p_A=p_B=4/8=1/2$. Its Gini impurity is

G_{\mathrm{parent}}=1-\left(\frac12\right)^2-\left(\frac12\right)^2=\frac12.

The parent entropy is

H_{\mathrm{parent}}=-\frac12\log_2\left(\frac12\right)-\frac12\log_2\left(\frac12\right)=1\text{ bit}.

Both values reflect a balanced parent node. Impurity is zero for a pure node and, for two classes, is largest when the two class proportions are equal.

Compare Every Distinct Threshold

For this predictor, the distinct candidate thresholds lie between consecutive observed values: $1.5,2.5,\ldots,7.5$. At each threshold, first count the classes on each side. Then calculate each child’s impurity and weight it by its share of the eight observations. The table reports the resulting decreases, rounded to six decimal places; the accompanying calculations show how the leading values arise.

Worked Example: Comparing Gini and Entropy Decreases

At $t=1.5$, the left child contains one A and no B, while the right child contains three A and four B. The weighted child Gini impurity is

\frac18(0)+\frac78\left[1-\left(\frac37\right)^2-\left(\frac47\right)^2\right] =\frac78\cdot\frac{24}{49} =\frac37.

Thus the Gini decrease is $1/2-3/7=1/14=0.071429$. For entropy, the left child is pure, while the right child has entropy $H(3/7,4/7)$, so the decrease is

1-\frac78H\left(\frac37,\frac47\right) =0.137925381\ldots \approx 0.137925\text{ bits}.

At $t=3.5$, the children have counts $(2\text{ A},1\text{ B})$ and $(2\text{ A},3\text{ B})$. Their Gini impurities are $4/9$ and $12/25$, respectively. The weighted child value and decrease are

\frac38\cdot\frac49+\frac58\cdot\frac{12}{25} =\frac16+\frac{3}{10} =\frac{7}{15}, \qquad \frac12-\frac{7}{15}=\frac{1}{30}=0.033333.

For entropy, the child entropies are $H(2/3,1/3)$ and $H(2/5,3/5)$. The decrease is

1-\frac38H\left(\frac23,\frac13\right) -\frac58H\left(\frac25,\frac35\right) =0.048794941\ldots \approx 0.048795\text{ bits}.

The counts and decreases for all distinct thresholds are:

Threshold	Left counts (A, B)	Right counts (A, B)	Gini decrease	Entropy decrease (bits)
1.5	(1, 0)	(3, 4)	0.071429	0.137925
2.5	(1, 1)	(3, 3)	0.000000	0.000000
3.5	(2, 1)	(2, 3)	0.033333	0.048795
4.5	(2, 2)	(2, 2)	0.000000	0.000000
5.5	(3, 2)	(1, 2)	0.033333	0.048795
6.5	(3, 3)	(1, 1)	0.000000	0.000000
7.5	(4, 3)	(0, 1)	0.071429	0.137925

The zero decreases at $2.5,4.5,$ and $6.5$ follow because each child has the same balanced class proportions as the parent. The values at $5.5$ mirror those at $3.5$, and those at $7.5$ mirror the split at $1.5$. Both criteria therefore select either $1.5$ or $7.5$ as a best threshold. To make the fitted tree unique here, use the explicit tie rule “choose the smallest maximizing threshold”; the selected threshold is $1.5$.

Why the Weighted Calculation Is the Right One

The weighted child impurity is not an arbitrary convention. It is exactly the average child impurity when an observation is selected uniformly from the parent node. The following identity also explains the meaning of impurity decrease for the Gini criterion.

Result: Suppose the parent has class proportions $p_k$, and its children have proportions $w_L,w_R$ and class proportions $p_{Lk},p_{Rk}$. Assume both children are nonempty, so $w_L+w_R=1$, and $p_k=w_Lp_{Lk}+w_Rp_{Rk}$. Then the Gini decrease is $$ G_{\mathrm{parent}}-\left(w_LG_L+w_RG_R\right) =\sum_{k=1}^{K}\left[w_L(p_{Lk}-p_k)^2+w_R(p_{Rk}-p_k)^2\right]\geq 0. $$

To prove the identity, substitute $G=1-\sum_k p_k^2$ into the left-hand side. The constant terms cancel, leaving

\sum_{k=1}^{K}\left[w_Lp_{Lk}^2+w_Rp_{Rk}^2-p_k^2\right].

For each class $k$, the relation $p_k=w_Lp_{Lk}+w_Rp_{Rk}$, together with $w_L+w_R=1$, gives

w_Lp_{Lk}^2+w_Rp_{Rk}^2-p_k^2 =w_L(p_{Lk}-p_k)^2+w_R(p_{Rk}-p_k)^2.

Summing this equality over classes proves the stated formula. Each term on its right is nonnegative, so splitting cannot increase weighted child Gini impurity relative to the parent when the proportions are computed from these same observations. A zero decrease means the children have the same class proportions as the parent; a positive decrease means at least one child’s proportions differ.

Construct and Evaluate the Cellwise Classifier

After choosing a split, a classification tree still needs a class prediction in each resulting cell. Under empirical zero-one loss, the prediction that minimizes the number of misclassified observations in a cell is a class with the largest count in that cell. If several classes tie for the largest count, any of them minimizes that cell’s empirical error; a fixed tie rule can be used for reproducibility.

Result: In a cell containing $n_C$ observations, let $n_{Ck}$ be the count in class $k$. If the cell is assigned a single class label $a$, its number of training errors is $n_C-n_{Ca}$. This is minimized by any $a$ maximizing $n_{Ca}$, and the minimum empirical error proportion within the cell is $1-\max_k(n_{Ck}/n_C)$.

Indeed, assigning label $a$ correctly classifies exactly the $n_{Ca}$ observations in that class and misclassifies the other $n_C-n_{Ca}$. Minimizing this error is equivalent to maximizing $n_{Ca}$. Dividing the resulting minimum error count by $n_C$ gives the stated proportion.

Worked Example: The Selected Split’s Classifier and Training Error

The tie rule selects $t=1.5$, giving a left cell with one A and a right cell with three A and four B. The majority label on the left is A; the majority label on the right is B. The fitted cellwise classifier is therefore

\hat f(x)= \begin{cases} \mathrm{A}, & x\leq 1.5,\\ \mathrm{B}, & x>1.5. \end{cases}

It correctly classifies the single left observation and the four class-B observations on the right. It misclassifies the three class-A observations on the right. Thus its training error count is $0+3=3$, and its training error proportion is

\widehat R_{\mathrm{train}}=\frac{3}{8}=0.375.

This calculation evaluates the classifier on the eight observations used to construct it. It does not give the population risk $P\{\hat f(X)\ne Y\}$ unless additional assumptions or an independent evaluation sample justify an estimate of that risk. Nor does the selected split necessarily minimize training error among all possible tree structures: here the decision was made by maximizing impurity decrease at this node.

Reading the Comparison Carefully

The numbers show several points that matter when interpreting split calculations. First, report the criterion: “best split” is incomplete unless it means best under Gini, entropy, or another specified rule. Second, use child-size weights before comparing with the parent. Third, state how tied thresholds are handled. In this example, Gini and entropy agree on the best impurity decrease, but the two endpoint thresholds tie under each criterion.

A useful check is that each computed decrease equals parent impurity minus the weighted child value, using proportions and weights from the same node. For example, at $t=1.5$, the right child’s Gini is $24/49$, not $24/49$ multiplied by its size; the size weighting is applied once, as $7/8$. Applying the size factor twice would understate the child contribution and overstate the split’s improvement.

Common Mistakes

Taking an unweighted average of child impurities. Use each child’s fraction of the parent observations as its weight. Here the children at $t=1.5$ have sizes one and seven, not equal sizes.
Confusing impurity decrease with classification error decrease. Impurity uses the full class proportions; the majority-class training error uses only the count outside the majority class. They are different quantities.
Comparing Gini and entropy numbers as though they shared a scale. Choose the best threshold within a stated criterion. Entropy is measured in bits; Gini is not.
Reporting a unique threshold when the maximum is tied. Both endpoints maximize each criterion here. State a tie rule or report both maximizers.
Calling training error the population risk. The observed error on the fitting data is not, by itself, an unbiased or guaranteed estimate of future error.

Key takeaway: For each candidate classification split, calculate child class proportions, compute each child impurity, weight by child size, and subtract from parent impurity. Then assign each resulting cell its empirical majority class and evaluate errors separately from impurity.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

For a node with class proportions $3/5$ and $2/5$, calculate its Gini impurity and entropy.
At threshold $t=3.5$, why must the child Gini values be weighted by $3/8$ and $5/8$?
Which thresholds maximize Gini decrease in the worked data, and what tie rule was used to select one?
For the selected split, how many training observations are misclassified, and which cell contributes those errors?
Why does the observed training error $3/8$ not, without more information, equal the population classification risk?