决策树

前言

记录自己的学习思路，搬用了较多原文。 且为了偷懒，原文处多用省略号。

第四章、决策树

4.1、基本流程

在介绍基本流程前，我们先来了解一下决策树的概念，以及决策树学习的目的。

• 由左侧注释可知： 决策树既可以指学习方法，也可以指学得的树。要根据叙述的上下文环境而定。现在我介绍的是学习方法。 决策树是一类基于树结构来进行决策的机器学习方法。

  • 对于树结构，大家一定都不陌生，这里我简单介绍一下决策树的组成。决策树由一个根节点、若干内部节点和若干叶节点；根节点包含样本全集；其他节点对应一个测试属性，其包含的样本集合会被该属性划分到子节点中；叶节点对应了不同的预测结果。 我们的目的是从包含样本全集的根节点找到它到每个叶节点的路径对应一个判定预测序列。

• 决策树学习的目的：是为了产生一棵泛化能力强的树，其流程遵守简单直观的“分而治之”的策略。

• 对于决策过程，书上给出了一个形象的例子——西瓜问题。对于该问题，明确要做的决策是：“这是好瓜吗？” 看图4.1，决策过程中，我们会基于它的每个属性进行一系列的子决策，每个子决策的结果或是导出最终结论，或是到出进一步的判定问题。当所有判定结束后， 每个子节点就对应了决策的结论。

• 有了对过程的大概认识，下面我来介绍一下决策树学习的基本算法.

  如图4.2，显然，决策树的生成是一个递归过程，递归停止的条件有三个：1.2.3，对于三种情况，其类别判定规则如书上介绍。

---

刚刚在介绍决策过程时，不知道大家有没有一个疑惑？ 为什么先根据色泽进行划分，之后再根据根蒂，我是否可以改变一下顺序？其实，划分的顺序，对应图4.2算法中的第8行——从A中选择最优划分属性。这是我们决策树学习的关键。

如何选择最优划分属性呢？ 让我们开始4.2节的学习。

4.2、 划分选择

一般而言，随着划分过程的不断进行，我们希望决策树的分…..越来越高。

4.2节，介绍了三种划分属性选择的指标。分别是信息增益，增益率和基尼指数。

• 我们先来了解一下信息增益，在了解信息增益前，先看一下信息熵，书上的定义：（公式）。我们已经学过了信息论与编码，这个概念大家都不陌生。熵，代表了物体的不确定性。所有，熵越小，不确定性越小，D的纯度就越高。
• 信息增益是针对某个属性而言的，假定离散属性a有V个…..,看信息增益公式，前面是D的信息熵，后面是按属性a进行划分后各部分信息熵的加权求和。
  • 一般而言，信息增益越大….属性。
  • 下面来介绍一下书上的这个举例。
    • 见附录

• 下面我们来介绍增益率
  • 第一段中，书上介绍了不以编号作为候选属性的原因。（大概介绍一下）
  • 上面这个例子，其实就反应了信息增益的一个不足——信息增益准则对可取值数目较多的属性有所偏好。 为减少…定义为：
  • 分子部分为属性a的信息增益，分母为属性a的固有值（是一个关于属性a的熵）
    • 之所以会用信息增益 除以 固有值，是因为属性a的取值数目越多，固有值得取值一般越大。（类似于相对值，会更加准确一点）
  • 需要注意的是：增益率准则对可取值数目较少的属性有所偏好。因此C4.5 算法选择特征的方法是先从候选特征中选出信息增益高于平均水平的特征，再从这些特征中选择增益率最高的。

• 最后，介绍一下基尼指数，公式如下，直观来说，Gini（D）反映了从数据集….纯度越高。
• 采用和式（4.2）相同得形式，（假装有公式）。于是，…即：。

4.3、 剪枝处理

• 剪枝的概念： 字面意思理解就好，它是决策树学习算法对付“过拟合”的主要手段。

• 分类

  • 预剪枝

    在决策树生成过程中，对每个节点在划分前进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标为叶节点。

  • 后剪枝

    先从训练集生成一棵完整的决策树，然后自底向上的对非叶节点进行考察，若将该节点对应子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。

• 课本举例

  (结合例子对两方法优劣进行说明)

• 两方法优缺点

  • 预剪枝
    • 优点：
      1. 降低了过拟合风险
      2. 显著减少了决策树训练时间开销和测试时间开销
    • 缺点：
      1. 有些分支划分暂时不能带来泛化性能提高，但在其基础上进行的后续划分可导致性能的显著提高。
      2. 这种基于“贪心”本质禁止分支展开，给预剪枝决策树带来欠拟合的风险。
  • 后剪枝
    • 优点：
      1. 比预剪枝保留了跟多分支，欠拟合风险更小，泛化性能往往由于预剪枝决策树。
    • 缺点：
      1. 训练时间开销要大的多

4.4、连续与缺失值

• 连续值处理

  到目前为止，我们仅讨论了基于离散属性来生成决策树。现实任务中常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。

  由于连续属性取值不再有限，所有不能直接根据连续属性的可取值进行划分，这时，我们要用到连续属性离散化技术，最简单的时采用“二分法”对其处理，这正是C4.5决策树算法中采用的机制。

  balabal，写不动了（就照着书读）。

  强调：85页画线（即连续属性还可以作为后代节点的划分属性）

• 缺失值处理

  现实任务中，会遇到不完整的样本，即样本的的某些属性值缺失。 如果简单放弃不完整样本，显然是对数据信息的极大浪费

  • 对于利用缺失数据，我们将面临两个问题：

    • 如何在属性值缺失的情况下进行划分属性选择

      信息增益 = 无缺失样本比例 X 无缺失样本的信息增益

    • 在给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分

      对于样本x，若在属性a上取值未知，那么则将x同时划入所有子节点，且样本权重在对应子节点中调整为r·w（看书就行）。其实就是让统一样本以不同概率划入到不同的子节点中。

• 多变量决策树

  我们把每个属性是为空间坐标中的一个坐标轴，南无d个属性所描述的样本对应了d维空间的一个数据点。对样本分类就以为着在这个坐标空间寻找不同样本之间的分类边界

  决策树的分类边界有一个明显的特点：轴平行，即他的分类边界由若干个与坐标轴平行的分段组成。

  显然，分类边界…开销会很大。

  • 多变量决策树概念就是实现“斜划分”甚至更加复杂的划分

  • 与传统单变量决策树的区别：

    不是维每个非叶子节点寻找一个最优的划分属性，而是视图建立一个合适的线性分类器（对属性的线性组合）