决策树怎么处理连续特征和缺失值？

简化版

连续特征：不能像离散特征那样每个取值一个分支，而是二分——把该特征的值排序，取相邻两值的中点作为候选阈值，遍历所有候选阈值、选让纯度提升最大的那个，按「特征 ≤ t / > t」分成两支。一个连续特征在树的不同层可多次使用（用不同阈值）。缺失值：C4.5 的做法是——计算增益时只用该特征非缺失的样本（再按非缺失比例折算）；划分样本时，把缺失该特征的样本按各分支的样本比例、带权重同时分到所有分支；预测时遇到缺失，也按权重走多个分支再汇总。CART 则用代理分裂（找一个和最优特征划分最相似的替代特征来分）。

详细版

连续特征处理（二分法）：

1. 对该连续特征的取值排序：a₁ < a₂ < ... < aₙ
2. 候选阈值取相邻值中点：tᵢ = (aᵢ + aᵢ₊₁)/2
3. 对每个 tᵢ，按「≤tᵢ / >tᵢ」二分，算纯度提升（增益/基尼）
4. 选提升最大的阈值作为分裂点

连续特征可在不同节点用不同阈值重复使用（离散特征在 ID3/C4.5 里用过即弃）。

缺失值处理（C4.5）——三个子问题：

子问题	做法
用哪些样本算增益	只用该特征非缺失的样本，增益再乘以「非缺失样本占比」ρ
缺失样本划分到哪	按权重分到所有分支（权重 = 各分支非缺失样本比例）
预测时遇缺失	同样按权重走多分支，结果按权重加权汇总

CART 缺失值： 用代理分裂（surrogate split）——找与最优分裂结果最接近的替代特征，缺失时用替代特征来分。

完整版教学

一、连续特征：为什么要二分，不能每值一支

离散特征（如「颜色∈{红,绿,蓝}」）可以每个取值一个分支。但连续特征（如「年龄」「收入」）取值几乎每个样本都不同，如果每个值一个分支，就会分出无数个只含一两个样本的分支——严重过拟合、且无泛化意义（这正是「信息增益偏向多值特征」的极端体现）。

所以连续特征必须离散化成二分：找一个阈值 t，把样本分成「特征值 ≤ t」和「特征值 > t」两组。问题变成：t 取多少最好？

二、怎么找最优阈值——排序 + 遍历中点

标准做法（C4.5、CART 都用）：

1. 把该连续特征在当前节点的所有取值排序：a₁ < a₂ < ... < aₙ
2. 相邻两个值之间取中点作为候选阈值：tᵢ = (aᵢ + aᵢ₊₁)/2，共 n-1 个候选
3. 对每个候选 tᵢ，按「≤tᵢ / >tᵢ」把样本二分，计算这次分裂的纯度提升
   （C4.5 用信息增益/增益比，CART 用基尼）
4. 选纯度提升最大的 tᵢ 作为该特征的最优分裂点

为什么取相邻值中点？ 因为只有当阈值跨过两个相邻样本值时，划分结果才会变化；取中点既能代表这个「分界」，又让边界离两侧样本都留有余地（泛化更好）。

一个重要细节：连续特征在树里可以重复使用。比如上层用「年龄 ≤ 30」分，下层子树里还能用「年龄 ≤ 50」再分——同一个连续特征不同阈值，能表达「年龄的多个区间」。这和 ID3/C4.5 里离散特征「用一次就分光」不同。

三、优化：只在类别边界处考虑阈值

朴素做法要遍历 n-1 个候选阈值，样本多时慢。一个经典优化：只有当排序后相邻样本的类别标签不同时，中间的中点才可能是最优分裂点。因为如果相邻两样本同类，在它们之间切一刀不会改变纯度趋势。据此只考察「类别发生变化处」的候选阈值，大幅减少计算量。

四、缺失值处理为什么棘手

真实数据常有缺失。决策树处理缺失要回答三个独立的问题：

有缺失时，怎么计算某特征的分裂增益（用来选特征）？
选定分裂特征后，缺失该特征的样本该分到哪个分支？
预测新样本时，它在分裂特征上缺失，往哪个分支走？

C4.5 对这三个问题都给了带权重的优雅方案。

五、C4.5 的缺失值方案——按权重「软分配」

问题 1（算增益）：计算特征 a 的增益时，只用在 a 上非缺失的样本来算信息增益，然后乘以一个折扣系数 ρ = 非缺失样本占比。这样缺失越多的特征，增益被打折越多，避免因为缺失多而误判其价值。

问题 2（分样本）：选定用特征 a 分裂后：

非缺失的样本：正常按其取值分到对应分支。
缺失的样本：不是丢弃，也不是硬塞进某一支，而是按各分支中非缺失样本的比例，拆成带权重的「部分样本」同时进入所有分支。例如某分支占非缺失样本的 70%，缺失样本就以 0.7 的权重进入该分支。

这样缺失样本的「影响」被按比例分摊到各分支，信息没被浪费。

问题 3（预测）：预测时若样本在某节点的分裂特征上缺失，就按训练时各分支的权重同时走所有分支，到达多个叶子，最后把各叶子的结果按权重加权得到最终预测。

六、CART 的缺失值方案——代理分裂

CART 用不同思路——代理分裂（surrogate split）：

训练时，为每个节点的最优分裂特征找若干代理特征：这些代理特征的划分结果和最优特征最相似（能最大程度重现同样的样本划分）。
当某样本在最优分裂特征上缺失时，就依次用代理特征来决定它走哪个分支。

代理分裂的好处是利用了特征间的相关性——如果「年龄」缺失，可能用与之高度相关的「工龄」来近似划分。

替代分裂的排序只使用主分裂特征与候选特征都非缺失的样本，比较候选切分对主切分左右归属的复现程度。预测时若主特征缺失，就依次尝试可用的高排名替代分裂；若替代特征也缺失，最终可退回到训练样本较多的子节点等默认策略。不同库未必实现经典 CART 的替代分裂，例如有些提升树直接学习缺失值的默认方向，回答时应把“算法思想”和“具体实现”分开。

七、现代实现的做法（XGBoost/LightGBM）

值得一提，现代梯度提升树对缺失值有更简洁的处理：为每个分裂学习一个「默认方向」——训练时把缺失样本分别试着划到左、右分支，选让增益更大的方向作为默认；预测时缺失样本直接走默认方向。这比 C4.5/CART 更省事，效果也好，所以用 XGBoost 时常常直接保留缺失值交给模型（详见特征工程缺失值专题）。

八、用排序算例串起阈值与缺失路由

某连续特征的已排序取值为 [2, 3, 7, 8]，标签为 [0, 0, 1, 1]。候选中点是 2.5、5、7.5；阈值 5 把两类完全分开，若父节点 Gini 为 0.5，分裂后加权 Gini 为 0，下降量就是 0.5。若 10 个训练样本里 2 个缺失，C4.5 计算该特征增益时先用 8 个非缺失样本，再乘非缺失比例 0.8。

candidates = {(x[i] + x[i+1]) / 2}
score(t) = impurity(parent) - weighted_impurity(children)
adjusted_gain = observed_ratio * gain_on_observed

对象/方案	核心机制	选择或风险
C4.5	按非缺失比例修正增益，缺失样本带权走多支	实现和预测成本较高
经典 CART	代理分裂按相似划分依次备用	代理特征也缺失时需后备策略
现代提升树	每个候选分裂学习缺失默认方向	默认方向属于该节点而非全局

排序去重 → 生成相邻中点 → 逐阈值算增益 → 记录最优阈值
                                      └→ 同时确定缺失路由

记忆钩子：连续值的核心是“比较候选划分”，缺失值的核心是“训练和预测必须使用同一套路由规则”。

九、常见误区与追问

误区：连续特征要先手工分箱才能训练决策树。 精确树可直接枚举相邻取值间的候选阈值，直方图树才会先做近似分桶。
误区：缺失值统一填 0 与原生缺失路由等价。 0 可能是有效数值，填充会改变排序和分裂含义。
追问：连续特征用过一次后还能再用吗？ 可以，不同节点可在同一特征上选择不同阈值。
追问：只检查标签变化处的中点总安全吗？ 对常见未加权分类不纯度可大量裁剪候选，但重复值、样本权重和具体实现需要单独处理。
追问：默认方向是整个模型共用吗？ 不是，提升树通常为每个节点的每个已选分裂记录方向。

十、加强记忆

连续特征处理靠二分：取值排序后以相邻中点为候选阈值，遍历选纯度提升最大的阈值，按「≤t / >t」分两支；连续特征可在不同层用不同阈值重复使用；未加权分类树常可优先检查相邻标签变化处的阈值，但重复值、样本权重和具体不纯度实现要单独核对。缺失值——C4.5 分三步：算增益只用非缺失样本再乘非缺失占比 ρ、缺失样本按分支比例带权重分到所有分支、预测时按权重走多支再加权汇总；CART 用代理分裂（找划分最相似的替代特征来分）；XGBoost/LightGBM 则为每个分裂学一个缺失默认方向，最省事。

简化版

详细版