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
计算属性下单个分类的信息熵
色泽根蒂敲声纹理肚脐触感
青绿蜷缩沉闷清晰凹陷硬滑
乌黑稍蜷浊响稍糊稍凹软粘
浅白硬挺清脆模糊平坦
10.9544340030.9709505940.7642045070.8631205691
0.9182958340.9852281360.9709505940.72192809510.970950594
0.7219280950000

 

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

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

 

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

 

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

 

表6
计算条件熵
色泽根蒂敲声纹理肚脐触感
0.8893773810.8548275870.8567211130.6169106490.7083437640.991456057

 

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

 

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

 

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

 

表7
计算信息增益
色泽根蒂敲声纹理肚脐触感
0.1086226190.1431724130.1412788870.3810893510.2896562360.006543943

 

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

 

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

 

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

 

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

 

4.笔记2:剪枝处理

 

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

 

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

 

5.笔记3:连续值处理

 

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

 

6.笔记4:缺失值处理

 

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

Be First to Comment

发表回复

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