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

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

🌺历史文章列表🌺

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

文章目录

    • 决策树(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 D D ),它的熵定义为:
H ( D ) = − ∑ i = 1 m p i log ⁡ 2 ( p i ) H(D) = - \sum_{i=1}^m p_i \log_2(p_i) H(D)=i=1mpilog2(pi)
其中:

  • m m m 是类别的总数。
  • p i p_i pi 是数据集中属于第 i i i 类的样本所占的比例。
信息增益(Information Gain)

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

  • H ( D ) H(D) H(D) 是数据集 D D D 的信息熵。
  • V V V 是特征 A A A 的可能取值数。
  • D v D_v Dv 是根据特征 A A A 的取值 v v v 分割得到的子集。
  • ∣ D v ∣ / ∣ D ∣ |D_v| / |D| Dv∣/∣D 表示取值 v v v 的样本在数据集 D D D 中的比例。
  • H ( D v ) H(D_v) H(Dv) 是子集 D v D_v Dv 的熵。
算法流程
  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 A A 的取值分布,它的计算公式为:

固有信息 = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ 2 ( ∣ D v ∣ ∣ D ∣ ) \text{固有信息} = - \sum_{v=1}^V \frac{|D_v|}{|D|} \log_2 \left( \frac{|D_v|}{|D|} \right) 固有信息=v=1VDDvlog2(DDv)
其中:

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

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


处理连续型变量

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

步骤

  1. 生成候选划分点:将连续特征值按升序排列,计算每个相邻值的中点作为候选划分点。例如,如果连续特征的两个相邻值为 x i x_i xi x i + 1 x_{i+1} xi+1,候选划分点为 t = x i + x i + 1 2 t = \frac{x_i + x_{i+1}}{2} t=2xi+xi+1
  2. 计算信息增益比:对于每个候选划分点 ( t ),将数据集划分成两个子集
    • 子集 1:特征值 ≤ t \leq t t 的样本。
    • 子集 2:特征值 > t > t >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 D D,其基尼指数定义为:
基尼指数 = 1 − ∑ i = 1 m p i 2 \text{基尼指数} = 1 - \sum_{i=1}^m p_i^2 基尼指数=1i=1mpi2
其中:

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

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

Gini ( D , A ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Gini ( D v ) \text{Gini}(D, A) = \sum_{v=1}^V \frac{|D_v|}{|D|} \text{Gini}(D_v) Gini(D,A)=v=1VDDvGini(Dv)

其中:

  • V V V 是特征 A A A 的取值个数。
  • D v D_v Dv 是根据特征 A A A 的取值 v v v 划分得到的子集。
  • Gini ( D v ) \text{Gini}(D_v) Gini(Dv) 是子集 D v D_v Dv 的基尼指数。
回归任务均方误差(Mean Squared Error, MSE)

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

  • ∣ D ∣ |D| D 是数据集中样本的数量。
  • y i y_i yi 是第 i i i 个样本的真实值。
  • y ^ \hat{y} y^ 是数据集 D D 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 在剪枝策略上各有特点,分别针对不同的任务和模型复杂度进行了优化。


http://www.mrgr.cn/news/70739.html

相关文章:

  • 【Python爬虫之:使用 Funboost 分布式函数调度爬取视频】
  • Windows系统编程 - 注册表
  • 【深度学习】金属齿轮缺陷检测【附链接】
  • 【MySQL实战45讲笔记】基础篇——redo log 和 binlog
  • 23种设计模式-模板方法(Template Method)设计模式
  • 记录———封装uni-app+vant(u-upload)上传图片组件
  • [C++]——位图与布隆过滤器
  • Rust 模板匹配——根据指定图片查找处于大图中的位置(支持GPU加速)
  • APP封装系统 app误报毒app可上传 自动实现5分钟随机更换包名和签名
  • VMnet NAT模式配置
  • Perfetto中如何使用SQL语句
  • MutationObserver与IntersectionObserver的区别
  • IEEE JSSC更新|Tiny Tapeout:让每个人都能设计定制芯片
  • 【C】一文速学----线程池原理与实战
  • 【计算机网络】网络框架
  • C0028.在Clion中快速生成头文件中声明的函数的方法
  • 车载诊断架构---域控下挂节点信息同步策略
  • 基于51单片机密码锁—有3个密码lcd1602显示
  • 【项目开发】RESTful架构及RESTful API设计指南
  • dapp获取钱包地址,及签名
  • js.零钱兑换
  • python:用 sklearn 转换器处理数据
  • 【C++ 篇】类之华章:超越固有模式,品味面向对象的璀璨光芒
  • OSG开发笔记(三十一):OSG中LOD层次细节模型介绍和使用
  • MySQL数据库的备份与还原
  • 大模型论文精华—20241111