如何从零构建决策树分类器

决策树通过依次询问输入行的特征来预测结果。我们将用纯 Python 为五名患者构建一棵树，并手工核对每次分裂。

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

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

决策树也是随机森林和梯度提升的基础模型。理解一棵树如何选择分裂，有助于理解这些集成方法。

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

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

下载完整 Python 示例，运行 python3 heart_tree.py。

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

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

training_data = [
    ["normal", 0, "No"],
    ["fixed", 0, "Yes"],
    ["reversable", 2, "Yes"],
    ["reversable", 1, "Yes"],
    ["fixed", 0, "No"],
]

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

stress_test（Thal）记录铊检查结果：正常、固定缺损或可逆缺损。代码保留源数据的拼写 reversable。vessels（Ca）表示透视中显影的主要血管数量，范围为 0 到 3，并非病变血管数量。定义见 UCI 数据集文档。

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

这张图里有两种节点。

菱形是决策节点，各自保存一个是非问题，将行送入 True 或 False 分支。我们的 CART 风格树始终分成两个子节点；其他树算法可以使用更多分支。

方框是叶子，保存到达该处的训练行的标签计数：Yes: 2、Yes: 1, No: 1 或 No: 1。除以总数，得到类别频率估计：100% Yes、50/50 和 100% No。这些极小样本无法确定新患者患病的概率。

决策节点将行送到叶子，从而划分输入空间。对于数值特征，阈值沿某个坐标轴切分。下图使用另一组合成数据说明边界形状：直线、神经网络风格的平滑曲线及树分裂均为示意；k 近邻面板则由所绘制的点计算得到。

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

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

还需要停止规则。这里在没有候选分裂能带来超过微小数值容差的不纯度下降时停止。此时叶子可能仍混杂，即使进一步连续分裂可以分开这些行，例如 XOR 模式。深度限制和最小叶子样本数可以进一步控制过拟合。

从行到问题

将每个特征与当前行中它的每个不同值配对，生成候选。类别规则测试相等关系，例如 stress_test == fixed；数值规则测试阈值，例如 vessels >= 1 对计数 1、2、3 都为真。

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

本实现一次检查一个特征，并以观测值作为数值阈值。这是简化，并非 CART 的要求：scikit-learn 使用相邻不同值的中点。两种方式提供相同的训练集划分，但可能将两个观测值之间的新输入分到不同分支。CART 的类别分裂也可以测试类别子集；这里仅测试单个类别与其余类别。

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

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

FEATURES = ["stress_test", "vessels", "disease"]

class Rule:
    """One yes/no test: a column, and the value it is compared against."""

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

    def holds(self, row):
        observed = row[self.column]
        if isinstance(self.value, (int, float)):
            return observed >= self.value     # numeric: threshold
        return observed == self.value         # categorical: equality

    def __repr__(self):
        operator = ">=" if isinstance(self.value, (int, float)) else "=="
        return f"Is {FEATURES[self.column]} {operator} {self.value}?"

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

Scikit-learn 要求数值输入。对于 stress_test 这样的无序特征，独热编码保留类别而不引入顺序：

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

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

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

LightGBM 和 XGBoost 支持类别分组，按类别统计量排序后搜索候选组。CatBoost 对许多类别特征使用有序目标统计，对部分类别较少的特征使用独热编码，具体取决于配置。参见 CatBoost 文档。

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

选择分裂前，先用基尼不纯度衡量标签混杂程度，再计算按样本数加权后的不纯度下降。代码将其称为 gain；严格来说，信息增益通常指相应的熵下降。

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

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

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

独立地有放回抽取两个元素，记录它们是否属于不同种类，然后重复。第一次抽取后先放回，再抽第二次，才可以像下文那样相乘概率。

下图给出每个集合的一组示意序列，各含十对：

左集合有四对是两个不同类别；右集合有七对。除以抽样次数就得到估计值——$\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 减去它就是不同的概率。

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

集中度统计量 $\sum_k p_k^2$ 也用于辛普森指数和赫芬达尔–赫希曼指数。基尼不纯度等于一减去该和，而不是同一统计量。

五行数据上的基尼

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

def label_counts(rows):
    """Tally the labels in a pile — the label is always the last column."""
    counts = {}
    for row in rows:
        counts[row[-1]] = counts.get(row[-1], 0) + 1
    return counts

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

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

def gini(rows):
    """Impurity of a pile: 0 when every row in it carries the same label."""
    if not rows:
        raise ValueError("Cannot measure impurity of an empty group")
    impurity = 1
    for count in label_counts(rows).values():
        share = count / len(rows)
        impurity -= share ** 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)$ 减去它。

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

零增益表示此次分裂没有改变加权不纯度。若子节点全都纯净，增益达到最大值，即父节点的全部不纯度。

值得强调一下第 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，胜出的换成了第二个。加权不只是把分数缩小——它翻转了次序，而由于这是根节点，两个答案会给出自上而下都不同的树。

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

def split_rows(rows, rule):
    """Sort every row into the pile where the rule holds, and the pile where it does not."""
    true_pile, false_pile = [], []
    for row in rows:
        (true_pile if rule.holds(row) else false_pile).append(row)
    return true_pile, false_pile

def split_gain(parent_impurity, true_pile, false_pile):
    """What went in, minus the two piles that came out, each weighed by its share."""
    share = len(true_pile) / (len(true_pile) + len(false_pile))
    return parent_impurity - share * gini(true_pile) - (1 - share) * gini(false_pile)

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

机制——先分裂，再递归

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

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

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

贪心指只选择当前节点的最佳分裂，不向前搜索，也不重新考虑之前的决定。即时增益为零的分裂仍可能为后续有用分裂创造条件，例如 XOR。我们的停止规则会错过这种情况。

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

选择根分裂——以及平局

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

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

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

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

def choose_split(rows):
    parent_impurity = gini(rows)
    winning_gain, winning_rule = 0, None

    for column in range(len(rows[0]) - 1):
        for value in sorted(set(row[column] for row in rows), reverse=True):
            rule = Rule(column, value)
            true_pile, false_pile = split_rows(rows, rule)

            if not true_pile or not false_pile:
                continue  # this rule doesn't divide the data

            gain = split_gain(parent_impurity, true_pile, false_pile)

            if gain >= winning_gain:
                winning_gain, winning_rule = gain, rule

    return winning_gain, winning_rule

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

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

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

if gain >= winning_gain:

这里平局的两个问题选出了完全相同的两组训练患者，因此不会改变这些组的后续划分。但对于 normal 且 vessels=3 这样的新组合，预测可能不同。我们按降序遍历不同值，使平局处理可复现；>= 仍让最后一个并列候选胜出。

递归——构建整棵树

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

class Leaf:
    def __init__(self, rows):
        self.counts = label_counts(rows)

class Node:
    def __init__(self, rule, if_true, if_false):
        self.rule = rule
        self.if_true = if_true
        self.if_false = if_false

def grow_tree(rows):
    if not rows:
        raise ValueError("Training rows must not be empty")
    gain, rule = choose_split(rows)

    if gain <= 1e-12 or rule is None:
        return Leaf(rows)          # base case: no rule helps anymore

    true_pile, false_pile = split_rows(rows, rule)
    return Node(rule, grow_tree(true_pile), grow_tree(false_pile))

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

这棵树深度为 2，共有三个叶子。根节点将两条满足 vessels >= 1 的训练行送到纯 Yes 叶子。这只是对这两行的描述，并非医学规则。

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

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

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

训练过程选择树的结构、阈值和叶子标签计数。递归调用返回后，模型就可以预测；本实现没有梯度更新或训练轮次。

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

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

def descend(row, node):
    if isinstance(node, Leaf):
        return node.counts

    branch = node.if_true if node.rule.holds(row) else node.if_false
    return descend(row, branch)

def as_percentages(counts):
    total = sum(counts.values())
    return {label: f"{count / total:.0%}" for label, count in counts.items()}

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

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

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

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

混合叶子给出 50/50，因为两类各有一个样本。这是基于两行数据的经验估计，并不能证明总体风险是 50%，也不是完整的不确定性估计。同样输入却有冲突标签，会为只用这些特征的确定性预测器设定训练误差下限。若库要返回单个类别，还必须规定计数平局时如何选择。

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

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

同一特征可以在多个节点使用。各节点根据到达该处的行重新生成候选，因此这些行中不存在的值就不再是该节点的候选。例如，根节点的 False 子节点没有 vessels=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" 变成一个独立类别。

未见类别会与所有不满足相等测试的值一起进入 False 分支。模型既不会识别这种新情况，也不会降低显示的百分比。上例中的 100% No 仅来自一个含有一行训练数据的叶子。

缺失值支持取决于实现。有些库学习默认分支，原始 CART 可以使用替代分裂。但这些机制不会自动将 "NA" 这样的任意字符串识别为缺失值，需要使用库规定的表示方式。

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

这是一个简化的 CART 风格实现，主要局限包括不受约束的增长、对训练样本的敏感性、简化的类别处理以及缺少明确的缺失值策略。

深树可能过拟合。 它可以通过创建小叶子持续改善训练拟合，却将样本噪声反映在预测中。在增益极小时停止只能避免即时无用的分裂，不能控制泛化；深度限制、最小叶子大小和剪枝才用于控制这一问题。

较大的示例使用 scikit-learn 的 DecisionTreeClassifier。它遵循同样的贪心思路，但中点阈值、平局处理和停止细节可能使结果与我们的树不同。

现在把它对准乳腺癌数据集（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 (scikit-learn)
  depth      7
  leaves     19
  train acc  1.000
  test acc   0.912

训练准确率 1.000 表示全部 398 个训练标签都被正确预测，并不要求每行一个叶子：该树只有 19 个叶子。在 171 行留出数据上，准确率为 0.912。

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

在这次数据划分中，深度 2 的留出准确率为 0.947，高于深度 7 的 0.912，虽然训练准确率更低。这说明了过拟合，但不能证明深度 2 普遍最优。如果用这些结果选择深度，留出集就在充当验证集；选好模型后应在独立测试集上评估。

单棵树也可能不稳定。 训练行的微小变化可以改变得分接近时的胜出候选，从而影响下方子树。这种样本敏感性与遍历无序集合等可以避免的实现问题不同。

对候选值排序可以消除 Python 集合顺序导致的运行间差异，但不能消除统计不稳定性：换一批训练样本仍可能得到不同的树。

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

增加深度通常会降低偏差并提高方差，但这是趋势，不是对每个数据集或准确率的保证。给定现有特征后的噪声会限制可达到的期望表现；小训练集中一对冲突样本并不能量化总体的这一限制。

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

预剪枝通过 max_depth、min_samples_leaf 等参数限制增长。后剪枝先生成较大的树，再删除分支。CART 的代价复杂度剪枝权衡训练不纯度和每个叶子的惩罚，scikit-learn 用 ccp_alpha 控制惩罚强度。应通过验证集或交叉验证选择该值，并保留独立测试集。

随机森林对随机选择行和特征训练的多棵树取平均，在误差并非完全相关时降低方差。梯度提升依次拟合树，以改善集成损失。接下来可以阅读回归树文章。

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

我们的分裂搜索会反复扫描相同的行。生产实现可以复用计数或直方图来减少工作量，还可能采用不同的候选阈值、类别支持、缺失值处理和平局规则，因此差别不只是速度。

循环跑遍每个特征以及该特征取到的每个不同值，所以候选数量是 特征数 × 取值数。 每个候选随后要付出一次对数据的完整遍历：split_rows 走过每一行把它分到两堆里，而 split_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，split_rows 走过全部五行，把 210 放进 False 列表，其余四个放进 True 列表。随后 split_gain 对每个调用 gini，而 gini 走过那个一行的堆去数标签，再走过那个四行的堆去数标签。分裂访问五次，计数访问五次。对 >= 250，一切又从同样这五行重新开始，如此沿着清单往下：

>= 233:  split_rows 5 rows → gini({210}) + gini({233,250,286,300})   = 10 visits
>= 250:  split_rows 5 rows → gini({210,233}) + gini({250,286,300})   = 10 visits
>= 286:  split_rows 5 rows → gini({210,233,250}) + gini({286,300})   = 10 visits
>= 300:  split_rows 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}——所以凡是不在阈值以下的就在阈值以上。任何问题都不必重读数据——每个只要两次查表和一次减法，基尼由四个整数得出。

对于 $n$ 行、$d$ 个特征，朴素搜索在一个节点上可能需要 $O(dn^2)$ 工作量。将各数值特征排序后顺序扫描，在类别数量固定时，包括排序在内约需 $O(dn\log n)$。排序后的扫描本身是线性的。这是单节点比较，整棵树的构建成本还取决于树形。