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

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

news 2024/11/14 2:49:59

🌺历史文章列表🌺

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

文章目录

决策树（Decision Tree）概述
基本概念
任务类型
分类任务
回归任务
分类和回归中的差异

决策树算法的具体实现
比较总结
ID3（Iterative Dichotomiser 3）
原理
主要特点
信息熵（Entropy）
信息增益（Information Gain）
算法流程
优点
缺点

C4.5
原理
主要特点
信息增益比（Information Gain Ratio）
固有信息（Intrinsic Information）
处理连续型变量
处理缺失值
算法流程
优点
缺点

CART（Classification and Regression Tree）
原理
主要特点
分类任务基尼指数（Gini Index）
回归任务均方误差（Mean Squared Error, MSE）
分类树算法流程
回归树算法流程
优点
缺点

决策树的过拟合和欠拟合
解决欠拟合
解决过拟合

剪枝（Pruning）
预剪枝（Pre-pruning）
后剪枝（Post-pruning）
C4.5 的错误率估计剪枝操作
CART 的成本复杂度剪枝操作

总结

决策树（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$ )，它的熵定义为：
$\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。
当所有特征都被使用，或所有样本都属于同一类别时，停止划分。

优点

简单易懂：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 算法将其转化为一个二值问题（例如，小于某个阈值和大于等于该阈值），以便将连续变量用于决策树的分裂。

步骤：

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

处理缺失值

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

步骤：

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

算法流程

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

优点

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

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

缺点

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

CART（Classification and Regression Tree）

原理

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

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

主要特点

划分准则：
- 分类任务：使用基尼指数作为划分准则。
- 回归任务：使用均方误差作为划分准则。
适用数据类型：支持离散和连续特征。
剪枝：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$ 中所有样本的均值。

分类树算法流程

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

回归树算法流程

遍历每个特征：对于每个特征，尝试在数据集中的不同数值作为可能的分裂点。
计算分裂后的均方误差：对于每个分裂点，计算其分裂后左右子集的加权均方误差（MSE），公式如下：
选择最优分裂点：选择使得分裂后均方误差最小的分裂点，将该特征和分裂点作为当前节点的分裂依据。
递归构建树：对分裂后的左右子节点重复步骤 1-3，继续寻找最优分裂点，构建新的子节点。
停止条件：当达到预设的停止条件时（例如节点样本数小于设定阈值或MSE降低不明显），停止递归分裂。此时，该节点成为一个叶节点，并赋予其目标值的平均值作为预测值。

优点

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

缺点

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

决策树的过拟合和欠拟合

解决欠拟合

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

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

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

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

解决过拟合

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

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

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

限制树的深度（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）来决定是否剪枝。它通过对每个分支的误分类情况估计，如果剪去子树后能减少误分类率，就将该子树替换为叶节点。

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

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

CART 的成本复杂度剪枝操作

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