种树不止为了环境！谁说决策树不是树。

本文介绍的内容如下所示：

1. 生活中的决策树

有一人前来买瓜…如何能够观察瓜的特征，从而在没熟的瓜中一眼丁真出保熟的甜瓜呢？这样是否能够避免那场因为不熟的瓜而导致的惨案？让ai一搜得到一个表格：

特征	好瓜表现	坏瓜表现
瓜皮颜色	鲜亮、均匀，底色绿	颜色暗淡、不均匀、有斑点
条纹	纹路清晰、深浅分明	纹路模糊、杂乱无章
瓜蒂	绿色新鲜，瓜蒂卷曲	瓜蒂干枯、发黄或脱落
瓜脐	小而圆，颜色浅黄	大而扁，颜色深

这张表告诉了我们一沓决策规则。而决策树，就是把这些规则组织成树形结构，让计算机也能像老吃家对各种瓜进行”望闻问切”的检查。

2. 决策树的基本概念

2.1 树的结构：从瓜摊到数据结构

想象你站在瓜摊前，脑子里的决策过程是这样的：

这一系列的决策都对应着决策树算法中几个必须了解的概念：

def	meaning	example
根节点	树的起点，包含全部样本	“瓜皮颜色鲜亮？”
内部节点	中间决策点，对应一个特征测试	“条纹清晰？”、”瓜蒂新鲜？”
叶子节点	最终决策结果，不再分裂	“好瓜🍉”、”坏瓜❌”
路径	从根到叶的决策一条龙	颜色→条纹→结果
深度	树的最大层数	买瓜时思考了四步

2.2 决策树的两大特性

特性1-互斥性

任意两个叶子节点的决策路径不可能同时成立

路径 A: 颜色鲜亮 → 条纹清晰 → 好瓜
路径 B: 颜色鲜亮 → 条纹模糊 → 坏瓜

对于一个具体的瓜，只能走其中一条路径，不会既好又坏

特性2-完备性

所有可能的输入样本都能找到对应的叶子节点

1 2	无论瓜是什么特征组合，最终都会落到某个叶子节点上不会出现"无法判断好坏"的两难情况，当然判断错误是另外一回事。

2.3 条件概率决策

决策树预测条件概率：

$P(Y=c_k \mid X_1=x_1, X_2=x_2, ..., X_n=x_n)$

人话：

在已知特征瓜皮颜色=$x_1$、条纹=$x_2$、瓜蒂=$x_3$…的条件下，这个瓜是好瓜 ($c_k$) 的概率是多少？

叶子节点存储的就是这个概率的值。某个叶子节点包含 10 个训练样本，其中 8 个好瓜、2 个坏瓜，那么：

$P(\text{好瓜} \mid \text{此叶节点}) = 0.8$

2.4 决策树属于归纳学习

归纳 (Induction) vs 演绎 (Deduction)：

类型	方向	例子
演绎	一般→特殊	“所有卷蒂瓜都甜” + “这个瓜卷蒂” → “这个瓜甜”
归纳	特殊→一般	“这100个卷蒂瓜都甜” → “卷蒂瓜可能都甜”

决策树是归纳学习：从大量具体样本中归纳出通用规则。

2.5 树的好坏

寻找最好的决策树，就是希望这个模型不但在训练集上的表现优良，而且在其他数据的测试集上也表现不俗，具有足够的泛化能力；在同一性能下，模型所代表的树越简单，运行的性能就越好：

评价指标	含义	问题
深度	树太深规则太细；树太浅规则太粗	内部指标
节点数	节点多规则复杂，节点少规则简单	内部指标
复杂度	衡量深度+复杂度	内部指标
拟合优度	在测试集上的表现优度	外部指标

3. 特征选择

决策树有个大问题，硅基脑袋如何学习到每次分裂应该选哪个特征？，我咋知道这个特征好，那个特征差呢？就像买瓜例子中，为什么先问”颜色”而不是先问”瓜脐”？这就需要用熵来衡量。

3.1 熵-不确定性的度量

熵的定义：

$H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k$

$D$ 数据集； $K$ 类别数量；$p_k$ 第 $k$ 类样本的比例。

买瓜例子：假设我们有 10 个瓜，6 个好瓜，4 个坏瓜：

$p_{\text{好}} = 0.6, \quad p_{\text{坏}} = 0.4$ $H(D) = -(0.6\log_2 0.6 + 0.4\log_2 0.4) \approx 0.971 \text{ bit}$

熵的直观理解：

情况	好瓜比例	坏瓜比例	熵值	含义
完全确定	100%	0%	0	没有不确定性
完全不确定	50%	50%	1.0	最大不确定性
部分确定	60%	40%	0.971	中等不确定性

3.2 条件熵-已知特征后的不确定性

定义：

$H(D \mid A) = \sum_{v=1}^{V} \frac{|D_v|}{|D|} H(D_v)$

$A$ 某个特征； $V$ 特征 $A$ 的取值数量； $D_v$ 特征 $A$ 取值为 $v$ 的子集。

买瓜时，用 “瓜皮颜色” 特征进行划分：

颜色	样本数	好瓜	坏瓜	子集熵
鲜亮	6	5	1	$H_1 = 0.65$
暗淡	4	1	3	$H_2 = 0.81$

$H(D \mid A_\text{颜色}) = \frac{6}{10} \times 0.65 + \frac{4}{10} \times 0.81 = 0.714 \text{ bit}$

在知道颜色后，不确定性从 0.971 降到了 0.714。

3.3 特征的价值-信息增益

$\text{g}(D, A) = H(D) - H(D \mid A)$

比如对于瓜的颜色特征：

$\text{g}(D, A_\text{颜色}) = 0.971 - 0.714 = 0.257 \text{ bit}$

知道特征 $A_{i}$ 后，不确定性减少了多少可以被信息增益衡量！信息增益越大，特征越好！

3.4 信息增益比-避免特征对数值的偏好

信息增益在日常计算中存在一个现象：信息增益偏向取值多的特征：

1 2	特征 A: 颜色 (2 种取值) → Gain = 0.257 特征 B: 瓜的评级 (一级瓜、二级瓜、三级瓜、优级瓜、特级瓜) → Gain > 0.257

使用原总熵进行数据尺度上的归一化后，一定程度熵可以抑制，取值越多的特征，分母越大，$g_R$ 越小：

$g_{R}(D, A) = \frac{g(D, A)}{H_{A}(D)} = \frac{g(D, A)}{-\sum_{i=1}^{M} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}}$

3.5 基尼指数 (Gini Index)-另一种度量方法

Gini指数的定义如下，对于存在 $K$ 类的样本集：

$\text{Gini}(D) = 1 - \sum_{k=1}^{K} p_k^2$

特征分裂后的基尼指数：

$\text{Gini}_A(D) = \sum_{v=1}^{V} \frac{|D_v|}{|D|} \text{Gini}(D_v)$

通过计算子树的指数和该节点开始的单节点数的字之差：

$\text{Gini}_A(T) - \text{Gini}_A(T_k)$

如果基尼指数越小，差值越大，特征越好优度更好。

4. 为了跳出思维怪圈而剪枝！

4.1 剪枝 (Purning)

剪枝能够杀死训练集误差给模型带来的过拟合弊端，同时也给模型增加泛化能力。牺牲一点训练精度，换取更好的泛化能力看起来对于过拟合的模型 (比如下面那个) 而言是个很好的选择。

1 2	训练集：100 个瓜，准确率 99% 测试集：50 个新瓜，准确率只有 60%

4.2 预剪枝 (Pre-Pruning) & 后剪枝 (Post-Pruning)

在树构建过程中就设置停止的条件。就像把豆芽菜放在暗室里，注定其颜色是黄的，这种方法就是预剪枝。常用的有这两种：

最大深度，即树不能超过 d 层

最小信息增益，即 $g(A,D)<ε$ 的情况下就不分裂

先让树充分生长，然后自底向上剪掉不必要的分支的方法就是后剪枝，是不是很像韭菜长了一茬割一茬呢(●’◡’●)。

4.4 后剪枝方法详解

method 1: 悲观错误剪枝 (PEP, Pessimistic Error Pruning)

用统计修正来估计真实错误率。

首先计算进行了连续性修正的错误概率：

$E_{T} = 1-P(Y = k | X) = \frac{N_e + 0.5}{N}$ $E_{T_{t}} = \frac{\sum N_{e_{i}} + 0.5 \times L}{N}$

$N_e$ 剪枝后叶节点作为单节点的错误数 ; $N_{e_{i}}$ 子树 $i$ 的错误分类总数 ; $L$ 子树叶子节点总数 ; $N$ 样本总数 ;

$0.5$ 为统计学上的连续性修正，二项分布是一个离散分布，写作为：

$P(X = k ) = \binom{N}{k} \times p^k \times (1-p)^{N-k}$

这个离散二项分布的期望是 $E=np$、方差是 $\alpha^2 = np(1-p)$ ，因而标准差为 $\text{std} = \sqrt{np(1-p)}$，发现二项分布和正态分布的期望方差相似的规律，对概率进行累计求和会发现正态分布的结果会比离散的二项分布的结果要小，计算累计密度时则需要加上0.5。

$\text{如果 }E_{T_{t}} \leq E_{T} + \text{std}，\text{小于悲观误差，则剪枝}$

method 2：基于最小错误剪枝 (MEP, Minimum Error Pruning)

核心思想：用验证集直接评估剪枝前后的错误率。

步骤：

预留 30% 数据作为验证集
用训练集长满树
自底向上，对每个内部节点：
- 计算剪枝后在验证集的错误率
- 计算不剪枝在验证集的错误率
- 选择错误率低的方案

method 3：代价复杂度剪枝 (CCP, Cost-Complexity Pruning)

代价复杂度剪枝可以在模型的训练错误率与树的复杂度之间寻找最优平衡点，其代价函数定义为：

$C_\alpha(T) = C(T) + \alpha \cdot |T|$

其中 $C(T)$ 表示子树 $T$ 在训练数据上的经验误差：

$C(T) = \sum_{t=1}^{T} N_t \cdot H_{t}(T) = -\sum_{t=1}^{T}\sum_{i=1}^{M} N_t \log_2 \frac{N_{tm}}{N_t}$

$T$ 表示树的叶节点个数，$\alpha \geq 0$ 是调节两者权重的复杂度惩罚参数。当 $\alpha \rightarrow 0$ 时模型仅追求训练误差最小，倾向于生成完整树；当 $\alpha$ 增大时，模型更偏好结构简单的树, $\alpha \rightarrow \infty$ 时模型为单节点树。

剪枝过程从完整树 $T_0$ 开始，对每个内部节点 $t$ 定义其子树 $T_t$，计算该节点的剪枝增益，$C_\alpha(t)$ 表示该节点为单节点树是的代价函数，相对的，$C_\alpha(T_t)$就是该节点存在子树延续的代价函数:

$g(t) = \frac{C_\alpha(t) - C_\alpha(T_t)}{T_t - 1} = \frac{[C(t) + \alpha \cdot 1] - [C(T_t) + \alpha \cdot |T_t|]}{|T_t| - 1}$

在临界点处 $C(t) - C(T_t) = \alpha \cdot (T_t - 1)$，因此 $g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1}$ 是剪掉以 $t$ 为根的子树后，单位复杂度减少所带来的误差增加量。

首先令 $\alpha_0 = 0$，计算当前树中所有内部节点的 $g(t)$ 值，选择 $g(t)$ 最小的节点 $t_0$ 进行剪枝，将其子树 $T_{t_0}$ 替换为单叶节点，得到新树 $T_1$，同时记录 $\alpha_1 = g(t_0)$；然后对 $T_1$ 重复上述过程，得到 $\alpha_2, T_2$，依此类推，直到树退化为仅含根节点的树 $T_n$，由此生成一个嵌套的树序列 $\{T_0, T_1, T_2, \ldots, T_n\}$ 和对应的参数序列 $\{0 = \alpha_0 < \alpha_1 < \alpha_2 < \ldots < \alpha_n\}$。

对于任意 $\alpha \in [\alpha_i, \alpha_{i+1})$，树 $T_i$ 都是该区间内代价函数 $C_\alpha(T)$ 的最优解。最后，交叉验证树序列中的每棵树 $T_i$ 计算其 Gini 或 MSE $R_{\text{val}}(T_i)$，选择验证集误差最小的树 $T_k$ 作为最终模型，若多棵树误差相近则优先选择复杂度更低的树。

5. ID3 algorithm：决策树的开山之作

5.1 算法流程

1. 判断终止条件

若数据集中所有样本属于同一类别（$\forall \mathbf{x} \in D, y(\mathbf{x}) = C_k$），或可用特征集为空（$A = \emptyset$），则直接生成叶节点并返回；否则继续执行后续步骤。

2. 计算数据集熵

计算当前数据集 $D$ 的经验熵，用于衡量数据集的混乱程度：

$H(D) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$

其中 $K$ 为类别总数，$|C_k|$ 为第 $k$ 类样本的数量，$|D|$ 为样本总数。

3. 计算特征信息增益

对每个特征 $A_i \in A$，计算其信息增益：

$g(D, A_i) = H(D) - H(D|A_i) = H(D) - \sum_{v=1}^{V} \frac{|D_v|}{|D|} H(D_v)$

其中 $D_v$ 为特征 $A_i$ 取值为 $v$ 的子数据集，$V$ 为 $A_i$ 的取值个数。

4. 选择最优划分特征

选取信息增益最大的特征 $A_g$ 作为当前节点的划分标准：

$A_g = \underset{A_i \in A}{\arg\max} \ g(D, A_i)$

若 $g(D, A_g) < \epsilon$（$\epsilon$ 为预设阈值），则生成叶节点并标记为 $D$ 中的多数类；否则以 $A_g$ 为当前节点继续划分。

5. 递归构建子树

对 $A_g$ 的每一个可能取值 $v$：

生成分支节点
对应子数据集 $D_v = \{ \mathbf{x} \in D \mid A_g(\mathbf{x}) = v \}$
递归调用构建过程：$\text{Tree}_v = \text{ID3}(D_v, A \setminus \{A_g\})$

6. 返回决策树

整合所有分支节点，输出完整的决策树 $T$。

5.3 例子演示

数据集

编号	颜色	条纹	瓜蒂	敲声	好瓜
1	鲜亮	清晰	新鲜	清脆	是
2	鲜亮	清晰	新鲜	沉闷	是
3	鲜亮	清晰	干枯	清脆	是
4	鲜亮	模糊	新鲜	清脆	是
5	鲜亮	模糊	干枯	沉闷	否
6	鲜亮	模糊	干枯	清脆	否
7	青绿	清晰	新鲜	清脆	是
8	青绿	清晰	干枯	清脆	是
9	青绿	模糊	新鲜	沉闷	否
10	青绿	模糊	干枯	沉闷	否
11	暗淡	清晰	新鲜	沉闷	否
12	暗淡	清晰	干枯	沉闷	否
13	暗淡	模糊	新鲜	沉闷	否
14	暗淡	模糊	干枯	沉闷	否
15	青绿	清晰	新鲜	清脆	是

第 1 步：计算根节点熵

$H(D) = -\left(\frac{7}{15} \log_2 \frac{7}{15} + \frac{8}{15} \log_2 \frac{8}{15}\right)$ $H(D) = -(0.467 \times -1.099 + 0.533 \times -0.907) = 0.997 \text{ bit}$

第 2 步：计算各特征信息增益

特征一：颜色

取值	样本数	好瓜	坏瓜	子集熵计算
鲜亮	6	4	2	$H = -(\frac{4}{6}\log_2\frac{4}{6} + \frac{2}{6}\log_2\frac{2}{6}) = 0.918$
青绿	5	4	1	$H = -(\frac{4}{5}\log_2\frac{4}{5} + \frac{1}{5}\log_2\frac{1}{5}) = 0.722$
暗淡	4	0	4	$H = 0$ (纯度100%)

使用颜色分割的条件熵：

$H(D|A_\text{颜色}) = \frac{6}{15} \times 0.918 + \frac{5}{15} \times 0.722 + \frac{4}{15} \times 0 = 0.607$

信息增益：

$g(D,A_\text{颜色}) = 0.997 - 0.607 = \mathbf{0.390}$

第 3 步：选择最优划分特征

特征	信息增益
颜色	0.390
条纹	0.289
瓜蒂	0.289
敲声	0.289

选择颜色作为根节点的最优划分特征。

第 4 步：递归生成子树

继续根据上述的步骤生成子树。

第 5 步：返回决策树

当特征集 $A$ 为空时或样本数据点分完后，返回子树如下。

6. C4.5 算法

6.1 核心改进

C4.5 算法在 ID3 的基础上进行了3项重要改进，使其更加实用和稳健。

改进一：信息增益比代替信息增益

ID3 算法使用信息增益作为特征选择标准，但存在的问题我们上文已经提前剧透了：偏向于取值较多的特征。C4.5 引入信息增益比代替信息增益来校正这一偏差：

$g_{R}(D, A) = \frac{g(D, A)}{H_A(D)}$

改进二：连续特征离散化

ID3 只能处理离散特征，而 C4.5 可以处理连续特征。其核心思想是对连续特征寻找最佳分割点，将连续值转化为二值离散特征。

首先将该特征的所有取值升序排列；取相邻两个值的中点作为候选分割点。若有 $n$ 个不同取值，则产生 $n-1$ 个候选分割点；对每个候选分割点计算信息增益比；最优选择增益比最大的分割点作为该特征的最优划分点。

改进三：后剪枝机制

C4.5 引入后剪枝来提高泛化能力。剪枝策略基于错误率评估：

首先，生成完整的决策树。然后，用独立的验证集估计每个子树的错误率。接着，自底向上检查每个内部节点，如果将该子树替换为叶节点后错误率不增加（或有所减少），则执行剪枝。重复此过程直到根节点，无法再剪枝为止。

这种基于错误率的剪枝能有效降低模型复杂度，避免过拟合。

6.2 C4.5 算法流程

输入：训练集 $D$，特征集 $A$，阈值 $\epsilon$

输出：决策树 $T$

过程：
首先检查终止条件。若 $D$ 中所有样本属于同一类别，直接返回单节点树，标记为该类别。若特征集 $A$ 为空，或样本数量少于预设阈值，也返回单节点树，标记为 $D$ 中的多数类。

其次进行特征选择。对每个特征 $A_i$，若为连续特征则寻找最佳分割点；若存在缺失值则计算比例 $\rho$ 进行修正；然后计算该特征的信息增益比 $g_{R}(D, A_i)$。

接着选择最优特征。选取信息增益比最大的特征 $A_g$。若 ${g_{R}}(D, A_g) < \epsilon$ ，说明没有特征能有效划分数据，返回单节点树。

然后递归构建树。对 $A_g$ 的每个取值（或连续特征的分割点）生成子节点，将缺失该特征值的样本带权重分配到各子节点，对每个子数据集递归调用 C4.5 算法。

最后进行后剪枝。生成完整树后，使用验证集进行自底向上的剪枝操作，直到无法再剪枝为止。

返回最终生成的决策树 $T$。

7. CART 算法

CART（Classification And Regression Tree）算法是 ID3/C4.5 的改进版本。使用二叉树替换转化可能出现的多叉树，使用Gini 指数而非基于熵的信息增益度量对特征进行选择，改用代价-复杂度剪枝算法结合*交叉验证选择最优的剪枝后子树作为模型代表得出最优子树 $T$。

7.2 回归树-平方误差 (MSE)

回归树用于预测连续值，其核心思想是将输入空间划分为若干个区域，每个区域内的样本使用相同的预测值。

叶节点预测值： 每个叶节点的预测值为该节点内所有样本目标值的均值：

$c_m = \frac{1}{|R_m|} \sum_{x_i \in R_m} y_i$

其中 $R_m$ 表示第 $m$ 个叶节点对应的区域。

分裂标准： 选择能使平方误差最小化的特征和分割点：

$\min_{j,s} \left[ \sum_{x_i \in R_1} (y_i - c_1)^2 + \sum_{x_i \in R_2} (y_i - c_2)^2 \right]$

其中 $j$ 表示特征索引，$s$ 表示分割点，$R_1$ 和 $R_2$ 分别表示分割后的两个区域，$c_1$ 和 $c_2$ 分别为两个区域内样本的均值。回归树的目标是让每个区域内的样本尽可能相似，这样用均值代表该区域的预测值时误差最小。

7.4 CART 算法流程

分类树构建过程

输入： 训练集 $D$，特征集 $A$，停止条件（如最小样本数、最大深度等）

输出： 二叉决策树 $T$

执行过程：

首先检查是否满足停止条件。若满足（如所有样本属于同一类、样本数少于阈值、达到最大深度等），则返回叶节点，预测值为该节点中的多数类别。

其次进行最优分裂点搜索。对每个特征 $A_j$，遍历其所有可能的分割点 $s$，计算每个分割点对应的基尼指数，找到该特征的最佳分割点。

然后选择全局最优分裂。比较所有特征的最佳分割点，选择基尼指数最小的 $(j^, s^)$ 作为当前节点的分裂方案。

接着分割数据集。按照最优分裂点将数据集划分为两部分：$D_1 = \{x \mid x_{j^} \leq s^\}$ 和 $D_2 = \{x \mid x_{j^} > s^\}$。

最后递归构建子树。对 $D_1$ 和 $D_2$ 分别递归调用上述过程，构建左右子树。

生成完整树后，进行代价复杂度剪枝，得到最终的决策树 $T$。

7.5 代价复杂度剪枝

CART 使用代价复杂度剪枝（Cost-Complexity Pruning），剪枝步骤：

第一步，从完整树 $T_0$ 开始。

第二步，对每个内部节点 $t$，计算剪枝后的误差增加量与叶节点减少量的比值：

$g(t) = \frac{R(t) - R(T_t)}{|T_t| - 1}$

其中 $R(t)$ 表示将节点 $t$ 作为叶节点时的误差，$R(T_t)$ 表示以 $t$ 为根的子树的误差，$|T_t|$ 表示该子树的叶节点数。

第三步，选择 $g(t)$ 最小的节点进行剪枝，得到新树 $T_1$。

第四步，重复上述过程，得到树序列 $T_0, T_1, T_2, \ldots, T_n$，其中 $T_n$ 为只有根节点的树。

第五步，使用独立的验证集评估每个树的性能，选择验证误差最小的树 $T_k$ 作为最终模型。

8. 总结

决策树单模型能力有限，但集成方法让它焕发第二春：

集成方法	核心思想	代表算法
Bagging	多棵树投票	Random Forest
Boosting	迭代修正错误	GBDT, XGBoost, LightGBM

现代梯度提升树（XGBoost/LightGBM/CatBoost）是 Kaggle 竞赛和工业界常用手段之一。

植树节种下的不只是一棵树，更归纳的形象化思维智慧的闪光！⭐

参考文献：

Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning.
Quinlan, J. R. (1993). C4.5: Programs for Machine Learning.
Breiman, L., et al. (1984). Classification and Regression Trees.
李航。(2012). 统计学习方法。清华大学出版社。

机器学习算法04-决策树