机器学习（西瓜书）第 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)（信息增益）稍加改造：

4.7 缺失值的处理

缺失值

其中“权重划分”指的是：给定划分属性，若样本在该属性上的值缺失，会按权重同时进入所有分支

一个例子

区别变化是在计算总的信息增益时前面乘上 无缺失值样例占比

选其中最大的信息增益：

把有值的样本进入各个属性的划分结果当作了没有值的样本进入的先验