决策树全解读：熵、信息增益、CART与剪枝实战笔记

如果你也和我一样，第一次接触决策树时觉得“这有什么难的”，后来对照李航《统计学习方法》第五章做学习笔记，才发现熵、条件熵、信息增益、剪枝这些概念每一个都能展开讲一堆东西——那这篇内容应该能帮你省掉不少绕弯的时间。

这篇笔记不是照着教材把公式抄一遍，而是从我个人学习过程出发，把决策树的模型结构、特征选择原理、三种生成算法、剪枝策略，以及离开课本后做工程必然会碰到的连续值、缺失值和调参问题串起来讲。适合正在啃《统计学习方法》的同学，也适合想把决策树真正用明白的从业者。

1. 决策树模型到底在做什么：路径、规则和条件概率分布

1.1 从“一连串是或否的问题”开始

决策树做的事情，本质上是用“如果……就走到下一个问题，否则走另一条路”的方式，把样本一层一层分到不同桶里。根节点放第一个判断，内部节点放后续判断，叶节点给出最终类别，回归树则在叶节点给出数值。

举一个最朴素的例子：判断一个人是否会去打球，可以先问“今天是否下雨”，如果下雨直接判定不去，如果不下雨再问“温度是否高于25度”，温度高去、温度低不去。这个流程画出来就是一棵三层的小树。

从数据结构角度看，决策树由节点和有向边组成。每个非叶节点对应一个特征上的测试，每条边对应一种测试输出，每个叶节点对应一个类别或数值。算法的学习过程，就是从训练数据中自动确定这些测试条件、树的深度和叶子结构，而不是靠人手工设计规则。

这里有一个很容易被忽略的点：决策树的“分裂”不一定只能二分裂。ID3和C4.5的树形是多叉的，一个离散特征有几个取值就分几个分支；CART强制二叉树，即使特征是离散的，也只做“属于某取值”和“不属于某取值”两种划分。这个差异在后面会直接影响基尼指数的使用方式。

1.2 把树看成规则集合，再看成条件概率分布

一棵完整的决策树，所有从根到叶的路径合在一起，构成一组互斥且完备的分类规则集合。

“互斥”意味着任意一个样本按照特征判断逐层走，只会落进唯一一个叶子，不可能同时匹配两条路径；“完备”意味着所有可能的特征组合都能走到某个叶子。这也是决策树可解释性的来源——你随时可以把一个预测结果回溯成若干条“特征等于什么”或“特征小于等于什么”的落点记录。

从概率视角看，每个叶子其实存放着一个条件概率分布 P(类别 | 落到该叶子的样本)。树的分类结果取该叶子下条件概率最大的那个类别。所以决策树学习本质上是估计一组条件概率分布，同时希望这棵树足够小、足够简洁。

书里强调的“决策树学习相当于用极大似然估计选择条件概率模型”，指的就是这个意思：树结构不同，对应的条件概率分布集合就不同，学习过程是在这个假设空间里挑一个模型，再挑一组概率参数。

1.3 学习一棵树必须解决的三个问题

读这一章时，最好先在心里搭一个框架：学习决策树只解决三件事。

第一是特征选择，也就是每次分裂时选哪个特征、按什么标准选。这涉及信息增益、信息增益比、基尼指数，是第五章最容易卡住的地方。

第二是树的生成，即如何从根节点开始，用递归方式不断分裂，直到满足停止条件。ID3、C4.5、CART三个算法的差别，集中体现在这个环节。

第三是剪枝，也就是如何对已经生成的树做简化，把过于复杂的分支删掉，提升泛化能力。很多初学者把注意力全放在特征选择上，等真拿到数据跑训练时才明白，剪枝才是控制模型效果的关键。

后面的章节，就按这三个问题逐一展开。

2. 特征选择：熵、条件熵与信息增益的完整链条

2.1 为什么要用“熵”来度量纯度

分裂的目标是让分支内部越来越“纯”，也就是同一个分支里的样本类别尽可能一致。那怎么量化“纯”？

教材引入了信息论里的熵。设训练数据集为 D，类别数为 K，第 k 类样本占比为 p_k，则熵定义为：

H(D) = -Σ p_k log₂(p_k)

熵越大表示不确定性越强、集合越混乱。拿两类问题举例：10个样本，5个正类5个负类，熵等于1；9个正类1个负类，熵约等于0.469。直观上，后者基本可以确定分类结果，所以混乱程度更低。

熵有两个值得记住的性质。第一，当各类别占比完全均匀时，熵最大，因为此时最不确定；第二，当某类占比趋近1时，熵趋近0，因为此时几乎可以确定。这也是树模型在分裂时“选熵下降最多”的理论基础。

2.2 信息增益怎么算：一个能动手验算的例子

熵衡量分裂前的混乱度，条件熵 H(D|A) 衡量按特征 A 划分后的加权平均混乱度，信息增益就是两者之差：

g(D, A) = H(D) - H(D|A)

信息增益越大，说明用了该特征后不确定性下降最多，也就是这个特征越值得用来分裂。

以书上的经典贷款数据为例。15个样本中9个“放贷”、6个“不放贷”，总熵 H(D) ≈ 0.971。按“年龄”特征划分：青年5人、中年5人、老年5人。青年组是2正3负，中年组是3正2负，老年组是4正1负。三组各自熵分别约为0.971、0.971、0.722，加权平均后条件熵约0.888，所以年龄的信息增益约0.083。

把其余特征也算一遍，结果如下表。

“有房子”的信息增益最大，于是根节点选择它。后续每个子节点重复这个过程，直到满足停止条件。

这类算例看起来简单，但非常值得自己动手验一遍。我在学习时发现，只读公式很容易产生“看懂了”的错觉，真拿纸笔算一次，才会注意到分组的样本数、每组的类别比例、加权计算这些细节，也才能真正理解条件熵为什么是“加权平均”。

2.3 信息增益的“偏好病”和信息增益比修正

信息增益有一个很要命的问题：它天然偏爱取值数量多的特征。

极端情况是拿“样本编号”当特征。每个样本一个取值，按它划分后每个分支只有一个样本，条件熵直接为0，信息增益达到最大。但这个特征完全没有泛化能力，新样本来了根本不会被分到已见过的分支里。

为了修正这个问题，C4.5改用信息增益比：

g_R(D, A) = g(D, A) / H_A(D)

其中 H_A(D) 是特征 A 本身的熵。特征取值越多，H_A(D) 通常越大，增益比就被压得越低，相当于给“多分支”加了惩罚。

但信息增益比并不完美，它又会反过来偏向取值很少的特征。C4.5在实际实现里采用一个启发式：先从候选特征中筛出信息增益高于平均水平的特征，再从中选信息增益比最大的。很多资料不写这个细节，但面试和推导时经常被问到，值得记住。

2.4 基尼指数：CART换了一种更省事的度量

CART分类树用的是基尼指数，定义是：

Gini(D) = 1 - Σ p_k²

对于两类问题，5正5负时基尼指数为0.5，9正1负时约为0.18。基尼指数和熵的变化趋势几乎一致，区别在于不用计算对数，工程上实现更快、数值上也更稳定。

按特征 A 划分后的基尼指数，是所有分支基尼指数的加权平均，CART在每个节点选择使划分后基尼指数最小的特征和切分点。

这里有个容易被忽略的细节：既然基尼指数和熵趋势一致，为什么树模型实际实现里很少直接用“误分类率”做分裂指标？因为误分类率对概率变化不敏感。类别占比从0.8变成0.9时，误分类率可能没变化，但熵和基尼指数都会明显下降，所以基于信息论的两个指标能更细致地区分不同划分的好坏。

2.5 三个指标在实践中的选择

我的个人经验是：做理解、做推导时优先掌握信息增益和增益比，因为概念链完整；做工程时，sklearn的DecisionTreeClassifier默认criterion='gini'，多数场景够用，换成entropy也很常见，两者通常不会带来质的区别。

不要花太多时间纠结“基尼指数一定比熵好”或者相反。它们在同一样本集上选出来的特征往往差不多，真正决定模型上限的是数据质量、特征工程和深度控制。

3. ID3、C4.5、CART：三棵树，三种生长逻辑

3.1 ID3：信息增益驱动的多叉树

ID3是最早被广泛使用的决策树生成算法，核心逻辑一句话：从根节点开始，每次在所有候选特征里选信息增益最大的特征作为当前分裂特征，按该特征每个取值生成一个子节点，然后对每个子节点递归调用同样过程，直到信息增益很小或没有可选特征。

ID3用的是多叉树，一个离散特征有几个取值就分几路。它的贡献是建立了“用信息增益做贪心生长”的范式，但缺陷也很明显：不支持连续特征，不处理缺失值，完全不剪枝，而且会选到“编号”这类高基数特征。真实数据里几乎没法直接用。

所以ID3对我来说更像一个教学模型，价值在于把树生长的基本流程讲清楚。

3.2 C4.5：把缺失值和连续值补上

C4.5在ID3基础上做了四个关键升级。

第一，用信息增益比替代信息增益，缓解多取值偏好。第二，支持连续特征，做法是把连续值排序后取相邻值中点作为候选切分点，再按最大增益比选出最优切分点。第三，支持缺失值，不是丢弃缺失样本，而是按权重策略处理。第四，增加剪枝机制，避免树无限生长。

C4.5的树形仍然是多叉树。它在教学和传统统计软件里地位很高，但现代机器学习框架里直接实现C4.5的反而很少。原因在于CART结构更简洁，同时还能回归，更适合被工程优化和集成。

3.3 CART：回归、分类都能做的二叉树

CART和前面两个算法最大的区别是：它是严格的二叉树，每个节点只做一次“是/否”的判断。

分类树用基尼指数最小化选特征；回归树则用平方误差最小化。回归树的生成核心是搜索最优切分变量 j 和最优切分点 s，把特征空间切成 R1 和 R2 两个区域，每个区域用样本标签均值做预测，目标是最小化：

min [ Σ(xi∈R1) (yi - c1)² + Σ(xi∈R2) (yi - c2)² ]

其中 c1、c2 是两个区域的均值。这个切分点通过遍历特征所有候选取值来确定，计算量不小，但逻辑非常直接。

因为CART是二叉树，它对离散特征也能做二分，比如“城市是不是北京”和“城市是不是上海”是两个不同的分裂点，同一个离散特征可以在不同层重复出现。这和多叉树“一个特征只在一层用一次”的直觉完全不同，经常有人在这里绕晕。

3.4 一表看懂三个算法的差异

面试时被问“三个算法有什么区别”，这张表基本就是标准答案。但更进一步的追问通常是：为什么CART要强制二叉树？答案和基尼指数的计算方式有关——基尼指数对二分类划分天然适合，二叉树也可以递归处理多取值特征，同时为后续随机森林、梯度提升的工程实现提供了统一结构。

3.5 现代框架里它们的位置

现在打开sklearn，找不到一个叫“ID3分类器”或“C4.5分类器”的类。DecisionTreeClassifier本质上是CART的优化实现：二叉树结构、支持分类回归、支持连续特征、剪枝对应ccp_alpha参数。而criterion参数可以设置成entropy，相当于在CART框架里改用信息增益选特征。

所以我的建议是：别执着于“复现ID3”，先把CART吃透，再回头对比ID3和C4.5的差异，知识体系会清晰很多。

4. 剪枝这一节，值得多读几遍

4.1 不剪枝会发生什么

贪心生成整棵树时，每个叶子追求的都是训练集上尽量纯净。问题在于：训练集里总会有噪声和偶然规律，树会把它们也一并学进去。叶子越分越细，单个叶子里的样本越来越少，个别噪声样本甚至被单独划分成一个分支。

结果就是训练集上几乎满分，验证集上掉分严重。这就是过拟合。

决策树的过拟合尤其隐蔽，因为它表现得很“合理”：每个分支都有真实的样本支撑，你很难从结果反推哪里是噪声。所以剪枝不是可选项，而是树模型训练的必要环节。

4.2 预剪枝和后剪枝的取舍

预剪枝在树生长过程中提前停止分裂。每次打算分裂前，先用验证集评估：这次分裂如果能带来验证集精度提升，就允许分裂，否则直接剪掉，当前节点变成叶节点。

优点是训练快，缺点是很可能欠拟合。因为当前分裂不提升精度，不代表后续几层不提升。可能你提前停止了，后面本来能挖出的规律也没了。预剪枝有点像“因噎废食”，它需要依赖经验设置好max_depth、min_samples_split、min_samples_leaf这些阈值。

后剪枝是先让树完整长出来，再从底向上尝试剪掉内部节点：把某个内部节点替换成叶节点，如果验证集精度不下降甚至提升，就保留这个剪枝结果。

后剪枝通常比预剪枝更稳，因为它基于完整树做全局判断，但代价是要先生成完整树，内存和训练开销更大。

4.3 CART代价复杂度剪枝：从α=0到α=∞

教材里的CART剪枝算法是第五章里最容易被跳过、但最该认真读的一节。

CART给树定义了一个带惩罚的损失函数：

C_α(T) = C(T) + α|T|

其中 C(T) 是训练误差，|T| 是叶节点数，α 是控制复杂度惩罚的系数。α=0时，完全生长的树最优；α 趋向无穷大时，单根节点的树最优。不同 α 对应不同复杂度的最优树。

对树中每个内部节点 t，计算阈值：

g(t) = [C(T_t) - C(t)] / (|T_t| - 1)

T_t 表示以 t 为根节点的子树，|T_t| 是这棵子树的叶节点数。当 α 小于 g(t) 时保留子树更好；α 增大到 g(t) 时，单节点 t 和子树 T_t 的损失相等，但单节点更简单，所以选择剪掉。

每轮选出所有 g(t) 中最小的节点剪枝，得到一棵新树，然后重复这个过程，直到只剩根节点。这样就得到一个嵌套子树序列 T₀, T₁, ..., T_n。最后用独立验证集或交叉验证在这个序列里选出误差最小的那棵，作为最终模型。

这个流程的精妙之处在于：它不是在拍脑袋定一个深度，而是给出一组“不同复杂度下各自最优”的树，再靠数据决定选哪棵。理解了这一点，再去看 sklearn 的ccp_alpha参数，思路就完全一致了。

4.4 工程里的剪枝其实是参数调优

现实中很少有人自己实现剪枝流程，工程上主要靠预剪枝参数控制树的大小。

比较实用的几个参数是max_depth、min_samples_split、min_samples_leaf和max_features。它们本质上是在限制树的生长空间：深度太大致过拟合，叶子样本太少致噪声影响过大。max_depth=3到5的树在很多结构化数据上已经能看、能用。

sklearn 还提供了后剪枝参数ccp_alpha，对应CART代价复杂度剪枝。实际操作时可以按一小步一小步增大ccp_alpha，用验证集观察精度变化，选出精度下降可接受范围内最简洁的那棵树。

提示：调树参数时先看训练集和验证集的精度 gap。gap 很大说明过拟合，往限制生长方向调；两者都低说明欠拟合，需要放开限制或检查特征工程。

5. 课本之外的功课：连续值、缺失值和sklearn实测

5.1 连续特征切分点怎么找

C4.5和CART对连续特征的做法类似：先把训练样本按该特征值排序，把相邻两个值的中点当成候选切分点，逐个尝试，选出使信息增益、增益比或基尼指数最优的那个点作为切分点。

举个例子：某连续特征取值是 [1, 2, 3, 5, 8]，排序后相邻中点分别是 1.5、2.5、4、6.5。对这些候选点逐个计算分裂收益，收益最大的就是当前节点的最优切分点。

连续特征还有一个特点：它可以在不同层反复使用，不违反“特征只用一次”的直觉——这个直觉只在多叉树处理离散特征时才成立。在CART二叉树里，一个连续特征完全可以先在第1层按3.0划分，又在第3层按7.5划分。

真正做工程时会遇到性能问题：每个节点处理连续特征都要重新排序，特征多时训练很慢。所以有些场景会先把连续特征分桶离散化，减少排序开销，同时降低过拟合风险。

5.2 缺失值处理的权重思想

C4.5处理缺失值的思路，不是把缺失样本丢掉，而是给样本分配权重，再按权重参与分裂和分布。

具体分两步。第一步，在计算某个特征的增益时，只拿该特征没有缺失的样本算“增益”，然后把结果乘以无缺失样本的占比，作为最终增益。第二步，样本落到各分支时，缺失样本不是不知道往哪走，而是按各分支现有样本比例，带着权重同时进入所有分支，后续计算时它的贡献被“稀释”。

这个思想的本质是：缺失信息没有被浪费，只是被降权使用。相比直接丢弃缺失行，它能保留更多信息，尤其当缺失值比例较高时差异更明显。

sklearn 的树模型在新版本中开始逐步支持缺失值，但旧版会直接报错或强制要求预处理。真正理解C4.5的权重思路，对阅读其他树类算法源码和回答面试题都很有帮助。

5.3 多变量决策树，留个印象即可

教材里还提到一种多变量决策树：每个非叶节点不是拿单个特征做判断，而是对特征的线性组合做判断，形式类似“特征1×0.3 + 特征2×0.7 ≥ 阈值”。

好处是表达能力更强，边界不再是轴平行，而是可以有斜向切割。代价是解释性明显下降，每个节点变成了一个难以直接口述的线性公式，计算复杂度也上升很多。

主流工业级实现依旧是标准CART，多变量树更多属于研究方向。这一节了解思想即可，不必深挖。

5.4 用sklearn跑树模型时容易踩的坑

我用DecisionTreeClassifier踩过不少坑，挑几个典型的分享。

类别特征不能直接喂给树。sklearn的树默认不支持原生类别型输入，需要先用OrdinalEncoder或OneHotEncoder处理。OneHot之后高基数特征依然更容易被选中，这和前面讲的信息增益偏好一脉相承。

版本不同，缺失值支持也不同。旧版本遇到 NaN 直接报错，新版本逐步支持缺失值策略，但不要假设所有环境都支持，先查清楚当前版本再决定是否预处理。

树模型方差大，要固定随机种子。同一个训练集，不固定random_state，两次训练出来的树可能差别很大。这是决策树本身的特性，也是后面随机森林、梯度提升存在的根本原因。

可视化要限制深度。用plot_tree导出树时，深度超过4到5层就很难看清，建议先用max_depth限制，再可视化，否则画出来一团黑。

feature_importances_有偏好。sklearn给出的特征重要性基于节点分裂时的基尼减少量累计，对数值特征和高基数特征天然更友好。解读时别当绝对真理，只作为特征筛选的参考之一。

5.5 这一章是所有树模型的地基

随机森林做的事情，是对多棵决策树做Bagging平均；梯度提升树做的，是对弱决策树做加法；XGBoost、LightGBM虽然加入了大量工程优化，但“找最优切分”“控制树复杂度”“叶子权重”这些核心模块，依然能从第五章的框架里找到对应。

把单棵决策树的逻辑吃透，后面看集成模型的源码会顺畅很多。如果跳着读，只背公式不推敲“为什么这么设计”，到了集成学习阶段很容易被各种不变量、梯度近似、直方图分裂绕晕。

我自己读这一章时最大的感受是：决策树的公式并不多，难点全在“为什么”。信息增益为什么有偏好，剪枝为什么要用 α 控制，缺失值为什么要用权重——每一个问题都对应真实数据里的一个痛点。

建议你读完这篇内容后，拿一份真实表格数据，手动对两三个特征算一遍信息增益，再拿sklearn调一调max_depth和ccp_alpha，体会会比只看书深很多。决策树这章不长，但它是整个树模型家族的地基，值得反复啃。