Press "Enter" to skip to content

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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

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

 

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

 

 

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

 

 

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

 

 

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

 

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

 

西瓜数据集2.0 (版权来自 周志华教授-《》)

表1
编号 色泽 根蒂 敲声 肚脐 触感 好瓜
1 蜷缩 浊响 清晰 凹陷 硬滑
2 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑
3 乌黑 蜷缩 浊响 清晰 凹陷 硬滑
4 青绿 蜷缩 沉闷 清晰 凹陷 硬滑
5 浅白 蜷缩 浊响 清晰 凹陷 硬滑
6 青绿 稍蜷 浊响 清晰 稍凹 软粘
7 乌黑 稍蜷 浊响 稍糊 稍凹 软粘
8 乌黑 稍蜷 浊响 清晰 稍凹 硬滑
9 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑
10 青绿 硬挺 清脆 清晰 平坦 软粘
11 浅白 硬挺 清脆 模糊 平坦 硬滑
12 浅白 蜷缩 浊响 模糊 平坦 软粘
13 青绿 稍蜷 浊响 稍糊 凹陷 硬滑
14 浅白 稍蜷 沉闷 稍糊 凹陷 硬滑
15 乌黑 稍蜷 浊响 清晰 稍凹 软粘
16 浅白 蜷缩 浊响 模糊 平坦 硬滑
17 青绿 蜷缩 沉闷 稍糊 稍凹 硬滑

 

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

 

表2
属性计数表
色泽 根蒂 敲声 纹理 肚脐 触感
青绿 = 6 蜷缩 = 8 沉闷 = 5 清晰 = 9 凹陷 = 7 硬滑 = 12
乌黑 = 6 稍蜷 = 7 浊响 = 10 稍糊 = 5 稍凹 = 6 软粘 = 5
浅白 = 5 硬挺 = 2 清脆 = 2 模糊 = 3 平坦 = 4

 

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

 

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

表3
属性子分类标签计数(是否好瓜 是:否)
色泽 根蒂 敲声 纹理 肚脐 触感
青绿

6 = 3:3

蜷缩

8 = 5:3

沉闷

5 = 2:3

清晰

9 = 7:2

凹陷

7 = 5:2

硬滑

12 = 6:6

乌黑

6 = 4:2

稍蜷

7 = 3:4

浊响

10 = 6:4

稍糊

5 = 1:4

稍凹

6 = 3:3

软粘

5 = 2:3

浅白

5 = 1:4

硬挺

2 = 0:2

清脆

2 = 0:2

模糊

3 = 0:3

平坦

4 = 0:4

 

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

表4
计算属性下单个分类的信息熵
色泽 根蒂 敲声 纹理 肚脐 触感
青绿 蜷缩 沉闷 清晰 凹陷 硬滑
乌黑 稍蜷 浊响 稍糊 稍凹 软粘
浅白 硬挺 清脆 模糊 平坦
1 0.954434003 0.970950594 0.764204507 0.863120569 1
0.918295834 0.985228136 0.970950594 0.721928095 1 0.970950594
0.721928095 0 0 0 0

 

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

表5
计算属性下分类除以所有样本的比例
色泽 根蒂 敲声 纹理 肚脐 触感
青绿 蜷缩 沉闷 清晰 凹陷 硬滑
乌黑 稍蜷 浊响 稍糊 稍凹 软粘
浅白 硬挺 清脆 模糊 平坦
6/17 = 0.352941176 0.470588235 0.294117647 0.529411765 0.411764706 0.705882353
0.352941176 0.411764706 0.588235294 0.294117647 0.352941176 0.294117647
0.294117647 0.117647059 0.117647059 0.176470588 0.235294118

 

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

 

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

 

表6
计算条件熵
色泽 根蒂 敲声 纹理 肚脐 触感
0.889377381 0.854827587 0.856721113 0.616910649 0.708343764 0.991456057

 

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

 

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

 

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

 

表7
计算信息增益
色泽 根蒂 敲声 纹理 肚脐 触感
0.108622619 0.143172413 0.141278887 0.381089351 0.289656236 0.006543943

 

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

 

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

 

3.笔记1:为什幺ID3要选择信息增益这个指标呢?

 

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

 

4.笔记2:剪枝处理

 

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

 

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

 

5.笔记3:连续值处理

 

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

 

6.笔记4:缺失值处理

 

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

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注