决策树_(预剪枝和后剪枝)_以判断西瓜好坏为例_youhahhhh的博客-程序员宅基地_西瓜数据集决策树

技术标签: 算法  剪枝  决策树  

剪枝的目的:

剪枝的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本,不停地对结点进行划分,因此这会导致整棵树的分支过多,也就导致了过拟合。决策树的剪枝策略最基本的有两种:预剪枝(pre-pruning)和后剪枝(post-pruning):

  • 预剪枝(pre-pruning):预剪枝就是在构造决策树的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来决策树模型泛化性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。
  • 后剪枝(post-pruning):后剪枝就是先把整颗决策树构造完毕,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛化性能的提升,则把该子树替换为叶结点。

一、数据集:

在这里插入图片描述

其中{1,2,3,6,7,10,14,15,16,17}为测试集,{4,5,8,9,11,12,13}为训练集。

二、预剪枝

再回顾一下预剪枝:预剪枝就是在构造决策树的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来决策树模型泛化性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。

使用以上数据集,根据信息增益可以构造出一颗未剪枝的决策树(图片来自西瓜书):
在这里插入图片描述
具体构造过程如下:
(1)分别计算所有特征的信息增益,据此选出决策树的根节点
在这里插入图片描述
由上述计算结果可知:信息增益值:脐部(0.276)=色泽(0.276)>纹理(0.174)=敲声(0.174)>根蒂(0.115)>触感(0)

(2)因为色泽和脐部的信息增益值最大,所以从这两个中随机挑选一个,这里选择脐部来对数据集进行划分,即为决策树的第①个节点;这会产生三个分支,分别是凹陷、稍凹、平坦,对应节点②,节点③,节点④;
在这里插入图片描述
而此时是预剪枝。需要判断是否按照“脐部”进行划分,判断标准:看划分前后的泛化性能是否有提升,如果划分后泛化性能有提升,则划分;否则,不划分,具体计算如下:

  • 划分前:根据训练集,类别标记为训练样例数最多的类别,由于训练集中的好瓜与坏瓜是相同多的类别,均为5,因此任选其中一类,此处选择了好瓜作为标记类别(也就是说10个瓜,管他好的坏的,全标记是好瓜了)。此时验证集(3个好瓜,7个坏瓜)在这棵决策树上的精度为3/7=42.9%
  • 划分后:(9,13)这两个编号的瓜原本都是坏瓜,结果都被分成好瓜了,其他瓜(4,5,8,11,12)都被分对了。所以验证集在这棵决策树上的精度为5/7=71.4%
  • 比较: 42.9% < 71.4%,所以划分后的泛化能力有提升,应该对“脐部”进行划分
  • 此时划分后的决策树为:
    在这里插入图片描述
    (3)在对“脐部”进行划分的基础上,再对节点②进行划分,再次使用信息增益挑选出训练集{1,2,3,14}中值最大的那个特征为“色泽”、“根蒂”与“纹理”(三个的增益值同样最大),随便选一个,选的是色泽,再对“色泽”进行划分,即下图所示,此时与(1)步骤相同,分别计算划分前后,对验证集的泛化性能是否有提升,有,划分;否则,越划越差就别划了
    在这里插入图片描述
    看圈出来的部分,可见按照“色泽”进行划分后,验证集精度反而下降,所以别划分“色泽”这个特征了(禁止划分);

(4)在对“脐部”进行划分的基础上,再对节点③进行划分,再次使用信息增益挑选出训练集{6,7,5,17}值最大的那个特征为“根蒂”、“敲声”、“触感”(三个的增益值同样最大),随便选一个,选的是根蒂,再对“根蒂”进行划分,即下图所示,此时与(1)步骤相同,分别计算划分前后,对验证集的泛化性能是否有提升,有,划分;否则,越划越差就别划了
在这里插入图片描述
看圈出来的部分,可见按照“根蒂”进行划分后,验证集精度不变,所以别划分“根蒂”这个特征了(禁止划分);

(5)对于结点 ④ ,其所含训练样本已属于同一类,所以不再进行划分。

所以基于预剪枝策略生成的最终的决策树为:
在这里插入图片描述

预剪枝总结:

预剪枝的优点

降低过拟合风险和显著减少了训练的时间和测试时间

预剪枝的缺点

带来了欠拟合风险。因为有些分支的当前划分虽然不能提升泛化性能,但在其基础上进行的后续划分却有可能导致性能显著提高

三、后剪枝

再回顾一下后剪枝:后剪枝就是先把整颗决策树构造完毕,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛化性能的提升,则把该子树替换为叶结点。
之前提到,使用(一、数据集)中的数据集,根据信息增益可以构造出一颗未剪枝的决策树(图片来自西瓜书):
在这里插入图片描述
在这里插入图片描述

后剪枝步骤:
(1)首先考察上图中的结点 ⑥,若将以其为根节点的子树删除(即剪枝),即相当于把结点⑥ 替换为叶结点,替换后的叶结点包括编号为{7,15}的训练样本,把该叶结点标记为“好瓜”(因为这里正负样本数量相等,都为1,所以随便标记一个类别),此时的决策树在验证集上的精度为4/7=57.1%(而未剪枝的决策树为3/7=42.9%),所以对节点⑥决定剪枝

(2)然后考察上图中的节点⑤, 此时:未剪枝前在验证集上的精度为4/7=57.1%(即(1)中剪枝结果的精度),而剪枝之后在验证集上的精度也为4/7=57.1%,所以对节点⑤决定不剪枝

(3)同上,对节点②进行考察,发现剪枝前:4/7=57.1% ,剪枝后:5/7=71.4%,所以对节点②决定剪枝
(4)同上,对节点③进行考察,发现剪枝前:5/7=71.4% ,剪枝后:5/7=71.4%,所以对节点③决定不剪枝
(5)最后,对节点①进行考察,发现剪枝前:5/7=71.4% ,剪枝后(此时和预剪枝中要不要对节点①“脐部”进行划分时的不划分状态的精度一致):3/7=42.9%,所以对节点①决定不剪枝

所以基于后剪枝策略生成的最终的决策树为:
在这里插入图片描述

后剪枝总结

后剪枝优点:

后剪枝比预剪枝保留了更多的分支,欠拟合风险小,泛化性能往往优于预剪枝决策树

后剪枝缺点:

后剪枝训练时间开销大,后剪枝过程是在生成完全决策树之后进行的,需要自底向上对所有非叶结点逐一考察

四、总结(两种剪枝策略对比)

在这里插入图片描述

参考文献
[1]: 周志华 《机器学习》
[2]:决策树(decision tree)(二)——剪枝
[3]:决策树的预剪枝与后剪枝

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45067943/article/details/121578470

智能推荐

js基础(对象)_weixin_30871701的博客-程序员宅基地

对象属于一种符合数据类型,在对象中可以保存多个不同的数据类型的属性对象的分类:  1、内建对象,由ECMAScript定义的对象,在任何实现中都可使用。比如:Math、String、Number、Boolean、Function、Object。。。。。  2、宿主对象,由js运行环境提供的对象,主要指浏览器指定的对象,比如:BOM、DOM console.log(...

git钩子放服务器_git 钩子 自动部署代码_weixin_39995439的博客-程序员宅基地

git 钩子 自动部署代码2019-04-23 15:23:05赞:35此文章是在有git仓库的条件下编写,如果不知道如何搭建git服务端可以点击 linux服务器上搭建git服务器先来到git仓库目录下cd /home/git/aiArguNet.git直接进入仓库的hooks目录cd hooks/创建post-receive 文件vim post-receive在文件里面写入#!/bin/ba...

VLC缓冲机制简介_小河码的博客-程序员宅基地_vlc 缓存

最近在做播放器的缓冲优化,学习了解下几个优秀开源播放器的缓冲设计方案,边看边学,本文记录下VLC的缓冲机制。先附上github地址:GitHub - videolan/vlc: VLC media player - All pull requests are ignored, please follow https://wiki.videolan.org/Sending_Patches_VLC/播放器的缓冲区管理一般在demxuer模块,VLC也不例外,缓冲逻辑的对外接口文件是vlc/mod

rtp推流收集网站_泰勒朗斯的博客-程序员宅基地

Unable to receive RTP payload type 96 without an SDP file describing it当我们的ffmpeg传递的是rtp的新类型(即动态类型),没办法直接使用命令来播放rtp流,而需要使用sdp文件https://blog.csdn.net/fsencen/article/details/70824946FFMPEG的RTP推流H264和AAC文件https://blog.csdn.net/Martin_chen2/article/detail

visio画图复制粘贴到word_解决Visio画图复制到word中格式不正确的问题_包包妈咪的博客-程序员宅基地

领导说需要画流程图,同事们都是使用word中的画图工具,我喜欢用Visio,我们的文档需要整合到一个文档里去。但是,使用Visio画的图与用Word画的图显示出来效果相差甚远。为了愉快地合作,我需要统一格式,我要么舍弃Visio,要么要想办法让Visio中的图与Word做出的图效果一样。打心底我觉得Visio要方便很多,于是便有了此文。问题解决前后的效果比对见下图:(两者的字体都是一样的:5号(1...

mysql pri_关于mysql:SQL键,MUL,PRI和UNI_夏洛喵的博客-程序员宅基地

MySQL中MUL,PRI和UNI有什么区别?我正在使用以下命令进行MySQL查询:desc mytable;其中一个字段显示为MUL键,其他字段显示为UNI或PRI。我知道如果键是PRI,则每个表只能有一个记录与该键关联。 如果键是MUL,是否表示可能有多个相关记录?这是mytable的响应。+-----------+---------+------+-----+---------+------...

随便推点

nsis安装mysql服务语句_NSIS自定义界面选择安装_甘肃省博物馆的博客-程序员宅基地

在我分享软件的过程,慢慢想让自己的软件很独特,就开始接触了各种打包软件,开始自己用易语言自写打开软件,可是一切总不是那么完美,后来无意中发现了NSIS,堪称打包的极品。打包效果预览:请自行下载查看,相信效果绝对不会让你后悔下载下来。百度音乐暴风影音QQ浏览器这里分享下界面自定义的基本教程:/*---------------------------------------自定义页面结合组件选择安装测...

a4纸对折c语言,一张A4纸最多可对折几次,这个实验太好玩了_兔希求职咖青的博客-程序员宅基地

A4纸大家都不陌生,有的朋友每天都在用,可是你知道一张A4纸最多能对折多少次吗,结果会让你大吃一惊,看完下面这个有趣好玩的实验,自己也动手试一下吧,看看自己能对折多少次呢?实验准备:一张A4纸(70g/㎡)一张普通报纸(对比实验)1.取一张A4纸,放于桌上,进行第1次对折,很轻松就对折了,看来能对折10来次不成问题,哈哈。2.随后第2次对折也是相当的轻松,第3次对折也愉快的完成了。对折3次后的纸比...

苏州大学应用技术学院计算机二级,苏州大学应用技术学院怎么样_苏州大学一本与二本有什么差别..._Amelie-大脸法语的博客-程序员宅基地

苏州大学应用技术学院怎么样_苏州大学一本与二本有什么差别苏州大学应用技术学院怎么样苏州大学应用技术学院成立于1997年,是苏州大学的二级学院。三本都差不多的,看它母体吧,这所学校的老师有苏大本部,也有自己院校的,一般专业老师就有自己学院的,我的专业老师就是学院的,大学就是大概学学,要想有所竞争优势,就要学会精通你的最擅长的,而不是皮毛。吃:食堂就像一般中学的差不多,小吃街的,有炒饭,拉面,不是很干...

python多进程爬虫写入mysql_爬虫连接mongodb、多线程多进程的使用_十三德州解说的博客-程序员宅基地

一、连接mongodb1、 设置数据库 client=pymongo.MongoClient(‘localhost’)2、 db=client[‘lagou’]设置连接的数据库名称POSITION_NAME=’’ 、PAGE_SUM 、PAGE_SIZE 等为你设置的变量名称。3、DATA_NAME=’dataposition’ # # 指定数据库的...

计算机应用里面的题,计算机应用教程习题解答与上机练习_欧皇·诸葛莺的博客-程序员宅基地

计算机应用教程习题解答与上机练习语音编辑锁定讨论上传视频《计算机应用教程习题解答与上机练习》一书的出版社是清华大学出版社,出版时间是2011年3月1日。本书可作为高等学校文科类专业及其他非计算机专业的计算机公共课的教材。书名计算机应用教程习题解答与上机练习ISBN9787302244622类别教科书页数178页定价36.00元出版社出版时间2011年3月1日装...

samba在linux之间共享文件挂载报错_wzq-blog的博客-程序员宅基地

测试linux和windows之间是可以登录的,但是在两个linux系统之间挂载报错,提示“mount error(13): Permission deniedRefer to the mount.cifs(8) manual page (e.g. man mount.cifs)”samba服务端安装配置好后,在客户端安装cifsyum install -y cifs使

推荐文章

热门文章

相关标签