如何从零构建一棵决策树

神经网络非常适合非结构化数据——像素、波形、字符序列——这类数据里单个输入值本身什么也说明不了。给深度网络喂够这类数据，它会学出自己的特征：像素模式、词义、音频纹理，这些都极难手工设计；然后它会在类别之间画出数据所要求的任意边界，无论多么曲折。

但现实世界中极大一部分机器学习并不跑在这种数据上。它跑在表格数据上——住在表格里的数据，形状就像电子表格或数据库查询的结果。每一行代表一个样本或一次观测——一笔交易、一位患者、一次配送、一名球员；每一列是一个有名字、有自身含义的特征。

一个很好的例子是克利夫兰心脏病研究，其中每一行是一位患者，最后一列正是我们想预测的东西：

上面被染色的最后一列包含一个已观测到的结果：这位患者最终查出有心脏病，那位最终没有。该列称为标签；它之前的每一列描述这个案例，只有这一列说明案例的结局。我们想学的是两者之间的关系——从标签已知的案例中学，以便应用到标签未知的案例上。当标签是一个类别时（就像这里），这就是分类任务。

在这种形状的数据上最常获胜的方法是梯度提升：一个接一个地训练小模型，每个都纠正前面留下的错误。这套配方并不在乎那个小模型是什么，但实践中梯度提升与决策树的组合在表格数据上表现最好。决策树是一种通过对列提问、沿着答案往下走直到给出裁决来预测的模型；提升法和随机森林一样属于集成——上百棵树的答案被合成一个，胜过任何单棵树。

人们通常是通过实现的名字而非方法的名字认识梯度提升的——XGBoost，以及它的兄弟 LightGBM 和 CatBoost——即便在 LLM 时代，它们仍悄悄支撑着相当大比例的生产级 ML。Uber 用分布式 XGBoost 估算到达时间，Stripe 用它抓欺诈团伙，Dropbox 在其由 LLM 驱动的企业搜索内部跑着一个 XGBoost 排序器。

表格数据上会出现两类任务：分类，答案是一个类别；回归，答案是一个数字——薪水、价格。决策树两者都能处理。本文构建的是分类器；把同样的代码对准数值目标，把不纯度度量换成该目标的方差、把叶子的标签计数换成它们的平均值，你就得到了一个预测数字的回归模型——代码里别的什么都不用改，尽管由此得到的模型会有不少变化，那是姊妹篇文章的主题。

提升法是后续文章的主题。本文聚焦它要重复上百次的那一部分：一棵决策树是如何从一张行的表格里建起来的——它的问题从哪来、其中一个如何被选中、以及分裂何时停止。我们用纯 Python 写，不用 NumPy，不用 scikit-learn，只用五行小到每个数字都能手算的数据。

两种节点类型，以及它们切出的区域

我们将使用克利夫兰心脏病研究中的五位患者。 完整表格有 303 位患者和十三个特征（预测变量），但我们只用五行和其中两个特征，外加标签：

给定一位患者的负荷试验结果和血管数量，这棵树要预测该患者是否患有心脏病——所以值得先弄清这两列记录了什么。

stress_test（源文件中的 Thal）是铊负荷试验，用于在静息和运动状态下成像心肌血流：normal 表示血流看起来正常；fixed 缺损在两种状态下都缺血——组织已因既往心梗坏死；reversable 缺损只在运动时缺血，是狭窄但仍存活的血管。 vessels（Ca）是在透视下显示病变的主要冠状血管数，0 到 3。

我们要把这五行不断分成越来越小的组，用特征及其取值来决定每一行归属哪一组。 一连串分裂画出来就是一张分叉的图，「树」这个名字正来源于此。

这张图里有两种节点。

菱形是决策节点：每个装着一个决定分支逻辑的问题，向外引出两条边，True 和 False，到达的每一行都会被送往其中一条。 取决于算法，一个节点可以有超过两条分支：ID3 和 C4.5 会给 stress_test 每个取值一条分支，一次分出三个子节点。我们实现的是 CART，它只问是/否的问题，所以这里的节点永远只有两条边。这也是所有主流实现所采用的方式——用不纯度度量打分的二元分裂——从 sklearn 的 DecisionTreeClassifier 到随机森林和 XGBoost 内部的树都是如此。

方框是叶子：路径到此结束，不再提问，叶子所持有的一切就是走过同一条路径的训练患者所带标签的计数。这些计数就是它对落到这里的任何新患者给出的答案——所以上面的方框写着 Yes: 2、Yes: 1, No: 1 和 No: 1：两位血管有病变的患者，都患病；两位无法区分却结论相反的患者；一位明确未患病的患者。把这些计数除以总数就得到概率：第一个叶子 100% Yes，最后一个 100% No，中间那个 50/50。

这两种节点类型就是模型的全部：决策节点为一行路由，叶子回答它，而从顶端进入的每位患者最终恰好落在一个叶子里。决策树把表格的行划分成若干组——而这些组可以画出来，成为所有可能的（负荷试验，血管数）取值空间中的区域。画出来，它们就赋予树标志性的样貌：每条边界都是平行于坐标轴的切割，因为每个问题只指明一列和一个值。下面它与另外三种分隔同一批点的方式并列——一条直线、神经网络会在其间弯出的平滑曲线，以及 k 近邻通过让每个位置由离它最近的训练点投票而得到的锯齿轮廓。

那么，真要造一棵这样的树需要什么？我们需要两样东西。

• 一种从表格中生成候选问题的方法，因为树总得从某处得到它们。
• 一种给这些候选打分的方法，好挑出最好的那个——一个决策节点只持有一个问题，不能更多。

除此之外，我们还需要一条何时停止的规则，因为我们通常不希望一直分裂到每一行都拥有自己的叶子。放任不管，结局正是如此，因为分裂只有在没有任何问题能进一步划分某堆数据时才会用尽。这样的树是把表格存了下来，而不是从中学习：一个只装着单个训练患者的叶子只能重复那位患者的结局，于是被路由到那里的任何新患者拿到的是一个人的结果，而不是从许多人身上看到的规律。

从行到问题

每个决策节点都装着一个问题，所以建树就意味着选择问题。要构建候选清单，把每个特征与它在数据中取到的每个值配对——每一对就是一个问题。列的类型决定比较方式。类别列要求精确匹配——Is stress_test == fixed? 对固定缺损的患者为真，对其他人都为假。数值列则给出一个阈值——Is vessels >= 1? 对有 1 条病变血管的患者为真，对所有更高的患者也为真，这正是让该值成为数轴上的切点、而非用来匹配的名称的原因。

这种配对就是整个生成器，值得完整写出来。我们的数据集有两列，各有三个不同取值，于是得到一个六对的清单：

一列、一个值、一次比较：这就是一个问题的全部，在这里如此，在任何别的数据集上也如此。 CART 从不把两个条件合成一个问题，比如 stress_test == normal AND vessels >= 1；从不拿一列去权衡另一列；也从不使用数据集中不存在的值——不会有夹在两个观测计数之间的 vessels >= 1.5，也不会有 vessels >= 3，因为 3 在我们这五行数据里从未出现。

这六个就是这棵树能问的全部——而且并非全都会进入成品树。多数候选被尝试、打分然后否决；这里只有两个活到成为我们将要构建的树中的问题，另外四个被评估后丢弃。而且这个清单是有限的——绝不会长于表中不同取值的个数——正因如此，下一步可以干脆把它们全都试一遍。

在代码里，问题由一个小类定义。Question 保存一个列索引加一个值，其 match 方法通过查看所取值的类型来决定采用两种比较中的哪一种：

class Question:
    def __init__(self, column, value):
        self.column = column
        self.value = value

    def match(self, example):
        val = example[self.column]
        if is_numeric(val):
            return val >= self.value      # numeric: threshold
        else:
            return val == self.value      # categorical: equality

    def __repr__(self):
        condition = ">=" if is_numeric(self.value) else "=="
        return "Is %s %s %s?" % (header[self.column], condition, str(self.value))

def is_numeric(value):
    return isinstance(value, int) or isinstance(value, float)

实现这套匹配逻辑有几种方式。我们用的是 match 内部那三行的 is_numeric 分支，正是它让这棵树能在完全不做预处理的情况下同时处理一个文本列和一个数值列。各家库并不都走这条路。

scikit-learn 的树要求数值输入，所以 stress_test 必须先做独热编码——每个取值一个 0/1 列：

于是树在我们问 stress_test == fixed 的地方问 is_fixed >= 0.5——同一个分裂，摊在三列上。这个 0.5 本身没有意义：该列只含 0 和 1，任何介于两者之间的切割都分出同样的行，而 sklearn 会把阈值放在两个相邻取值的中点。一个有四个类别的列会直接变成四个这样的 0/1 列，每列仍在 0.5 处被提问——编码横向膨胀，而每个问题仍是对一个值的是/否检验。

LightGBM、CatBoost 和 XGBoost 按子集分裂：它们一次检验一组类别，这仍然是关于一列的一个问题——区别在于被检验的值是一个集合而非单个类别：

ours:    Is stress_test == fixed?
theirs:  Is stress_test in {normal, reversable}?

度量一个数据集的杂乱程度

现在我们知道如何构建候选问题清单了，接下来要理解的是如何给它们打分、决定哪个成为该节点的问题。为此我们需要一个度量标签堆有多混杂的指标，称为基尼不纯度，以及一种按「解开混杂的程度」给每个问题打分的办法——它分出的两堆比原来那一堆少混杂多少。这个分数叫信息增益，增益最大的问题获胜。

先看基尼不纯度，它度量一个集合有多混杂——用一个数说明其中的东西是同一类，还是多类混杂。

假设你要判断两个集合中哪个更混杂。看一眼下面的图就足以断定第二个集合更多样：四类而非两类，且分布更均匀。眼睛瞬间就能定夺。

现在假设我们并不知道任一集合的构成——没有计数、没有类别清单，只能伸手进去取出一个东西。我们还能给多样性一个数吗？

得到这样一个数的一种办法是采样：随机取两个物件，记录它们是同类还是异类，放回去，再重复。 取回来是异类的比例，就是集合混杂程度的估计，而且它除了抽样所显示的以外，不需要知道关于集合的任何东西。

假设我们在每个集合上各做了十次。结果如下：

左集合有四对是两个不同类别；右集合有七对。除以抽样次数就得到估计值——$\hat{d}$ 上的帽子表示这是由样本估计出的值，与由整个总体算出的值相对：

而且这个数的行为正如我们所愿。它越小，说明两次随机抽取取回同类的次数越多——集合越均一。它越大，说明两次抽取不同的次数越多——集合越多样。 抽得越久，估计也越精确：十对已足以区分这两个集合，一百对则能把每个数字钉死。继续抽下去，它会稳定到一个确切值上。

不过一般来说你根本不必采样：当你知道集合里有什么时，一点概率论就能直接给出那个确切值。 算出两次抽取一致的概率，再用 1 减去它。

以左集合为例。它十个物件中有七个是蓝色方块，所以单次抽取是方块的概率为 0.7——连抽两个方块的概率是 $0.7 \times 0.7 = 0.49$。圆形给出 $0.3 \times 0.3 = 0.09$。抽取相同只有这两种方式，所以它们有 $0.49 + 0.09 = 0.58$ 的概率一致。 但我们要的是相反的一面——两次抽取取回不同的频率——既然每次抽取要么相同要么不同，那就是 1 减去相同的概率：$1 - 0.58 =$ 0.42。

右集合是同样的计算，只是有四类而不是两类：

两次抽取有 30% 的时间一致，于是有 0.70 的时间不同——与采样得到的十分之七吻合，而且一次都不用抽。

同样的逻辑也可以用几何方式展示。 把每一个有序的抽取对摆成网格中的一个格子——第一次抽取在横轴，第二次在纵轴。十个物件给出一百个格子，而这张网格就是全部可能的结果：

那个确切值有个名字。从一个集合中随机抽取的两个物件属于不同类别的概率，就是该集合的基尼不纯度，写下来是：

其中 $p_k$ 是集合中属于类别 $k$ 的比例。两半是同一件事的两种说法：$\sum_k p_k^2$ 是抽取一致的概率——对每个类别，两次都落进去的概率，累加起来——而 1 减去它就是不同的概率。

把我们两个集合代进去，就是刚才那段算术的压缩形式：

这个统计量比机器学习更古老，在其他领域以别的名字出现——生态学里叫辛普森指数，经济学里叫赫芬达尔-赫希曼指数。

五行数据上的基尼

现在我们可以为这五行计算基尼不纯度了。首先需要按类别做个计数，在我们这里类别就是标签：上面的集合装的是方块、圆形、三角和星星，而一堆行装的是 Yes 和 No。所以就数一数，某一堆里各标签各有多少，因为本文中的每个量都来自这个字典。

def class_counts(rows):
    """Counts the number of each type of example in a dataset."""
    counts = {}  # label -> count
    for row in rows:
        label = row[-1]  # the label is always the last column
        if label not in counts:
            counts[label] = 0
        counts[label] += 1
    return counts

对整个数据集跑第一遍，class_counts(training_data)，得到 {'No': 2, 'Yes': 3}——我们五位患者按类别的统计。

现在有了计数，就可以算基尼不纯度了——四行 Python：

def gini(rows):
    """Calculate the Gini Impurity for a list of rows."""
    counts = class_counts(rows)
    impurity = 1
    for lbl in counts:
        prob_of_lbl = counts[lbl] / float(len(rows))
        impurity -= prob_of_lbl**2
    return impurity

这个循环就是那个公式，每个标签一项——喂给它一堆全是 Yes 的患者，它返回 0.0；喂一个 Yes 和一个 No，它返回 0.5。我们自己的训练集，三个 Yes 对两个 No，起点是：

gini(training_data) → 0.48

我们将遍历每个候选问题，看谁留下的混杂最少，所以 0.48 是要打败的数字。它也是个很高的起点：只有两个标签时，基尼在两者对半时取到最大值 0.5，所以三个 Yes 对两个 No 让我们停在 0.48——差不多是五行数据能达到的最杂乱程度。

信息增益——给分裂打分

我们的目标是给问题打分，而现在我们已经会算一堆行的不纯度了。于是可以用一个候选问题做分裂，测量它产生的两堆各自的不纯度，再与起始状态比较。这就是信息增益的配方，我们用它来评判一个问题。

写下来只有一行：

而它有四步：

1. 用该问题分裂堆 $S$，得到两堆——$S_L$ 是回答 True 的行，$S_R$ 是回答 False 的行；
2. 对它们各跑一次 gini；
3. 把这两个数合成一个，按各边分到多少行加权：$\frac{|S_L|}{|S|}$ 给出左堆的权重，$\frac{|S_R|}{|S|}$ 给出右堆的权重，每个都是父节点中走向那一边的行的占比；
4. 用父节点的不纯度 $\text{Gini}(S)$ 减去它。

剩下的就是该问题去掉的不纯度——越高，问题越好。

把它读作一笔关于不确定性的交易。用上一节多样性的说法，加权和是分裂之后剩余的多样性，而增益是提出这个问题所去掉的多样性。增益为 0 意味着两堆和它们来自的那一堆一样混杂，也就是这个问题什么都没分开；而两个子节点都变纯的问题去掉了原有的全部混杂。所以我们要猎取增益最大的问题——那些用一个问题的代价买来最多「被去掉的多样性」的问题。

值得强调一下第 3 步的加权究竟为何必要，因为没有它这个分数很容易被骗。我们的两个候选 Is stress_test == normal? 和 Is vessels >= 1?，都把五行分成一个基尼恰为 0 的完美纯净子节点和一个仍然混杂的子节点。它们的区别在于那个干净子节点带走了多少数据：一个只剥离出单独一位患者，留下四行混杂；另一个带走两位，留下三行。只有加权能看见这个差别。它让纯净子节点只按其分量计数，于是只有一行的子节点几乎不起作用，而留下的烂摊子决定了分数。

下面把两者都完整算出来，每个的两个子节点用两种方式合并——先等权计数，再按各子节点所占行数的比例加权：

现在对另一个候选做同样处理。Is vessels >= 1? 同样切出一个完美纯净的子节点，但那个子节点装着两位患者而非一位，它留下的堆是三行而非四行——而且更脏：0.444 而不是 0.375：

所以这两张图里的数字显示的东西比「重新缩放」更强。 等权计数时，Is stress_test == normal? 得 0.293，Is vessels >= 1? 得 0.258，于是第一个问题胜出。加权后，它们变成 0.180 和 0.213，胜出的换成了第二个。加权不只是把分数缩小——它翻转了次序，而由于这是根节点，两个答案会给出自上而下都不同的树。

这就是我们实现分裂及其信息增益的方式，包括加权在内。partition 执行第 1 步，把行分到某个问题造出的两堆里；info_gain 执行第 2 到 4 步，用产出与投入相比来打分：

def partition(rows, question):
    """Split rows into those matching the question, and those that don't."""
    true_rows, false_rows = [], []
    for row in rows:
        if question.match(row):
            true_rows.append(row)
        else:
            false_rows.append(row)
    return true_rows, false_rows

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)

在上面两个候选上跑一遍，它们返回 0.180 和 0.213——正是图中手算出的那两个数，如今是算出来的，而不是画出来的。

机制——先分裂，再递归

现在我们有了全部零件：生成问题的方法、度量一堆有多混杂的方法，以及为一个问题对它做了什么打分的方法。下面是把它们拼起来的流程。一棵决策树是按一条配方、作用在一堆训练行上长出来的：

1. 试遍数据允许的每个问题——每个特征、该特征取到的每个值。
2. 按每个问题把堆中标签解开混杂的程度打分——这就是信息增益，建立在基尼不纯度之上，正如我们刚推导的那样。
3. 如果没有问题有帮助，就停下：这堆成为一个叶子，其标签计数成为预测。
4. 否则用最佳问题把这一堆分成两个更小的堆。
5. 对这两堆各自运行同一套流程。

这个流程有个规范名字——递归二元分裂——一种自顶向下的贪心算法，通过接连把数据集划分成两组来构建决策树。它从根节点的全部数据开始，评估每个特征和分裂点以最小化误差或最大化纯度，并在每个新子组上重复这一过程，直到触及某个停止上限。

称这个算法贪心，意思是它只看眼前这一堆来决定每次分裂。它拿走在此处得分最高的问题，然后再也不回头：当子节点结果糟糕时不会重新审视这个选择，也从不与树中别处的分裂做协调。每一步都是局部最优，却不保证成品树是最优的树——下一节会展示，要暴露这个差距其实不需要多少：两个根问题得分完全相同，而它们之间的取舍改变了下面的一切。

递归这一点正是切出引言那张图里那些矩形的原因：每次调用拥有特征空间中的一块区域——即通过了它上方所有问题的行——并且要么再细分这块区域，要么把它封成一个叶子。那些矩形就是递归底部的那些堆。

选择根分裂——以及平局

在构建整套递归之前，先快速看看在单个节点上运行的那部分实现——寻找最佳分裂问题。在根节点，该节点持有全部五位患者，而做搜索的函数是 find_best_split，它尝试每个特征的每个取值并留下最好的。

它是两层嵌套循环——外层是每一列，内层是该列取到的每个不同值——它们产生的每一对都要经过四步：

1. 用列和值构造一个 Question；
2. 用它 partition 这些行，分成它造出的两堆；
3. 用 info_gain 给这两堆打分；
4. 把该分数与迄今最佳比较，若胜出则保留这个问题。

当两层循环结束时，仍然持有最佳分数的那个问题就是函数的返回值。

def find_best_split(rows):
    best_gain = 0
    best_question = None
    current_uncertainty = gini(rows)
    n_features = len(rows[0]) - 1

    for col in range(n_features):
        values = set([row[col] for row in rows])
        for val in values:
            question = Question(col, val)
            true_rows, false_rows = partition(rows, question)

            if len(true_rows) == 0 or len(false_rows) == 0:
                continue  # this split doesn't divide the data

            gain = info_gain(true_rows, false_rows, current_uncertainty)

            if gain >= best_gain:
                best_gain, best_question = gain, question

    return best_gain, best_question

在根节点调用一次，它会给生成器产出的每个问题打分，并返回这个结果：

六个问题——两列各三个不同取值——但只有五个拿到了数字。Is vessels >= 0? 对每位患者都为真，因为 0 是该列取到的最小值，于是它把五行全都送进 True 分支、一行都不送进 False 分支。一个子节点装下整堆，另一个什么都没有，这不是分裂而是复制——什么都没被划分，也就无从打分。len(true_rows) == 0 or len(false_rows) == 0 这道守卫在 info_gain 见到它之前就把它丢掉了。反正它的增益恰好会是 0——一个子节点毫无分量，另一个就是父节点本身——但跳过它还能防止在其他候选都不高于零时，把一个「非分裂」当作最佳问题返回。

现在看这张表的顶部，因为那才是有意思的部分。 两个不同的问题返回了相同的分数 0.2133。 在真实数据上，平局和接近平局很常见；一旦出现，靠后的候选会覆盖靠前的。 这一行为是实现细节，在我们的算法里它来自两件事：列是按索引顺序扫描的，所以 stress_test（第 0 列）先到，随后被同样出色的 vessels（第 1 列）悄悄顶掉；以及比较写成了 >= 而不是 >，这才让顶掉得以发生：

if gain >= best_gain:

平局和接近平局在真实数据上层出不穷，这正是这个小毛病成为问题的原因。数据里没有任何东西偏爱 vessels 胜过 stress_test——是一个比较运算符做的决定，而由于这是根节点，其下的一切都建立在这个选择之上。行数据的微小改动就足以翻转一次接近平局，并重组下方的整棵子树。这正是单棵树成为高方差模型的原因：它的形状取决于训练时用的那份特定样本。我们会在文章接近结尾处回到这一点，它是解释「为什么单棵树很少是你上线的模型」的两个败因之一。

递归——构建整棵树

既然单个节点已能找到自己的问题，我们就可以构建整棵树了——那个在一堆又一堆数据上运行该搜索并存下结果的递归。存储需要开篇那张图里每种节点类型各一个类：Leaf 保存到达它的那些行的标签计数，Decision_Node 保存一个问题和两条分支。用教科书的词汇说，问题是一条分裂规则——一个特征上的一个谓词——而决策节点就是把这条规则接进流程图，两条分支为它的是/否答案提供去处。你可以把一棵完成的树看作一系列分裂规则。 从树顶开始、沿路向下施加——find_best_split 学出这些规则，而节点就是被选中的规则所居住的地方。

class Leaf:
    def __init__(self, rows):
        self.predictions = class_counts(rows)

class Decision_Node:
    def __init__(self, question, true_branch, false_branch):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch

def build_tree(rows):
    gain, question = find_best_split(rows)

    if gain == 0:
        return Leaf(rows)          # base case: no question helps anymore

    true_rows, false_rows = partition(rows, question)
    true_branch = build_tree(true_rows)
    false_branch = build_tree(false_rows)

    return Decision_Node(question, true_branch, false_branch)

在五位患者上运行，我们得到的是这样一棵树——画出来时每条分支上的堆都可见：

这棵树深两个问题，有三个叶子。让我们从上往下读，从根开始：vessels >= 1，平局的胜者。每位有病变血管的患者都患有心脏病，这条分支立刻终止于一个纯净叶子——两人都是，一个问题搞定。

这值得停下来体会：一整组数据毫无杂质地从数据中掉了出来——基尼为 0，由一个问题产生。往下一层，那位孤零零的 normal 患者做了同样的事——并且注意，stress_test 有三个取值，而这棵树只问了其中一个。stress_test == fixed? 把固定缺损的患者剥离出去，而所有非 fixed 的一起走 False 分支，不加区分。这里恰好只剩那位 normal 患者，因为两位 reversable 患者在根节点就走了。

这棵树的三个叶子中有两个是纯的；除了那对冲突的患者外，每一行训练数据都被归入一个零混杂的组，而递归在每个组中停下，正是因为已经没有不纯度可去除了。

剩下第三个叶子，对完全相同的一组特征值持有一个 Yes 和一个 No。没有任何问题能把这两位患者分开——任何别的模型也不能，因为能区分他们的东西根本不在数据里。若我们使用更多预测变量，这或许可以解决，因为被我们丢掉的十一列很可能藏着能把这两位患者分开的东西。

这个给问题打分、按胜者分裂并递归的过程，本质上就是训练流程。 神经网络的架构是预先设计好的——层数、宽度、连线——梯度下降在这个固定框架内把里面的数值推动上千次。树没有固定框架，也没有任何东西被推动：训练发明了每个节点问哪个特征、在什么阈值、以什么顺序、到多深。神经网络训练固定结构内部的数值；树训练结构本身，而它的数值作为汇总掉落出来——恰好到达的那些行的计数。这里没有轮次也没有收敛：每个节点把候选打一次分，留下最高的，然后再也不回头；所以当 build_tree 的根调用返回时，训练就结束了。这个模型从未逐渐变好；它是被逐渐建起来的。

分类——从叶子上读出概率

预测又是递归，而且比训练代码更短：

def classify(row, node):
    if isinstance(node, Leaf):
        return node.predictions

    if node.question.match(row):
        return classify(row, node.true_branch)
    else:
        return classify(row, node.false_branch)

def print_leaf(counts):
    total = sum(counts.values()) * 1.0
    return {lbl: str(int(counts[lbl] / total * 100)) + "%" for lbl in counts}

每个 Decision_Node 存着一个 Question——一个列索引加一个值——而 match 把该行在那一列的条目与之比较，返回一个普通的 True 或 False。这个布尔值是 classify 所需的全部：True 把行送下 true_branch，False 送下 false_branch，递归一落到 Leaf 就停止。

拿一位患者的数据 ['fixed', 0, 'Yes']，看看树如何预测他是否患心脏病：

1. 根问 Is vessels >= 1?；match 读取该患者的 vessels 条目——是 0——由于该值是数值型，它计算 0 >= 1，得到 False，于是这行走假分支；
2. 该节点问 Is stress_test == fixed?；match 读取该患者的 stress_test 条目——'fixed'——由于该值是字符串，它计算 'fixed' == 'fixed'，得到 True，于是这行走真分支；
3. 那条分支是一个 Leaf，所以 classify 返回存在那里的计数：一个 Yes 和一个 No。

classify 返回的这些计数就是原始形式的预测。它们可以被读作单个标签，取叶子里最常见的那个——这就是 sklearn 之类库中 predict 的做法，在纯叶子中毫无歧义，{'Yes': 2} 就意味着 Yes。它们也可以被读作概率，把每个计数除以总数，这就是 predict_proba，也是这里 print_leaf 所做的。

对这位具体患者来说，两个计数各为一，所以两种读法分别是「没有多数」和「50/50」——同一个事实，说两遍。而 50/50 正是应该给出的答案：两位训练患者拥有完全相同的特征却结论相反，所以宣称确定的模型就是在撒谎，而在这个领域里这不是修辞。这是不可约误差，叶子计数免费地把它报告出来，不需要任何额外的不确定性机制。

下面这个小组件是稍大一点的玩具——两个数值特征、用阈值取代我们的混合类型——但机制完全相同，而且它同时展示了树的两种视角。左面板是划分；右面板是行走。两个滑块是特征值 $x_1$ 和 $x_2$——拖动它们即构造出一行新数据并让它在特征空间中移动。那个点越过虚线的那一刻，恰好就是穿过树的路径改变的那一刻，因为区域和叶子是同一个对象换了身衣服。

另外请注意，这棵树把记作 $x_1$ 的特征用了两次——一次在根，另一次在往下两层处、用了不同的阈值。 这是同一列上的两个不同问题——同一个特征，不同的值——因为一个特征并不会因为被拿来分裂就用完了：第一刀分开它能分开的，剩下的行仍可能沿同一条轴继续可分。

正因如此，决策节点的数量与特征的数量是彼此独立的。特征只提供菜单；数据决定哪些问题会被问、被问多少次——而且这份菜单是在每个节点重建的，而不是为整棵树一次性固定。find_best_split 从眼前的行里读出它，values = set([row[col] for row in rows])，所以候选问题清单会随着堆的缩小而缩小：我们的根可以问 Is vessels >= 2?，但它下面的节点不行，因为到达那里的行没有一个取值为 2。

现在把五位它从未见过的患者交给它，全都是同一个文件里的真实行：

patient   2  ['normal',     3]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient   9  ['reversable', 1]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient 266  ['fixed',      0]   Actual: Yes.  Predicted: {'Yes': '50%', 'No': '50%'}
patient  88  ['NA',         0]   Actual: No.   Predicted: {'No': '100%'}
patient 267  ['NA',         0]   Actual: Yes.  Predicted: {'No': '100%'}

第一条测试行是 ['normal', 3, 'Yes']，而 vessels 计数为 3 在训练中从未出现过——我们的五位患者只出现过 0、1 和 2。它照样落进了一个叶子，因为 vessels >= 1 是阈值而不是查表：3 越过了它，走的路径和 1 一样。阈值免费地泛化到训练取值之外。

缺失值则是另一回事：模型根本没有正确处理它们。患者 88 和 267 没有记录负荷试验——文件里写的是 NA——由于 NA 从未在训练中出现，它无法通过 stress_test == fixed? 的检验，于是滑向 False 分支，这就是患者 267 明明患病却被返回 {'No': '100%'} 的原因。

实践中你会在训练前处理这个问题——丢掉不完整的行、填补缺失项，或者把 "missing" 变成一个独立类别。

但清洗训练数据并不能堵上这个缺口，因为明天来的患者仍可能带着一个树从未见过的 stress_test 取值。match 在类别列上使用的 == 比较失败，行滑向 False 分支，而返回的答案看起来与一个有充分依据的答案一模一样。这种沉默才是真正的缺陷——不是树错了，而是 {'No': '100%'} 里没有任何东西能把「三条自信的训练行」与「模型从未遇到过的取值」区分开。

真正的树库在设计上无需对数据集做任何预处理即可处理缺失值。XGBoost 为每个分裂学习一个默认方向，把它无法回答的行送往在训练数据上得分更好的那一侧；而 CART 的原始表述保留替代分裂——与主问题相关的备用问题，向任何无法回答主问题的行提出。

为什么一棵树不是故事的终点

我们构建的模型是货真价实的 CART，用了大约 200 行纯 Python；把它对准真实数据，它会给你长出一棵真正的树。不过我们的实现有两个问题，而树的世界其余部分正是为了应对它们而存在。

第一，如果没有东西阻止它生长，树会过拟合。 过拟合是指模型记住了训练数据而不是从中学习，从而失去了泛化到其他任何东西的能力。在神经网络里它通过权重发生：容量足够而正则化太少时，梯度下降会不停调整它们，直到网络几乎精确复现训练集。在树里它通过分裂发生：无人约束时，build_tree 会一直切下去，直到几乎每一行训练数据都拿到属于自己的纯叶子，因为唯一能让它停下来的只有 gain == 0。这里的容量轴不是「你训练了多久」，而是「你长了多深」，所以针对树的每一种正则化手段都是结构性的——深度限制、最小叶子规模、剪枝。

让我们看看这个问题在真实数据集上是如何显现的，用 sklearn 作为我们代码的公平替身：把 DecisionTreeClassifier(criterion="gini") 保持默认——没有深度限制、没有最小叶子规模、没有剪枝——那么它同样只有「纯度」这一条停止规则，于是它长出的树就是 build_tree 会长出的树，只是算得更快。

现在把它对准乳腺癌数据集（398 行训练、171 行测试、30 个特征）：

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(
    data.data, data.target, test_size=0.3, random_state=0
)

unpruned = DecisionTreeClassifier(criterion="gini", random_state=0).fit(X_tr, y_tr)
print(unpruned.get_depth(), unpruned.get_n_leaves())
print(unpruned.score(X_tr, y_tr), unpruned.score(X_te, y_te))

for depth in (1, 2, 3, 5, 7):
    pruned = DecisionTreeClassifier(
        criterion="gini", max_depth=depth, random_state=0
    ).fit(X_tr, y_tr)
    print(depth, pruned.score(X_tr, y_tr), pruned.score(X_te, y_te))

那棵不受约束的树——没有任何东西拉住它——长成这样：

UNPRUNED (what build_tree does)
  depth      7
  leaves     19
  train acc  1.000
  test acc   0.912

这里的准确率就是预测标签与记录标签相符的行的比例——分别在建树所用的 398 行上测量，以及在它从未见过的 171 行上再测一次。因此训练准确率 1.000 意味着它把 398 行全做对了，而做到这一点靠的是不断分裂，直到那些「掉队者」——拒绝与任何其他行归为一组的行——各自坐进自己的叶子：与我们在五位患者身上看到的 gain == 0 行为一模一样，只是行数从 5 变成了 398。

现在加上我们的版本所没有的那一个旋钮——max_depth，一个对树最多能问多少层的硬性上限，无论是否还有增益可收都会停止分裂。用同一棵树在一系列深度上限下运行并汇总结果，得到：

把最后两行对照着读，因为整堂课的要义都在这里。从深度 2 走到深度 7 把训练准确率从 0.960 提升到 1.000，却让模型变得更差——测试准确率从 0.947 跌到 0.912。未剪枝的树不只是浪费。它被一棵深度只有它三分之一、还做错了 4% 训练数据的树击败。多出来的那五层深度就是树在背诵 398 行具体数据，而 build_tree 无从知晓，因为从内部看，这些分裂每一个都降低了不纯度。

第二个问题是树不稳定——把数据改一点点，它可能长成另一副形状。 这把我们带回到那个用来把候选增益与迄今最佳作比较的 >=，以及循环恰好访问这些候选的顺序。贪心打分在真实数据上不停产生平局和接近平局，而哪一边获胜取决于一个未写进文档的实现细节——你已经在根节点亲眼见过：两个分数相同的问题，由一个字符做出裁决。把同一份代码对准完整的克利夫兰研究——297 位无缺失值的患者、全部十三个预测变量、207 行训练与 90 行留出——在成品树 35 个决策节点中的十个上，两个候选问题得分完全相同，却把患者切成不同的堆。数据中没有任何东西能把它们分开，所以算法保留哪一个都是任意的——而任何扰动分数的因素都会翻转选择并重建其下的一切。

而代价落在真实患者身上。删掉一行训练数据再重新拟合，回来的树会让 90 位留出患者中多达 12 位带着不同的诊断回家。什么都不改，预测也仍会移动——find_best_split 按 set 的迭代顺序访问打平的候选，而这个顺序每次运行都不同，于是在完全相同的患者上跑十次得到了四个不同的模型，彼此之间在多达 4 个（共 90 个）诊断上不一致。在同一份数据上跑两次会交给你两个不同的模型，而按算法自身的标准，两个都是正确的。

这两种行为是偏差-方差权衡的两面。在统计学习中，偏差是用较简单的模型近似复杂现实所引入的误差——一个僵硬到无法表示该规律的模型，无论你给它多少数据都会出错。方差是指如果换一个训练集来估计，拟合出的模型会变化多少：在另一批患者样本上重训，高方差的方法会给你一个明显不同的模型，犯明显不同的错误。

随着方法变得更灵活，这两者朝相反方向移动，而对树来说灵活性就是深度。让它保持浅，它就太简单、抓不住规律——高偏差——但很稳：换一份样本训练，回来的大致还是同一棵树。让它生长，它就能拟合任何东西，包括噪声——低偏差——代价正是上面描述的那种不稳定，也就是方差。训练准确率只会奖励两者中的前者，因为更深的树总能更好地拟合自己的那些行；而测试准确率对两者都负责——所以在表中它在深度 2 处见顶，此后一路下滑。而且没有任何深度能把测试误差压到零，因为在这两项之下还压着我们在那个 50/50 叶子处遇到的不可约误差——结果中特征根本决定不了的那部分。

针对这些问题有一些成熟的方法——深度上限、每个叶子的最少行数、值得为之分裂的最小增益，以及事后回剪分支。 实践中你很少把它们用在一棵孤零零的树上；它们是你在集成内部调节的旋钮——一个由许多树构成的模型，其答案被合并为一个，而随机森林和梯度提升正是这样的东西。

我们来看看唯一在单棵树层面适用的解法——剪枝，它相当于把 gain == 0 换成一条知道何时收手的停止规则。补救手段分为两大命名家族。预剪枝（提前停止）从一开始就拒绝生长：max_depth、每次分裂或每个叶子的最少行数、最小增益阈值——上面那个深度滑块就是最粗暴形式的预剪枝。它便宜，但在第二重意义上仍然贪心：一个弱分裂可能是通往其下强分裂的大门，而提前停下的树永远无从得知（即所谓的视界效应）。后剪枝先让树完全长成，再把在留出数据上不划算的分支剪掉；CART 的经典版本是代价复杂度剪枝：把树的评分定为它的误差加上每个叶子的价格，然后剪掉一切养不活自己的部分。这才是树的损失函数终于被写成显式形式——拟合项加复杂度惩罚，正是正则化在别处所采取的同一形状——而 sklearn 把这个价格暴露为 ccp_alpha。

不稳定性通常根本不在单棵树内部解决。与其寻找更聪明的破平规则，不如别再依赖一棵树。种很多棵，每棵用略有不同的行与列的样本，好让它们落在平局的不同一侧，然后把它们的答案平均：这就是随机森林，而平均正是抵消方差的手段。改为按顺序种，每棵纠正上一棵的错误，那就是梯度提升，它由我们刚写的同样的树构成——加上深度上限和不同的目标——见 From one tree to XGBoost。

我们的版本比真实实现慢在哪

我们的实现缺少一项重要的优化技术，而每个真正的库都有它。其他一切都与生产级实现所做的相符——相同的候选问题、相同的不纯度、相同的增益、选出相同的分裂——但我们写的 find_best_split 是字面意义上的暴力搜索。

循环跑遍每个特征以及该特征取到的每个不同值，所以候选数量是 特征数 × 取值数。 每个候选随后要付出一次对数据的完整遍历：partition 走过每一行把它分到两堆里，而 info_gain 对每堆调用 gini，后者又从零开始数它的标签。这是 $O(\text{features} \times \text{values} \times \text{rows})$。在每列三个取值的五行数据上，看不出来。在连续特征上——比如胆固醇——几乎每一行都带着不同的取值，于是候选数随数据增长，而每个候选仍要付出一次完整扫描：关于行数是二次的，在十万行上毫无希望。

取 cholesterol 列的五行——210（No）、233（No）、250（Yes）、286（Yes）、300（Yes）。生成器把它们变成五个候选问题，每个观测值一个，其中四个真正能把这堆分开：

跟着其中两个——>= 233 和 >= 250——走一遍我们的代码。

对 >= 233，partition 走过全部五行，把 210 放进 False 列表，其余四个放进 True 列表。随后 info_gain 对每个调用 gini，而 gini 走过那个一行的堆去数标签，再走过那个四行的堆去数标签。分裂访问五次，计数访问五次。对 >= 250，一切又从同样这五行重新开始，如此沿着清单往下：

>= 233:  partition 5 rows → gini({210}) + gini({233,250,286,300})   = 10 visits
>= 250:  partition 5 rows → gini({210,233}) + gini({250,286,300})   = 10 visits
>= 286:  partition 5 rows → gini({210,233,250}) + gini({286,300})   = 10 visits
>= 300:  partition 5 rows → gini({210,233,250,286}) + gini({300})   = 10 visits

四十次行访问，而且行与行之间什么都没有被沿用——尽管每一对堆与它上面那一对恰好只差一行。

把这同样五行按胆固醇排序，并带上每位患者最终的 disease 标签，真实实现就是这样保存它们的：

真实实现在第一次遍历中就把两个答案都拿到手。先按该特征给行排序，然后在评估第一个候选时走一遍，途中维护一个已见标签的累计计数——到这一趟走完时，之后每个候选也都被回答了：

每一行都是上一行加上刚刚走过那行的标签：210 是 No，所以计数以 {No: 1} 开场；233 又是一个 No，把它推到 {No: 2}；250 是 Yes，加上第一个 Yes；依此类推。每行一次自增，五行，一趟。

由于行是按升序到达的，这些累计计数中的每一个同时也是落在某个特定阈值之下的那一组——这就是它变成答案的原因：

由于增益公式对两个子节点都要加权，两组都需要——但随着扫描推进只跟踪第一组。等于或高于阈值的那一组从不需要计数；它可以推出来。节点自身的总计在创建时就已算好——这里是 {No: 2, Yes: 3}——所以凡是不在阈值以下的就在阈值以上。任何问题都不必重读数据——每个只要两次查表和一次减法，基尼由四个整数得出。

每个特征建一张这样的表，因为每一列有自己的排序和自己的阈值：按胆固醇排序并扫描，再按年龄排序并扫描，如此下去，所有表中最好的那一行成为该节点的问题。全部差别就在这里。我们的版本为每个候选付一次完整遍历；扫描法为每个特征付一次遍历，然后从沿途建好的表上把每个候选读出来。在五行时这看不出来；在十万行时，这就是一秒钟与一星期的差别。