Why Threshold Search Matters
A regression tree makes predictions by dividing observations into groups. For a numeric predictor, the tree must decide where to place a cut: for example, whether a hypothetical insurance policy’s annual mileage is at most a threshold or above it. A useful cut places observations with similar outcomes together, so that the squared errors around the groups’ means are small.
Searching thresholds is a finite calculation, not a matter of guessing a plausible cut from a graph. Sort the observed predictor values, form one candidate between each adjacent pair of distinct values, and calculate the reduction in squared error for each candidate. This tutorial considers one numeric predictor at a time. It does not address how to compare predictors.
The predictor determines which observations go into each child; the outcomes determine how good that division is. For any group \(G\), its sum of squared errors is \(SSE(G)=\sum_{i\in G}(y_i-\bar y_G)^2\), where \(\bar y_G\) is the mean outcome in that group. The parent error is calculated before splitting; the split error is the sum of the two child errors.
From Sorted Values to Candidate Thresholds
First sort the predictor values and remove duplicates for the purpose of finding candidate locations. If the distinct values are \(z_1<z_2<\cdots<z_k\), the usual candidate thresholds are the midpoints \(c_j=(z_j+z_{j+1})/2\), for \(j=1,\ldots,k-1\). Each candidate separates the observations at one adjacent gap. A midpoint is a convenient representative: any threshold strictly between the same adjacent values assigns exactly the same observations to each child and therefore gives the same squared-error reduction.
There are \(k-1\) candidate splits when there are \(k\) distinct values. A threshold below the smallest observed value or at or above the largest observed value would leave one child empty, so it is not a valid binary split. If there is only one distinct predictor value, no threshold can divide the node into two nonempty children.
The squared-error reduction for a candidate \(c\) is \(\Delta(c)=SSE(\text{parent})-SSE(\text{left})-SSE(\text{right})\). Because the parent error is the same for every candidate, maximizing \(\Delta(c)\) is equivalent to minimizing the sum of the child errors. Calculate the parent error once, then compare each candidate’s child-error total against it.
Why the Reduction Formula Works
The split reduction can also be written using the child sample sizes and means. This equivalent form helps check a calculation, but the direct SSE calculation remains a clear way to score candidate thresholds.
Here \(n_L,n_R\) are the numbers of observations in the left and right children, and \(\bar y_L,\bar y_R\) are their outcome means. To justify the identity, write the parent mean as the size-weighted average of the child means. For each child, expand the squared deviations around its own mean; the cross-product terms sum to zero because deviations from that child mean sum to zero. Thus the parent SSE equals the sum of the two child SSEs plus the squared deviations of the child means from the parent mean, weighted by child size.
The result shows why a large difference between child means can yield a strong split, but the child sizes matter too. A small group can make a seemingly large mean difference less influential than it first appears. The identity is valid for squared-error splitting with nonempty children and child means as predictions; it is not a formula for classification-tree impurity measures.
Scoring Every Candidate
Worked Example: Finding the Best Gap in a Mileage Predictor
A hypothetical training node contains five policies. The predictor \(x\) is annual mileage in thousands of miles, and \(y\) is a continuous claim-cost measure in thousands of dollars. The observations, already sorted by mileage, are \((1,1),(3,2),(6,3),(8,9),(11,10)\). Find the best threshold for this predictor using squared-error reduction. These are hypothetical training values; no interest rate, mortality assumption, or probability distribution is assumed.
Method. Form a midpoint at each adjacent mileage gap, calculate parent SSE, then calculate both child SSEs and the reduction for every candidate. This avoids choosing a cut based only on visual appearance or on a large difference between two neighboring outcomes.
The distinct predictor values are \(1,3,6,8,11\), so the four candidate thresholds are \(2,4.5,7,9.5\). The parent outcome mean is \((1+2+3+9+10)/5=5\). Therefore the parent SSE is \((1-5)^2+(2-5)^2+(3-5)^2+(9-5)^2+(10-5)^2=16+9+4+16+25=70\).
At \(c=2\), the left outcomes are \([1]\), with SSE \(0\). The right outcomes are \([2,3,9,10]\), with mean \(24/4=6\) and SSE \(16+9+9+16=50\). Total child SSE is \(50\), so \(\Delta(2)=70-50=20\).
At \(c=4.5\), the left outcomes are \([1,2]\), with mean \(1.5\) and SSE \(0.25+0.25=0.5\). The right outcomes are \([3,9,10]\), with mean \(22/3\). Their SSE is \(169/9+25/9+64/9=258/9=86/3\). Total child SSE is \(0.5+86/3=175/6\), so \(\Delta(4.5)=70-175/6=245/6\), or approximately \(40.8333\).
At \(c=7\), the left outcomes are \([1,2,3]\), with mean \(2\) and SSE \(1+0+1=2\). The right outcomes are \([9,10]\), with mean \(9.5\) and SSE \(0.25+0.25=0.5\). Total child SSE is \(2.5\), so \(\Delta(7)=70-2.5=67.5\).
At \(c=9.5\), the left outcomes are \([1,2,3,9]\), with mean \(15/4=3.75\) and SSE \(7.5625+3.0625+0.5625+27.5625=38.75\). The right outcome is \([10]\), with SSE \(0\). Thus \(\Delta(9.5)=70-38.75=31.25\).
Check and conclusion. The reductions are \(20,\ 40.8333,\ 67.5,\ 31.25\), so the greatest is \(67.5\) at \(c=7\). The split assigns mileages \(1,3,6\) to the left and \(8,11\) to the right, as required by the sorted values. The common mistake avoided here is treating the largest gap between predictor values as automatically the best cut; the scores depend on the outcomes, not on gap width.
Worked Example: Comparing Nearby Gaps With Similar Outcomes
A hypothetical node records a numeric predictor \(x\), measured in tens of service visits, and a continuous outcome \(y\), measured in thousands of dollars. Its sorted observations are \((10,4),(20,5),(30,5),(40,12)\). Find the threshold with the largest squared-error reduction. No probability distribution or insurance payment assumption is used.
Method. Score all three adjacent gaps. In particular, do not assume that an observation with a repeated outcome has to be assigned to one side or the other; the predictor threshold determines the assignments.
The candidate thresholds are \(15,25,35\). The parent mean is \((4+5+5+12)/4=6.5\), and the parent SSE is \(6.25+2.25+2.25+30.25=41\).
At \(c=15\), the left SSE for \([4]\) is \(0\). The right outcomes \([5,5,12]\) have mean \(22/3\). Their SSE is \(49/9+49/9+196/9=294/9=98/3\). The reduction is \(41-98/3=25/3\), or approximately \(8.3333\).
At \(c=25\), the left outcomes \([4,5]\) have mean \(4.5\) and SSE \(0.25+0.25=0.5\). The right outcomes \([5,12]\) have mean \(8.5\) and SSE \(12.25+12.25=24.5\). Total child SSE is \(25\), giving reduction \(41-25=16\).
At \(c=35\), the left outcomes \([4,5,5]\) have mean \(14/3\) and SSE \(4/9+1/9+1/9=2/3\). The right outcome \([12]\) has SSE \(0\). The reduction is \(41-2/3=121/3\), or approximately \(40.3333\).
Check and conclusion. The reductions \(8.3333,16,40.3333\) show that \(c=35\) is best for this predictor. The right child contains one observation, which is nonempty and therefore a valid split under the stated calculation. A separate tree-growing rule could impose a minimum child size, but that is not part of this threshold-scoring calculation.
Worked Example: Checking a Candidate Set on an Irregular Scale
A hypothetical node contains observations \((x,y)=(0,3),(1,4),(5,4),(9,8),(10,9)\). The predictor is recorded in arbitrary numeric units, and the continuous outcome is in thousands of dollars. Identify and score the candidate threshold at \(7\), then compare it with the other candidates. No distribution, interest rate, or mortality assumption is specified.
Method. Use the same midpoint-and-SSE procedure even though the gaps between predictor values are unequal. This prevents the common mistake of using a fixed increment, such as testing every integer, rather than testing each distinct adjacent gap.
The candidate thresholds are \(0.5,3,7,9.5\). The parent mean is \((3+4+4+8+9)/5=5.6\), and its SSE is \(6.76+2.56+2.56+5.76+11.56=29.2\).
At \(c=0.5\), the left SSE is \(0\). The right outcomes \([4,4,8,9]\) have mean \(25/4=6.25\) and SSE \(5.0625+5.0625+3.0625+7.5625=20.75\). The reduction is \(29.2-20.75=8.45\).
At \(c=3\), the left outcomes \([3,4]\) have mean \(3.5\) and SSE \(0.5\). The right outcomes \([4,8,9]\) have mean \(7\) and SSE \(9+1+4=14\). The total child SSE is \(14.5\), so the reduction is \(29.2-14.5=14.7\).
At \(c=7\), the left outcomes \([3,4,4]\) have mean \(11/3\) and SSE \(4/9+1/9+1/9=2/3\). The right outcomes \([8,9]\) have mean \(8.5\) and SSE \(0.25+0.25=0.5\). Total child SSE is \(2/3+1/2=7/6\), so the reduction is \(29.2-7/6=841/30\), approximately \(28.0333\).
At \(c=9.5\), the left outcomes \([3,4,4,8]\) have mean \(19/4=4.75\) and SSE \(3.0625+0.5625+0.5625+10.5625=14.75\). The right SSE is \(0\), so the reduction is \(29.2-14.75=14.45\).
Check and conclusion. The largest reduction is approximately \(28.0333\), at \(c=7\). The result is consistent with the allocation: the three lower outcomes are grouped together, and the two higher outcomes form the other child. The common mistake avoided is to assume that irregularly spaced predictor values require a special scoring formula; only the candidate midpoints change.
Common Mistakes and Practical Checks
A threshold search is short enough to audit systematically. Before selecting a cut, check that every candidate separates two nonempty groups, that the sorted order has been used correctly, and that each child mean was calculated from the outcomes assigned to that child. A calculation that uses the predictor values in the SSE instead of the outcomes is scoring separation in the wrong quantity.
- Testing values rather than gaps. The standard candidate set has one midpoint per adjacent pair of distinct observed predictor values, not one candidate for every possible numerical value.
- Forgetting the split convention. With the rule \(x_i\le c\) on the left and \(x_i>c\) on the right, a midpoint between adjacent values assigns the lower value left and the higher value right.
- Comparing child SSEs without the same parent baseline. The parent SSE is constant across candidates, so the smallest child-error total and the largest reduction identify the same split.
- Rounding intermediate values too soon. Keep exact fractions or sufficient precision for child means and SSEs, then round only when reporting a final decimal. Close candidate scores can otherwise be misordered.
- Overstating what the best threshold means. It is the best split for the current node and this predictor under squared error. It is not necessarily the best predictor, nor does it by itself establish that the split will perform well on new observations.
In practice, the threshold search is a greedy local calculation: it chooses the best immediate reduction among the candidates being considered. Its value is that it turns a potentially continuous search into a finite, reproducible comparison. The same procedure can be applied again at a later node, using only the observations that reach that node.
Check Your Understanding
For each problem, use the stated squared-error criterion and show the candidate thresholds before choosing a split.
- A node has sorted pairs \((x,y)=(2,1),(5,4),(8,10)\). Calculate the reduction at each candidate and identify the best threshold. (Answer: Candidates \(3.5\) and \(6.5\); reductions \(24\) and \(37.5\), respectively; best threshold \(6.5\).)
- A node has sorted pairs \((1,2),(2,3),(4,3),(7,8)\). Find the candidate with the largest reduction. (Answer: Candidates \(1.5,3,5.5\); reductions \(32/3,9,64/3\), respectively; best threshold \(5.5\).)
- A node has sorted pairs \((0,0),(4,2),(6,8),(12,10)\). Compute the parent SSE and choose the best candidate threshold. (Answer: Parent SSE \(68\); candidates \(2,5,9\); reductions \(100/3,64,100/3\), respectively; best threshold \(5\).)
- A node has five observations whose predictor values are \(3,3,6,10,10\). How many candidate thresholds are there, and where are they? (Answer: Two candidates, \(4.5\) and \(8\), formed between the distinct values \(3,6,10\).)
- All observations in a node have predictor value \(12\), but their outcomes vary. Can this predictor produce a valid threshold split at this node? (Answer: No; there is only one distinct predictor value, so no threshold creates two nonempty children.)