Why a Small Change Can Reshape a Tree
A decision tree is built through a sequence of local choices. At each node, the fitting procedure considers eligible splits and selects one that improves a chosen criterion, subject to constraints such as minimum node size. The next split is then selected using only the observations that reached each child. This recursive process makes a tree easy to interpret, but it can also make its structure sensitive to the data.
A small change matters most when it changes which candidate split is best near the root. Because the root determines which observations reach every later node, a different root can create different child samples, different opportunities for splitting, and different terminal-node rules. This does not mean that every small data change will produce a substantially different tree. It means that a tree’s structure is not guaranteed to change smoothly as the data change.
The examples below focus on the mechanism, not on assessing stability across repeated perturbations. In each case, compare the candidate splits using the same criterion before and after the data change. The key is to recompute the quantities for the changed data rather than carrying forward an old split score.
How a Root Choice Controls Later Rules
For a regression tree, a common split criterion is the reduction in within-node sum of squared errors. For a node containing responses \(y_1,\ldots,y_n\), its prediction is the node mean \(\bar{y}\), and its sum of squared errors is \(\sum_{i=1}^{n}(y_i-\bar{y})^2\). A candidate split is preferred when its children have a smaller total sum of squared errors.
Worked Example: One Changed Response Reverses the Root Split
A hypothetical pricing team fits a regression tree to four policy records. Predictor \(X\) divides records 1 and 2 from records 3 and 4. Predictor \(Z\) divides records 1 and 3 from records 2 and 4. The responses are claim-cost indices, in thousands of dollars. Compare the root splits before and after record 4’s response changes.
| Record | \(X\) | \(Z\) | Original response | Changed response |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 1 | 0 | 1 | 1 |
| 4 | 1 | 1 | 1 | -1 |
Original data. The parent mean is \((0+0+1+1)/4=0.5\), so the parent sum of squared errors is \(4(0.5^2)=1\). Splitting on \(X\) gives child responses \([0,0]\) and \([1,1]\), each with sum of squared errors 0. The total is 0, so the reduction is \(1-0=1\). Splitting on \(Z\) gives \([0,1]\) and \([0,1]\). Each pair has mean \(0.5\) and sum of squared errors \((0-0.5)^2+(1-0.5)^2=0.5\). The children total \(1\), giving a reduction of \(1-1=0\). The root split is \(X\).
After the response changes. The responses are now \([0,0,1,-1]\). Their mean is 0 and the parent sum of squared errors is \(0^2+0^2+1^2+(-1)^2=2\). Under \(X\), the children are \([0,0]\) and \([1,-1]\). Their means are 0 and 0, so their total sum of squared errors is \(0+2=2\), a reduction of 0. Under \(Z\), the children are \([0,1]\) and \([0,-1]\). Their means are \(0.5\) and \(-0.5\); each child has sum of squared errors \(0.5\). The total is 1, so the reduction is \(2-1=1\). The root is now \(Z\).
The downstream rules differ too. With the changed data, splitting each \(Z\) child on \(X\) separates the remaining pairs into single records. The resulting rules are \(Z=0\) and \(X=0\), predict 0; \(Z=0\) and \(X=1\), predict 1; \(Z=1\) and \(X=0\), predict 0; and \(Z=1\) and \(X=1\), predict -1. With the original responses, the \(X\) root already creates two constant-response children. The example uses deliberately tiny data to make the mechanism visible: one changed response alters the preferred root and hence the paths used to describe predictions.
Method and mistake avoided. The method is to recompute the parent and child sums of squared errors for every candidate using the same response values. A tempting but wrong shortcut is to retain the original root score after changing record 4; that score no longer describes the changed data.
Small Changes Can Move a Numeric Threshold
For a numeric predictor, candidate splits are often formed between adjacent observed predictor values. Changing a response can change which candidate threshold has the largest reduction in error, even when all predictor values remain fixed. The chosen threshold affects not only which child receives each observation, but also how a reader interprets the resulting rule.
Worked Example: A Changed Outcome Moves the Best Cut Point
A hypothetical analyst fits a regression tree to four records with predictor values \(x=1,2,3,4\) and responses \([0,0,10,10]\). Candidate thresholds are the midpoints \(1.5\), \(2.5\), and \(3.5\). Then the response for \(x=2\) changes from 0 to 9. Find the best root threshold before and after the change.
Before the change. The parent mean is \((0+0+10+10)/4=5\), and the parent sum of squared errors is \(4(5^2)=100\). At threshold \(2.5\), the children are \([0,0]\) and \([10,10]\), with total sum of squared errors 0, so the reduction is 100. At threshold \(1.5\), the children are \([0]\) and \([0,10,10]\). The second child mean is \(20/3\); its sum of squared errors is \(400/9+100/9+100/9=600/9\), or \(66.6667\). The reduction is \(100-600/9=33.3333\). At threshold \(3.5\), the children are \([0,0,10]\) and \([10]\). The first child mean is \(10/3\), giving sum of squared errors \(100/9+100/9+400/9=600/9\); the reduction is again \(33.3333\). Thus \(2.5\) is the best threshold.
After the change. The responses are \([0,9,10,10]\). At \(1.5\), the children are \([0]\) and \([9,10,10]\). The second mean is \(29/3\), and its sum of squared errors is \((9-29/3)^2+(10-29/3)^2+(10-29/3)^2=2/3\). At \(2.5\), the children are \([0,9]\), with mean \(4.5\) and sum of squared errors \(40.5\), and \([10,10]\), with sum of squared errors 0. The total is \(40.5\). At \(3.5\), the first child is \([0,9,10]\), with mean \(19/3\) and sum of squared errors \((361+64+121)/9=546/9=60.6667\); the other child has error 0. The smallest child total is \(2/3\), so the best threshold moves to \(1.5\).
The parent mean after the change is \(29/4=7.25\), and its sum of squared errors is \(70.75\). Therefore, the chosen threshold’s reduction is \(70.75-2/3=70.0833\), confirming it is a substantial improvement over the unsplit node. A rule that previously separated the two low responses from the two high responses now separates \(x=1\) from all larger values. The changed response has altered the fitted rule, not the predictor measurements.
Method and mistake avoided. The method is to calculate each candidate’s child errors using the changed response and then compare totals. Do not assume that the original threshold remains optimal merely because the predictor values and their order have not changed.
Classification Splits: Weight Each Child Correctly
Classification trees also make local split choices, but their criterion concerns class composition rather than response means. One commonly used impurity measure is Gini impurity. If the proportions of classes in a node are \(p_1,\ldots,p_K\), its Gini impurity is \(1-\sum_{k=1}^{K}p_k^2\). A candidate split’s weighted child impurity is the sum of each child’s impurity multiplied by that child’s fraction of the parent observations. The split gain is parent impurity minus weighted child impurity.
Worked Example: One Relabeled Case Changes the Classification Root
A hypothetical review team classifies four applications as having an event (1) or not having an event (0). Candidate split \(A\) divides records 1 and 2 from records 3 and 4. Candidate split \(B\) isolates record 1 from records 2, 3, and 4. Compare the Gini gains before and after record 2 is relabeled from event to no event.
Before the change. The labels are \([1,1,0,0]\), so the parent has class proportions \(1/2\) and \(1/2\), and impurity \(1-(1/2)^2-(1/2)^2=0.5\). Split \(A\) produces two pure children, so its weighted child impurity is 0 and its gain is 0.5. Split \(B\) produces a pure event child of size 1 and a child of size 3 with proportions \(1/3\) and \(2/3\). The latter impurity is \(1-(1/3)^2-(2/3)^2=4/9\). Its weighted child impurity is \((1/4)(0)+(3/4)(4/9)=1/3\), so its gain is \(0.5-1/3=1/6\). The selected root is \(A\).
After the change. The labels are \([1,0,0,0]\), so the parent proportions are \(1/4\) and \(3/4\), with impurity \(1-(1/4)^2-(3/4)^2=0.375\). Under \(A\), the first child has labels \([1,0]\) and impurity \(0.5\); the second is pure. The weighted child impurity is \((2/4)(0.5)+(2/4)(0)=0.25\), so the gain is \(0.375-0.25=0.125\). Under \(B\), both children are pure, so the weighted child impurity is 0 and the gain is 0.375. The selected root changes to \(B\).
Under the original root \(A\), the rule for records 1 and 2 predicts event. Under the changed root \(B\), the rule for records 2, 3, and 4 predicts no event. Thus record 2 itself moves from a child predicting event to a child predicting no event. This is a concrete example of one changed label altering both a root choice and a downstream classification rule.
Method and mistake avoided. The method is to recompute the parent impurity, each child impurity, and the child-size weights after the label changes. A common wrong calculation for split \(B\) before the change is to average the child impurities equally: \((0+4/9)/2=2/9\). That treats a one-record child as if it were as large as the three-record child. The correct weighted value is \((1/4)(0)+(3/4)(4/9)=1/3\), which gives the correct gain \(1/6\).
What to Conclude From a Changed Tree
These examples illustrate three related reasons small changes can matter. First, candidate split scores may be close, so a modest change in one score can reverse the ranking. Second, numeric thresholds are selected from the observed predictor values, while their quality depends on the outcomes in the resulting groups. Third, a changed root creates new child samples, and every later split is selected within those changed samples.
A structural difference is not, by itself, proof that one fitted tree is wrong or that its predictions must be worse. Tree fitting is a data-dependent procedure: a changed structure may have similar predictions, or it may create materially different rules for some cases. Interpret the fitted rules in the context of the data used to construct them, and distinguish changes in structure from changes in predictive performance. Assessing stability across repeated perturbations is a separate task.
- Recalculate, do not assume. After a data change, recompute candidate split scores and any relevant child sizes.
- Trace the path. A root change can alter which observations are available for every downstream rule.
- Keep the criterion consistent. Compare all candidates with the same impurity or error measure and the same weighting convention.
- Separate structure from performance. A different tree structure does not automatically establish a better or worse model.
Check Your Understanding
For each problem, calculate or reason from the stated split criterion rather than assuming the original tree structure persists.
- A regression node has responses \([2,2,6,6]\). A candidate split groups the first two responses together and the last two together. What is the parent sum of squared errors, the child total, and the reduction? (Answer: Parent sum of squared errors \(=16\); child total \(=0\); reduction \(=16\).)
- A classification node has labels \([1,1,0,0]\). A split makes two pure children. What is the parent Gini impurity and the split gain? (Answer: Parent impurity \(=0.5\); gain \(=0.5\).)
- A classification node has labels \([1,0,0,0]\). A split isolates the positive case and leaves the three negative cases together. Compute the Gini gain. (Answer: Parent impurity \(=0.375\); weighted child impurity \(=0\); gain \(=0.375\).)
- With predictor values \(1,2,3,4\) and responses \([0,0,8,8]\), compare thresholds \(1.5\), \(2.5\), and \(3.5\) using child sums of squared errors. Which threshold is best? (Answer: Threshold \(2.5\), with child total \(0\); the totals at \(1.5\) and \(3.5\) are each \(128/3\).)
- Why can changing one response alter rules several splits below the root, even if no predictor values change? (Answer: The response change can alter the selected root; that changes which records enter each child, so later split choices are made on different subsets.)