一、树是怎么长大的

做法是递归地切：在当前节点上，找一条「轴对齐」的分界线（某个特征不大于某个阈值）， 把点分成两半；两半各自再切，直到某一半已经纯了、或者点太少。 每个叶子最后填一个类别——这半区里最多的那一类。 选哪条线？标准是「加权基尼下降最多」。 基尼是「1 减去各类占比的平方和」，纯节点的基尼是 0，对半分的是 0.5。 两侧的基尼按样本数加权加起来，取最小的那个切法。 「轴对齐」这三个字是关键，也是它最大的局限。 每次只能切「x1 大于某值」或者「x2 大于某值」，切不出斜线。 所以一条斜的边界，树只能用很多小台阶去逼近——台阶越多，模型越复杂，越容易把噪声也当台阶。 Demo 里长出来的树有 15 个叶子、连叶子分 9 层。 训练误差 5.00%，看着非常好。 可测试误差 24.50%——比训练误差高出 19.5 个百分点。 这 24.50% 里，8 个百分点是这份数据自己的噪声地板（标签被翻了 8%）， 剩下 16.5 个百分点才是模型没学对的地方。 记住这个 16.5：它是这一节要打掉的东西。

二、剪枝：拿误分数换叶子数

剪枝的办法是给「复杂度」标个价：让每个叶子都收一笔费用。 要最小化的东西从「误分数」变成「误分数 加 alpha 乘叶子数」。 alpha 就是每个叶子的价格：alpha 大，叶子贵，树就倾向于少长； alpha 是零，就只看误分数，树会长到底。 具体怎么剪？自下而上递归判断： 对每个内部节点，比较「把它整枝砍掉当一个叶子会错几个」和「保留子树会错几个、 但多 k 个叶子」。 前者更小就砍，否则保留。 一遍递归下去就剪完了，不用反复迭代。 这个式子和第 4 章的正则化是同一个形状。 那里是「残差平方和 加 惩罚系数乘系数长度」，这里是「误分数 加 惩罚系数乘叶子数」。 换了个复杂度度量而已：一个是系数的范数，一个是叶子的个数。 有一个细节值得记：比较的时候必须用严格小于。 我第一版写成「小于等于」，结果 alpha 等于零时只要误分数持平就全部塌掉，整棵树缩成一个叶子。 因为树是按基尼切的，不是按误分数切的，所以大量节点的「误分数」和子树相等——用小于等于， 它们全被判成「砍掉更划算」。

三、实测：U 形曲线

四、这件事的一般形态

「训练误差降、测试误差升」这个形态，配上一个可调的复杂度参数，就叫「模型选择」问题。 第 4 章的模型选择讲的是「用交叉验证挑带宽」，这里挑的是 alpha，形式上不同， 本质上是同一件事：在一族模型里挑复杂度合适的那个。 还有一个更省事的做法：不剪，而是限制树长（max_depth）或者每个叶子的最少样本数。 这两种做法在实践里更常见，因为它们更简单。 代价是它们「一刀切」——所有分支用同一个限制； 而剪枝是自下而上逐枝判断，深度不同的分支可以有不同待遇。 最后提醒一句：alpha 必须靠验证集挑，不能用训练集挑。 因为训练误差随 alpha 单调上升，用训练集挑的话永远会选 alpha 等于零，也就是永远选最大的树。 这和「不能用训练误差挑惩罚系数」是同一条纪律。

五、动手 Demo：剪枝分类：15 个叶子测试误差 24.50%，剪到 4 个叶子降到 17.67%

造 120 个训练点和 600 个测试点：x1、x2 均匀分布在负 2 到 2 的方形里， 标签由「x2 落在哪条带子里」决定，再把 8% 的标签随机翻转当作噪声。 先让树长到底（每个叶子至少 2 个点、不纯就继续切），看它的叶数、训练误差和测试误差， 并把前几层规则打出来。然后扫 alpha 做代价复杂度剪枝，记录叶子数、训练误差、测试误差。 最后把最优点那棵树的规则也打出来，和全树对照。

def prune(nd, alpha):                      # 代价复杂度剪枝
    if nd['feat'] < 0:                     # 已经是叶子
        return nd, nd['err'], 1
    L, eL, kL = prune(nd['l'], alpha)
    R, eR, kR = prune(nd['r'], alpha)
    if nd['err'] + alpha * 1 < (eL + eR) + alpha * (kL + kR):
        leaf = make_leaf(nd)               # 整枝砍掉更划算
        return leaf, leaf['err'], 1
    out, out['err'], out['leaves'] = nd, eL + eR, kL + kR
    out['l'], out['r'] = L, R
    return out, eL + eR, kL + kR

for a in (0, 3, 12):
    p = prune(full, a)[0]
    print(n_leaves(p), 1 - acc(p, Xtr, ytr), 1 - acc(p, Xte, yte))

实跑输出：

--------------------------------------------------------------------
剪枝分类：15 个叶子测试误差 24.50%，剪到 4 个叶子降到 17.67%
--------------------------------------------------------------------
  训练集                   120 个点、二维，标签是「x2 落在几条带子里」，再随机翻掉 8%
  测试集                   600 个点，同一套规则、另一次抽样
  长树                     贪心选「加权基尼下降最多」的轴对齐切分，直到纯或者只剩 2 个点
  剪枝                     代价复杂度：最小化「误分数 加 alpha 乘叶子数」

  全树叶数                 15 个，连叶子分 9 层
  全树训练误差             5.00%
  全树测试误差             24.50%

  先看看长出来的树长什么样（只打到第三层）：

  如果 x2 不大于 -1.170：
    如果 x1 不大于 0.778：
      判成 -1（16 个点，错 0 个）
    否则：
      如果 x1 不大于 1.314：
        判成 +1（2 个点，错 1 个）
      否则：
        判成 -1（2 个点，错 0 个）
  否则：
    如果 x2 不大于 -0.102：
      判成 +1（37 个点，错 0 个）
    否则：
      如果 x2 不大于 1.319：
        判成 -1（41 个点，错 11 个）
      否则：
        判成 +1（22 个点，错 0 个）

  **树把空间切成一个个小方盒，每个盒子里填多数类。**
  **训练误差只有 5.00%，看着很好；测试误差 24.50%，多了 19.50 个百分点。**
  **多出来的那部分，全是它把噪声也当成规律记住了。**

  再扫 alpha（越大越倾向于剪）：

  alpha   叶子数   训练误差   测试误差
  -----------------------------------
      0       15      5.00%     24.50%
    0.5       10      5.00%     19.67%
      1        6      7.50%     19.17%
      2        5      8.33%     19.50%
      3        4     10.00%     17.67%
      6        4     10.00%     17.67%
     12        2     25.83%     36.83%
     20        1     40.83%     49.17%

  **测试误差那一列是个 U 形：24.50% 一路降到 17.67%，再往下剪就崩到 49.17%。**
  **最好的那一格是 alpha 等于 3、4 个叶子，测试误差 17.67%。**
  **训练误差从 5.00% 涨到 10.00% 才换来这个结果——这就是「故意让训练集变差一点」：用一点训练误差，换一大块泛化。**
  **alpha 从 0 到 3，训练误差只涨了 5.00 个百分点，测试误差却降了 6.83 个。**
  **这说明被剪掉的那些分支，本来就没在学规律——它们在学噪声。**

  剪到 4 个叶子的树是这个样子：

  如果 x2 不大于 -1.170：
    判成 -1（20 个点，错 1 个）
  否则：
    如果 x2 不大于 -0.102：
      判成 +1（37 个点，错 0 个）
    否则：
      如果 x2 不大于 1.319：
        判成 -1（41 个点，错 11 个）
      否则：
        判成 +1（22 个点，错 0 个）

  **四条规则就把整个空间说完了。**
  **对比前面那棵 15 个叶子的树，规则从十几条压到四条，而测试误差反而更低——这就是剪枝的全部意义。**
  **它和第 4 章的模型选择是一回事：叶子数就是「模型复杂度」，alpha 就是「每多一个叶子收多少费」。**
  要说明：**这份数据是我按规则造的，翻掉的 8% 标签是纯噪声，所以测试误差有个 8% 左右的下限。**
  **全树的测试误差 24.50% 比这个下限高 16.50 个百分点，那部分就是过拟合的量。**

nd['err'] 这个字段必须一直是「把这个节点整体判成多数类会错几个」， 长树的时候绝对不要去改它。 我第一版在长树时把它改成了「子树误分数之和」，结果剪枝时两边一比较永远相等， alpha 只要大于零整棵树就缩成一个叶子。 这个 bug 很阴：alpha 等于零时结果完全正常，一调大就全塌，看着像「剪枝太狠」， 其实是字段被覆盖了。 返回值里同时带「误分数」和「叶子数」，是为了让父节点不用重新遍历子树去数。 递归剪枝的复杂度是 O(叶子数)，很便宜； 真正贵的是长树那一步，因为每个节点都要把所有阈值试一遍。 np.unique((sort(v)[1:] + sort(v)[:-1]) / 2) 是「所有相邻值的中点」， 这是轴对齐切分的标准候选集。 不用等距网格，因为网格可能正好错过数据密集的那一段； 用中点则保证每个候选都真的把数据分成两半。 代价是候选数和样本数一样多，节点多的时候会很慢。 切分标准用的是基尼，不是误分数。 换成误分数的话，很多切分会让两侧误分数不变（比如一个 60 比 60 的节点， 切成 30 比 30 和 30 比 30，误分数一点没降），算法会直接停住。 基尼是平滑的，能看出「更纯了一点」，所以能继续往下走。 这也是「代理指标」的一个例子：真正想要的是误分数，能优化的是基尼。 min_leaf=2 这个限制决定了树能长多细。 设成 1 的话，树可以一路切到每个叶子一个点，训练误差精确为零，但那已经不是在学习， 是在记电话号码。 要说明：这份数据是我按规则造的，翻掉的 8% 标签是纯噪声。 所以测试误差有个 8% 左右的下限，全树的 24.50% 里有一大半是这个下限之上多出来的。 真实数据的「下限」你不知道，这也正是为什么必须留一份测试集。

30 秒实验

1. 把 8% 的标签翻转改成 20%，重跑。 全树的测试误差会变成多少？最优 alpha 会变大还是变小？为什么？
2. 把训练集从 120 个减到 40 个，重跑。过拟合会变严重还是变轻？最优点会往哪个方向移？
3. 不加 alpha，改成限制 max_depth 等于 2、3、4、6，各跑一遍。 最好的深度是几层？它和 alpha 等于 3 那棵树比，谁更好？

常见误区

1. 「剪枝就是删掉一些分支，让模型简单一点」。 说法不算错，但漏了最关键的一点：剪枝有明确的判据。 它不是「凭感觉删」，是「最小化误分数加 alpha 乘叶子数」。 没有判据的删枝等于换了个模型，不能叫剪枝。
2. 「训练误差越低越好」。 全树训练误差 5.00%、剪枝后 10.00%，可测试误差是 24.50% 对 17.67%。 训练误差低一倍的那个模型，泛化差了一大截。 这句话在第 1 章、第 4 章都出现过，这里是它在分类问题上的又一次实证。
3. 「树能自动挑出有用的特征，所以不用管特征工程」。 它能挑，但挑得不一定准。 Demo 里全树就切了两次完全无关的 x1，因为在那 120 个点上切一下能少错一两个。 树对「碰巧有用」的噪声特征没有免疫力，尤其在样本少的时候。
4. 「alpha 越大模型越简单，所以越大越安全」。 过了最优点就变成欠拟合，测试误差会重新涨上去。 实测里 alpha 从 3 走到 12，叶子从 4 个掉到 2 个，测试误差从 17.67% 冲回 36.83%。 「简单」和「好」不是一回事。

树能剪到一个合适的复杂度，但它有个改不掉的毛病：训练集换一批点，长出来的树就变一个样。 下一节不管复杂度了，换个思路——让很多棵这样的树一起投票。 奇怪的是，这个办法对深树有效，对很简单的树完全无效，原因藏在「方差」这个词里。

• ☐ （本节完，下一节 9.2 9.2）

相关笔记

• Bagging 学习法
• Boosting 学习法
• 层级模型
• 模型选择
• 使用 Ramp 损失的鲁棒学习
• 🤖 图解机器学习 · 索引