• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

机器学习导论(11)-决策树剪枝处理

ml admin 3年前 (2016-11-20) 3025次浏览 0个评论 扫描二维码

在上一篇文章讲到了决策树的基本概念和决策树属性划分方法,传送门决策树基本概念

考虑到决策树容易产生过拟合的情况,也就是说当前的决策树有很多的节点,整个决策树很大,此时会把样本中一些并不需要拿来作为

分类的属性学习到,因此学习的决策树模型并不是最优的模型,这就是机器学习中的过拟合现象,与此相关的概念就是欠拟合,欠拟合主要是因为当前的样本不够,导致实际在学习的时候可以用来学习的信息很少,因此也会出现学习不好的现象,好吧,打住开始重点了


决策树剪枝有两种方法:预剪枝和后剪枝

二者的区别在于预剪枝在参与决策树的构造,后剪枝是在构造完决策树之后在自底向上进行剪枝,下面以周志华–机器学习中的西瓜数据来说明预剪枝和后剪枝算法的操作过程,先给出相应的西瓜数据

new-image-rto9y

 

预剪枝

基于 ID3 信息增益方法划分属性的方式构造决策树,首先对上述的数据集使用脐部属性划分,会有三个分支,稍凹、凹陷和平坦,那么现在有一个问题是否需要这样进行划分呢?预剪枝会对当前进行划分前后进行相应的性能评估

new-image-0sp84

从上图可以看出对脐部进行划分之后识别的准确为 71%,大于不划分的情况 41%,因此需要保存相应的分支。

计算的过程如下:

首先未划分之前,使用脐部特征去验证测试样本集,只有 4、5、8 被正确的分类,分类正确率为 3/7=41%

ps:脐部特征不划分就是说不需要考虑测试样本的脐部属性,所有的西瓜都被认定为好瓜,因此只有三个瓜被正确的分类,其余都被错误的分离

划分之后训练样本根据脐部属性分为三个子训练集(1、2、3、14)和(6,7,15,17)和(10,16),分别标记为好瓜、好瓜和坏瓜,此时测试样本集中 4、5、8、11、12 均被正确的分类,因此计算得到的准确率为 5/7=71%

同理后续其他属性是否需要相应的预剪枝则根据当前描述的方法一个一个判定。

预剪枝会避免决策树的过拟合现象,由于避免了不必要的节点展开,一定程度上减少决策树训练的时间和测试的时间,但是也存在欠拟合的风险。

后剪枝

后剪枝是在决策树已经生成之后再去自底向上进行相应的剪枝判定。

在上一幅图中给出了初步训练得到的决策树,现在我们根据当前的决策树进行相应的剪枝处理

首先将节点 6 的分支全部剪掉,则当前节点包含的样本只有 7 和 15,不考虑纹理此时二者都是好瓜

剪之前测试集中只有 4、11、12 被准确的识别,相应的准确率为 41%

剪枝后测试集中 4、9、11、12 被准确识别,相应的准确率为 57%

从上述结果可以看出此时需要剪枝,节点 6 剪枝处理,其他节点也是这样

剪枝后决策树如下

new-image-0s0el

预剪枝后剪枝对比

对比后剪枝可以发现,后剪枝可以保留了更多的分支,相比于预剪枝欠拟合风险更小,但是后剪枝是根据已经训练好的决策树自底向上逐层扫面判定,因此会导致训练的时间和开销比预剪枝较大。


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明机器学习导论(11)-决策树剪枝处理
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!