机器学习（西瓜书）第 4 章决策树

4.1 决策树基本流程

决策树模型

在这里插入图片描述

基本流程

在这里插入图片描述
在第⑵种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第⑶种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别.注意这两种情形的处理实质不同：情形⑵是在利用当前结点的后验分布，而情形⑶则是把父结点的样本分布作为当前结点的先验分布.

基本算法

在这里插入图片描述
由算法4 .2可看出，决策树学习的关键是第8 行，即如何选择最优划分属性.一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高.

4.2 信息增益划分

信息增益

信息论中最重要的理论——熵

信息熵度量一个集合的纯度

自信息：对于随机变量大X，它每个取值x都有它的概率p(x)
信息熵是自信息的期望
在这里插入图片描述

从公式可以看出，信息熵最小，纯度最高的情况：有一个所占比例是1，其他所占比例都是0，此时信息熵为0

当X的各个取值的概率均等时（样本中每一个的概率均等时），信息熵最大（也就是最不确定），纯度最低

为什么要使用信息熵来算？
——
在这里插入图片描述

信息增益：在已知属性（特征）a的取值后y的不确定性减少的量，也即纯度的提升

计算出D^v的信息熵,再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重|D ^v|/|D|,即样本数越多的分支结点的影响越大，于是可计算出用属性a对样本集D 进行划分所获得的“信息增益”

ID3决策树：以信息增益为准则来选择划分属性的决策树
在这里插入图片描述

可以用信息增益的方式来度量用这种方式划分的价值

信息增益的定义：划分前的信息熵 - 划分后的信息熵

最优化的属性：要让信息增益最大，即每一步划分后的结果只要最少的信息。尽可能的干净

一个例子

在这里插入图片描述
首先求出未划分前，当前样本集合（根节点）的信息熵

在这里插入图片描述

如果以属性“色泽”划分，对于D1（色泽=青绿），3条正类，3条负类，因此信息熵公式如上
在这里插入图片描述

4.3 其他属性划分准则

信息增益准则对可取值数目较多的属性有所偏好，即偏好了分枝多的属性（分到每个分枝上的数目就会越少）

例如若把“编号””也作为一个候选划分属性，则根据式(4.2)可计算出它的信息增益为0.998,远大于其他候选划分属性.这很容易理解：“编号”将产生17个分支，每个分支结点仅包含一个样本，这些分支结点的纯度已达最大.然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测.

基于ID3，C4.5现在的改进：不再以信息增益作为划分的准则，而是使用增益率

增益率

在这里插入图片描述

分母IV是分支越少越好，而分子是信息增益越大越好

那么两者折中的点在哪里呢？没有一个绝对正确的权衡，无法找到一个完美的决策树

增益率准则对可取值数目较少的属性有所偏好，因此，通常在C4.5中的做法——启发式：先把信息增益做一个标准，把高于平均水平的找出来，再其中挑增益率最大的；而不是直接由增益率排序而来，因为增益率对可能取值数目较少的属性有所偏好

规范化：把原先不可比较的东西，变得可以比较了
归一化：是规范化的特殊形式，是针对数值属性的。规范化至0与1之间

基尼指数

基尼值和基尼指数
在这里插入图片描述

基尼值越小，碰到异类的概率就越小，纯度自然就越高

按属性划分后的基尼值，我们称为基尼指数

CART决策树：选择基尼指数最小的属性作为最优划分属性在这里插入图片描述
实际操作时，CART决策树（二叉树）和前面按信息增益的决策树（不一定是二叉树）在具体选划分点时有所区别，和前面的基尼公式也有所不同：

在这里插入图片描述

划分选择 vs 剪枝

在这里插入图片描述

4.4 决策树的剪枝

为何剪枝对决策树泛化性能影响更显著？
——剪枝是决策树对付“过拟合”的主要手段

在这里插入图片描述

4.5 预剪枝与后剪枝

现在我们假定使用“留出法”来在剪枝过程中评估剪枝前后决策树的优劣，即预留一部分数据用作“验证集”以进行性能评估

数据集

在这里插入图片描述

预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
在这里插入图片描述

这就是预剪枝最终得到的决策树

在这里插入图片描述
在用属性“脐部”划分之后，图4.6中的结点2、3、4分别包含编号为｛1,2,3,14｝、｛6,7,15,17｝、｛10,16｝的训练样例，因此这3 个结点分别被标记为叶结点“好瓜”、 “好瓜”、 “坏瓜”.此时，验证集中编号为(4,5,8,11,12)的样例被分类正确，验证集精度为5/7 x 100% = 71.4% > 42.9%.于是，用 “脐部”进行划分得以确定.

对比图4.6和图4.5可看出，预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销.但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可
能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显
著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了
欠拟合的风险.

后剪枝

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

后剪枝：先生成一颗完整的决策树，然后看中间做属性决策的结点能否用叶节点来替换它
注意是从最深的开始考虑，因为越深的越可能是受到overfitting的影响的结果
在这里插入图片描述

在这里插入图片描述
——如果剪枝了：

在这里插入图片描述

对比图4.7和图4.6可看出，后剪枝决策树通常比预剪枝决策树保留了更多的分支.一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预
剪枝决策树.但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上
地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树
和预剪枝决策树都要大得多.

预剪枝 vs 后剪枝

在这里插入图片描述

4.6 连续值的处理

到目前为止我们仅讨论了基于离散属性来生成决策树.现实学习任务中常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性.由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分.此时，连续属性离散化技术可派上用场.最简单的策略是采用二分法(bi-partition)对连续属性进行处理，这正是C4.5决策树算法中采用的机制[Quinlan, 1993].

给定样本集D 和连续属性a.假定a在D上出现了 n个不同的取值，将这些值从小到大进行排序
显然，对相邻的属性取值a_i与a_i+1 来说，t在区间[a^i,a ^i+1)中取任意值所产生的划分结果相同.因此,对连续属性a,我们可考察包含n- 1个元素的候选划分点集合

即把区间[a^i,a ^i+1)的中位点(a ^i,a ^i+1)/2作为候选划分点.然后，我们就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分.例如,
可对式(4.2)（信息增益）稍加改造：
在这里插入图片描述