Decision Tree Threshold Search & Edge Cases

September 2026 · 5 min read

Training chooses a threshold by comparing the groups it creates. The useful question is “which rows change sides?” Once that is clear, a huge feature range and repeated values become straightforward to handle.

Try one boundary per observed gap

Suppose the sorted feature values are [2, 2, 5, 11, 1000000000]. Use the rule x < threshold to send a row left. These three thresholds produce all possible nonempty partitions:

Between 5 and 11, any threshold greater than 5 and at most 11 gives the same training partition. A midpoint is a convenient representative. Its precise position can still affect predictions for future rows inside that gap.

Move rows once instead of rebuilding each child

Start with every row on the right. Move equal-valued groups to the left in sorted order, updating the two children’s label counts. Score the boundary only when both children satisfy the leaf-size limit.

sort rows by this feature
left = empty; right = all rows
for each group of equal values:
    move the group from right to left
    if right is empty: stop
    if either child is too small: continue
    score the weighted child impurity
    keep the best boundary seen so far

Repeat for each feature. The impurity chapter supplies the score; the number of candidates depends on distinct observed values, not the size of the numeric range.

Equal values must stay together

The two rows with value 2 cannot be separated by a threshold on this feature, even if their labels differ. Another feature might distinguish them. If their entire feature vectors are identical, feature tests cannot resolve conflicting labels.

Make the stored threshold match the scored partition

For finite adjacent distinct values low < high, our strict < rule needs low < threshold <= high. Floating-point arithmetic can round a midpoint to an endpoint. Also, both (low + high) / 2 and low + (high - low) / 2 can overflow on some finite inputs.

In C++20, std::midpoint from <numeric> avoids arithmetic overflow. Guard against rounding to the lower endpoint:

double threshold = std::midpoint(low, high);
if (!(threshold > low)) threshold = high;

This keeps the training partition correct for the stated comparison rule. An implementation using <= needs the corresponding opposite endpoint convention.

Decide these behaviors explicitly

Keep the search; change its statistics

Classification uses label counts to score impurity. Squared-error regression uses counts and target statistics to score deviations from each child’s mean. Both can use the same sorted boundaries. When maintaining sums and squared sums, account for floating-point cancellation on large, nearly equal targets.

Connect the search to a complete tree

The C++ tree series covers recursive construction. Use the boundary rules here when reviewing its split-search code, then continue to training cost and pruning.

Sources and next steps

• Decision-tree split formulation — Candidate partitions and weighted child impurity.
• C++ standard draft: midpoint — Overflow and rounding guarantees of std::midpoint.