Tutorials › Exam SRM - Statistics for Risk Modeling › Deriving Weighted Impurity Reduction

Home  /  Tutorials  /  Exam SRM / Classification Trees and Pruning

Exam SRM · Classification Trees and Pruning · Tutorial 578 of 926

Deriving Weighted Impurity Reduction

See why a split’s child impurities must be weighted by node size, then calculate and interpret the resulting impurity reduction.

Intermediate 10 min read

What You'll Learn

  • Define the parent impurity, child impurities, and split gain
  • Derive child-node weights from the probability that a case enters each child
  • Calculate weighted impurity reduction for binary and multiclass examples
  • Explain why an unweighted average can misrepresent a split
  • Check split calculations and interpret zero or positive gain

Why Child-Node Sizes Matter

A classification-tree split partitions the cases in a parent node among two or more child nodes. Those children may have different sizes. If one child contains most of the cases, its class composition should have more influence on the split’s overall assessment than the composition of a very small child. The standard calculation captures this by weighting each child’s impurity by its share of the parent’s cases.

This tutorial derives that weighting and the resulting split-gain formula. It applies whether the impurity measure is Gini impurity, entropy, or another suitable measure based on class proportions. The weighting argument is separate from how a particular impurity measure is defined.

Definition: Let a parent node contain \(n\) cases and have impurity \(I(P)\). A split creates \(K\) child nodes. Child \(j\) contains \(n_j\) cases and has impurity \(I(C_j)\), where \(\sum_{j=1}^{K} n_j=n\). The child’s weight is its case share, \(n_j/n\). The split’s weighted child impurity is \(\sum_{j=1}^{K}(n_j/n)I(C_j)\), and the impurity reduction, or split gain, is \(\displaystyle I(P)-\sum_{j=1}^{K}(n_j/n)I(C_j)\).

All impurity values in a calculation must use the same impurity measure. The case counts determine the weights; they are not themselves impurity values. A child with twice as many cases as another receives twice the weight, regardless of how pure or impure either child is.

Deriving the Weighted Average and Gain

The weighting follows from considering a case selected at random from the parent. The probability that this case belongs to child \(j\) is \(n_j/n\). If the selected child is assigned its child-node impurity as a score, the expected score is the probability-weighted average of the children’s scores.

$$ P(\text{selected case is in child }j)=\frac{n_j}{n}, \qquad E[\text{child impurity}] =\sum_{j=1}^{K}\frac{n_j}{n}I(C_j). $$

The split is assessed by comparing the parent’s impurity with this expected child impurity. Subtracting the latter from the former gives the reduction:

$$ \operatorname{Gain} =I(P)-\sum_{j=1}^{K}\frac{n_j}{n}I(C_j). $$

The same formula can be understood by putting the node scores on a total-case scale. The parent’s impurity contribution is \(nI(P)\), and the children’s combined contribution is \(\sum_{j=1}^{K}n_jI(C_j)\). Dividing the difference by \(n\) gives the gain per parent case. This interpretation explains why adding child impurities without accounting for node size is not a comparable calculation.

Key result: Each child impurity is multiplied by the fraction of the parent’s cases in that child. The weights sum to one: \(\sum_{j=1}^{K}n_j/n=1\). Therefore the weighted child impurity is an average on the same per-case scale as the parent impurity.

For standard concave impurity measures based on class proportions, the weighted child impurity cannot exceed the parent impurity when the children partition the parent cases. To see why, let \(\boldsymbol{p}_j\) be the vector of class proportions in child \(j\). The parent’s class-proportion vector is the weighted mixture \(\boldsymbol{p}=\sum_j(n_j/n)\boldsymbol{p}_j\). Concavity of the impurity function \(I\) gives

$$ I(\boldsymbol{p}) \geq I\left(\sum_{j=1}^{K}\frac{n_j}{n}\boldsymbol{p}_j\right) \geq \sum_{j=1}^{K}\frac{n_j}{n}I(\boldsymbol{p}_j), $$

where the first expression is simply \(I(\boldsymbol{p})\), and the final expression is the weighted child impurity. Thus gain is nonnegative for these standard measures in the ordinary partition setting. A gain of zero occurs when the children have the same class proportions as the parent, so the split has not improved class separation under that impurity measure.

Worked Calculations

Worked Example: A Small Child and a Large Child

A hypothetical claims-screening tree has 80 cases in a parent node. Using one fixed impurity measure, the parent impurity is 0.40. A proposed split creates a child of 20 cases with impurity 0.10 and a child of 60 cases with impurity 0.35. Calculate the weighted child impurity and gain. Also calculate the result from incorrectly giving the two children equal weights.

Method. First calculate each child’s share of the parent: \(20/80=0.25\) and \(60/80=0.75\). The weights sum to \(0.25+0.75=1\).

Weighted child impurity. Multiply each child impurity by its case share:

$$ \frac{20}{80}(0.10)+\frac{60}{80}(0.35) =0.25(0.10)+0.75(0.35) =0.025+0.2625 =0.2875. $$

Gain. Subtract the weighted child impurity from the parent impurity: \(0.40-0.2875=0.1125\). The split reduces impurity by 0.1125.

Equal-weight error. Treating the children as equally important gives \((0.10+0.35)/2=0.2250\) as the child average, and then \(0.40-0.2250=0.1750\) as the apparent gain. This overstates the gain because it gives the 20-case child the same influence as the 60-case child. The correct gain is 0.1125, not 0.1750. The common mistake avoided here is averaging child impurities without using their case counts.

Check. The weighted child impurity, 0.2875, is below the parent impurity, 0.40, and their difference is exactly 0.1125.

Worked Example: Three Unequal Children

A hypothetical policy-review node contains 120 cases. Its impurity is 0.42. A proposed partition produces children with case counts 90, 20, and 10, and respective impurity values 0.34, 0.45, and 0.60. Find the weighted child impurity and gain.

Method. The child weights are \(90/120=0.75\), \(20/120=1/6\), and \(10/120=1/12\). They sum to \(0.75+1/6+1/12=9/12+2/12+1/12=1\).

Apply the weights to the corresponding impurity values:

$$ \begin{aligned} I_{\text{children}} &=\frac{90}{120}(0.34)+\frac{20}{120}(0.45)+\frac{10}{120}(0.60)\\ &=0.75(0.34)+\frac{1}{6}(0.45)+\frac{1}{12}(0.60)\\ &=0.255+0.075+0.050\\ &=0.3800. \end{aligned} $$

The gain is \(0.42-0.3800=0.0400\). The split reduces impurity by 0.0400. Notice that two smaller children are more impure than the parent, but the 90-case child has most of the weight. The correct weighted result is 0.3800, not the simple average \((0.34+0.45+0.60)/3=0.4633\). That unweighted calculation would give an apparent gain of \(0.42-0.4633=-0.0433\), which does not represent the case-weighted split assessment.

Check. The weighted contributions sum to \(0.255+0.075+0.050=0.3800\); subtracting from 0.42 gives 0.0400.

Worked Example: Computing Impurity From Class Counts

A hypothetical three-class triage node contains 40 cases: 20 in class A and 20 in class B, with none in class C. Use Gini impurity, \(I=1-\sum_k p_k^2\), to calculate the parent impurity and the weighted child impurity for a split whose children have these class counts: child 1 has 8 A and 2 B; child 2 has 10 A and 10 B; child 3 has 2 A and 8 B. There are no class C cases in the children.

Parent impurity. The class proportions are \(20/40=0.5\), \(20/40=0.5\), and \(0/40=0\). Therefore \(I(P)=1-(0.5^2+0.5^2+0^2)=1-(0.25+0.25)=0.50\).

Child 1. Its size is \(8+2=10\), and its proportions are 0.8, 0.2, and 0. Its Gini impurity is \(1-(0.8^2+0.2^2+0^2)=1-(0.64+0.04)=0.32\).

Child 2. Its size is \(10+10=20\), and its proportions are 0.5, 0.5, and 0. Its impurity is \(1-(0.25+0.25)=0.50\).

Child 3. Its size is \(2+8=10\), and its proportions are 0.2, 0.8, and 0. Its impurity is \(1-(0.04+0.64)=0.32\).

Weight and combine. The child weights are \(10/40=0.25\), \(20/40=0.50\), and \(10/40=0.25\). Thus \(I_{\text{children}}=0.25(0.32)+0.50(0.50)+0.25(0.32)=0.08+0.25+0.08=0.41\). The gain is \(0.50-0.41=0.09\).

Check. The weights total 1, and the gain equals parent impurity minus weighted child impurity: \(0.50-0.41=0.09\). The common mistake avoided is using the class counts to compute child impurities but then forgetting to weight those impurities by the child sizes.

What the Gain Does and Does Not Say

Gain is a per-case comparison of a parent node with the children produced by a particular split. A larger positive gain means a larger reduction under the chosen impurity measure for that partition. The formula does not say that every child must be less impure than its parent: as the second worked example shows, an individual child can have greater impurity while the weighted average of all children is lower.

The calculation also depends on the cases assigned to each child. If the child counts do not add to the parent count, then the partition or the arithmetic needs checking before calculating gain. If a node has no cases, its case share is zero, but such a node is not a meaningful child for an ordinary split. Use a single impurity measure throughout a comparison; subtracting a weighted Gini average from a parent entropy value, for example, has no valid interpretation.

Common Mistakes

  • Giving each child equal weight. The weight is \(n_j/n\), not \(1/K\), unless all \(K\) children have the same number of cases.
  • Using child counts as weights without dividing by the parent count. The weights must sum to one. If using the total-case scale instead, compare \(nI(P)\) with \(\sum_j n_jI(C_j)\) consistently.
  • Reversing the subtraction. Gain is parent impurity minus weighted child impurity. A positive value represents a reduction.
  • Comparing incompatible impurity measures. Parent and child values in one gain calculation must be computed using the same measure.
  • Assuming every child must improve. The criterion compares the parent with the weighted average of its children, not each child separately.
Key takeaway: A child’s influence is proportional to the fraction of parent cases it contains. Calculate the weighted child impurity first, then subtract it from parent impurity. This produces a gain on a consistent per-case scale.

Check Your Understanding

For each problem, use the stated impurity values with one consistent impurity measure. Check that the child weights sum to one before finding gain.

  1. A parent has 50 cases and impurity 0.36. Its children have 10 cases with impurity 0.10 and 40 cases with impurity 0.30. Find the weighted child impurity, the correct gain, and the gain from incorrectly using equal child weights. (Answer: weighted impurity \(=0.2600\); correct gain \(=0.1000\); equal-weight gain \(=0.1600\))
  2. A 100-case parent has impurity 0.48. A split creates children of sizes 70 and 30 with impurities 0.40 and 0.50. Find the weighted child impurity and gain. (Answer: weighted impurity \(=0.4300\); gain \(=0.0500\))
  3. A parent has impurity 0.50 and is divided into three children: 40 cases with impurity 0.20, 30 with impurity 0.40, and 30 with impurity 0.60. Calculate the weighted child impurity and gain. (Answer: weighted impurity \(=0.3800\); gain \(=0.1200\))
  4. Two candidate partitions of the same parent have impurity 0.45. Partition A has child sizes 20 and 80 with impurities 0.15 and 0.42. Partition B has child sizes 50 and 50 with impurities 0.30 and 0.38. Calculate each gain and state which has the larger gain. (Answer: A weighted impurity \(=0.3660\), gain \(=0.0840\); B weighted impurity \(=0.3400\), gain \(=0.1100\); B has the larger gain)
  5. A parent has 100 cases and impurity 0.42. Its children have 5 cases with impurity 0.00 and 95 cases with impurity 0.40. Calculate the weighted child impurity and correct gain, then compare with the gain obtained by using an unweighted average. (Answer: weighted impurity \(=0.3800\); correct gain \(=0.0400\); unweighted-average gain \(=0.2200\))

Previous

Next

Back to Tutorials
Clinical Biostats