当前课程知识点:机器学习概论 >  第二章 决策树学习(I) >  2.3 经典决策树算法ID3 >  经典决策树算法ID3(2)

返回《机器学习概论》慕课在线视频课程列表

经典决策树算法ID3(2)在线视频

下一节:经典决策树算法ID3(3)

返回《机器学习概论》慕课在线视频列表

经典决策树算法ID3(2)课程教案、知识点、字幕

熵是信息论里面特别基础的一个概念 什么是熵呢

在这个里面假设就是你一共有

在我们这个问题里面我们来去解释 假设你一共有N个类

每一个类呢你把它叫做j 那么熵是∑起来-P乘以log(P)

就是每一个 这个样本属于类的概率

乘以它以2为底的概率的log值 乘到一起

它的所有的加到一起因为是负的所以前面加一个-号

就是∑-P乘以log(P) 好那么有一个定义

如果概率为零 因为log(0)本来是没有值的

所以我们就定义一下log(0)就是0 就是0乘以log(0)等于0

那么在这个信息论里面呢

其实熵就是用来衡量我们信息的纯的程度的

所以其实在物理学上面也是这样

就是有熵最大什么原理或者熵减小的原理

熵变大的原理等等这样的

举一个例子 我们假设只有两类的话

我们在这里画这样的一个图出来 其实我们的entropy这个熵

就可以画出这样的一个图 横坐标是其中某一个类的概率

我们假设简化来说就两类 那么这样的话

比如说这个类它的probability是

其中一个类的probability是0.2的话 0.1的话

那么另外一个类的概率就是0.9 0.1乘以log(0.1)再减去0.9乘以log(0.9)

你就可以画出这样 它就是在这个值

所以这个是整个熵 你会发现均匀分布的时候熵最大

熵其实在这里描述的就是不确定性

如果放在我们的二分类问题里面

其实就相当于说我有10个样本5个是正例 5个是负例

其实这个就是最不确定的 就是来一个新的样本

我到底应该分在正例还是负例呢

因为你现在已有的观察到的是均匀分布的

所以我觉得是最不确定 所以它是一个描述信息的不确定性

那你如果是判断到了 我其中有九个都在正例 一个是负例

我什么都不做 我来了一个新的样例的时候

你会觉得它更有可能相对比较确定应该在正例上面

那如果所有的都是正例 没有负例的话 你如果观察没有偏的话

那它就基本上完全可以确定 那你的信息不确定性就是零

就是熵 熵就是零

好 所以这个就是我们可以用熵来描述信息的不确定性

当然到这里大家应该已经可以体会到

它为什么可以用来描述我们信息的纯度

就可以用熵的变化来去描述我们决策树到底怎么找

我当前的这个类是最好的那个类

举个例子 就是每一个节点有了呢 你就可以计算出当前在

就是当前状况还没有经过属性的时候

我的当前的Entropy就是29/64等等 计算出来这个熵0.993

熵非常大 经过它之后

那么经过它之后我们怎么判断接下来的熵怎么算呢

刚才看到我们已经计算好的这个开始的这个熵了

那接下来一步怎么做呢

我们其实怎么来判断基于除了熵之外我们还能计算什么

就其实信息的纯度和不纯度不是只有一个熵可以用的

我们跟大家介绍另外的两个指标 一个叫做Gini 就是基尼

其实大家应该听说过基尼系数这个词

是在判断一个国家的贫富差距是不是足够大的上面

有一个基尼系数 Gini impurity

这个Gini impurity呢实上也是一个非常常用的一个measure

它事实上衡量的是任何如果i和j是两个类

任何两类不同的话 对于你这些样例来说

P(Wi)乘以任何两类之间的两个

就是P(Wi)乘以P(Wj)的概率之积的求和

如果你看一下会发现 它其实相当于等于1减去其中P(Wj)的平方

所以Gini是一个特别简单的一个计算方式

从这个公式你就能够看出来 前面的这个熵

它不是一个有封顶的 而根据Gini的系数会看到

它会无限接近于1 当你的类的个数非常多的时候

你其实如果每一类的概率都非常小的话 类又非常多

其实你这个会非常接近1 但是它会有一个1的上限

所以它是一个有顶的 也因为这个原因和其他的很多那个原因呢

这个人 不知道大家有没有在人工智能课上听说过

这个人很著名 他是模式识别领域的一个非常著名的学者

也是我们在第一堂课给大家推荐的

参考书之一《模式分类》那本书的作者

他就很喜欢Gini 用Gini这样的impurity 不纯度

还有一个叫做misclassification impurity 就是错误分类的

基于这样的信息的不纯度的衡量

这时候你这个类的不纯度 其实就是你这个类的最大概率

就是你所有的样例 所有的j的不同的类里面

所有的P(Wj)里面最大的那一个 用1减去它

事实上就是可能会误分类的这样的情况

所以这个是误分类的错误率 基于错误分类的impurity

所以我们事实上 这三个都非常常用

给大家一点概念 这个是基于熵的impurity 横坐标是有多少个类

然后我们是双纵坐标 大家看这个图的时候一定注意一下

双纵坐标 左边这个纵坐标是最大熵 然后最大熵是红色的这条线

就红色的这条线看左边的这个坐标轴 然后这个蓝色的线是概率

概率看右边的这个坐标轴 然后所以你会看到如果它一类的话

这个熵它的概率就是1 如果只有一类的话概率就是1 熵就是0

因为是非常确定的

然后如果类别越多你的概率就是会这样下降的趋势

然后我们的Entropy是在逐渐的 在逐渐增加

这个并没有封顶我们只是画到了16 再继续画下去

你的熵还会再继续的增加下去 熵增这个是简单

那么Gini呢 Gini是什么呢 Gini我们的公式也写在这儿了

所以其实你会看到 如果这个是Gini的话

那么最大的Gini的不纯度impurity它会发生在1减去N

乘以N分之1的平方 为什么是这个 其实就是每一个

每一个都是均匀分布的 均匀分布的话

它每一类的概率就是N分之一

然后P的平方就是N分之一的平方 因为它是有个∑

一共有这个类 所以再乘以一个N 然后前面1减去它

其实简化一下就是1减去N分之1

所以1减N分之1它的最大的Gini不纯度事实上

我们可以看到 Gini 就是红色的这条线 所以它最大值等于1

所以它是一个这种曲线 它有封顶的一个值

然后我们的这个probability 这个probability注意一下

跟刚才的那个 我们不是1到16之间 所以它长的不完全一样

看上去好像更陡了但其实是因为我们横坐标画到了256

再往下呢 这个是misclassification 然后其实很容易可以证明

如果你有N个类的话 我证明的过程就不再跟大家口述了

大家你回去可以自己稍微算一下

可能用一分钟的时间就能够理解得出来 对于有N个类来说呢

我们最大的错误分类的就是误分类的impurity这个不纯度呢

也是等于1减去N分之一

而我们刚才已经算过说最大的Gini的Impurity

也是等于1减N分之一 所以它们俩是一样的

就考虑最大的Impurity的时候 分别在Gini还是在misclassification

这两个metric下 它们俩的取值是一样的

因此这个图的形状也是一样的

好 这个也是它们和Entropy之间的差别 我们刚才回过头来

刚才已经看到了 回到我们那个问题 什么是最好的

我们要选最好的那个节点是这样

那么什么是最好的呢

我们其实想知道的是说让信息的impurity的变化最大

就是信息的不纯度的变化最大 就原来很不纯现在变得很纯了

这个之间有一个变化有一个δ 我们希望这个δ最大

那么比如说当我们用熵来衡量的时候 那就是熵的变化最大

熵呢 我们一般每增加了一个节点 我们的熵都会减小

因为信息就会越来越确定 因此呢熵一直在减小 那么熵的

从原来的熵很大 现在到熵很小 它减到非常小

也就是熵的变化最大的时候

那么熵的变化我们是用Information Gain

就是你的信息不确定性减小了

也就说明你的信息获得了新的信息

这也是Information Gain这个名字的由来

什么是Information Gain呢

Information Gain在我们这个问题上面的定义就是

它其实都是一样的

我们只是在这里面给出来我们这个问题下的描述

就是我们当前S 就是这个数据集

就是我们当前的这个训练样本集

然后给了当前的训练样本集以及当前你想用的那个节点

想用的那个feature A 那个attribute A 那个经过你当前这个数据集

经过这个节点之后 它的信息的Information Gain

就等于在这节点之前它的熵 和经过了这个节点之后

每一个子节点的熵 乘以这个节点它的似然度

就是有多少样本分到了这个子节点 有多少样本在这个节点上

乘以它的这个Entropy 所以事实上前面的是原始的Entropy 熵

后面是我们期望的经过这个之后的期望的熵

机器学习概论课程列表:

第一章 绪论

-1.1 课程介绍

--课程介绍(1)

--课程介绍(2)

-1.2 机器学习的背景

--机器学习的背景

-1.3 什么是机器学习

--什么是机器学习

-1.4 机器学习系统设计

--机器学习系统设计(1)

--机器学习系统设计(2)

-第一章作业

-第一章课件

第二章 决策树学习(I)

-2.1 决策树的基本概念

--决策树的基本概念

-2.2 决策树的实例和发展历史

--决策树的实例和发展历史

-2.3 经典决策树算法ID3

--经典决策树算法ID3(1)

--经典决策树算法ID3(2)

--经典决策树算法ID3(3)

-2.4 过拟合和前剪枝

--过拟合和前剪枝

-第二章作业

-第二章课件

第三章 决策树学习(II)和贝叶斯学习

-3.1 下午茶时间:勒索软件

--下午茶时间:勒索软件

-3.2 后剪枝

--后剪枝

-3.3 决策树的改进和归纳学习假设

--决策树的改进和归纳学习假设

-3.4 贝叶斯学习的背景

--贝叶斯学习的背景

-3.5 极大似然假设、朴素贝叶斯和最小描述长度

--极大似然假设、朴素贝叶斯和最小描述长度

-第三章作业

-第三章课件

第四章 马尔可夫模型和隐马尔可夫模型

-4.1 下午茶时间:微博的垃圾检测

--下午茶时间:微博的垃圾检测

-4.2 马尔可夫模型

--马尔可夫模型

-4.3 隐马尔可夫模型

--隐马尔可夫模型

-4.4 评估问题

--评估问题(1)

--评估问题(2)

-4.5 解码问题

--解码问题

-4.6 隐马尔可夫模型的应用

--隐马尔可夫模型的应用

-第四章课件

-第四章作业

第五章 假设检验

-5.1 下午茶时间:图灵奖

--下午茶时间:图灵奖(1)

--下午茶时间:图灵奖(2)

-5.2 假设评估

--假设评估(1)

--假设评估(2)

--假设评估(3)

-5.3 置信度和置信区间

--置信度和置信区间(1)

--置信度和置信区间(2)

--置信度和置信区间(3)

-5.4 有限数据下的比较

--有限数据下的比较

-第五章课件

-第五章作业

第六章 基于实例的学习

-6.1 下午茶时间:黑洞照片

--下午茶时间:黑洞照片

-6.2 基于实例的学习的基本概念

--基于实例的学习的基本概念

-6.3 最近邻算法

--最近邻算法

-6.4 K邻近算法

--K近邻算法

-6.5 KD树

--KD树

-6.6 距离加权的K近邻算法

--距离加权的K近邻算法

-第六章课件

-第六章考试

第七章 支持向量机(I)

-7.1 支持向量机的背景

--支持向量机的背景

-7.2 线性支持向量机

--线性支持向量机(1)

--线性支持向量机(2)

--线性支持向量机(3)

--线性支持向量机(4)

--线性支持向量机(5)

-第七章课件

-第七章作业

第八章 支持向量机(II)和无监督学习

-8.1 核函数支持向量机

--核函数支持向量机:向量空间

--核函数支持向量机:核函数(1)

--核函数支持向量机:核函数(2)

-8.4 支持向量机总结

--支持向量机总结

-8.5 无监督学习简介

--无监督学习简介(1)

--无监督学习简介(2)

-8.6 层次聚类

--层次聚类

-8.7 K-means聚类和K-medoids聚类

--K-means聚类和K-medoids聚类

-第八章课件

-第八章作业

经典决策树算法ID3(2)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。