从ID3到CART：决策树三大算法核心原理与实战对比

1. 决策树的前世今生：为什么笔记week9一定要啃这三个算法

如果你和我一样，学机器学习学到第9周，大概率会被ID3、C4.5、CART这三兄弟搞得有点晕。很多人觉得决策树不就是“一堆if-else”吗，为什么还要花一周时间去研究什么信息增益、增益率、基尼系数？

但实际做项目你就会发现，决策树远没有表面看起来那么简单。一个真正可用的决策树，要考虑特征怎么选、连续值怎么切分、缺失值怎么办、剪枝怎么剪、深度设多少。而ID3、C4.5、CART恰恰是把这些核心问题拆解清楚的三个经典方案。理解它们，等于把决策树的底层地基打了个通透，后面再看随机森林、GBDT、XGBoost这些树模型的时候，你会明显感觉省力很多。

这个笔记适合两类人：一类是正在上课或者自学，被教材公式劝退的初学者，你想搞懂为什么要有这些公式，而不只是套公式；另一类是用Scikit-learn调参但总觉得不够踏实的工程师，理解了CART的切分逻辑，才能真正理解max_depth、min_samples_split这些参数背后的意义。

我会尽量用“人话”把底层逻辑讲清楚，重点讲三个算法的设计动机和它们之间的演进关系，顺便配上我实际调试中踩过的坑和总结的经验。

2. 从一根分叉的树枝说起：决策树整体设计思路拆解

2.1 为什么是“树”而不是“规则表”

先退一步，想想决策树要解决什么问题。给定一批样本，每个样本有一堆特征(x1, x2, ..., xn)，还有一列目标y。分类问题就是根据x判断y属于哪一类，回归问题就是预测y的具体数值。

最朴素的做法是写一堆if-else规则。但很快会发现，特征一多、样本一多，规则之间会打架、冲突、冗余。如果规则是程序里写死的，遇到新数据就完全没法扩展。

树结构比规则表高明的地方在于它天然是嵌套的、分层的。根节点拿一个特征做判断，把样本分开，左子树继续在自己的范围内做更细的判断，右子树同理，一层层往下。这种嵌套结构有几个好处：一是规则共享路径片段，避免重复判断；二是每个节点只关心自己范围内的数据，局部性很强；三是剪枝操作可以控制树的复杂度，防止过拟合。

你可以把决策树想象成一套“分治策略”：拿到一批样本，别想着一步登天，先找一个判断维度把它们劈成两半，让每一半内部的类别纯度提高，然后对每一半递归做同样的事。关键问题是：每次分叉的时候，选哪个特征、在哪个取值上切，才能让分类效果最好？

2.2 “纯度”是决策树最核心的度量尺度

“切完之后让每一半内部更纯”——这句话里的“纯”，是决策树算法所有公式的精神内核。

什么算纯？一个节点里如果全是同一类样本，那它当然纯到极致。如果里面各类别混杂得厉害，那就很不纯。决策树的每一层分叉，本质上是想尽办法让子节点的纯度尽可能高。

那用什么来量化纯度？有几个经典工具：信息熵、基尼系数、方差。它们都能描述一个集合内部混乱程度的大小。信息熵是从信息论借来的，基尼系数是经济学家发明的收入不平等指标，方差直接用于回归树。三个算法的核心差异，主要就是选用了不同的纯度度量，以及处理特征偏好时做了哪些修正。

2.3 三个算法一条演进线

ID3是最早引起广泛关注的决策树算法，核心逻辑是用信息增益选特征。但它有个致命缺点：极度偏好取值种类多的特征。比如“学号”这种每个样本一个值的特征，信息增益会高得离谱，因为它直接把数据劈成了每个叶子只有一个样本。

C4.5是ID3的作者本人做的升级版，核心改进包括用信息增益率代替信息增益，处理连续特征（离散化切分），处理缺失值，以及引入后剪枝策略。C4.5在实践中比ID3稳健得多。

CART又问世得稍晚一点，采用二分递归分割的方式——每次都只劈两叉，而不是按特征的所有取值大分叉。它对分类树用基尼系数，对回归树用方差最小化。更重要的一点是，CART生成的树与随机森林、GBDT等集成模型无缝衔接，目前Scikit-learn的DecisionTreeClassifier底层就是CART。

弄明白这三者，你的脑海中要有一条主线：ID3提出了一个思想框架，C4.5补齐了各种工程细节，CART则做出了高效稳健的通用数据结构。下面一个个拆。

3. 核心细节解析：三个算法各有什么底牌

3.1 ID3：信息熵与信息增益的计算逻辑

先复习信息熵。假设当前节点包含D个样本，其中有K个类别，第k类样本占比是pk，那么这个节点的信息熵定义为：

Ent(D) = - sum(pk * log2(pk))，k从1到K。

对数底取2，单位是比特。如果某个类别占比为0，对应项就是0，因为0乘以log2(0)取极限为0。这个值越大，说明集合内类别越混乱；越小说明越纯。纯粹只有一个类时，log2(1)=0，熵就是0，最纯状态。

选特征的时候，假设离散特征a有V个取值，根据这V个取值把D分成V个子集D1, D2, ..., DV。那么用特征a划分之后的总熵，是这些子集信息熵的加权平均，权重是子集样本占比|Di| / |D|。划分前的熵减去划分后的加权熵，就是信息增益：

Gain(D, a) = Ent(D) - sum(|Di| / |D| * Ent(Di))

这个差值越大，说明这个特征让不确定性减少得越多，那就优先选它。

看起来很美？实际操作中就会发现一个严重问题。假设我们有一个“用户ID”特征，每个样本的ID都不同，那么每个子集只有一个样本，每个子集内部天然纯到极致，加权熵为0，信息增益达到最大值。于是ID3每次都会选这个特征，生成一个深度极深、无比复杂、在实际预测中毫无用处的树。这就是“偏好取值种类较多的特征”这一毛病的来源。

我当时在课堂上学到这一块的时候，心里冒出来的问题就是：信息增益本质上是在衡量“这个特征给样本分群之后，群内同质性的提升程度”。但如果群的粒度太细，同质性当然高，但泛化能力为0。信息增益没有对“分了多少群”做惩罚，缺了一个正则项。

3.2 C4.5：增益率如何救场，代价是什么

C4.5的解法很优雅——把信息增益除以一个“固有值”来归一化。这个固有值本质上就是特征a自身的熵：

IV(a) = - sum(|Di| / |D| * log2(|Di| / |D|))

特征a取值种类越多，IV(a)越大，相当于对多取值的特征做了惩罚。

增益率定义为：

Gain_ratio(D, a) = Gain(D, a) / IV(a)

注意这里不能简单地选增益率最大的特征。因为IV(a)很小（比如某些取值分布极不均匀的特征，IV(a)非常小），增益率会被放大到惊人的程度，这又走向另一个极端。C4.5的实际做法是：先从候选特征里选出信息增益高于平均水平的特征，再从里面挑增益率最大的。

你可能会问，C4.5这一点不是仍然有点绕吗？对，确实是。但这在机器学习里很常见——当你试图修正一个偏差，往往会引入另一个偏差。C4.5的增益率不是完美方案，但是比ID3的信息增益要均衡得多。

此外C4.5还做了几件很重要的事：

连续特征处理。离散特征可以直接按取值打叉，连续特征怎么办？C4.5的办法是把连续值排序，找相邻值的中位点作为候选切分点，然后算每个切分点划分后的信息增益（或者增益率，原作者在具体实现里其实用的是信息增益来挑切分点），选增益最大的那个点作为二分点。这个思路直接影响后面CART的实现。

缺失值处理。样本的某个特征缺失了，C4.5不会直接丢弃样本。它的做法是对缺失特征样本按权重处理：在有缺失值的特征划分节点时，缺失样本按照当前节点各子集的比例分配到各个分支里，同时把权重同步按比例缩小。这套机制简单有效，直到今天很多工业级实现仍然沿用类似思路。

后剪枝。C4.5采用悲观剪枝策略，用带惩罚项的训练误差来评估剪掉某个子树后误差是否会下降。这个思路就是“用训练数据评估泛化误差”，虽然不如验证集剪枝直接，但好处是不用留一块数据专门做验证。

我在实际使用C4.5风格实现的时候（比如开源的一些决策树工具），最大的感触是：连续特征候选切分点的数量会直接影响训练速度。数据量一大，每个节点都要对连续特征排序，那代价是相当可观的。所以CART在工程实现上改成在候选切分点中做近似采样，极大提升了效率。这就是学术逻辑与工程逻辑之间的真实鸿沟。

3.3 CART：二叉树结构 + 基尼系数 + 剪枝套餐

CART全称是Classification And Regression Tree，也就是分类回归树。它的结构很多地方比前两者更规整：

第一，CART是严格的二叉树。离散特征的每个取值不再是“一叉”，而是把取值空间切成“属于这个子集”和“不属于这个子集”两类。对多取值离散特征，CART会尝试所有二元组合划分，找一个最优的组合。这也意味着CART生成的树更偏“宽”而不是“深”，因为每次只切两半，但切法非常灵活。

第二，分类树用基尼系数。基尼系数定义是：

Gini(D) = 1 - sum(pk^2)，k从1到K。

pk是第k类样本占比。如果所有样本都属于一个类，那pk是1，Gini=0，最纯。如果两类的比例是50%对50%，Gini就是1 - (0.5^2+0.5^2) = 0.5，最混乱。

特征a将节点划分后，基尼指数是划分后的加权平均：

Gini_index(D, a) = sum(|Di| / |D| * Gini(Di))

我们选择基尼指数最小的特征作为切分特征。

为什么用基尼系数不用信息熵？两个原因：一是计算快，基尼系数不需要算log函数，工程上省下的计算量非常可观；二是两者在数值变化趋势上非常接近，基尼系数是熵在pk=1附近的一阶泰勒近似，分类效果差异通常很小。业界选择简单胜于精确。

第三，回归树的切分准则换成了方差。对回归问题，一个节点内部的目标值方差，反映了这个节点预测的偏差程度。切分时需要找一个特征和切分点，使得左右子节点的加权方差之和最小。其实质是在做分段常数回归的局部拟合。

第四，CART的剪枝用的是代价复杂度剪枝，这比C4.5的悲观剪枝要严谨。它定义了一个整体代价：

C_alpha(T) = error(T) + alpha * |T|

error是树在训练集上的误差，|T|是叶子个数，alpha是正则化强度。对给定的alpha，可以通过遍历子树，找一个让C_alpha最小化的子树。实际操作中，先生成一棵大树，然后逐步增大alpha，得到一系列嵌套的子树，最后用验证集从这组子树里挑一个泛化性能最好的。

我鼓捣过一段时间的Scikit-learn决策树，发现它在剪枝上其实更简单直接：sklearn不实现复杂的剪枝算法，而是通过max_depth、min_samples_split、ccp_alpha来做控制。其中ccp_alpha就是代价复杂度剪枝的alpha参数，如果设置得合适，可以避免过拟合，而且不会像max_depth那样一刀切得那么粗暴。

3.4 三者对照表

光靠文字描述不够直观，我把三者的核心差异放一张表里，方便你复习时快速回看。

这张表不是让你背的，而是提醒你，当你今天直接调用sklearn.tree时，你其实是在用CART的思路以及C4.5的部分工程处理（比如缺失值逻辑在某些实现中有借鉴）。你心里必须清楚自己用的是什么工具，以及这个工具继承了谁的血统。

4. 手工推演一个案例：特征选择的全过程

4.1 一个可以手算的小样本集

公式看多了容易飘，我们来手算一个极其简单的例子。假设我们有10个样本，两个特征：天气（晴/阴/雨）、风速（高/低），目标是“是否去公园”（去/不去）。

样本数据如下：

先把根节点的信息熵算出来。10个样本里，“去”有5个，“不去”有5个，所以：

Ent(D) = - (5/10 * log2(5/10) + 5/10 * log2(5/10)) = - (0.5 * (-1) + 0.5 * (-1)) = 1

现在按“天气”划分。天气取值为晴、阴、雨。晴的样本有1、2、7，标签是：不去、去、不去，也就是2个不去，1个去。它的熵是：

Ent(晴) = - (2/3 * log2(2/3) + 1/3 * log2(1/3)) ≈ 0.918

阴的样本有3、4、8，标签全为去，熵为0。

雨的样本有5、6、9、10，标签是不去、不去、不去、去，也就是3个不去，1个去。熵是：

Ent(雨) = - (3/4 * log2(3/4) + 1/4 * log2(1/4)) ≈ 0.811

按天气划分后的加权熵：

(3/10) * 0.918 + (3/10) * 0 + (4/10) * 0.811 ≈ 0.2754 + 0 + 0.3244 = 0.5998

信息增益是1 - 0.5998 ≈ 0.4002。

4.2 再算风速，选出切分特征

按“风速”划分。风速高的样本是1、3、5、7、9，对应标签是不去、去、不去、不去、不去，也就是1个去，4个不去。熵：

Ent(高) = - (1/5 * log2(1/5) + 4/5 * log2(4/5)) ≈ 0.7219

风速低的样本是2、4、6、8、10，对应标签是去、去、不去、去、去，也就是4个去，1个不去。熵同样约0.7219。

加权熵 = 0.5 * 0.7219 + 0.5 * 0.7219 = 0.7219。

信息增益是1 - 0.7219 ≈ 0.2781。

两个特征的增益比较：天气是0.4002，风速是0.2781，所以ID3在这里会选择“天气”作为根节点的切分特征。这比较符合直觉——天气对是否出门玩的影响更大。

再往深一层验证CART的基尼系数逻辑。根节点基尼是1 - (0.5)^2 - (0.5)^2 = 0.5。按天气划分：晴的基尼是1 - (1/3)^2 - (2/3)^2 = 4/9 ≈ 0.4444；阴的基尼是0；雨的基尼是1 - (3/4)^2 - (1/4)^2 = 6/16 = 0.375。加权基尼是(3/10)*0.4444 + (3/10)*0 + (4/10)*0.375 ≈ 0.1333 + 0 + 0.15 = 0.2833。这个值比0.5明显下降了，说明划分后纯度提升显著。如果选风速，两叉的基尼分别是4/9和?算一下就发现基尼指数会比按天气划分的高。结论一样但计算效率更高。

我在初学阶段反复手算过几次这种小样本的熵和基尼系数，收获非常大。你看公式觉得抽象，但一旦你真刀真枪摆出一个只有10个样本的表格，亲手算一遍特征选择的过程，后面再读任何决策树源码，脑子里都能浮现出对应的计算流程。

4.3 信息增益率在这个例子里会怎么变

如果你在课程作业里，导师逼你对比ID3和C4.5在这个小数据集上的差异，你会怎么做？先算“天气”这个特征自身的熵IV：

天气取晴、阴、雨的比例分别是3/10、3/10、4/10，所以：

IV(天气) = - (0.3log2(0.3) + 0.3log2(0.3) + 0.4log2(0.4)) ≈ - (0.3(-1.737) + 0.3*(-1.737) + 0.4*(-1.322)) ≈ 1.572

风速的IV：高、低各5个，IV=1。

天气的增益率 = 0.4002 / 1.572 ≈ 0.2546。风速的增益率 = 0.2781 / 1 = 0.2781。

很有趣：在C4.5的准则下，风速的增益率反而超过了天气，也就是说C4.5会选风速作为根节点特征。这就是“修正多取值偏好”后的结果，天气虽然是有效分类特征，但它有三个取值，IV惩罚较大；风速是二值特征，惩罚较小。这样做的结果是什么？C4.5生成的树可能不如ID3那么深，但也更稳健。这个小细节你在考试和面试中都容易遇到，值得在心里留个印子。

5. 实操过程：从零手写一份决策树的核心循环

5.1 伪代码级别的实现思路

不管学术论文怎么写，决策树的代码实现大致可以收敛成下面这个模板：

function build_tree(samples, features): 如果 samples 中的标签全部相同: 返回叶子节点，标签为该类别 如果 features 为空或无法继续划分: 返回叶子节点，标签为样本数最多的类别 对于每个特征 f: 计算划分后的纯度指标（信息增益/增益率/基尼指数） 选择纯度提升最大的特征和切分点 按照切分结果把 samples 分成子集 对于每个子集，递归调用 build_tree

这段逻辑看着简单，但实际写的时候有三个容易出问题的地方：第一，递归出口不止“标签全同”和“特征用完”两个，还要考虑“某个子集为空”和“样本太少没法继续分”的情况；第二，连续特征排序后，切分点应该设在两个相邻值的中点，有些刚上手的人直接把样本值当切分点，导致代码在预测时如果遇到没见过的特征值直接报错；第三，如果你用信息增益，一定要检查一下当前节点是不是所有候选特征增益都是0，如果是，树就不该再长下去，否则纯属浪费时间还容易过拟合。

5.2 用Python手写一个简化版的决策树

这里我用Python写一个极简版CART分类器，主要为了展示核心逻辑，不做太多工程优化。代码可以拿去跑一遍，但生产环境请直接用sklearn。

import numpy as np from collections import Counter class SimpleCART: def __init__(self, max_depth=None, min_samples_split=2): self.max_depth = max_depth self.min_samples_split = min_samples_split self.tree = None def _gini(self, y): counts = Counter(y) total = len(y) gini = 1.0 for c in counts.values(): p = c / total gini -= p * p return gini def _split_gini(self, y_left, y_right): n_left = len(y_left) n_right = len(y_right) n_total = n_left + n_right gini_left = self._gini(y_left) gini_right = self._gini(y_right) return (n_left / n_total) * gini_left + (n_right / n_total) * gini_right def _find_best_split(self, X, y): n_samples, n_features = X.shape best_gain = -np.inf best_feature = None best_threshold = None base_gini = self._gini(y) for f in range(n_features): values = np.unique(X[:, f]) for i in range(len(values) - 1): threshold = (values[i] + values[i + 1]) / 2.0 left_mask = X[:, f] <= threshold right_mask = ~left_mask if left_mask.sum() == 0 or right_mask.sum() == 0: continue cur_gini = self._split_gini(y[left_mask], y[right_mask]) gain = base_gini - cur_gini if gain > best_gain: best_gain = gain best_feature = f best_threshold = threshold return best_feature, best_threshold def _build_tree(self, X, y, depth): if len(set(y)) == 1: return Counter(y).most_common(1)[0][0] if depth == self.max_depth or len(y) < self.min_samples_split: return Counter(y).most_common(1)[0][0] feature, threshold = self._find_best_split(X, y) if feature is None: return Counter(y).most_common(1)[0][0] left_mask = X[:, feature] <= threshold right_mask = ~left_mask left_subtree = self._build_tree(X[left_mask], y[left_mask], depth + 1) right_subtree = self._build_tree(X[right_mask], y[right_mask], depth + 1) return {"feature": feature, "threshold": threshold, "left": left_subtree, "right": right_subtree} def fit(self, X, y): X = np.asarray(X) y = np.asarray(y) self.tree = self._build_tree(X, y, 0) def _predict_one(self, x, node): if not isinstance(node, dict): return node if x[node["feature"]] <= node["threshold"]: return self._predict_one(x, node["left"]) return self._predict_one(x, node["right"]) def predict(self, X): X = np.asarray(X) return np.array([self._predict_one(row, self.tree) for row in X])

这个代码有个特点：它只支持数值特征，因为阈值用二分法找的。如果你拿一组玩具数据跑，比如上面的天气例子，需要把天气映射成数值（晴=0，阴=1，雨=2），风速映射成数值（高=1，低=0）。

跑下来的结果你会发现，这个简化版CART用的是基尼系数的二分切分，它可能会把天气切成“晴”和“非晴”，或者“雨”和“非雨”等分组，选基尼指数最小的那个。这和sklearn的行为基本一致，逻辑也很直白。

实际写的时候我还踩过一个坑：_find_best_split里如果所有候选划分都因为某一边为空而continue，best_feature就会是None，这时必须返回一个叶子。不然递归根本停不下来，直接栈溢出。

5.3 剪枝到底怎么做，参数怎么选

如果你拿上面这个手写CART跑真实数据，十有八九会过拟合，尤其是不设置max_depth的时候。剪枝方案大概分两类：预剪枝和后剪枝。

预剪枝是在构建树的过程中就阻止它展开。常见办法包括限制max_depth、min_samples_split、min_samples_leaf，以及限制划分后子集的样本数不少于某个阈值。我在实际项目中，最常用的组合是max_depth=5到7，min_samples_leaf=10到20。如果你的数据偏小，这两个值要相应调小一点，不然可能连有效的划分都做不出来。

后剪枝是先建一棵大树，再回头把不可靠的分支剪掉。sklearn里可用ccp_alpha实现代价复杂度剪枝。具体操作是用sklearn的cost_complexity_pruning_path拿到一组有效的alpha值，然后遍历它们去训练不同的树，再用验证集评估选出一个最优alpha。我之前在一个信贷数据集上试过，不剪枝的树在训练集上准确率能做到98%，但验证集只有82%；设定合适的ccp_alpha之后，训练集降到90%，验证集反而涨到87%。这就是后剪枝的典型收益。

很多人对剪枝有一个误区，觉得剪枝就是把树的规模变小，所以只要减小max_depth就行。其实不对，剪枝的核心是减少特征空间被切得过细导致的方差放大。过深的树对边界样本极度敏感，一个样本位置稍微挪一下，整棵树的分叉都可能变。适当的剪枝相当于用药，把这种震荡抑制住，换来的是稳定的泛化性能。

5.4 连续特征和缺失特征到底怎么办

用CART处理连续特征，最标准的做法就是排序后枚举中点切分，这也是我上面代码做的事。但需要注意一个工程细节：如果连续特征有异常值，排序后中位点选择会受影响。比如有一个极端值1000，其他值都在0到10之间，排序后会产生很多极端切分候选点，但这些点实际上只拆分出去一个异常样本，对整体纯度提升几乎没有帮助。解决方案是先做分位数裁剪或者把连续特征做分桶，或者设置min_samples_leaf来过滤掉这种只包含一个样本的子集。

缺失特征的现实情况很复杂。sklearn里的DecisionTreeClassifier，默认是不对缺失值做填充的，而是在节点分裂的时候把缺失特征的样本分到增益最大的那个分支（实际上是计算增益时忽略缺失样本，分配时用代理分裂策略）。C4.5的方法则是把缺失样本按当前节点各分支的样本比例分下去。我个人的建议是：如果缺失比例低于5%，直接用均值或众数填充影响不大；如果缺失比例很高，建议单独建模，或者把它变成“是否缺失”这个二值特征，往往比强行填充要靠谱。

6. 常见问题与排查技巧实录

6.1 为什么我的决策树训练集准确率接近100%，测试集却一塌糊涂？

这是几乎所有初学者第一次用决策树都会撞见的状况。核心原因就是树太深，叶子节点里甚至每个叶子只有一个样本。决策树没有做任何平滑处理，它把训练数据里的每一个细节都背下来了，包括噪声。

解决办法优先级如下：先调max_depth和min_samples_leaf，这两个参数改动最直接；然后试ccp_alpha后剪枝；最后才考虑做特征筛选。这里有个小技巧：你可以打印出树的叶子节点数量。200棵叶子的树在几千样本的数据集上，过拟合风险已经很高了。

6.2 决策树的特征重要性排序可信吗？

很多人在项目汇报里喜欢把sklearn的feature_importances_做成柱状图，然后说“这个特征是最重要的”。这个结论要小心。CART里的特征重要性是每个特征被选作切分特征时，基尼指数下降量的累积（归一化后）。如果两个特征高度相关，重要的那个特征会抢走几乎全部贡献，另一个特征重要性趋近于0。这不代表后一个特征没用，只是信息被前一个覆盖了。

而且sklearn的feature_importances_在bagging这类集成模型里也被一并继承，如果你用的是随机森林，务必要注意特征集合是否存在高相关。否则你会被一张乍看很可靠的重要性排序图带着走，做了一个实际上站不住脚的决策。

6.3 信息增益和基尼系数结果不一致，正常吗？

正常。它们俩对纯度提升的评估虽然有单调性相似，但并非完全相等。比如在有些小数据集上，特征A的信息增益略大于B，但基尼指数反而略微偏向B。课堂作业里老师让你对比ID3和CART选出来的树，经常出现不同的结构，这是可以解释的。

我自己在写作业时犯过的错是，直接把信息增益算出来取最大就完事，没有看增益是否明显大于其他特征。有些时候几个特征的增益差得很小，那选哪个其实都差不多。懂了这个道理之后，你去看实际工业项目里的决策树，会发现根节点选出来的特征往往是和业务直觉高度一致的，那些只领先0.01的特征不值得执迷。

6.4 为什么树模型对异常值有时候那么“刚”？

决策树分叉的时候，只关心一个阈值，所有小于等于阈值和大于阈值的样本被粗暴分成两组。异常值一旦跨过某个切分点，就会被分到一个很小的子集，叶子节点的预测会被带偏。比如回归树里，如果你的目标值有一个极端离群点，它所在的叶子节点预测值会被拉得很高。要对异常值鲁棒一些，可以考虑用分位数切分替代原始值切分，或者像是LightGBM那样在直方图算法层面做去噪。

6.5 一个速查表：决策树常见问题定位

6.6 从ID3到CART，你应该带走什么

讲了这么多，我最想强调的不是你能背出公式，而是你能看见算法设计者当年面对的问题。ID3告诉我们什么是信息增益，粗暴好用但会有偏好；C4.5给出增益率和一堆工程化补丁，让决策树真正可以用起来；CART则用二叉树、基尼系数和剪枝，把决策树做成了可扩展的通用结构，也让随机森林和梯度提升有了坚实的底座。

今天你打开sklearn，只需两行代码就能生成一棵决策树，但如果你不理解背后“每次选一个特征把数据劈开，让子节点越来越纯”这个核心理念，你调参就永远是瞎猫碰死耗子。理解了这些底层逻辑，你再去看GradientBoosting、XGBoost的split finding算法实现，会发现它们本质上做的事情全是同一件事：在树节点上找最优切分特征和切分位置，只不过换上了更精密的估计手段和更高效的工程框架。

我在实际工作中，有一次做回归预测任务，训练数据里有一个特征缺失率高达60%，但业务方坚持认为它很重要。我没有直接丢弃，而是把缺失值单独作为一类，并设置了min_samples_leaf来防止小样本分裂，最后树模型确实在缺失模式下发现了一个有趣的规律。类似这种细节，书本不太会教你，恰恰是在寒暄完理论之后真正让模型效果拉开差距的地方。

如果你正在学week9这部分内容，建议动手做三件事：回到那个10样本的小数据集，手动把ID3的信息增益、C4.5的增益率、CART的基尼系数各算一遍；用sklearn的DecisionTreeClassifier去拟合一个公开数据集，然后打印出树结构（plot_tree）观察它每一步在干什么；最好再把上面的手写CART跑起来，看看剪枝前后测试集准确率的变化。做完这三件事，你对决策树的掌握程度会超过一大半只看不练的同学。