2.4 分裂增益公式与分裂点查找算法

2.4 分裂增益公式与分裂点查找算法

分裂增益 = 左叶分数 + 右叶分数 − 父叶分数 − γ；增益大于零才分裂，贪心选最大者。 本节手推并验证增益公式，然后讲精确贪心、近似分桶、直方图三种查找算法的取舍——增益公式是"裁判"，查找算法是"球探"。

上一节的闭式解回答了"树形一定怎么办"，但树形本身从哪里来？答案是一个贪心循环：对每个节点，遍历候选切分点，算出每个切分的增益，选最大的执行；若最大增益不超过零，节点停止生长。本节先把裁判（增益公式）立起来，再谈球探（查找算法）怎么在巨量候选里省力。

一、增益公式：一次分裔回本了吗

把一个叶子切成两个，结构分数的变化是：左叶 −0.5·G_L²/(H_L+λ)、右叶 −0.5·G_R²/(H_R+λ) 加起来，减去原来单叶的 −0.5·G²/(H+λ)，再减掉多出一个叶子的"税" γ。写成文字公式：增益 = 0.5·[ G_L²/(H_L+λ) + G_R²/(H_R+λ) − G²/(H+λ) ] − γ。注意 G = G_L + G_R（g 可加），所以增益衡量的是"同一批 g、h，切成两堆后平方和结构能多榨出多少"。

直接用代码验证，并顺带演示 γ 的剪枝闸门作用：

import numpy as np

g = np.array([-2.18, -1.48, -0.08, 1.62, 2.12])
h = np.ones(5)
lam = 1.0

def leaf_score(G, H):
    return -0.5 * G**2 / (H + lam)

# 父节点全部 5 个样本；候选切分：客流 12、15、18 三处
candidates = [(g[:2], h[:2], g[2:], h[2:]),   # 切在12：左2右3
              (g[:3], h[:3], g[3:], h[3:]),   # 切在15：左3右2
              (g[:4], h[:4], g[4:], h[4:])]   # 切在18：左4右1

parent = leaf_score(g.sum(), h.sum())
for i, (gl, hl, gr, hr) in enumerate(candidates):
    gain = leaf_score(gl.sum(), hl.sum()) + leaf_score(gr.sum(), hr.sum()) - parent
    for gamma in (0.0, 0.5, 1.5):
        verdict = "分裂" if gain - gamma > 0 else "剪枝(不分裂)"
        if gamma == 0.5:
            print(f"切分方案{i+1}  原始增益={gain:.4f}  gamma={gamma}  -> {verdict}")
​

运行输出：

切分方案1  原始增益=1.8242  gamma=0.5  -> 分裂
切分方案2  原始增益=2.0838  gamma=0.5  -> 分裂
切分方案3  原始增益=0.8962  gamma=0.5  -> 分裂
​

方案 2（切在客流 15）增益最大，正是 2.3 手算的那棵树——两次独立计算互相印证。再把 γ 提到 1.5：方案 3 的净增益 0.896 − 1.5 < 0，被闸门拦下。γ 不是后处理的剪枝参数，而是长在增益公式里的前置税，这就是 XGBoost 的"生长即剪枝"。

二、候选切分点从哪来：三种查找算法

精确贪心要把特征所有取值挨个试，单特征 m 个不同值就要 m−1 次增益计算；千万行数据、上百特征时不可行。XGBoost 提出近似算法：按特征的分位数把候选切分点压缩到若干桶边界，只试这些边界。它有两种模式——全局模式在建树前提出一次候选、全程复用，省算力但粗；局部模式每次分裂后按当前节点的 g、h 分布重新提候选，精细但贵。后来 LightGBM 把这条路走到极致（直方图算法），XGBoost 2.0 之后也加入了 hist 树方法。三者的取舍：

按分位数提候选时用 加权分位数：每个候选区间的权重不是样本个数，而是该区间 h 的总和。直觉是 h 大的样本损失曲面弯得厉害，切分边界应该在这些区域更密——二阶导数在这里第二次发挥定价作用。

# 加权分位直觉演示：h 大的样本附近切分更密
import numpy as np
vals  = np.array([1, 2, 3, 4, 5, 6, 7, 8])
h_wgt = np.array([0.1, 0.1, 0.1, 3.0, 3.0, 0.1, 0.1, 0.1])
total = h_wgt.sum()
# 按累计 h 权重找 3 等分点
cum = np.cumsum(h_wgt) / total
for q in (1/3, 2/3):
    idx = np.searchsorted(cum, q)
    print(f"累计权重到 {q:.2f} 处 -> 候选边界落在值 {vals[idx]}（h 密集区）")
# 运行输出:
# 累计权重到 0.33 处 -> 候选边界落在值 4（h 密集区）
# 累计权重到 0.67 处 -> 候选边界落在值 5（h 密集区）
​

两个候选边界全落在 h=3.0 的密集区（值 4、5 之间），普通等频分位则只会各管一段——加权分位把"火力"集中到损失最敏感的位置。

⚠️ 常见坑：以为近似算法精度一定差。论文与竞赛复盘都显示，在大数据上近似分桶的最终精度损失通常在小数点后几位，换来的是数倍加速；真正伤精度的往往是候选桶数设得过少（比如 sketch_eps 给到 0.5 以上）。

本节要点回顾

• 增益 = 0.5·[左叶分数 + 右叶分数 − 父叶分数] − γ，贪心取最大，净增益不正则不分裂
• 手算三方案中切在客流 15 最优，与 2.3 的结构分数互证
• γ 是前置税，生长与剪枝合并为同一判断
• 精确贪心 / 近似全局 / 近似局部直方图三档取舍，数据越大越靠后
• 加权分位数按 h 的累计权重提候选，切分火力对准损失敏感区

增益公式解决了"干净数据怎么长树"。真实数据有缺失值、内存装不下、多核闲置——下一节看稀疏感知与系统设计如何把这些工程约束一并处理。

一句话衔接历史：LightGBM 正是把本节的近似分桶思路推进为逐层直方图加叶子生长策略，才在后来的大规模竞赛中与 XGBoost 分庭抗礼——第 5.5 节的对比实验会给出量化数字。