后剪枝在线视频

那上节课我们介绍的什么办法呢

其中第一种后剪枝的办法叫做错误率降低剪枝

思路特别简单我们回顾一下 就是我原来这棵树已经构建好了

那我一步一步的从任何一个子树开始做起

对比一下我现在所有的子树 看看剪掉了之后

再验证集上哪一个效果更好 剪了之后

我们决策树性能提升的最高 我们就把它剪掉

然后接下来再剩下的里面 再一步一步的去剪这些子树

直到做完了 就是直到你再继续做下去 就会带来性能的损失了

所以这样其实是我们上节课介绍的办法

当时我们还给大家留了一个讨论的问题 就是你剪了之后

本来它有两个分枝就意味这些数据它的标签是不一样的

它们原来有同样的输入 但是剪完之后 输出不一样了

那我们把它剪掉了 我应该给它什么样的输出

会有几种办法 这个当时我给大家留了一个小的尾巴

其实在我们的讲义上面我们给出来了 我们提到的一些思路

大家可以回去思考 如果还有其他想法的同学

也还可以继续跟我们沟通 那我们接下来就开始讲一种

新的后剪枝的办法 除了这种错误率降低剪枝

还有其他的什么可以剪的办法

有一种办法叫做基于规则的后剪枝 Rule Post-pruning

这个其实也是一个很自然的想法

其实我们已经知道一个决策树它可以对应成很多规则的集合

从上到下我们在决策树上 这节课一开始就说从根节点

到叶子节点它其实就是一条规则 与的关系

两个不同分支是或的关系 那你一棵决策树就可以写成

很多的规则 那么规则后剪枝做的事情就是第一步

我先把决策树把它拆分成很多的规则

比如说其实我们当时说我们要不要进行这个运动

比如说如果天气很晴朗 湿度很高 那我就不去打网球了

这是其中的一条规则 它可能是其中的一条分支

那我们做规则后剪枝 那我们应该怎么做呢

第一我们要把规则拆开 把规则的每一个前件都拆开

拆成比如说这一天的天气是晴朗 这是一个前件

还有一个前件如果这个湿度很高

当然你还可以其中是这两个与的关系 也可以是同一个前件

好 把它拆开之后 我们来对规则这个

我们对剩下拆完之后的这个规则来去

我们其中刚才说的剪枝的办法就是你可以剪掉任何其中的一部分

比如说剪掉预报的天气晴朗

或者剪掉我们湿度比较高的这样的部分 我们就把这些

把它剪掉 看一看剪掉之后 你还剩下了什么样的规则

每一条的规则在你的数据集上 在你的验证集上都会有一个精度

比如说如果天气晴朗 并且湿度很高 那么就不打网球

这个其中的假设 你一共有30个样例是符合这种情况的

但其中有20个样例是天气晴朗 但是湿度低

其中你可能还有另外有20个样例天气晴朗 但是湿度低

所以你去打了球 这个时候你如果把湿度很高的这个前件剪掉了

就会变成如果天气晴朗就不打网球了

这种情况下我们刚才说一共有30+20=50个样例

其中有30个是对的 另外20个是天气的确晴朗

但是我去打球了 并不是没打球 所以有20个做错了

因此单用这一条规则 就是保留下来的 如果天气晴朗就不打球

单用这一条规则也是在50个里面做对了30道

所以这个你是会有一个精度的 任何一个被剪掉

剩下的那个规则都会有一个这样的精度

那接下来我们下一步就会把这个规则按照他们的做估计的精度

来做一个排序 精度最高的放在最前面先去判断

然后它判断不了的 放到下面去经过后面的规则

用这个来排序 排完了之后 我们事实上就用我们最后得到的

这样的结果来去对我们的实例来去做

而且是有序的这样的规则对实例进行判断 来去分类

那么最后 事实上有一个有意思的事情 经过这种规则后剪枝

当然我们也仍然去看如果你剪了之后 如果你事实上性能变差了

就说明总的数据的性能变差了

就说明你这一条是不能够被剪掉的 如果你把这一条剪掉了之后

总的性能没有变差 那你其实就是可以保留的

所以剪掉了之后 如果总得的性能没有变差

那就说明这条应该被剪掉 如果剪掉了之后 性能变差了

那就说明这条应该保留下来 接下来有一个特别好玩的事情

一定要提醒大家注意 基于这样的办法 你剪完枝之后

你的这个决策树它可能原来是一棵决策树

现在它可能恢复不成一棵树了 因为它中间的一些枝被剪掉了

被剪断了 所以这是一个之前可能大家不一定注意到的事情

你有可能会把这个枝给剪掉了 最后弄完了之后 它是两个

一个是这个规则 一个是这样的两个规则

所以它可能恢复不成一棵原始的决策树了

这种办法规则后剪枝的办法 经常会用在

实际上它是特别常用的办法 它也被采用到了C4.5这个算法上

就是我们说C4.5是ID3算法的一个更进化的版本

那么这个时候我们其实就想带着大家一起讨论讨论

为什么我们要把决策树先把它变成规则

然后再剪枝或者说对比这种规则后剪枝的方法

和之前剪掉这些子节点 就是叶子节点的办法相比

它有什么好处 就是在这种剪的办法里面

根节点和叶子节点是一样的 就存在了我们刚才举的这个例子的可能

如果你用之前的错误率降低剪枝

你一定先剪掉的是那些叶子节点 然后再一步一步的往上面剪

但是在规则后剪枝你不受这个限制

你其实是有可能会根节点和叶子节点是一样的

上面的祖父节点和后面的子孙节点是一样的

所以其实这个时候你就有可能有更灵活的剪枝的策略

所以在原来的书里面 你要么在错误率降低剪枝的办法里面

你要么整个子节点都剪掉了 要么就是把它整个都保留

但是在规则后剪枝里面 你可能会保留这个子节点的一部分

还有刚才有同学提到过根节点和叶子节点它是没有什么限制的

另外它的可读性也还是挺强的 因为我们其实把它

最后都是一个规则 人对规则的可解释性还是比较强的

因此我们在讨论完这些内容之后

基本上决策树学习的一些核心的问题我们都讨论了

我们其实回顾一下都讨论了哪些东西

首先我们介绍了决策树学习的基本的概念

然后其次我们以ID3算法 一个非常基本的算法为例

来介绍了算法是怎么设计的 其中有两个核心的问题

就是我怎么选择当前要做的 接下来应该选择哪个节点去构建

第二应该什么时候停止 这个大家可以根据我们的思路

来一起跟上我们的思路来想

另外我们还讨论了一下在这个里面你可能应该

决策树适合什么样的特征 然后以及ID3算法

我们上次说也是有一定的偏置的 这个偏置是我们本身

你的整个假设空间的表达能力是完备的

所以并没有这个空间的限制

但是我们在搜索找到那一棵树的过程 这个搜索过程是有偏置的

所以我们最后找到的应该不一定是 很有可能不是全局最优

我们有可能只是一个局部最优 因为我们并没有做回溯

那么我们接下来要讨论一个特别重要的观念的问题概念

叫做Overfitting过拟合 再次强调过拟合问题是

你做任何机器学习的系统设计和机器学习系统

都可能会遇到的问题 都需要考虑的问题

只是在决策树学习里面它表现的非常的明显

使得我们一定要在算法里面本身就涉及到这样的过拟合的

解决过拟合的问题 那我们想到的办法就是剪枝

我们刚才已经带大家回顾了后剪枝和前剪枝的几种不同的思路

一般来说在真实的环境下前剪枝会比较快 所以它比较高效

但是后剪枝通常你得到的效果会更好一点

因为毕竟你利用了更多的数据 然后再回退回去看怎么做比较好

那么决策树学习有什么好处呢

最大的好处是它跟我们人做决策的思路其实特别像

你其实别人问你一个问题

比如说你妈妈问你今年暑假要不要回家

你可能说如果我们有什么事 并且我没有什么事我可能会回家

或者说因为有什么事所以我不回家了

其实这就是一个人决策的很自然的过程 非常简单

非常容易理解 然后对噪声数据有一定的鲁棒性

是因为我们在每一步里面 尽量用了多个数据一起来做统计分析

并不是一个数据产生一个结果点 它实际使用的非常多

在我们的 比如说医疗诊断 还有什么信用卡的风险分析等等

还有智能的调度 总之其实在很多很多情况下

决策树它会被当成一个基准的对比方法 在很多很多问题里面

如果你没有更好的办法 你可能差不多就会实现一个决策树

来看看 基础的就是这样 我应该至少能够做到这么好

然后看看有没有可能再有其他算法的提升

但并不是说这个问题已经完全讨论完了 我们再来讨论一点点

它的更进一步的话题 第一个就是实际情况上

我们之前会说我们决策树比较适合于使用离散的这个数值

因为它会有分支 左分支 右分支 或者一个节点下面

有N个分支 那是因为你会有N个取值

当你是连续值的时候怎么办 你不可能说我有无限多个分支

那离散的数据点怎么办呢 比如说温度

在不同温度下面你测量到 观测到不同温度下 我会有一些决策

你并不能够让每一个温度给它一个分支 有什么办法呢

其中一个非常简单的思路就是我把它区间化

就是把连续数据的区间化 把它离散化

是一个特别特别常用的做法

那最简单的区间化就是你按照平均来分区间

比如说你想让它有五个分支 那这个五就会变成你系统里的

参数了 你想让它有五个分支 你就可以从它的取值范围

值域范围分成五段 那么属于每五段的 就属于其中的一个分支

这是一种做法 但是当然这样你就完全没有考虑到

它的训练数据的状态和它的lable

因此实际上人们在这个里面常用的一种办法之一

我们并不是说它是唯一有效的办法

比如说我们现在就取得了第二种办法

但这个办法有一个是说我去找在相邻的两个数据点

它们的决策发生了变化的点 比如说这里的48度和60度

之前是No 现在是Yes 把这两个发生变化点之间去平均

砍一刀这个是你一个区间的分割

下一个变化的时候80度和90度之间 决策发生了变化

你就取85砍一刀 用这样的变化来做区间化

是一种比较有效的做法

事实上Fayyad他是在决策树比较有贡献的

一个研究者 他在1991年的时候曾经发表过论文

做了一些证明 说这样的划分的方法事实上

是比较符合信息增益最大的方式的

所以一般就会成为一种比较通用的办法

如果你不是基于你的问题有更具体的先验知识的话

那你就不妨可以采用这样的办法来做

第二个就是如果我们的属性有非常多的取值怎么办

其实我们会想到我们使用的 用的是信息增益

它其实天然的会对 如果你有很多的分支

很多种不同取值的话 那天然会倾向于对这样是有偏置的

比如说我到底要不要做这个体育运动

我们可以当天的天气情况 但你也可以可能取一个值

是说这一值是日期 就是3月14号去了 3月15号没去

3月13号没去等等 你如果把一年的每一天都作为一个日期的话

你会有365个分支 然后在这种情况下

你会发现你计算信息增益 这一个是最确定的

所以事实上如果有一个分支 但这是比较极端的例子

一般来说分支越多 它的信息增益就会相对的变化会比较大

所以会被优先选到