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

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

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

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

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

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

好 说了这么多的背景知识

事实上我们已经了解了机器学习的基本概念

以及决策树学习它是用来解决什么问题的 就我们说的task的这个部分

接下来我们看一看算法 基本上决策树的算法呢

比较经典的就是我们刚才说的CART CART它是一个简称

是classification and regression trees C是classification A是and

就是用于做分类或者是回归的数 然后它的general的framework

其实就是四步 第一步就是我先用我的训练数据先构造出一棵树来

初始化的构造出一棵树 然后呢我们接下来会去看

关于当前的这个Decision tree 就是这个决策树

我们事实上每次它要做的事情就是

基于我们的训练数据来一步一步的往下分裂

所以通常决策树是从 决策树都是从上往下构建的

最初都是一个节点 从最初的那个节点我选择出来之后

根据训练样例的状态 我把它分裂成了两个或者多个分支

然后就是你选了一个feature之后 它就变成了两个或多个分支

据你的可能的那个特征可能的取值

然后每一个分支再继续往下分裂下去

然后第三步就是什么时候停止分裂呢 如果你这个节点已经纯了

如果数据已经纯了就停止分裂了

当然还有一个补充就是 或者它 你还没完全分好

但是你已经可接受了 也可以停止了 就是达到了停止条件就行

这就是一个简单的一个framework

所以跟大家在计算机领域的学的数据结构里面的树的构造

基本上是一脉相承的 它们都是利用到了树的构造

所以非常多的决策树的算法都是基于这样的一个CART的框架的

那我们先从经典的ID3算法给大家介绍起 你可以看到

它是一个自顶向下的 这样的贪心搜索的方法

但是还有一个有趣的是它是一个递归的算法 递归的算法是什么

因为大家如果是 你们应该绝大多数同学都已经学过数据结构了

然后在构造树的时候我们往往会用到递归

就是当前的节点然后分裂 分裂完了之后呢

以分裂完的其中某一个又当成当前节点我们再继续分裂

然后一直到结束了 再一步一步的传递回去

所以你的这个完整的 这样的一个circle是这样的

就是其中一个流程是这样的

我呢去找到下一步要去用到的最好的那一个属性

那一个决策属性 我接下来要去 在这个基础上去做分裂的

那一个属性就是我们把它叫做当前最好 下一个最好的

然后呢 那么比如说我如果发现下一个最好的是outlook

那么我们就把这个属性当作当前的这个节点了

这个决策树的节点 然后我们基于这个属性 你就会有不同的取值

它就会走到不同的分支上 然后到了这个分支之后呢

我们每一个分支呢 你就可以构建出每一个分支

它自己的子孙的节点 然后如果你把你的训练样例都分配到

按照它们的取值 分配到相关的分支上 如果已经分好了

那你其实就可以perfect classified 你可以停止了

比如说在这个里面所有的都是yes了

那你就可以把它停止了

在分支上它就perfect了 很完美的分好了

如果没有呢 你这样就可以return了

没有的话呢 你其中的每一个的子孙节点 每一个子节点

你就又成为当前的这个最佳的节点 然后再继续往下走下去

比如说选择当前最好的节点 然后根据取值分到不同的

有不同的分支 如果在这个上面训练样例

已经有了最好的 完美的表现了

已经全都是一致分好了 那可以停止就可以停止了 然后如果没有呢

那就继续再做下去 所以这个就是一个ID3算法的最基本的工作 就做完了

所以基本上大家会觉得你这个

非常好的问题 其实这个问题也是我想问你们的

你刚好引出了我下面想说的 如果它没有perfect分类

其中有一种情况是说 刚才这位同学提到说它的所有属性取值都一样

但是它的label不一样 有的是yes 有的是no

我想问问大家你觉得这个时候是怎么回事

有可能是因为什么原因出现了什么

样本噪声 非常好 就肯定其中有错的

所以这个时候一般你比如说少量的样本你就把它当作噪声忽略

就取那个绝大多数都follow的那个 还有没有别的可能

对 其实说的 同学们知道掌握了这个意思了

它其实是你的属性没有抽全 你的特征不全

就其实它可能在这个问题上

非常有可能还有一个feature或者多个 是能够代表它们的区别的

但是你没抽出来 所以在你能观察到这些上面它是一样的

但输出不一样 这个时候啊你就可以特别开心

这就意味着你这个问题有可能找到新的解决思路了

就有可能在研究里面就意味着你可能能有新的发现了

就你的novelty的部分就出来了

所以呢这个时候一定要把这些数据拿出来好好看一看

然后去研究一下说还有什么地方它们是不一样的

就是一定要回退到原始数据上

而不是被你抽够特征的数据 回退到原始数据上看

还有什么因素我没考虑进来

好 所以这个是一个刚才有同学问特别好的问题

然后大家就已经回答过来了 好 那么这样看起来我们的这个ID3树

就是我们的决策数已经讲完了好像 而且算法也好简单

你看 如果你看这基本上已经快要是算法的伪码了

一行 每一行就是你是一个函数 然后你把这个函数 你把它写全了

这个算法就出来了 非常简单 对不对

但如果你真的写的时候 如果让你去实现的时候

你就会有一些问题 第一个问题是

你会发现他和你的算法实现还差很远

第一就是你的Best Decision 什么是最好的呀 我们不知道

我虽然说了一下 原则是说要把最好的选成当前

哪个是最好的呢 这是第一个问题 你不知道你就没办法写这个程序

第二个 什么是perfect classified 这个大家刚才有一点点体会了

比如说我们说它标签全都一致了就perfect了

或者如果有冲突了我们把冲突解决一下 还有没有其他的情况

什么是perfect了一样了 就分好了呢

所以我们需要再深入的去看一看 那么什么是

哪一个属性是最好的呢 比如说我们现在有个属性A A1就是在目前

我们其实是有29个正例和35个负例 然后在A1这个属性下

我们会分成true或false的时候 我们会发现左边这是21个正例5个反例

右边这个是8个正例 30个反例

而另外的属性分别是18正33负 和11正2负 哪个更好

简单看起来觉得还有点不太好判断对吗

我先跟大家介绍一下说基本的原则 就是越简单越好

什么叫越简单越好呢

就是我们希望这个决策树它最终是一个很简单的 比较压缩的

然后节点数比较少的树 比如说这两个例子这两棵树

它们都可以区分西瓜和柠檬 左边这棵树说看一看颜色 绿色的是西瓜

黄色的是柠檬 好 就两层

一个非叶子节点 两个节点 就判断一步就OK了

另外一个说先看大小 如果是大的就是西瓜但是如果大小小的话

我们再看颜色 颜色绿的是西瓜 然后颜色黄的是柠檬

最终也能分的出来 但是它需要三层 而且做更多一次判断

这样情况我们当然会觉得短一点的数更好 越简单的越好

越压缩的节点数少的就更好一些 所以这个想起来

其实我们在机器学习里面有一些原理

其中有一个原理叫做 就是奥卡姆的剃刀原理 有人呢

那个原理其实说白了最简单就是一句话就是越简单的越好

最简单的就是最好的 这是一个原则

有人说为什么起 为什么叫奥卡姆的剃刀原理 有两个说法

一个说法比较八卦说是奥卡姆这个人在早晨起床之后

对着镜子刮胡子的时候想到的 所以就把这个原理叫做奥卡姆剃刀

其实它是一个 首先它是一个哲学上面的一个理论或一个论点一个观点

事实上我们很多人把它用在了机器学习的原理上

另外一种说法是 因为它会感觉 当然是奥卡姆这个人提出来的

但是它为什么叫剃刀呢 就说你就好像是用剃刀一样

你去切除那些捡出那些不重要的东西

剩下的最简单的可能就是最核心的东西

所以为什么我们说它也是一个哲学呢

就是可能有的时候当你的生活变得特别不可控制的时候

你会发现回归简单一些的生活 可能有的问题迎刃而解

这是它的这个一系列的 就它在很多领域会有应用

在我们的决策树学习上面其实也有这样的

它只是是这样一个想法 一个原理 那么到底什么样的

是能够做到简单呢 其实也很难说 什么样的比较简单呢

其中比较多经常接受的是说 我们用纯度来去描述

就是我们如果在这个节点之后 经过了这个节点之后信息变得更纯粹了

每一个节点的信息变得更纯粹了 那么我们当前这个就是很好的

那么什么是更纯粹的呢

就是尽可能经过我们这个节点之后把它分的更纯粹了

那当然它也就和不纯的 就是impurity相结合

这个时候我们就会提出一个很有趣的东西

就是到底怎么样去衡量impurity

而我们会提到一个概念叫做熵

机器学习概论课程列表:

第一章 绪论

-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(1)笔记与讨论

也许你还感兴趣的课程:

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