4.1 基本流程

决策树是一类常见的机器学习算法，又称“判别树”，决策过程最终结论对应了我们所希望的判定结果。

image.png一个根节点：包括样本全集image.png若干个内部节点：对应属性测试
image.png若干个叶子节点🍃：对应决策结果

决策树的形成是一个递归过程。
生成叶子结点的三种情况：

  1. 当前节点包含的样本全部属于同一类别
  2. 当前属性集为空，或所有样本在所有属性上取值相同
  3. 当前节点包含的样本集合为空

4.2 划分选择

决策树学习的关键在于如何选择最优划分属性。一般而言,随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”(purity)越来越高

4.2.1 信息增益

知乎YJango解释“信息熵”的视频：（知乎指路）

1586599568192.mp4 (16.09MB)1586599572424.mp4 (14.06MB) “信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。假定当前样本集合为 第四章 决策树🌳 - 图6 中第 第四章 决策树🌳 - 图7 类样本所占比例为 第四章 决策树🌳 - 图8，则 第四章 决策树🌳 - 图9 的信息熵定义为：QQ截图20200412113424.png

  • 计算信息熵时约定：若 第四章 决策树🌳 - 图11，则第四章 决策树🌳 - 图12；
  • Ent（D）的最小值为0，最大值为 第四章 决策树🌳 - 图13；
  • Ent（D）的值越小，则 D 的纯度越高。

假定离散属性 a 有个可能的取值 {a，a2，…，aV}，若使用 a 来对样本集 D 进行划分，则会产生 V 个分支结点其中第 v 个分支结点包含了 D 中所有在属性 a 上取值为 a的样本，记为 D。我们可根据式(4.1)计算出 D 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 |D|/|D| 即样本数越多的分支结点的影响越大于，于是可计算出用属性 a 对样本集 D 进行划分所获得的“信息增益”(information gain)
QQ截图20200412145500.png
一般而言，信息增益越大，则意味着使用属性 a 来进行划分所获得的“纯度提升”越大，效果越好。因此，我们可用信息增益来进行决策树的划分属性选择，4.1节中算法选择属性QQ截图20200412145716.png。
image.png
IEIZ@T%F_0163XS)M`G(@3R.jpg

纹理信息增益最大，选为划分属性：

image.png
image.png

图4.3可更新为下图：

QQ截图20200412110044.png

一步步计算，一步步更新，（递归过程）最后可得到决策树

QQ截图20200412110143.png

4.2.2 增益率

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”(gain ratio)来选择最优划分属性。采用与式(4.2)相同的符号表示，增益率定义为
image.png
属性a“固有值”（intrinsic value）
QQ截图20200412111647.png
增益率准则对可取值数目较少的属性有所偏好。
C4.5并不是直接使用增益率：先找信息增益高于平均水平的，再选择增益率最高的。

4.2.3 基尼指数

CART决策树使用“基尼指数”选择划分属性。
数据集第四章 决策树🌳 - 图24的纯度可用基尼值度量：QQ截图20200412112952.png
直观看，Gini（D）反映了从第四章 决策树🌳 - 图26中随机挑两个样本，其类别标记不一致的概率。Gini（D）越小，纯度越高。
属性 a 的基尼指数（基尼不纯度）定义为：QQ截图20200412113030.png
属性集合 A 中，选得划分后基尼指数最小的属性作为最优划分属性QQ截图20200412113109.png

4.3 剪枝处理

剪枝是用来解决“过拟合”问题。
决策树剪枝的基本策略：“预剪枝”“后剪枝”（判断标准：决策树泛化标准是否提升？）

  1. 预剪枝：生成过程中，每个节点划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点;
  2. 后剪枝：生成完整树，自底向上进行考察

QQ截图20200412163214.png

4.3.1 预剪枝（自上而下）

QQ截图20200412164401.png
预剪枝的优缺点：

  • 优点
    1. 1. 降低过拟合风险
    2. 1. 显著减少训练时间和测试时间开销

  • 缺点

    1.          欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致                 性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，带来了欠拟合风险。

    4.3.2 后剪枝（自下而上）

    QQ截图20200412171454.png
    QQ截图20200412172339.png
    后剪枝的优缺点：

  • 优点

    1.          后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树

  • 缺点

    1.          训练时间开销大：后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一考察

    4.4 连续与缺失值

    4.4.1 连续值的处理

    由于连续属性的可取值数目不再有限，连续属性离散化技术可派上用场。比如二分法（bi-partition）对连续属性进行处理（C4.5决策树机制）。
    给定样本集D，连续属性a
    假定a在D上出现了n个不同的取值，从小到大排序
    image.png

对于连续属性a，我们可以考虑包含（n-1）个元素的候选划分点集合。
image.png
image.png
image.png
image.png

把密度按从小到大排序，0.243，0.245, 0.343，… 第一个二分点：（0.243+0.245）/ 2 = 0.244 第二个二分点… T密度={0.244, 0.294, 0.351, 0.381, 0.420, 0.459, 0.518, 0.574, 0.600, 0.621, 0.636, 0.648, 0.661, 0.681, 0.708，0.746}。以0.244位划分点，D{0.243}，D{其余}，计算信息增益。由式（4.8)可计算

逐个计算，选择信息增益最大的

可计算其信息增益为0.262, 对应划分点为0.381
与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性
image.png

4.4.2 缺失值处理

如何在属性缺失的情况下进行划分属性选择？
给定划分属性，若在该属性上的值缺失，如何对样本进行划分？
QQ截图20200413143736.png
给定训练集 D {1,2，…，17}和属性 a {色泽，根蒂，敲声，纹理，脐部，触感}
令image.png表示 D 中在属性 a 上没有缺失值的样本子集。{4,14,16}
假定属性 a 有 V 个可取值image.png
令image.png表示image.png中在属性 a 上取值为image.png 的样本子集 =>image.png
image.png
image.png表示image.png中属于第k类image.png的样本子集 =>image.png
image.png
每个样本 x 赋予一个权重image.png，定义
QQ截图20200413151955.png
image.png表示无缺失值样本所占比例
image.png表示无缺失值样本中第 k 类所占比例
image.png表示无缺失值样本中在属性a上取值image.png的样本
显然，image.png
（y为某个属性下又有n个取值，比如敲声取值有3个；V为a的属性取值，比如 a 有6个值）
将信息增益的计算式（4.2）推广为
image.png

QQ截图20200413150334.png

image.png
QQ截图20200413145839.png

QQ截图20200413150227.png

4.5 多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则 d 个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。
决策树所形成的分类边界有一个明显的特点：轴平行(axis-parallel),即它的分类边界由若干个与坐标轴平行的分段组成。
image.png
“多变量决策树”就是能实现这样的“斜划分”甚至更复杂划分的决策树，又称“斜决策树”
在此类决策树中，非叶节点不再是仅对某个属性，而是对属性的线性组合测试；
QQ截图20200413151329.png