[机器学习]ID3决策树 详细计算流程 周志华机器学习 笔记 原创Excel手算方法

1.用到的主要三条熵公式：

1.1 信息熵 详情见香农信息论 概率越平衡 事件所含有的信息量越大

1.2 条件熵 代表某一属性下不同分类的信息熵之和

1.3 信息增益 等于信息熵减去条件熵，从数值上，越大的信息增益在信息熵一定的情况下，代表条件熵越小，条件熵越小，即该分类下的不平衡性越大

2.西瓜数据集2.0的详细手算结点划分 原创的Excel方法

zhonglihao 即本人原创的这个excel计算方法适合初学者理解计算过程，不会迷糊

西瓜数据集2.0 （版权来自 周志华教授-《机器学习》）

step 1首先，统计每个属性下的分类计数，计算完可验证一下是否加起来的和等于17：

step 2 然后，在分类下统计该分类的正例(是好瓜)和反例(不是好瓜)的计数，通过加起来确定是否等于属性分类的计数：

这样我们就可以去计算条件熵了

step 3 通过上表先计算每一个属性分类的信息熵（公式1），若信息熵中有正例或反例为0，则整个信息熵公式的计算值为0，可以对比一下上表和下表的值：

step 4 根据条件熵公式 计算每个属性分类在该属性中的比例 如青绿分类所示为6个青绿分类除以17个样本，其余的计算雷同：

step 5 将表5和表4的分类属性进行乘加运算即可得到 属性下的条件熵：

例如 条件熵（ 色泽 ） = 1 *  0.352941176 + 0.918295834 * 0.352941176 + 0.721928095 * 0.294117647 = 0.889

step 6 回到西瓜数据表1，我们可以知道整个表的正反例的信息熵是

Ent = -（(8/17)*log2(8/17) + (8/17)*log2(8/17)）= 0.998

step 7利用全局信息熵减去表6中每一个属性的条件熵得到 该属性的信息增益：

如表7所示，可以得到每个属性的信息增益了，信息增益最大的属性将被用于作为这一层的结点，所以我们选择 纹理！纹理！纹理！重要的事情说三十遍 作为第一个结点，其余结点的计算雷同，把纹理属性去掉后，依照上述流程再做就可以了，不啰嗦。

观察数值可知此Excel计算得出的数值与周志华机器学习中的数值一致，整个计算过程也比较容易理解，不容易出错。

3.笔记1：为什么ID3要选择信息增益这个指标呢？

zhonglihao的定性回答：从第一层结点最终选择属性纹理可知，纹理属性中 的三个分类 的正反例基本都是最不平衡的，意味着选择纹理作为结点能够尽可能减少往后结点的判断数，减少分支和深度，使得整颗决策树的分类效率达到最大，大概是这么一回事，也是信息增益计算的初衷吧。

4.笔记2：剪枝处理

*剪枝处理有助于提升决策树的泛化能力

在未剪枝前先计算 验证集的分类准确率 a，然后对某一结点进行裁剪，并把该结点固定为一个分类，观察剪枝后 验证集的准确率是否有上升，若变好则确定裁剪，若变差，则保留该结点。

5.笔记3：连续值处理

对连续值进行 排序 后，于某一点割裂两边，并计算二分后的信息增益，取信息增益最大的分割点作为不等式判决值。

6.笔记4：缺失值处理

强制计算存在的分类属性信息增益，最后把信息增益乘以 存在的属性数/总样本 比例，加入了权重值。