万字长文解读机器学习——决策树

🌺历史文章列表🌺

1. 机器学习——损失函数、代价函数、KL散度
2. 机器学习——特征工程、正则化、强化学习
3. 机器学习——常见算法汇总
4. 机器学习——感知机、MLP、SVM
5. 机器学习——KNN
6. 机器学习——贝叶斯
7. 机器学习——决策树
8. 机器学习——随机森林、Bagging、Boosting、集成学习
9. 机器学习——聚类算法（Kmeans、GMM-使用EM优化）
10. 机器学习——降维

---

---

决策树（Decision Tree）概述

决策树是一种基于树形结构的机器学习算法，广泛应用于分类和回归任务中。它通过一系列的规则将数据集划分为不同的子集，从而进行分类或预测。决策树算法直观、易于解释，并且能够处理复杂的特征交互。

基本概念

• 节点（Node）：
  • 根节点（Root Node）：树的起始节点，表示整个数据集。
  • 内部节点（Internal Node）：表示数据集的划分条件，包含特征和阈值。
  • 叶节点（Leaf Node）：表示分类或回归的最终结果，包含类别标签或连续值。
• 分支（Branch）——决策规则：从一个节点到另一个节点的路径。
• 路径（Path）——决策过程：从根节点到叶节点的序列。
• 深度（Depth）——决策树的复杂度：从根节点到最深叶节点的最长路径长度。

任务类型

决策树既可以用于分类任务，也可以用于回归任务。

分类任务

在分类任务中，决策树用于将数据划分到不同的离散类别中。目标是通过一系列条件判断，将数据划分为不同类别，并最终在叶节点上输出类别标签。

• 常用算法（不同的划分特征的标准）：

  • ID3：使用信息增益来选择划分特征。
  • C4.5：使用信息增益比来选择划分特征，并支持连续特征处理。
  • CART（分类树）：使用基尼系数(Gini Index) 来选择最优划分特征。

• 应用场景：

  • 电子邮件分类（垃圾邮件识别）。
  • 图像识别（识别不同的物体类别）。
  • 医疗诊断（预测病人的健康状况类别）。

回归任务

在回归任务中，决策树用于预测连续值。目标是通过一系列的分裂操作，将数据划分成不同的区间，并在每个叶节点上输出一个数值（通常是该节点中所有样本的均值）。

• 常用算法：

  • CART（回归树）：使用**最小化均方误差(Mean Squared Error, MSE)**或其他度量标准来选择最优划分特征。

• 应用场景：

  • 房价预测（预测某个地区的房屋价格）。
  • 股票市场预测（预测股票的未来价格）。
  • 气象预测（预测某个地点的温度或降雨量）。

分类和回归中的差异

分类树（Classification Tree）：

• 输出的是离散类别标签。
• 每个叶节点表示一个类别。
• 划分标准基于分类纯度（如信息增益、基尼系数）。

回归树（Regression Tree）：

• 输出的是连续数值。
• 每个叶节点表示一个数值（如节点样本的均值）。
• 划分标准基于回归误差（如均方误差）。

决策树算法的具体实现

比较总结

算法	划分标准	支持连续特征	处理缺失值	树结构	优点	缺点	适用场景
ID3	信息增益	否	否	多叉树	实现简单，适合小规模数据	偏向于选择取值多的特征，不能处理连续变量	小规模、离散特征数据集
C4.5	信息增益比	是	是	多叉树	支持连续特征，能处理缺失值	计算复杂度高，生成树较大	大规模数据，有连续特征和缺失值的数据
CART	基尼系数	是	否	二叉树	适用于分类和回归问题，剪枝方便	对噪声数据敏感，容易过拟合	分类、回归任务，要求生成二叉树时

• ID3 适合小规模的、离散特征的数据集，但不适合处理连续特征和缺失值。
• C4.5 是 ID3 的改进版本，能处理连续特征、缺失值，适合处理复杂的大规模数据集。
• CART 能同时用于分类和回归任务，生成简洁的二叉树结构，但对噪声敏感，适合需要生成二叉树结构的应用场景。

ID3（Iterative Dichotomiser 3）

原理

• ID3 通过信息增益（Information Gain）来选择划分特征，ID3 选择信息增益最大的特征进行划分。信息增益表示划分数据集后信息熵的减少程度，熵越小，数据纯度越高。主要用于分类任务。

主要特点

• 划分准则：使用信息增益，优先选择信息增益最大的特征进行分裂。
• 适用数据类型：ID3 主要适用于离散特征，不支持连续特征的处理。
• 剪枝：ID3 本身没有提供剪枝机制，容易出现过拟合问题。

信息熵（Entropy）

信息熵用于衡量数据集的（纯度或）混乱程度。信息熵越高，数据越混乱；信息熵越低，数据越纯。

对于数据集 ( $D$ )，它的熵定义为：
$$H(D)=-\sum _{i=1}^m{p}_i{\log }_2(p_i)$$
其中：

• $m$ 是类别的总数。
• $p_i$ 是数据集中属于第 $i$ 类的样本所占的比例。

信息增益（Information Gain）

表示某一特征 $A$ 将数据集 $D$ 划分后的纯度提升程度。ID3 选择信息增益最大的特征进行划分。信息增益的公式为：
$$\text{信息增益}=H(D)-\sum _{v=1}^V\frac{|D_v|}{|D|}H(D_v)$$
其中：

• $H(D)$ 是数据集 $D$ 的信息熵。
• $V$ 是特征 $A$ 的可能取值数。
• $D_v$ 是根据特征 $A$ 的取值 $v$ 分割得到的子集。
• $|D_v|/|D|$ 表示取值 $v$ 的样本在数据集 $D$ 中的比例。
• $H(D_v)$ 是子集 $D_v$ 的熵。

算法流程

1. 计算当前所有特征对数据集的信息增益。
2. 选择信息增益最大的特征作为当前节点的划分标准。
3. 根据该特征的不同取值划分数据集，并在每个子集上递归地重复步骤 1 和步骤 2。
4. 当所有特征都被使用，或所有样本都属于同一类别时，停止划分。

优点

• 简单易懂：ID3 的核心思想和实现相对简单，能够快速生成决策树。
• 高效：ID3 计算信息增益后即可快速进行划分。

缺点

• 倾向于选择取值多的特征：ID3 更倾向于选择取值多的特征进行划分，可能导致过拟合。
• 只能处理离散特征：ID3 不能处理连续特征。
• 对缺失值不敏感：ID3 不能有效处理数据中的缺失值。

C4.5

原理

选择信息增益比（信息增益与分裂信息的比值）最大的特征进行划分，用于平衡特征数量和划分质量之间的关系。通过引入“分裂信息”（Split Information）来惩罚分裂数目较多的特征。支持连续特征，处理缺失值，加入剪枝。

主要特点

• 划分准则：使用信息增益比，避免 ID3 中对多值特征的偏向。
• 适用数据类型：支持离散和连续特征。
• 剪枝：C4.5 支持错误率估计的后剪枝策略，防止过拟合。

信息增益比（Information Gain Ratio）

信息增益比是信息增益与特征的“固有信息”之比。特征的固有信息衡量的是特征取值的均匀性。信息增益比的公式为：

$$\text{信息增益比}=\frac{\text{信息增益}}{\text{固有信息}}$$

其中，信息增益的公式与 ID3 相同。

固有信息（Intrinsic Information）

固有信息衡量的是特征 $A$ 的取值分布，它的计算公式为：

$$\text{固有信息}=-\sum _{v=1}^V\frac{|D_v|}{|D|}{\log }_2\left(\frac{|D_v|}{|D|}\right)$$
其中：

• $V$ 是特征 $A$ 的可能取值数。
• $D_v$ 是数据集 $D$ 中特征 $A$ 取值为 $v$ 的子集。
• $|D_v|/|D|$ 表示取值 $v$ 的样本在数据集 $D$ 中的比例。

在 C4.5 算法中，处理连续型变量和缺失值的方法具体如下：

---

处理连续型变量

当特征是连续型变量时，C4.5 算法将其转化为一个二值问题（例如，小于某个阈值和大于等于该阈值），以便将连续变量用于决策树的分裂。

步骤：

1. 生成候选划分点：将连续特征值按升序排列，计算每个相邻值的中点作为候选划分点。例如，如果连续特征的两个相邻值为 $x_i$ 和 $x_{i+1}$，候选划分点为 $t=\frac{x_i+x_{i+1}}{2}$。
2. 计算信息增益比：对于每个候选划分点 ( t )，将数据集划分成两个子集：
   • 子集 1：特征值 $\le t$ 的样本。
   • 子集 2：特征值 $>t$ 的样本。
3. 选择最佳划分点：计算所有候选划分点的信息增益比，选择信息增益比最大的划分点作为最终分裂点。这样可以有效地将连续变量转化为二值判断。

---

处理缺失值

在 C4.5 算法中，对于特征值缺失的样本，算法不会简单地丢弃，而是利用概率分布填充缺失值，从而有效利用数据。

步骤：

1. 计算样本权重：在计算信息增益比时，含缺失值的样本按照其在整个数据集中的比例被赋予一个权重。这些缺失样本将按比例分布到不同分支。
2. 按概率分配样本：在分裂节点时，缺失特征的样本将依据分支上的样本比例进行分配。例如，如果一个特征缺失的样本在某节点有 70% 的概率被归入左子树，则会将 70% 的权重分配给左子树，30% 的权重分配给右子树。
3. 分类时的缺失值处理：在决策树生成后进行预测时，对于测试样本中缺失的特征，C4.5 也使用概率分布填充，使其根据现有特征值的分布推断分类。

算法流程

1. 计算每个特征的信息增益比。
2. 选择信息增益比最大的特征作为划分特征。
3. 如果特征是连续型变量，将特征值划分为小于某个阈值和大于等于该阈值的两部分。
4. 处理缺失值，使用概率分布填充。
5. 递归地构建子树，直到满足停止条件。

优点

• 支持连续特征：C4.5 通过引入阈值分割，能够处理连续型变量。
• 减少过拟合倾向：使用信息增益比来进行特征选择，避免了对取值多的特征的偏好。
• 处理缺失值：能够处理数据集中缺失值的问题。

算法流程中的：
3. 如果特征是连续型变量，将特征值划分为小于某个阈值和大于等于该阈值的两部分。
4. 处理缺失值，使用概率分布填充。

缺点

• 计算复杂度较高：相比 ID3，C4.5 由于需要计算信息增益比、处理连续特征和缺失值，计算复杂度较高。
• 容易产生较大的树：C4.5 生成的树结构有时可能过大，需要进行剪枝以减少过拟合。

CART（Classification and Regression Tree）

原理

CART（Classification and Regression Tree）算法可以用于分类和回归任务。CART 构造的是一棵二叉树。

1. 对于分类任务，选择基尼指数最小的特征作为划分特征。
2. 对于回归任务，选择均方误差最小的特征进行分裂。

主要特点

• 划分准则：
  • 分类任务：使用基尼指数作为划分准则。
  • 回归任务：使用均方误差作为划分准则。
• 适用数据类型：支持离散和连续特征。
• 剪枝：CART 支持后剪枝策略，通过成本复杂度剪枝来防止过拟合。

分类任务基尼指数（Gini Index）

基尼指数用于衡量数据集的纯度。基尼系数越小，数据集的纯度越高。选择基尼指数最小的特征作为划分特征。

对于数据集 $D$，其基尼指数定义为：
$$\text{基尼指数}=1-\sum _{i=1}^m{p}_i^2$$
其中：

• $m$ 是类别的总数。
• $p_i$ 是数据集中属于第 $ i$ 类的样本所占的比例。

当一个特征 $A$ 有多个可能的取值时，特征 $A$ 对数据集 $D$ 的基尼指数可以表示为：

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

其中：

• $V$ 是特征 $A$ 的取值个数。
• $D_v$ 是根据特征 $A$ 的取值 $v$ 划分得到的子集。
• $\text{Gini}(D_v)$ 是子集 $D_v$ 的基尼指数。

回归任务均方误差（Mean Squared Error, MSE）

对于回归任务，CART 算法选择均方误差（MSE）最小的特征进行分裂。均方误差衡量的是预测值和实际值之间的平均平方差。对于数据集 $D$ ，均方误差定义为：
$$\text{MSE}=\frac{1}{|D|}\sum _{i=1}^{|D|}(y_i-\hat{y}{)}^2$$
其中：

• $|D|$ 是数据集中样本的数量。
• $y_i$ 是第 $i$ 个样本的真实值。
• $\hat{y}$ 是数据集 $D$ 中所有样本的均值。

分类树算法流程

1. 对每个特征，计算不同划分下的基尼系数。
2. 选择基尼系数最小的特征作为当前节点的划分特征。
3. 递归地构建二叉树。
4. 当达到停止条件（如节点样本数小于设定阈值）时，停止递归。

回归树算法流程

1. 遍历每个特征：对于每个特征，尝试在数据集中的不同数值作为可能的分裂点。

2. 计算分裂后的均方误差：对于每个分裂点，计算其分裂后左右子集的加权均方误差（MSE），公式如下：
   

3. 选择最优分裂点：选择使得分裂后均方误差最小的分裂点，将该特征和分裂点作为当前节点的分裂依据。

4. 递归构建树：对分裂后的左右子节点重复步骤 1-3，继续寻找最优分裂点，构建新的子节点。

5. 停止条件：当达到预设的停止条件时（例如节点样本数小于设定阈值或MSE降低不明显），停止递归分裂。此时，该节点成为一个叶节点，并赋予其目标值的平均值作为预测值。

优点

• 可处理分类和回归问题：CART 不仅适用于分类任务，也可用于回归任务。
• 生成二叉树结构：树结构简单，每个节点最多有两个分支，便于实现和计算。
• 易于剪枝：CART 提供了剪枝机制，可以有效减少过拟合。

缺点

• 对噪声数据敏感：CART 对于数据中的噪声较为敏感，容易生成较复杂的树结构。
• 基尼系数局限性：基尼系数在处理某些分类问题时效果不如信息增益或信息增益比。
• 连续特征处理较复杂：虽然 CART 可以处理连续特征，但需要遍历所有特征值进行划分，计算量较大。

决策树的过拟合和欠拟合

解决欠拟合

欠拟合要增加模型复杂度：

1. 增加树的深度
2. 减少最小样本分裂数，让更多节点可以分裂
3. 减少最小叶子节点数，让树生长得更深

欠拟合通常是因为模型的复杂度不够，无法很好地拟合训练数据。应对欠拟合的方法通常是增加模型复杂度。包括：

• 增加树的深度（max_depth）：通过增加决策树的深度，可以让模型拟合更多的数据特征，从而减少欠拟合。
• 减少最小样本分裂数（min_samples_split）：减少节点分裂所需的最小样本数，让更多节点可以分裂，使模型更复杂。
• 减少最小叶子节点数（min_samples_leaf）：减少叶子节点的最小样本数，让树生长得更深、更复杂。

解决过拟合

过拟合要增加模型复杂度：

1. 限制树的深度
2. 增加最小样本分裂数，限制树的生长
3. 增加最小叶子节点数，减少树的大小

过拟合是因为模型过于复杂，导致对训练数据的拟合过度。应对过拟合的方法通常是减少模型复杂度。包括：

• 限制树的深度（max_depth）：限制树的最大深度可以防止树过于复杂，有助于防止过拟合。
• 增加最小样本分裂数（min_samples_split）：通过增加节点分裂所需的最小样本数，可以限制树的生长，使树不至于过度拟合训练数据。
• 增加最小叶子节点数（min_samples_leaf）：增加叶子节点的最小样本数可以减少树的复杂度，防止过拟合。
• 使用剪枝技术（如代价复杂度剪枝）：剪枝是控制过拟合的重要技术之一，通过减少树的大小来防止模型过度拟合。

剪枝（Pruning）

剪枝是决策树中用来防止过拟合的一种技术。它通过移除或合并一些不必要的节点来减少树的复杂度，从而提高模型的泛化能力。剪枝可以分为两种方式：

预剪枝（Pre-pruning）

• 原理：在构建决策树的过程中，提前停止树的生长，以避免树过于复杂。
• 方法：
  1. 设置最大深度：限制决策树的最大深度，防止树过深导致过拟合。
  2. 设置最小样本数：要求每个节点至少包含一定数量的样本，如果样本数不足则停止划分。
  3. 设置最小信息增益：如果划分后的信息增益小于某个阈值，则停止划分。
• 优点：节省计算资源，减少构建时间。
• 缺点：可能会提前停止构建，导致欠拟合。

后剪枝（Post-pruning）

• 原理：在决策树完全生长后，通过评估树的各个子树的表现来剪去不必要的分支，从而简化模型。
• 方法：
  1. 子树替换（Subtree Replacement）：用一个叶节点替换一个子树，直到错误率最低。
  2. 子树提升（Subtree Raising）：将子节点提升到父节点位置，删除不必要的中间节点。
  3. 成本复杂度剪枝（Cost Complexity Pruning）：通过最小化模型复杂度和训练误差的加权和，选择最优的子树。
• 优点：能够更精确地控制模型复杂度，提高泛化能力。
• 缺点：计算量较大，剪枝过程复杂。

注：C4.5 和 CART 都使用了后剪枝post-pruning方法来防止决策树的过拟合。

C4.5 的错误率估计剪枝操作

C4.5 在剪枝过程中采用错误率估计（Error-based Pruning）来决定是否剪枝。它通过对每个分支的误分类情况估计，如果剪去子树后能减少误分类率，就将该子树替换为叶节点。

• 操作步骤：
  1. 对每个叶节点和子树进行错误率估计。C4.5 引入了拉普拉斯平滑估计来计算每个节点的错误率。
  2. 计算子树的错误率，如果子树的错误率比该子树替换为叶节点后的错误率高，则将该子树剪除，将其变为叶节点。
  3. 重复该过程，直到所有需要剪枝的子树都被剪除。

• 优点：这种剪枝策略考虑了训练数据中的随机性，可以有效防止过拟合。
• 局限性：由于需要计算每个节点的错误率，并进行多次迭代计算，剪枝过程的计算开销较大。

CART 的成本复杂度剪枝操作

CART 使用的是成本复杂度剪枝（Cost Complexity Pruning），也称为最小代价复杂度剪枝。基于子树的错误率和模型复杂度的权衡。计算每个子树的错误率和复杂度，复杂度用子树中节点的数量来衡量。CART 会逐步剪掉那些增加了模型复杂度但并没有显著降低错误率的子树。

• 原理：成本复杂度剪枝通过平衡模型的复杂度和预测误差来选择最佳子树。它会给每个子树分配一个代价复杂度得分（Cost Complexity Score），该得分考虑了模型的复杂度和训练误差之和。

• 代价复杂度（Cost Complexity）：
  

• 操作步骤：
  1. 计算当前决策树每个子树的代价复杂度得分 (R_\alpha(T))。
  2. 找到降低代价复杂度得分最多的子树，并将其剪除，合并为一个叶节点。
  3. 重复上述步骤，逐步剪枝，直到得到最优子树为止。
  4. 使用交叉验证等方法选择最优的 (alpha) 值，确定最终的剪枝结果。

• 优点：能够在模型复杂度和预测性能之间找到最优平衡点，较好地控制了模型的复杂度。
• 局限性：代价复杂度参数的选择对模型性能影响较大，需要进行交叉验证等方法来优化。

总结

• C4.5 主要用于分类任务，并使用错误率估计的后剪枝策略进行剪枝，以防止过拟合。它通过比较子树和叶节点的错误率来决定是否剪枝。
• CART 可用于分类和回归任务，采用成本复杂度剪枝方法，通过平衡模型复杂度和训练误差选择最优子树，确保模型具有良好的泛化能力。

因此，C4.5 和 CART 在剪枝策略上各有特点，分别针对不同的任务和模型复杂度进行了优化。