当前课程知识点:机器学习概论 > 第二章 决策树学习(I) > 2.3 经典决策树算法ID3 > 经典决策树算法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 机器学习系统设计
-第一章作业
-2.1 决策树的基本概念
--决策树的基本概念
-2.2 决策树的实例和发展历史
-2.3 经典决策树算法ID3
-2.4 过拟合和前剪枝
--过拟合和前剪枝
-第二章作业
-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 下午茶时间:图灵奖
-5.2 假设评估
--假设评估(1)
--假设评估(2)
--假设评估(3)
-5.3 置信度和置信区间
-5.4 有限数据下的比较
--有限数据下的比较
-第五章作业
-6.1 下午茶时间:黑洞照片
-6.2 基于实例的学习的基本概念
-6.3 最近邻算法
--最近邻算法
-6.4 K邻近算法
--K近邻算法
-6.5 KD树
--KD树
-6.6 距离加权的K近邻算法
-第六章考试
-7.1 支持向量机的背景
--支持向量机的背景
-7.2 线性支持向量机
-第七章作业
-8.1 核函数支持向量机
-8.4 支持向量机总结
--支持向量机总结
-8.5 无监督学习简介
-8.6 层次聚类
--层次聚类
-8.7 K-means聚类和K-medoids聚类
-第八章作业


