决策树

决策树：原理、特征选择与经典算法

决策树是一种常用的分类与回归模型，因其结构直观、易于理解和实现，被广泛应用于数据挖掘和机器学习领域。本文将详细介绍决策树的基本原理，重点讲解特征选择方法，并对ID3和C4.5两种经典算法进行说明。

1. 决策树简介

决策树模型通过一系列的“if-then”规则，将数据集划分为不同的类别或数值区间。树的每个内部节点表示一个特征的判断，每个分支对应一个判断结果，每个叶子节点对应一个类别或预测值。

决策树的构建过程本质上是递归地选择最优特征进行划分，直到数据集被“纯化”或满足停止条件。

2. 特征选择方法

特征选择是决策树构建的核心。每次划分时，算法需要从所有特征中选择一个“最优”的特征作为当前节点的划分依据。常见的特征选择准则有：

2.1 信息增益（ID3算法）

信息增益衡量的是“使用某特征划分数据后，系统信息的不确定性减少了多少”。信息增益越大，说明该特征越能有效区分样本。

• 信息熵：衡量样本集合纯度的指标。对于类别集合$D$，其熵为：
  $$
  Ent(D) = -\sum_{k=1}^K p_k \log_2 p_k
  $$
  其中$p_k$为第$k$类样本的比例。

• 信息增益：特征$A$对数据集$D$的信息增益为：
  $$
  Gain(D, A) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v)
  $$
  其中$D^v$为在特征$A$上取值为$v$的子集。

选择信息增益最大的特征进行划分。

2.2 信息增益率（C4.5算法）

信息增益倾向于选择取值较多的特征。为此，C4.5算法引入了信息增益率：

• 分裂信息（SplitInfo）：
  $$
  SplitInfo(D, A) = -\sum_{v=1}^V \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}
  $$

• 信息增益率：
  $$
  GainRatio(D, A) = \frac{Gain(D, A)}{SplitInfo(D, A)}
  $$

选择信息增益率最高的特征进行划分。

2.3 基尼指数（CART算法，简要）

基尼指数用于衡量集合的不纯度，CART算法采用基尼指数选择特征。本文不展开，重点关注ID3和C4.5。

3. 决策树的构建流程

1. 计算当前数据集的类别分布（熵或基尼指数）。
2. 对每个特征，计算其作为划分依据的指标（信息增益、信息增益率等）。
3. 选择最优特征进行划分，生成子节点。
4. 对每个子节点递归执行上述步骤，直到满足停止条件（如节点纯度高、样本数过少或无可用特征）。
5. 生成叶子节点，标记类别或输出值。

4. ID3算法

ID3（Iterative Dichotomiser 3）是最早的决策树算法之一，核心思想是每次选择信息增益最大的特征进行划分。

决策过程：

• 计算当前节点样本的熵
• 对每个特征，计算划分后的信息增益
• 选择信息增益最大的特征作为划分节点
• 对每个分支递归构建子树，直到所有样本属于同一类别或无特征可用

优点：实现简单，适合离散特征
缺点：偏向于取值多的特征，容易过拟合

5. C4.5算法

C4.5是ID3的改进版，主要改进有：

• 使用信息增益率作为特征选择标准，避免ID3偏向取值多的特征
• 支持连续特征的处理（通过阈值划分）
• 支持缺失值处理和剪枝

决策过程：

• 计算每个特征的信息增益率
• 选择信息增益率最大的特征进行划分
• 对连续特征，尝试不同的切分点，选择最优阈值
• 递归构建子树，支持剪枝以防止过拟合

优点：更适合实际数据，泛化能力更强
缺点：计算量较大，树结构可能较复杂

6. 决策树的可解释性

决策树的每个决策路径都可以转化为一组“if-then”规则，便于人类理解和分析。例如：