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

栏目: 编程工具 · 发布时间: 5年前

内容简介:1.11.2

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

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

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

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

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

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

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

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:缺失值处理

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


以上所述就是小编给大家介绍的《[机器学习]ID3决策树 详细计算流程 周志华机器学习 笔记 原创Excel手算方法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Swift编程权威指南(第2版)

Swift编程权威指南(第2版)

[美] Matthew Mathias、[美] John Gallagher / 陈晓亮 / 人民邮电出版社 / 2017-6 / 89.00元

Big Nerd Ranch是美国一家专业的移动开发技术培训机构,本书是其培训教材。书中系统讲解了在iOS和macOS平台上,使用苹果的Swift语言开发iPhone、iPad和Mac应用的基本概念和编程技巧。主要围绕使用Swift语言进行iOS和macOS开发,结合大量代码示例,教会读者利用高级iOS和macOS特性开发真实的应用。一起来看看 《Swift编程权威指南(第2版)》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

SHA 加密
SHA 加密

SHA 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具