决策树

date
Sep 11, 2022
Last edited time
Sep 25, 2022 05:11 AM
status
Published
slug
决策树
tags
ML
summary
之前的笔记, 现在放上来了
type
Post
origin
https://www.notion.so/lazurite/75537249da7c47a5969a86304f23d120
Field
Plat
决策树模型与学习决策树学习特征选择信息增益信息增益的算法决策树的生成ID3 算法C4.5 生成算法决策树的枝减树的剪枝算法CART 算法CART生成CART 剪枝

决策树模型与学习

  • 定义 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型: 内部结点( internal node) 和叶结点( leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。
notion image

决策树学习

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个，也可能一个都没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点, 并将这些子集分到所对应的叶结点中去; 如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。
决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。
决策树学习常用的算法有ID3、C4.5与CART,下面结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。

特征选择

对特征进行选择的准则是信息增益或者信息增益比.

信息增益

给定一个取有有限值的离散随机变量 , 其概率分布为: .
设训练数据集为 , 表示其样本容量，即样本个数。设有 个类 , , 为属于类 的样本个数，。 设特征 有 个不同的取值 , 根据特征 的取值将 划分为 个子集 , 为 的样本个数，。 记子集 中属于类 的样本的集合为 ,即 , 为 的样本个数。
  • 信息熵
      • 熵越大，随机变量的不确定性就越大。从定义可以验证: .
  • 条件熵
      • 条件熵 表示在已知随机变量 的条件下随机变量 的不确定性。随机变量 给定的条件下随机变量 的条件熵(conditional entropy) , 定义为 给定条件下 的条件概率分布的熵对 的数学期望
  • 信息增益
      • 特征 对训练数据集 的信息增益 ,定义为集合 的经验熵 与特征 给定条件下 的经验条件熵 之差，即 .
  • 信息增益比
      • 以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比 (information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。
      特征 对训练数据集 的信息增益比 定义为其信息增益 与训练数据集 关于特征 的值的熵 之比，即

信息增益的算法

  1. 计算数据集 的经验熵 .
  1. 计算特征 对数据集 的经验条件熵 .
  1. 计算信息增益.

决策树的生成

ID3 算法

  • 输入: 训练数据集 , 特征集 阈值 ;
  • 输出: 决策树 。
  1. 若 中所有实例属于同一类 , 则 为单结点树，并将类 作为该结点的类标记，返回 ;
  1. 若 , 则 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ;
  1. 否则，计算 中各特征对 的信息增益，选择信息增益最大的特征 ;
  1. 如果 的信息增益小于阈值 ,则置 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ;
  1. 否则，对 的每一可能值 ; 依 将 分割为若干非空子集 , 对第 个子结点，以 为训练集，以 为特征集，递归地调用步(1)~(5), 得到子树 , 返回 .
由于 ID3 算法只有树的生成, 因此容易过拟合.

C4.5 生成算法

C4.5算法与ID3算法相似，C4.5 算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。
  • 输入: 训练数据集 , 特征集 阈值 ;
  • 输出: 决策树 。
  1. 若 中所有实例属于同一类 , 则 为单结点树，并将类 作为该结点的类标记，返回 ;
  1. 若 , 则 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ;
  1. 否则，计算 中各特征对 的信息增益比，选择信息增益比最大的特征 ;
  1. 如果 的信息增益比小于阈值 ,则置 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ;
  1. 否则，对 的每一可能值 ; 依 将 分割为若干非空子集 , 对第 个子结点，以 为训练集，以 为特征集，递归地调用步(1)~(5), 得到子树 , 返回 .

决策树的枝减

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度,对已生成的决策树进行简化。
设树 的叶结点个数为 , 是树 的叶结点，该叶结点有 个样本点，其中 类的样本点有 个，, 为叶结点 上的经验熵 ， 为参数,则决策树学习的损失函数可以定义为
令:
则:
表示模型对训练数据的预测误差，即模型与训练数据的拟合程度， 表示模型复杂度，参数 控制两者之间的影响。较大的 促使选择较简单的模型(树),较小的 促使选择较复杂的模型(树)。 意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
剪枝，就是当 确定时，选择损失函数最小的模型，即损失函数最小的子树。

树的剪枝算法

  • 输入:生成算法产生的整个树 ,参数 ;
  • 输出: 修剪后的子树 。
  1. 计算每个结点的经验熵。
  1. 递归地从树的叶结点向上回缩, 计算树的损失函数值 。
  1. 设一组叶结点回缩到其父结点之前与之后的整体树分别为 与 , 其对应的损失函数值分别是 与 ,如果 , 则进行剪枝, 即将父节点变为新的叶节点.
可以使用动态规划实现

CART 算法

CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。
CART算法由以下两步组成:
  1. 决策树生成:基于训练数据集生成决策树，生成的决策树要尽量大
  1. 决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART生成

  1. 回归树的生成
      • 输入:训练数据集 ;
      • 输出:回归树 。
      在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树:
    1. 选择最优切分变量 与切分点 ,求解
        2. 遍历变量 ,对固定的切分变量 扫描切分点 ,选择使上式达到最小值的对 .
    2. 用选定的对 划分区域并决定相应的输出值:
    3. 继续对两个子区域调用步骤(1)，(2)，直至满足停止条件。
    4. 将输入空间划分为 个区域 ,生成决策树:
  1. 分类树的生成
      2. 分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。 基尼指数 分类问题中，假设有 个类，样本点属于第 类的概率为 ,则概率分布的基尼指数定义为
      对于给定的样本集合 ,其基尼指數为
      这里， 是 中属于第 类的样本子集，是类的个数。
      如果样本集合 根据特征 是否取某一可能值 被分割成 和 两部分，即
      则在特征 的条件下，集合 的基尼指数定义为
      基尼指数 表示集合 的不确定性，基尼指数 表示经 分割后集合 的不确定性。基尼指数值越大,样本集合的不确定性也就越大，这一点与熵相似。
      回归树的生成
  • 输入:训练数据集 ,停止计算的条件;
  • 输出: CART决策树。
      • 根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树:
  1. 设结点的训练数据集为 ,计算现有特征对该数据集的基尼指数。此时，对每一个特征 ,对其可能取的每个值 ,根据样本点对 的测试为“是”或“否”将 分割成 和 两部分，计算 时的基尼指数。
  1. 在所有可能的特征 以及它们所有可能的切分点 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
  1. 对两个子结点递归地调用(1), (2),直至满足停止条件。
  1. 生成CART决策树。

CART 剪枝

  • 输入: CART算法生成的决策树 ;
  • 输出:最优决策树 .
  1. 设 , 。
  1. 设 .
  1. 自下而上地对各内部结点 计算 , 以及
      2. 这里， 表示以 为根结点的子树， 是对训练数据的预测误差， 是 的叶结点个数。
      因为当 时, 与 有相同的损失函数值, 而 的节点更少, 因此 比 更可取, 对 进行剪枝.
  1. 对 的内部结点 进行剪枝，并对叶结点 以多数表决法决定其类，得到树 .
  1. 设 。
  1. 如果 不是由根结点及两个叶结点构成的树，则回到步骤(2);否则令 。
  1. 采用交叉验证法在子树序列 中选取最优子树 .

© Lazurite 2021 - 2024