一.问题描述

假设我们现在有这样一个数据集，记录了每次打篮球的时候，当天的天气、温度、湿度、刮风等情况

然后根据历史的数据集，我们用决策树算法生成了如下的图形：

决策树模型会根据大量的历史样本数据，运用算法选择合适的属性作为节点，最终构造出类似流程图的树状结构。

决策树的基本结构包含根节点、子节点（有子节点就有父节点，子和父是相对的，一个子节点可能是下一个分支节点的父节点）、叶子节点。

1.根节点：就是决策树最开始的节点，刚才我们生成的决策树图中，根节点就是“天气”。

2.子节点：就是树中间的一些节点，比如“温度”。

3.叶子节点：最底部的节点，已经不能再分下去，也是决策的结果。

在决策树的算法中，不管是ID3（信息增益），C4.5（信息增益率）还是CART（基尼系数），都在解决同样的问题：

1.选择哪个属性作为根节点。

2.选择那些属性作为子节点。

3.什么时候停止得到决策的结果，即叶子节点。

二.决策方式

1.ID3

1.1流程简介

ID3算法的规则非常简单，就是寻找信息增益最大的属性作为节点。信息增益最大，意味着使用这个属性之后，结果的不确定性最低

熵是用来衡量事物的不确定性，事物的不确定性越大，熵就越大，其公式为：

信息增益（information gain）的公式如下：

Ent是熵Entropy的缩写；

n是属性a所有值的数量，比如天气属性有三个值，{晴天、小雨、阴天}，那么n=3；

Ent(D)是原集合D的熵；是相应属性值对应的子集， 

 是各个子集的熵的加权和，权值为 的数量占原集合的比例。

这个公式描述的就是原集合D的熵在知道属性a之后熵减少了多少。熵减少意味着不确定减少，熵减少的数量就是信息增加的数量，获取信息可以减少不确定性。熵和信息的数量相等，意义相反。

如果一个数据集决策属性越杂，我们就说数据集的纯度越低，熵越大。如果决策属性的值都是打篮球，数据集纯度是最高的，没有任何不确定性，熵为0。当数据集决策属性的值有两个，一半是打篮球，一半是不打篮球，纯度最低，熵为1。

如果我们能找到某个条件属性（表中的天气、温度、湿度、刮风都称作条件属性），通过对数据集进行划分，使得决策属性（表中的是否打篮球称做决策属性）的不确定性降低，那么这个条件属性我们就作为决策树的节点。

根节点确认以后（比如例子中的天气），根据根节点的属性值（晴天、小雨、阴天都是天气属性的值），整个数据集又被划分为不同的子数据集（按照晴天、小雨、阴天，整个数据集分为不同的部分），然后对子数据集重复同样的计算，求出子数据集中使得决策属性不确定性最低的属性，将该属性作为子节点，直到不能再继续分下去，到叶子节点停止。

1.2实例详解

我们以打篮球的例子，来重复整个ID3算法的过程。

我们有11个样本的数据集D，其中标签属性中有7个输出为打篮球，4个为不打篮球。数据集D的不确定性是0.9457。

我们可以看到，如果以天气作为属性进行划分，信息增益为0.695。

如果以温度作为属性划分，信息增益为0.591。

湿度、刮风的计算细节就不再展示，同样的方法计算得出，当湿度作为属性进行划分，信息增益为0.6176；刮风作为属性进行划分，信息增益为0.0238。

计算结果显示，当天气作为属性时，信息增益最大。因为ID3算法就是寻找信息增益最大的属性作为节点，所以我们最终选取天气作为根节点。

天气已经确定为根节点，所以天气这个属性后面也不必再重复计算，以确保已经确定为节点的属性在任意路径最多只出现一次。

当天气等于晴天时，所有的结果都是打篮球，没有任何不确定性，所以不必再继续分下去，叶子节点就是打篮球；当天气等于小雨时，所有的结果都是不打篮球，没有任何不确定性，所以也不必再继续分下去，叶子节点就是不打篮球；当天气等于阴天时，结果有打篮球，也有不打篮球。所以我们必须再从温度、湿度、刮风等条件属性中，找到信息增益最大的属性作为节点，继续分裂下去。计算方法和上面一样，分别求出当条件是温度、湿度、刮风时的信息增益。经过计算我们会发现选择属性温度时，信息增益最大，所以阴天这个分支，继续选择温度作为子节点。

温度作为节点之后，再继续分裂，没有任何不确定性。当温度为中的时候，结果都是打篮球，低的时候，结果是不打篮球。所以整个决策树就构造完成了。

我们可以看到，刮风这个属性并没有在决策树中。说明刮风作为属性的时候，没有降低任何不确定性，对判断是否打篮球没有帮助，所以被算法排除掉了。

2.C4.5

C4.5算法在ID3算法上进行了改良，我们来看一下C4.5算法是如何解决ID3算法中的不足。

2.1处理连续值

离散型属性的值是有限的，比如属性天气的值只有三个：晴天、下雨、阴天，可以一一枚举。

而连续性属性的值不再有限，比如工资，有可能是6000，也有可能是6500，还有7000等等。如果将连续性属性的每一个值，当成单独的值来看待，就会生成下面这样的决策树。这个决策树对于我们判断问题来说，没有任何用处。我们需要得到的是，工资小于6000，大于6000小于10000这样的分类，而不需要每一个工资值的分类。

C4.5算法于是将连续的属性进行离散化，离散化策略就是二分法：

以贷款人员的数据集为例，我们来看看具体的计算过程：

年收入从小到大排列：70，95，100，120，125

计算中值T：82.5，97.5，110，122.5

下面计算T取不同值的信息增益

当T= 82.5时：

当T=97.5时：

同样的方法，求出当T=110、T=122.5时的信息增益，具体的计算过程就不再展示了。

最后我们发现当T=97.5时，信息增益最大。也就是说年收入以97.5作为阀值，划分的数据集不确定性最小。

2.2采用信息增益率代替信息增益

ID3算法由于采用的是信息增益，容易倾向于选择取值较多的属性作为节点。改良后的C4.5算法采用的是信息增益率，信息增益率=信息增益/属性熵。

公式：

其中属性熵：

当属性有很多值时，虽然信息增益变大了，但是相应的属性熵也会变大。所以最终计算的信息增益率并不是很大。在一定程度上可以避免ID3倾向于选择取值较多的属性作为节点的问题。

当属性为天气时，计算的信息增益、信息增益率如下

当属性为温度时，计算的信息增益和信息增益率如下：

我们对比发现，当温度作为条件时，由于温度有三个值（高、中、低），信息增益为0.32，远大于天气作为条件时的信息增益0.19。当使用信息增益率时，温度作为条件算出来的信息增益率为0.20，与天气作为条件的信息增益率0.19非常接近。

但是使用增益率可能产生另外一个问题，就是如果属性取值数目较少，我们来想一个比较极端的例子，假如属性只取一个值，属性熵就是0。我们知道一个数除以一个接近0的数，会变成无穷大。所以增益率可能会偏好取值比较少的属性。因此C4.5采用了一个启发式的算法，先从候选属性中找出高于平均水平的属性，再从高于平均水平的属性中选择增益率最高的属性。

2.3缺失值的处理

缺失值涉及到两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。

对于第一个子问题，某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。

对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。

具体计算方法，可以看看周志华老师的《机器学习》。

3.CART

CART对连续型属性处理方式和C4.5一样，只不过使用GINI值作为属性划分的依据，而C4.5是采用增益率作为依据。

对于离散型属性，C4.5是理论上有多少个离散值就分裂成多少个节点。但CART算法生成的是一颗二叉树，每一次分裂只会产生两个节点。

以打篮球案例中的“天气”属性为例，C4.5算法分裂成了小雨、晴天、阴天三个节点。如果是CART算法的话，会把属性值分为不同的组，{小雨}、{晴天、阴天}，{晴天}、{小雨、阴天}，{阴天}{晴天、小雨}，分别计算三组的基尼指数，然后选取基尼指数最小的值作为节点。

通过计算，我们发现{小雨}、{晴天、阴天}的划分方法，基尼指数最小，所以如果我们以天气属性作为划分，那么就选择{小雨}、{晴天、阴天}的分类

基尼指数的计算方法，由于没有使用对数，所以运算会比对数运算要快。

基尼值公式：

基尼指数公式：

数据集D，选择属性a划分后的基尼指数

比如数据集D，属性a的值把D分为D1、D2两个部分，那么在属性a的条件下，D的基尼指数表达式为：

三.减枝

1.预减枝

关于预剪枝（pre-pruning）的基本概念，下面就直接举个例子来看看预剪枝（pre-pruning）是怎样操作的。数据集为

可生成未减枝决策树

1.首先我们不按照任何属性划分训练集。训练集中正类和负类都是5例，那么可任选其中一类作为预测类别，假设我们选择正类，即所有测试数据均被预测为正类。那么此时验证集的预测正确率为=42.9%。

2.根据信息增益准则，我们选择“脐部”为根结点划分数据集。上图中结点2,3,4分别包含编号为{1,2,3,14}、{6,7,15,17}（正负类各一半，选正类）、{10,16}的训练样例，因此这3个结点分别被标记为“好瓜”、“好瓜”、“坏瓜”。此时，验证集的预测正确概率为=71.4%>42.9%，因此不需要剪枝，可以用属性“脐部”进行划分。

3.然后，决策树算法应该对结点2进行划分，基于信息增益准则将挑选出划分属性“色泽”。然而，在使用“色泽”划分后，验证集的准确率为57.1%<71.4%。因此，预剪枝策略将禁止结点2被划分。

4.同理，对结点3，最优划分属性为“根蒂”，划分后验证集准确率仍为71.4%。这个划分不能提升验证集精度，于是，预剪枝策略禁止结点3被划分。

对于结点4，其所含训练样例全部属于同一类，不再进行划分。

最终，预剪枝后生成如上图所示的仅有一层划分的决策树，亦称“决策树桩”(decision stump)。其验证集精度为71.4%。

预剪枝的优点：

1.降低了过拟合的风险。

2.减少了决策树的训练时间开销和测试时间开销。

预剪枝的缺点：

1.有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。因此预剪枝会有欠拟合的风险。

2.后剪枝

后剪枝先从训练集生成一棵完整决策树，该决策树的验证集精度为42.9%。

1.后剪枝首先考虑结点6，若将其领衔的分支剪除，则相当于把6替换为叶结点。替换后的叶结点包含编号为{7,15}的训练样本，于是，该叶结点的类别标记为“好瓜”，此时决策树的验证集精度提高至57.1%。于是，后剪枝策略决定剪枝。

2.然后考察结点5，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为{6,7,15}的训练样例，叶结点类别标记为“好瓜”，此时决策树验证集精度仍为57.1%。于是可以不进行剪枝。（⚠️此种情形下验证集精度虽无提高，但根据奥卡姆剃刀准则，剪枝后的模型更好，因此，实际的决策树算法在此种情形下通常要进行剪枝。）

3.同理，对于结点2，剪枝后验证集精度提升至71.4%。于是，执行剪枝。

4.结点3和结点1剪枝后均不能提升验证集精度，于是不执行剪枝。

后剪枝得到的决策树：

其验证集精度为71.4%。

后剪枝的优点：

1.欠拟合风险很小。

2.泛化性能往往优于预剪枝决策树。

后剪枝的缺点：

1.后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

参考链接：https://blog.csdn.net/u012328159/article/details/79285214

参考链接：https://zhuanlan.zhihu.com/p/89902999