数学原理

本章目标

1. 理解决策树如何通过递归划分特征空间完成分类。
2. 理解熵、信息增益、基尼不纯度在当前实现中的角色与数学定义。
3. 理解树深、叶节点数和剪枝思路为什么与过拟合直接相关。
4. 掌握每个超参数对应的数学含义与控制对象。

重点方法与概念速览

名称	类型	作用
信息熵 $H(Y)$	不纯度度量	衡量类别分布混乱程度，$H(Y)=-\sum p_k{\log }_2{p}_k$
信息增益 $\text{Gain}(D,A)$	划分标准	衡量某个特征带来的不确定性下降，$\text{Gain}=H(D)-H(D\mid A)$
增益率 $\text{Gain\_ratio}$	划分标准	修正信息增益偏好多值特征的问题
基尼不纯度 $\text{Gini}(D)$	划分标准	当前源码默认 criterion='gini' 对应的核心度量，$\text{Gini}(D)=1-\sum p_k^2$
树深	复杂度指标	反映树的层级深度，与 max_depth 参数直接对应
叶节点数	复杂度指标	反映划分后的终端区域数量，与 min_samples_leaf 参数相关

1. 决策树的核心思想

决策树通过递归地选择最优特征并按其取值将数据集分割为子集，构建一棵树状判别结构。每个内部节点对应一个特征判断，每个叶节点对应一个类别输出。

理解重点

• 决策树不像逻辑回归那样先学习一条全局边界，而是不断把数据切成更纯净的小区域。
• 每一次划分，本质上都是在问：用哪个特征、按什么阈值切，能让子节点更"纯"。
• 这也是为什么它常常被理解为一连串 if-else 规则的组合。

2. 熵与条件熵

信息熵

对随机变量 $Y$ 取 $K$ 个类别，若分布为 $p_k=P(Y=k)$，信息熵定义为：

$$H(Y)=-\sum _{k=1}^K{p}_k{\log }_2{p}_k$$

• 当所有类别等概率时，熵最大。
• 当所有样本属于同一类别时，熵为 0。

条件熵

给定特征 $A$ 将数据划分为 $V$ 个子集 $D_1,D_2,\dots ,D_V$：

$$H(Y\mid A)=\sum _{v=1}^V\frac{|D_v|}{|D|}H(Y_{D_v})$$

理解重点

• 熵衡量的是节点的类别混乱程度。
• 条件熵衡量的是：在用某个特征切分之后，子节点整体还剩多少混乱度。
• 因此一个好的划分，应该让条件熵尽量小。

3. 信息增益与增益率

信息增益

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

ID3 算法选择信息增益最大的特征进行分裂。

增益率

为修正信息增益偏好多值特征的问题，C4.5 引入特征固有值：

$$\text{IV}(A)=-\sum _{v=1}^V\frac{|D_v|}{|D|}{\log }_2\frac{|D_v|}{|D|}$$$$\text{Gain\_ratio}(D,A)=\frac{\text{Gain}(D,A)}{\text{IV}(A)}$$

理解重点

• 信息增益本质上是在比较划分前后的不确定性减少了多少。
• 增益率则试图抑制"取值很多的特征看起来天然更有用"这一偏差。
• 当前源码虽然没有直接使用这些术语作为参数，但理解这部分有助于读懂决策树分裂的基本思想。

4. 基尼不纯度与 criterion 参数

当前源码使用基尼不纯度作为默认划分标准。基尼不纯度的数学定义为：

$$\text{Gini}(D)=1-\sum _{k=1}^K{p}_k^2$$

对某个特征划分后的总体基尼不纯度：

$$\text{Gini}(D,A)=\sum _{v=1}^V\frac{|D_v|}{|D|}\text{Gini}(D_v)$$

参数速览

参数名	类型	说明	示例取值
criterion	str	划分不纯度度量函数。"gini" 对应 $\text{Gini}(D)=1-\sum p_k^2$，计算更快；"entropy" 对应 $H(D)=-\sum p_k{\log }_2{p}_k$，对概率变化更敏感。两者在大多数任务中表现接近。默认为 "gini"	"gini"、"entropy"、"log_loss"

理解重点

• 当前工程实现的理论核心应该落在基尼不纯度，因为源码默认 criterion='gini'。
• 基尼和熵都能衡量节点纯度，但基尼计算更快，也是 CART 风格实现的默认选择。
• 因此文档不应平均展开所有树算法，而应优先解释当前真实实现对应的 CART 风格分类树。

5. 树深与叶节点——复杂度控制参数

max_depth

树的最大深度 $d_{max}$。深度每增加一层，模型就能多切一次特征空间。数学上，一棵深度为 $d$ 的完全二叉树最多有 $2^d$ 个叶节点。

min_samples_split

内部节点继续分裂所需的最小样本数。设当前节点包含 $n$ 个样本，若 $n<$ min_samples_split，则该节点不再分裂。

min_samples_leaf

叶节点必须包含的最小样本数。若一次分裂会导致任一子节点样本数少于该值，分裂被拒绝。

参数速览

参数名	类型	说明	示例取值
max_depth	int 或 None	树的最大深度 $d_{max}$。限制划分轮数——深度越大，模型越复杂，越容易过拟合。None 表示不限制，节点持续分裂直到纯净或触及其他停止条件。默认为 None	3、6、None
min_samples_split	int 或 float	内部节点再划分所需最小样本数。若为 float（如 0.1），表示比例 × 总样本数。增大可抑制过拟合。默认为 2	2、4、10
min_samples_leaf	int 或 float	叶节点最少样本数。若为 float，表示比例。增大使树更保守——叶节点不会包含极少数样本。默认为 1	1、2、5

理解重点

• 树越深，越容易把训练集切得很细，拟合得很"完美"。
• 但切得太细通常意味着泛化能力下降，更容易记住噪声。
• 当前源码把 max_depth=6、min_samples_split=4、min_samples_leaf=2 显式写出来，就是在限制树的复杂度。

6. 剪枝与复杂度控制

预剪枝（当前源码采用）

在构建树时提前终止分裂，典型方式包括限制树深、限制叶节点最小样本数、限制继续分裂所需最小样本数。当前源码通过 max_depth、min_samples_split、min_samples_leaf 实现预剪枝。

后剪枝（理论补充）

在树构建完成后再回头删掉一部分分支，如代价复杂度剪枝（Cost Complexity Pruning）：

$$R_{\alpha }(T)=R(T)+\alpha |T|$$

其中 $R(T)$ 是树的误分类损失，$|T|$ 是叶节点数，$\alpha$ 是复杂度惩罚系数。

参数速览

参数名	类型	说明	示例取值
ccp_alpha	float	代价复杂度剪枝参数 $\alpha$。越大则剪枝越激进，叶节点越少。数学上最小化 $R(T) + \alpha \cdot	T

理解重点

• 当前源码最直接体现的是预剪枝思想，因为它通过 max_depth、min_samples_split、min_samples_leaf 控制复杂度。
• 文档可以提到后剪枝是经典思路和 ccp_alpha 参数，但不能写成当前流水线里已经显式执行了某个后剪枝步骤。

7. 数学原理如何映射到当前源码

以下表格将本章涉及的数学概念与当前仓库的代码实现一一对应：

数学概念	数学符号/公式	代码实现
基尼不纯度	$\text{Gini}(D)=1-\sum p_k^2$	criterion='gini'（DecisionTreeClassifier 默认）
信息熵	$H(D)=-\sum p_k{\log }_2{p}_k$	criterion='entropy'
最大树深	$d_{max}$	max_depth=6
最小分裂样本数	—	min_samples_split=4
最小叶节点样本数	—	min_samples_leaf=2
代价复杂度剪枝	$R_{\alpha }(T)=R(T)+\alpha \cdot |T|$	ccp_alpha=0.0（当前未启用）
特征重要性	基于不纯度下降加权	model.feature_importances_
树深度	实际 $d$	model.get_depth()
叶节点数	实际 $|T|$	model.get_n_leaves()

常见坑

1. 只知道决策树会"分裂"，却说不清它分裂的依据是不纯度下降。
2. 把信息增益、增益率、基尼不纯度混为一谈。
3. 忽略树深与叶节点数本质上是在控制模型复杂度。
4. 把 criterion='entropy' 与交叉熵损失函数混淆——这里的 entropy 是节点不纯度，不是损失函数。
5. 把剪枝写成当前源码里已经显式实现的完整后处理流程。

小结

• 决策树的核心，是不断选择能最大程度降低不纯度的划分。
• 当前源码默认使用 criterion='gini'，数学上对应 $\text{Gini}(D)=1-\sum p_k^2$。
• max_depth、min_samples_split、min_samples_leaf 分别从深度、分裂门槛、叶节点样本数三个角度控制复杂度。
• 读懂不纯度、树深和叶节点的关系之后，再看训练日志和特征重要性会更顺畅。