一、什么是决策树？

决策树通过对训练样本的学习，并建立分类规则，然后依据分类规则，对新样本数据进行分类预测，属于有效监督学习。

核心：所以数据从根节点一步一步落到叶子节点。

决策树的结构非常类似生活中的判断过程：

例如：

天气怎么样？

├── 晴天 → 湿度高吗？

│ ├── 是 → 不打球

│ └── 否 → 打球

└── 阴天 → 打球

其中：

• 根节点：第一个节点
• 非叶子节点：中间节点
• 叶子节点：最终结果节点

决策树的核心问题是：

如何选择最优特征进行数据划分？

不同算法采用了不同的方法：

• ID3：使用信息增益
• C4.5：使用信息增益率
• CART：使用基尼指数（Gini Index）

二、ID3 算法：基于信息增益选择特征

1. 信息熵（Entropy）

ID3 算法的核心思想是：

选择能够最大程度降低数据不确定性的特征作为划分依据。

衡量数据混乱程度的指标就是信息熵。

公式：

\[ H(D) = -\sum p_i \log_2(p_i) \]

其中：

• \( p_i \)：某一类别出现的概率
• 熵越小，数据越纯净
• 熵越大，数据越混乱

在决策树中，希望划分之后的数据熵越来越小。

文件中的案例使用"是否外出打球"作为分类任务：

14 天数据中：

• 打球：9 天
• 不打球：5 天

因此类别熵为：

\[ H(D) = 0.940 \]

2. 信息增益（Information Gain）

信息增益表示：

一个特征能够减少多少信息的不确定性。

公式：

\[ \text{Gain}(D, A) = H(D) - H(D|A) \]

如果某个特征带来的信息增益最大，则说明该特征最具有分类能力，会优先作为决策树节点。

3. ID3 案例计算

假设数据包含：

分别计算不同特征的信息增益。

（1）天气特征

天气划分后：

• 晴天：5 天
• 阴天：4 天
• 雨天：5 天

计算得到：

\[ H(D|\text{天气}) = 0.693 \]

因此：

\[ \text{Gain}(\text{天气}) = 0.940 - 0.693 = 0.247 \]

（2）温度特征

计算得到：

\[ \text{Gain}(\text{温度}) = 0.940 - 0.911 = 0.029 \]

（3）湿度特征

计算得到：

\[ \text{Gain}(\text{湿度}) = 0.151 \]

（4）风特征

计算得到：

\[ \text{Gain}(\text{风}) = 0.048 \]

最终结果：

因此：

\[ \text{天气} > \text{湿度} > \text{风} > \text{温度} \]

天气成为根节点。

三、C4.5 算法：解决 ID3 容易偏向取值多特征的问题

1. 为什么需要 C4.5？

ID3 算法存在一个问题：

如果某个特征拥有大量不同取值，例如：

• 编号
• 用户 ID
• 商品编号

虽然信息增益很高，但实际没有分类意义。

因此 C4.5 提出：

使用信息增益率代替信息增益。

2. 信息增益率

计算过程：

1. 计算类别熵
2. 计算每个属性的信息熵
3. 计算信息增益：\[ \text{Gain} = H(D) - H(D|A) \]
4. 计算信息增益率：\[ \text{GainRatio} = \frac{\text{Gain}}{H(A)} \]

选择信息增益率最大的特征。

3. C4.5 案例计算

计算结果：

排序：

\[ \text{天气} > \text{湿度} > \text{风} > \text{温度} \]

因此依旧选择天气作为首个划分节点。

四、CART 算法：基于基尼指数

CART（Classification And Regression Tree）是目前应用非常广泛的一种决策树算法。

它与 ID3、C4.5 最大的区别：

• ID3：信息增益
• C4.5：信息增益率
• CART：基尼指数

CART 选择：

使划分后的数据基尼指数最小的特征。

1. 基尼指数（Gini Index）

公式：

\[ \text{Gini}(D) = 1 - \sum p_i^2 \]

含义：

• Gini 越小，数据越纯
• 最好的划分方式就是让划分后的 Gini 指数最低

例如贷款预测案例：

根据年龄特征：

• 青年
• 中年
• 老年

分别计算不同年龄节点的基尼指数。

五、决策树剪枝：解决过拟合问题

1. 为什么需要剪枝？

在决策树学习过程中，模型会不断地对数据进行划分。

如果不限制树的生长：

例如：

有 1000 条训练数据，构建出来的决策树可能生成 1000 条不同的路径。

也就是说：

• 每一个样本都有自己对应的一条判断路线
• 树会完全记住训练数据
• 对训练数据预测效果很好
• 但是面对新的未知数据时，可能无法正确判断

这种现象称为：

过拟合（Overfitting）

即：

模型过度学习训练数据中的细节和噪声，导致泛化能力下降。

因此，需要通过剪枝（Pruning）降低模型复杂度，提高模型对新数据的预测能力。

2. 决策树如何剪枝？

决策树剪枝主要分为两种：

（1）预剪枝（Pre-Pruning）

预剪枝是在：

决策树生成过程中提前限制树的生长。

也就是说，在树还没有完全建立之前，根据一定条件停止继续划分。

例如：

• 限制树的最大深度
• 限制叶子节点数量
• 限制叶子节点最少样本数量

优点：

• 训练速度快
• 可以减少模型复杂度
• 防止过拟合

缺点：

• 可能提前停止，导致模型没有充分学习数据规律

（2）后剪枝（Post-Pruning）

后剪枝是在：

决策树已经完全生成之后，再删除不必要的分支。

流程：

1. 先构建完整决策树
2. 分析每个节点的重要程度
3. 删除贡献较小的节点
4. 得到更加简单的决策树

优点：

• 保留更多数据规律
• 通常泛化能力更强

缺点：

• 计算成本较高

3. 预剪枝策略

在实际机器学习中，预剪枝通常通过以下方式实现：

（1）限制树的深度

参数：

max_depth

表示：

决策树允许达到的最大层数。

例如：

如果设置：

max_depth = 3

表示树最多只有 3 层。

作用：

• 防止树无限增长
• 降低模型复杂度
• 减少过拟合

在数据量较小的时候，可以不限制深度；

如果：

• 样本数量多
• 特征数量多

则可以尝试限制树深度。

（2）限制叶子节点数量

参数：

max_leaf_nodes

表示：

限制决策树最大的叶子节点数量。

例如：

设置：

max_leaf_nodes = 10

那么：

• 当叶子节点达到 10 个
• 模型不会继续产生新的分支

作用：

• 控制树结构规模
• 防止模型学习过多细节

（3）限制叶子节点样本数量

参数：

min_samples_leaf

表示：

叶子节点中最少需要包含多少个样本。

例如：

min_samples_leaf = 5

表示：

一个叶子节点至少需要 5 个样本。

如果某个节点样本过少：

• 说明该节点可能只是在记忆训练数据
• 容易造成过拟合

因此可以进行剪枝。

4. 基尼系数与剪枝

CART 算法使用：

基尼指数（Gini Index）

作为节点划分标准。

公式：

\[ \text{Gini}(D) = 1 - \sum p_i^2 \]

其中：

• \( p_i \)：类别比例

基尼指数越小：

说明数据越纯。

在剪枝过程中：

如果某个节点继续划分后：

• 基尼指数下降不明显
• 分类效果提升很小

那么这个节点可能没有必要继续展开。

因此：

基尼系数不仅用于选择划分节点，也可以辅助判断树结构是否合理。

CART 算法本身就是通过基尼指数最小化准则进行特征选择。

5. 剪枝前后的决策树变化

剪枝前：

根节点 | ---------------- | | 节点A 节点B / \ / \ C D E F /|\ /|\ ...大量分支...

特点：

• 树结构复杂
• 节点数量多
• 容易过拟合

剪枝后：

根节点 | ---------------- | | 节点A 节点B | 结果

特点：

• 删除无意义分支
• 模型更加简单
• 泛化能力提高

六、sklearn 中的决策树剪枝参数

在 sklearn 中：

from sklearn.tree import DecisionTreeClassifier model = DecisionTreeClassifier( criterion='gini', max_depth=5, min_samples_leaf=10, max_leaf_nodes=20 )

其中：

<