决策树回归器连续特征最优分割点选择及相关实现疑问

Great question—this is a super practical detail that’s often glossed over in basic decision tree tutorials, so it’s totally reasonable to dig into the weeds here! Let’s break down your questions one by one, with concrete details on regression split point heuristics and the scikit-learn implementation.

First, a Quick Recap #

For classification tasks with continuous features, we can skip most split points by only checking where the target class changes (after sorting the feature). But for regression (both feature and target are continuous), every unique feature value could be a split point—and checking all of them is computationally expensive. So we need smart heuristics to narrow down candidates.

Common Heuristics for Regression Split Candidates #

Let’s cover the two main methods you mentioned, with extra detail on the second one:

Method 1: Midpoints Between Sorted Adjacent Feature Values #

This is exactly what scikit-learn uses for its DecisionTreeRegressor, and you’re spot-on about the source code observation. Here’s how it works:

1. Sort the training data by the continuous feature you’re evaluating.
2. For every pair of consecutive unique feature values, calculate their average (midpoint) as a candidate split threshold.
3. Evaluate each candidate using the regression split criterion (usually mean squared error, MSE) to pick the optimal split.

Why this works? Between two adjacent sorted feature values, the split outcome (which samples go left vs. right) won’t change—only the threshold between them matters. So we don’t need to check every single value, just these midpoints.

Method 2: Percentile-Based Candidate Selection #

This is a heuristic to cut down on candidates even more, especially for high-cardinality features (like sensor data with thousands of distinct readings). Here’s the step-by-step breakdown:

1. Sort the feature values first.
2. Compute percentiles of the feature distribution (e.g., 10th, 20th, ..., 90th—you can adjust the number for granularity).
3. Use these percentile values as your candidate split points (some implementations also add min/max to cover edge cases).
4. Evaluate each percentile threshold using MSE (or another regression criterion) to find the best split.

Practical use cases: This shines when you’re dealing with huge datasets where even checking all adjacent midpoints is slow. By using percentiles, you cap the number of candidates to a fixed number (like 10 or 20) regardless of how many unique values the feature has. The tradeoff is speed vs. split quality—fewer percentiles mean faster training, but you might miss the absolute optimal split. In practice, though, this difference is often negligible for real-world data.

Many gradient boosting libraries (like XGBoost or LightGBM) offer this as an "approximate split" option to speed up training on large datasets.

Scikit-Learn Implementation & That Mysterious Comment #

You’re correct about scikit-learn using adjacent midpoints! If you peek into the Cython code (in _splitter.pyx), you’ll see that after sorting the feature values, it computes split thresholds as the average of consecutive unique values.

As for that confusing comment: # sum of halves is used to avoid infinite value—you’re right that dividing by 2 doesn’t prevent division by zero. The comment is a bit of a misstatement, but here’s what it actually means:
When working with very large floating-point numbers, adding two huge values can cause numeric overflow (resulting in an infinite value). Instead of calculating (a + b) / 2, the code uses a/2 + b/2 (the "sum of halves") to reduce this risk.

For example, if a and b are both near the maximum float value, a + b would overflow to infinity. But a/2 and b/2 are each within the valid float range, so their sum is safe. The comment is pointing out this numeric stability trick—not avoiding division by zero. Division by 2 is never a problem here, but overflow during addition can be.

Final Practical Notes #

• Method 1 (midpoints) is the default in most libraries (like scikit-learn) because it balances speed and split quality well for most use cases.
• Method 2 (percentiles) is a great optimization for large datasets with high-cardinality features.
• Don’t stress too much about missing the "perfect" split—decision trees are robust to small suboptimal splits, especially when used in ensembles like random forests or gradient boosting.

内容的提问来源于stack exchange，提问作者DenisVasyov