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

机器学习9——决策树

news 2025/6/30 22:43:39

决策树

Intro

归纳学习（Inductive Learning）的目标：从训练数据中学习一般规则，应用于未见过的数据。
决策树是一个树形结构，其中：
- 每个分支节点表示一个属性上的选择（即决策条件）。
- 每个叶节点表示一个分类或决策结果。
可以从决策树提取从根到叶的路径，这种逻辑表达就是决策规则
决策树学习的目标和主要算法：
- 目标：从训练数据中归纳出决策树，用于分类或决策。
- 学习算法：
  - CLS（概念学习系统）：早期的决策树算法。
  - ID3 → C4 → C4.5 → C5：ID3的演化路径，逐步改进。
- 适用场景：
  1. 数据以属性-值对表示（例如，Outlook=sunny）。
  2. 目标函数输出离散值（例如，Yes/No）。
  3. 可能需要析取描述（即复杂的逻辑组合）。
  4. 训练数据可能包含错误。
  5. 训练数据可能有缺失的属性值。

CLS 算法（Concept Learning System）

核心思想：

CLS 使用一种递归方式构建决策树，不考虑划分属性的优劣。

算法步骤：

初始化：将整个训练集 $T$ 作为一个节点。
若 $T$ 中所有样本都是正类，生成正类叶子节点。
若所有样本是负类，生成负类叶子节点。
否则，从候选属性中任选一个属性 $X$ ，按其取值将 $T$ 划分为子集 $T_1, T_2, ..., T_n$ 。
对每个子集递归执行上面步骤。

存在问题：

不考虑属性的好坏，导致树结构不优（可能过深或过宽）；
无法处理数据噪声和过拟合问题；
没有“剪枝”（Pruning）机制。

ID3（信息论驱动的改进）

ID3 是对 CLS 的改进版本，由 Ross Quinlan 提出，核心引入了**信息增益（Information Gain）**来选择划分属性。

主要思想：

优先选择能够最大程度减少分类不确定性的属性（即信息增益最大的属性）进行划分。

ID3 的算法流程：

从训练集 $T$ 开始。
若所有样本同类，则创建叶子节点，标注该类。
否则，选择具有最高信息增益的属性 $A$ 进行划分。
根据 $A$ 的各个取值 $v_1, ..., v_n$ ，划分成子集 $T_1, ..., T_n$ 。
对每个 $T_i$ 递归执行以上步骤。

信息增益和熵的定义

ID3 需要评估每个属性的信息增益。

熵 Entropy（衡量数据的混乱程度）：

对于二分类问题：
$\text{Entropy}(S) = -p_1 \log_2 p_1 - p_2 \log_2 p_2$

$p_1$ ：属于类别1（例如“w”）的概率；
$p_2 = 1 - p_1$ ：属于类别2（例如“e”）的概率。

熵越高，表示样本越混乱，越难以分类。如下两图，在二分类中，两类样本的频率（出现概率）越接近，表明系统更混乱，更难以分类。

在这里插入图片描述

信息增益 Gain：

衡量使用属性 $A$ 进行划分后熵的下降程度。
$\text{Gain}(S, A) = \text{Entropy}(S) - \sum_{v \in A} \frac{|S_v|}{|S|} \text{Entropy}(S_v)$

$S$ ：整个训练集；
$S_v$ ：属性 $A$ 取值为 $v$ 的子集；
信息增益大的属性可以使数据集更快速地纯化（即更快得到单类子集）。

举例：

Hair 属性的 Gain = 0.199
Eye 属性的 Gain = 0.83
Height 的 Gain = 0

所以会优先选择 Eye 属性进行分裂。

ID3 的特性与限制

优点：

利用信息增益来选择划分属性，构建效率高；
可以自动选择最有“判别力”的属性。

缺点：

容易过拟合训练数据；
对噪声敏感；
只能处理离散属性（除非先离散化）。

防止过拟合：剪枝（Pruning）

决策树容易变得过深，对训练集记忆性太强。解决方法是剪枝（做实验时发现，以下方法都是后剪枝，即训练出决策树后进行剪枝）：

剪枝类型：

Reduced Error Pruning（简化误差剪枝）：

留出一个验证集；
如果剪掉一个节点后在验证集上的准确率不下降，则剪掉它；
持续剪枝直到无法提升准确率。

Rule Post-Pruning（规则后剪枝）：

规则后剪枝是决策树学习中的一种剪枝方法，旨在通过将决策树转换为规则集并简化规则，从而提高模型的泛化能力，避免过拟合。以下是其详细步骤和原理：

1. 完全生成决策树（允许过拟合）
- 目标：基于训练数据完整地生成一棵决策树，不限制树的深度或节点数量（允许过拟合）。
- 为什么：先让模型充分学习训练数据中的所有模式（包括噪声），后续再通过剪枝优化。
- 结果：一棵庞大且复杂的树，在训练集上表现很好，但在测试集上可能表现较差（过拟合）。
2. 将决策树转换为规则集
- 方法：从根节点到每个叶子节点的路径，生成一条对应的规则。
  - 每条规则的格式：
    IF (条件1 AND 条件2 AND ...) THEN (类别 = 叶子节点类别)
  - 示例：
    IF (年龄 ≤ 30 AND 收入 = 高 AND 学生 = 是) THEN (购买 = 是)
- 为什么转换为规则？
  - 规则比树结构更灵活，便于独立剪枝（可以单独删除某个条件）。
  - 规则可以重新排序或合并，进一步简化模型。
3. 对每条规则进行剪枝（删除冗余条件）
- 目标：删除规则中不必要的条件，提高规则的泛化能力。
- 方法：
  1. 对每条规则，尝试依次删除一个前提条件（如删除收入 = 高）。
  2. 用验证集评估剪枝后的规则准确率：
    - 如果删除某个条件后，规则的准确率提升或不变，则保留剪枝。
    - 如果准确率下降，则恢复该条件。
  3. 重复上述过程，直到无法进一步优化。
- 示例：
  - 原规则：
    IF (年龄 ≤ 30 AND 收入 = 高 AND 学生 = 是) THEN (购买 = 是)
  - 剪枝后可能变为：
    IF (学生 = 是) THEN (购买 = 是)（如果其他条件对准确率无贡献）
4. 按准确率排序规则，并用于分类
- 排序规则：将剪枝后的规则按估计准确率从高到低排序。
- 分类策略：
  - 对于新样本，按顺序检查规则，一旦满足某条规则，则直接应用其类别预测。
  - 如果样本不匹配任何规则，可指定默认类别（如训练集中的多数类）。
为什么规则后剪枝比直接剪树更好？
1. 更灵活的剪枝：树的剪枝只能删除整个子树，而规则剪枝可以单独删除某个条件。
2. 避免上下文依赖：在决策树中，节点的剪枝会影响整个子树，而规则相互独立。
3. 可读性更强：规则形式更接近人类逻辑，便于理解和调整。

大规模数据处理：Windowing

在数据量太大无法一次处理时，可采用滑窗法（Windowing）：

随机选一个小子集（称为“窗口”）；
构建决策树；
扫描整个训练集，找出未正确分类的样本；
将这些“例外”加入窗口，重新构建树；
重复直到没有错误样本。

归纳偏置与奥卡姆剃刀

ID3 采用了一种“归纳偏置”：

短树优于长树（偏好简单模型）；
信息增益大的属性优先被选；
贪心策略逐层构建，不回溯；

这种偏置体现了奥卡姆剃刀原则——优先选择最简单且解释力足够的模型。

C4.5

C4.5 的提出背景

为什么需要 C4.5？

ID3 是构建决策树的经典算法，但它存在如下问题：

不能处理连续属性（如温度、身高）；
对于有很多取值的属性（如日期），会过度偏向该属性（信息增益偏倚）；
不支持剪枝（易过拟合）；
不处理缺失属性值；
无法结合属性的获取成本。

C4.5 正是为解决这些问题设计的，是 ID3 的自然扩展。

C4.5 相较 ID3 的主要改进

改进点	描述
✅ 支持连续属性	把连续值转化为二元测试，例如 “温度 > 72.3”
✅ 处理缺失值	对缺失值进行推断或概率分配
✅ 使用增益率（Gain Ratio）	避免信息增益偏向多值属性
✅ 后剪枝（Post-pruning）	构建完整树后进行简化，防止过拟合
✅ 支持属性代价	学习低代价且有效的树结构
✅ 转化为规则集	提高可读性与泛化能力

处理连续属性（Continuous Attributes）

操作流程：

排序：将连续属性值排序。
候选划分点：找相邻样本中类标签变化的位置，设为候选切分点。
计算信息增益：对每个候选切分点计算信息增益。
选择最佳切分点：采用信息增益（或增益率）最大的位置。

例子：

属性：Temperature = [40, 48, 60, 72, 80, 90]
标签：PlayTennis = [No, No, Yes, Yes, Yes, No]

候选切分点：比如在 60 和 72 之间
生成新属性：Temperature > 66 ⇒ True/False

信息增益偏倚与增益率（Gain Ratio）

问题：

信息增益偏向于取值多的属性（例如日期：每次唯一 ⇒ 完全分开，但无泛化能力）。信息增益偏好高分支属性（取值多的属性），但这类属性可能没有实际分类价值。

解决方案：使用增益率。

C4.5 算法引入了 增益率（Gain Ratio），它在信息增益的基础上增加了分裂信息（Split Information） 的归一化。

（1）增益率的定义
$\text{GainRatio}(S, A) = \frac{\text{Gain}(S, A)}{\text{SplitInformation}(S, A)}$
其中：
- $\text{Gain}(S, A)$ 是信息增益。
- $\text{SplitInformation}(S, A)$ 衡量属性分裂的均衡程度。
（2）分裂信息（Split Information）

分裂信息计算的是属性A的分裂方式对数据的分散程度：
$\text{SplitInformation}(S, A) = -\sum_{i=1}^{c} \frac{|S_i|}{|S|} \log_2 \left( \frac{|S_i|}{|S|} \right)$
- 含义：
  - 如果 $A$ 的取值分布均匀（如“ID”每个值只对应 1 个样本），则 $\text{SplitInformation}$ 会很大，导致 $\text{GainRatio}$ 降低。
  - 如果 $A$ 的取值分布不均匀（如“性别”只有 2 个取值），则 $\text{SplitInformation}$ 较小， $\text{GainRatio}$ 受影响较小。
  - 有没有发现它的形式很像熵？也就是说，分出来的数据越分散，这个值越大（系统的熵高）。
（3）增益率的作用
- 惩罚取值过多的属性：
  - 例如“ID”或“日期”这样的属性，由于 $\text{SplitInformation}$ 极大，其 $\text{GainRatio}$ 会变得很小，从而降低被选中的概率。
- 更倾向于选择泛化能力强的属性：
  - 例如“年龄”“收入”等取值适中、分类能力强的属性。

后剪枝（Post-Pruning）

动机：

构建完全树可能过拟合，因此需在训练后简化。

步骤：

训练阶段允许构建“过拟合”的完整树；
将树中每条路径转换为规则；
逐条移除前提条件（条件越少越泛化），若准确率提高则保留；
用验证集评估规则；
按准确率排序使用这些规则分类。

示例规则：

IF (Outlook = Sunny) AND (Humidity = High) THEN PlayTennis = No
IF (Outlook = Sunny) AND (Humidity = Normal) THEN PlayTennis = Yes

缺失属性值处理（Missing Values）

问题：

某些样本缺少属性 A 的取值，该如何参与树构建？

可选方案：

用 A 的 最常见取值 填补；
用 与当前类别一致的样本中最常见的 A 值 填补；
概率分布赋值：每个可能值分配一个概率，让样本“部分参与”每个子集。

考虑属性代价（Attribute Cost）

在实际应用中，不同属性的获取代价不同（如医疗检查）。

目标：

在保证分类精度的前提下，尽可能降低总成本。

代价感知的信息增益形式：

Tan & Schlimmer (1990)：
$\frac{\text{Gain}^2(S, A)}{\text{Cost}(S, A)}$
Nunez (1988)：
$\frac{2^{\text{Gain}(S, A)} - 1}{(\text{Cost}(A) + 1)^w}, \quad w \in [0, 1]$

CART（分类与回归树）

CART 的核心特点

二元分裂（Binary Splitting）

每个节点只分成2个子节点（即使属性有多个取值），形成二叉树结构。
- 示例：
  - 对于“年龄”属性，CART 可能分裂为 年龄 ≤ 30 和 年龄 > 30，而不是像ID3/C4.5那样每个年龄值分一个分支。
- 优点：
  - 简化树结构，避免多值属性带来的过拟合。
  - 更适合处理连续型变量（通过阈值划分）。

支持分类和回归

分类任务：用**基尼指数（Gini Index）**或分类误差作为分裂标准。
回归任务：用**均方误差（MSE）**或平均绝对误差（MAE）作为分裂标准。
- 回归树示例：
  - 预测房价时，分裂条件可能是 面积 ≥ 100㎡，左右分支分别预测不同房价区间。

分裂标准

CART 的常见不纯度（Impurity）衡量标准：

标准名称	公式	特点
基尼指数（Gini）	$\sum_{i \neq j} P(\omega_i) P(\omega_j) = 1 - \sum_j P(\omega_j)^2$	计算高效，对类别分布敏感
分类误差（Misclassification Error）	$\max_j P(\omega_j)$	对噪声鲁棒，但不平滑
熵（Entropy）	$-\sum_j P(\omega_j) \log_2 P(\omega_j)$	类似信息增益，但CART较少直接使用

实际应用中最常用的是基尼指数，因为：

计算速度比熵快（无需对数运算）。
对类别分布更敏感，容易生成更平衡的树。

剪枝策略：代价复杂度剪枝（Cost-Complexity Pruning）

步骤：
1. 先生成一棵最大的树（允许过拟合）。
2. 通过交叉验证，逐步剪掉对模型性能贡献小的子树。
3. 选择验证误差最小的树作为最终模型。
优点：避免过拟合，提高泛化能力。

基尼指数（Gini Index）详解

定义

基尼指数衡量数据集的不纯度，值越小表示纯度越高：
$\text{Gini}(S) = 1 - \sum_{j=1}^k P_j^2$

$P_j$ 是类别 $j$ 在数据集 $S$ 中的比例。
基尼增益（分裂后的不纯度减少量）：
$\Delta \text{Gini} = \text{Gini}(S) - \left( \frac{|S_L|}{|S|} \text{Gini}(S_L) + \frac{|S_R|}{|S|} \text{Gini}(S_R) \right)$

计算示例

假设数据集 $S$ （10 样本）：

年龄 ≤ 30	购买（是/否）
是	5 是，1 否
否	2 是，2 否

根节点的基尼指数：
- $P(\text{是}) = \frac{7}{10}$ , $P(\text{否}) = \frac{3}{10}$
- $\text{Gini}(S) = 1 - \left( \frac{7}{10}^2 + \frac{3}{10}^2 \right) = 0.42$
分裂后左节点（年龄 ≤ 30）：
- $\text{Gini}(S_L) = 1 - \left( \frac{5}{6}^2 + \frac{1}{6}^2 \right) \approx 0.28$
分裂后右节点（年龄 > 30）：
- $\text{Gini}(S_R) = 1 - \left( \frac{2}{4}^2 + \frac{2}{4}^2 \right) = 0.5$
基尼增益：
$\Delta \text{Gini} = 0.42 - \left( \frac{6}{10} \times 0.28 + \frac{4}{10} \times 0.5 \right) = 0.42 - 0.368 = 0.052$
- 如果其他属性的增益更低，则选择“年龄 ≤ 30”作为分裂点。

CART vs ID3/C4.5 对比总结

特性	CART	ID3 / C4.5
分裂方式	二元分裂（二叉树）	多分支分裂（每个取值一个子节点）
适用任务	分类 + 回归	仅分类
划分标准	基尼指数、分类误差	信息增益、增益率
连续值处理	自动通过阈值划分（如“年龄 ≤ 30”）	需离散化
剪枝策略	代价复杂度剪枝	后剪枝（如规则后剪枝）
计算效率	更高（基尼指数计算快）	较低（需计算对数）