决策树

一、ID3

1. 算法结构

ID3的思想便是：

1、自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础)；

2、从“哪一个属性将在树的根节点被测试”开始；

3、使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益，or 信息增益率)。

4、然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。

5、重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。

信息增益：

二、C4.5

三、决策树剪枝

根据周志华老师《机器学习》一书中所描述是先对数据集划分成训练集和验证集，训练集用来决定树生成过程中每个结点划分所选择的属性；验证集在预剪枝中用于决定该结点是否有必要依据该属性进行展开，在后剪枝中用于判断该结点是否需要进行剪枝。

3.1 决策树的损失函数

决策树的生成，ID3、C4.5、Cart其实都是启发式算法，每一步都是在提升树的规模的时候找打当前步能使分类结果提升更明显的选择，这个选择的标准三个算法各不相同。所以三个算法仅仅只是最优化了损失函数中的经验误差，并没有考虑结构误差，也就是树的复杂度，所以需要对树进行剪枝。

3.2 预剪枝

核心思想就是，在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。

3.3 后剪枝

对于后剪枝，周志华老师《机器学习》中述说如下：

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

对于后剪枝，书中采用了具体的西瓜分类决策树作为剪枝操作讲解，跟着流程走下来感觉挺顺畅，无非就是对想要进行剪枝的结点进行验证集数据的准确性比较，如果剪枝能带来准确性的提高，那么就剪枝，否则保留。然后去判断其它需要考虑剪枝的结点。

在进行剪枝判断的操作中，只对底端结点进行判断。一步一步收缩至每一个底端结点对验证集数据都有更好的分类准确率为止。

剪枝的目的不是为了最小化损失函数，剪枝的目的是为了达到一个更好的泛化能力。而对于决策树来说，叶结点的数量越多，反应了决策树对训练数据的细节反应的越多，继而弱化了泛化能力。要想提高泛化能力就需要进行剪枝，而在 3.1 节中给出的损失函数中，α \alphaα 值衡量了损失函数中叶结点数量的权重，α \alphaα 值越大，在最小化损失函数时，需要更多的考虑叶结点数量的影响。α 可以看作一个系数，不同的 α 对应于不同的损失函数。而对于所有的这些损失函数来说，在训练集上进行决策树生成时候的步骤都一样，差别只是在判断某些结点是否进行展开的区别。

为什么要选择最小的α？
如果说没对一棵树剪枝前，其损失函数是 ，那么对其剪枝之后其损失函数就是，明显有，因为剪枝后的损失函数肯定更大，但是损失函数增加的最少的是不是就是最好的结果呢，其实增加的的部分就是剪去这个叶子节点带来的，那么带来的损失是多少呢，就可以用 来衡量。所以就是选取最小的节点。

三、 questions

• C4.5怎么去解决选择取值较少的特征的缺点？

我们从上面求解信息增益的公式中，其实可以看出，信息增益准则其实是对可取值数目较多的属性有所偏好！
现在假如我们把数据集中的“编号”也作为一个候选划分属性。我们可以算出“编号”的信息增益是0.998
因为每一个样本的编号都是不同的（由于编号独特唯一，条件熵为0了，每一个结点中只有一类，纯度非常高啊），也就是说，来了一个预测样本，你只要告诉我编号，其它特征就没 有用了，这样生成的决策树显然不具有泛化能力。
于是我们就引入了信息增益率来选择最优划分属性！

有了这个分母之后，我们可以看到增益率准则其实对可取类别数目较少的特征有所偏好！毕竟分母越小，整体越大。
于是C4.5算法不直接选择增益率最大的候选划分属性，候选划分属性中找出信息增益高于平均水平的属性（这样保证了大部分好的的特征），再从中选择增益率最高的（又保证了不会出现编号特征这种极端的情况）希望对大家有帮助~

• ID3、C4.5 关于预剪枝和后剪枝
• 决策树减少过拟合的办法
• 为什么后剪枝要选择一个最小α
• 决策树如何处理离散值

解决两个问题：
<1> 计算信息增益(或信息增益比或基尼系数等指标)时，遇到缺失值，如何处理？
<2> 每一次求出信息增益(或信息增益比或基尼系数等指标)后，找到最佳分割点后，求最佳分割点时遇到的缺失值如何处理？

• 样本中有缺失值的时候，，选取最优划分属性计算增益或者基尼指数的时候，对于原来的公式

使用下面的公式代替

注意：上式计算时就是使用了在属性a上无缺失值的样本集代替全样本集。然后需要乘以这个样本所具有的权重，因为这个样本可能在上一次分割的时候呗修改了权重。计算的信息增益需要乘以一个缺失系数。

• 对缺失值样本的划分，当选择了最优的划分属性之后，缺失值样本的划分就是，将这个样本划分到每一个叶子结点，但是毕竟这个样本存在有缺失的属性，那么肯定权值要比正常样本要低，所以将缺失值样本按不一样的几率划分到了全部分支中，而几率则等于正常值样本在每一个分支中所占的比例。也就是假如一个样本在某个属性上是缺失的，那么倾向于对这个属性赋值于比例最大的属性值（在样本较多的分支中获得较大的权重）

  四、参考文献

  https://blog.csdn.net/am290333566/article/details/81187562