当前位置：首页 > news >正文

机器学习系列-决策树

news 来源：原创 2025/7/21 13:45:10

文章目录

1. 决策树原理
- 决策树的构建流程
2. 案例
- 步骤 1：计算当前节点的熵
- 步骤 2：对每个特征计算分裂后的熵
- - (1) 按“天气”分裂数据集
  - (2) 计算分裂后的加权熵
- 步骤 3：计算分裂依据
- - 信息增益
  - 信息增益率
  - GINI系数（二叉树）
- 步骤 4：选择分裂节点
- - 停止条件
  - 继续分裂
  - 示例
- 步骤 5：剪枝
- - 示例数据集
  - 生成的决策树
  - 1. 预剪枝
  - 2. 后剪枝
  - 剪枝的效果
  - 对比

1. 决策树原理

决策树是一种以树状结构进行决策和分类的监督学习算法，适用于分类和回归问题。它通过递归地将数据集分割成更小的子集，最终生成一个类似于树状的模型。

决策树的构建流程

特征选择：
- 决策树选择某个特征对数据集进行分割，找到能够最优划分数据的特征。常用的分裂标准包括：
  - 信息增益（ID3算法）
  - 信息增益比（C4.5算法）
  - 基尼指数（CART算法）
数据分裂：
- 按照选择的特征，将数据集分割成若干子集。
递归构建：
- 对每个子集重复上述步骤，直到满足停止条件（如节点纯度达到某个阈值或节点样本数不足）。
终止条件：
- 达到树的最大深度。
- 节点中的样本数低于最小分割数。
- 分裂后的增益低于某个阈值。

2. 案例

一个小型分类数据集，目标是预测是否买票：

其它特征	天气	是否买票
…	晴天	否
…	阴天	是
…	雨天	否
…	晴天	是
…	阴天	是
…	雨天	否

步骤 1：计算当前节点的熵

熵公式：

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

D 为当前数据集；
K为类别数量；
pk为类别 k 的概率。

当前数据集中：

P(买票)=3 / 6=0.5；
P(不买票)=3 / 6=0.5。

熵为：

$\log_2 0.5 + 0.5 \log_2 0.5) = - (0.5 \times -1 + 0.5 \times -1) = 1$

步骤 2：对每个特征计算分裂后的熵

以特征“天气”为例，取值为“晴天”“阴天”“雨天”。根据此特征分裂数据集：

(1) 按“天气”分裂数据集

分裂结果为：

“晴天”：{否, 是}
“阴天”：{是, 是}
“雨天”：{否, 否}

分别计算每个子集的条件熵：

晴天：
$H(\text{晴天}) = - (0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1$
阴天：
$H(\text{阴天}) = - (1 \log_2 1 + 0 \log_2 0) = 0$
雨天：
$H(\text{雨天}) = - (0 \log_2 0 + 1 \log_2 1) = 0$

(2) 计算分裂后的加权熵

加权熵公式：

$H_\text{split}(D) = \sum_{v=1}^V \frac{|D_v|}{|D|} H(D_v)$

|D_v| 为分裂后子集的大小；
H(D_v) 为子集的熵。

加权熵：

$Hsplit(D)=\frac{2}{6}H(晴天)+\frac{2}{6}H(阴天)+\frac{2}{6}H(雨天) = \frac{2}{6} \times 1 + \frac{2}{6} \times 0 + \frac{2}{6} \times 0 = \frac{2}{6} = 0.333$

步骤 3：计算分裂依据

信息增益

计算以天气作为节点进行分裂的信息增益：

$\text{信息增益}(节点=天气) = H(D) - H_\text{split}(D) = 1 - 0.333 = 0.667$

信息增益率

计算以天气作为节点进行分裂的信息增益率：

定义固有值（Split Information）固有值是衡量分裂结果的复杂性，计算公式为：

$\text{固有值 (SplitInfo)} = -\sum_{v=1}^V \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}$

|D_v|：特征值 v 的样本数量；
|D|：总样本数量；
V：特征取值的数量。

$Ratio)=\frac{信息增益 (Gain)}{固有值 (SplitInfo)}= \frac{0.667} {- (\frac{2}{6} \times log_2 \frac{2}{6} + \frac{2}{6} \times log_2 \frac{2}{6} + \frac{2}{6} \times log_2 \frac{2}{6})} ≈ 1.26$

GINI系数（二叉树）

计算以天气作为节点进行分裂的GINI系数：
节点的 Gini 系数：

$\sum_{k=1}^K p_k(1-p_k) = (0.5^2+0.5^2)=0.5$

K：类别数量；
p_k：类别 k 的样本比例。

分裂后的加权 Gini 系数：

$G(晴天)=0.5^2+0.5^2=0.5$
$\times 0 +0 \times 1=0$
$\times 1+1 \times 0=0$
$G_\text{split}(D) = \sum_{v=1}^V \frac{|D_v|}{|D|} G(D_v) = \frac{2}{6} \times 0.5 + \frac{2}{6} \times 0 + \frac{2}{6} \times 0 ≈ 0.167$

V：特征的取值数量；
|D_v|：分裂后每个子集的样本数量；
G(D_v)：子集的 Gini 系数。

$\text{GINI系数}(节点=天气) = G(D) - G_\text{split}(D) = 0.5 - 0.167 = 0.333$

步骤 4：选择分裂节点

选择分裂评估指标中值最高的特征作为节点进行分裂

以天气特征为例，会从根节点分裂出三个子节点：A1( $D_\text{晴天}$ )、A2( $D_\text{阴天}$ )、A3( $D_\text{雨天}$ )

对子节点 A1、A2、A3 逐一检查是否需要继续分裂：

停止条件

数据集中所有样本的类别相同
- 如果 $D_\text{节点}$ 中的样本全为“是”或“否”，则该节点不再分裂，设为叶节点，标记类别。
- 如：节点 A2 的数据集中样本全为“是”，直接将其标记为“是”。
没有可用的分裂特征
- 如果所有候选特征都已用完，则取数据集中的多数类作为叶节点类别。
数据集为空
- 如果子节点对应的数据集为空（如：某特征值下没有样本），则设置该节点为叶节点，类别标记为父节点中样本的多数类。

继续分裂

如果未满足上述停止条件，则递归对子节点执行相同的分裂过程。

示例

初始数据按“天气”分裂，生成子节点 A1（晴天）、A2（阴天）、A3（雨天）。
检查子节点：
- $D_\text{晴天}$ ：包含两类，继续分裂；
- $D_\text{阴天}$ ：全为“是”，设为叶节点；
- $D_\text{雨天}$ ：全为“否”，设为叶节点。
对 $D_\text{晴天}$ 再选特征继续分裂。

通过递归，最终生成完整的决策树。

步骤 5：剪枝

剪枝是减少决策树复杂度、提升泛化能力的重要方法。剪枝分为 预剪枝（Pre-pruning） 和 后剪枝（Post-pruning）。以下是剪枝的一个具体示例：

示例数据集

天气	温度	是否刮风	湿度	是否买票
晴天	高	是	高	否
晴天	高	是	高	否
阴天	低	否	高	是
阴天	中	否	中	是
雨天	低	是	高	否
雨天	低	否	中	是

生成的决策树

初始决策树为：

在这里插入图片描述

1. 预剪枝

预剪枝的思想：在分裂节点前，提前评估分裂是否有意义。如果分裂不能显著提高决策树性能，则阻止分裂。

过程

节点 1：是否刮风？
- 在当前节点分裂前，计算 信息增益 或 Gini 系数减少量。
- 如果分裂的增益不足（例如小于设定阈值 0.1），则阻止分裂，直接将当前节点作为叶节点。
假设分裂后的性能提升不明显：
- 不再继续分裂。
- 节点 1 直接成为叶节点，类别标记为“否”（因数据集中“否”的样本更多）。

结果树

节点1：叶子节点 -> 否

2. 后剪枝

后剪枝的思想：先生成完整决策树，再通过后序遍历判断是否需要剪掉子树，用叶节点代替。

过程

从叶节点往上回溯，逐个评估子树是否需要剪枝。
节点 2：天气？
- 子树分类结果：
  - 晴天 -> 否
  - 雨天 -> 否
- 两个叶子节点的类别相同，且整棵子树的分类错误率与将节点 2 直接作为叶节点的错误率相同。
- 剪枝策略：将节点 2 直接替换为叶节点“否”。
节点 3：湿度？
- 子树分类结果：
  - 高 -> 是
  - 中 -> 是
- 两个叶子节点的类别相同，且整棵子树的分类错误率与将节点 3 直接作为叶节点的错误率相同。
- 剪枝策略：将节点 3 直接替换为叶节点“是”。

**结果树

节点1：是否刮风？ ├── 是 -> 叶子1：否 └── 否 -> 叶子2：是

剪枝的效果

模型简化：剪枝后，树结构更简单，更易于理解。
泛化能力提升：剪枝减少了对训练集的过拟合，提升了模型在测试集上的性能。

对比

原始树错误率：假设在测试集上的错误率为 15%。
剪枝后错误率：测试集错误率下降到 10%，显示模型的泛化性能提升。