专栏首页数据分析1480从零开始学Python【36】--决策树剪枝的来龙去脉

从零开始学Python【36】--决策树剪枝的来龙去脉

还没关注?

快动动手指!

往期回顾

从零开始学Python【34】--CART决策树(理论部分)

从零开始学Python【35】--CART决策树(实战部分)

前言

决策树的剪枝通常有两类方法,一类是预剪枝,另一类是后剪枝。预剪枝很好理解,就是在树的生长过程中就对其进行必要的剪枝,例如限制树生长的最大深度,即决策树的层数、限制决策树中间节点或叶节点中所包含的最小样本量以及限制决策树生成的最多叶节点数量等;后剪枝相对来说要复杂很多,它是指决策树在得到充分生长的前提下再对其返工修剪。常用的剪枝方法有误差降低剪枝法、悲观剪枝法和代价复杂度剪枝法等,下面将详细介绍这三种后剪枝方法的理论知识。

误差降低剪枝法

该方法属于一种自底向上的后剪枝方法,剪枝过程中需要结合测试数据集对决策树进行验证,如果某个节点的子孙节点都被剪去后,新的决策树在测试数据集上的误差反而降低了,则表明这个剪枝过程是正确的,否则就不能对其剪枝。为了使读者明白该方法的剪枝过程,以下图中的决策树为例,介绍该剪枝法的具体操作步骤。

1)将决策树的某个非叶子节点作为剪枝的候选对象(如图中的

处节点),如果将其子孙节点删除(对应的两个叶节点),则

处的节点就变成了叶节点。

2)利用投票原则,将此处叶节点中频数最高的类别用作分类标准(如图中剪枝后该叶节点属于类A)。

3)利用剪枝后的新树在测试数据集上进行预测,然后对比新树与老树在测试集上的误判样本量,如果新树的误判样本量低于老树的误判样本量,则将

处的中间节点替换为叶节点,否则不进行剪枝。

4)重复前面的三步,直到新的决策树能够最大限度地提高测试数据集上的预测准确率。

虽然该方法是最简单的后剪枝方法之一,但由于它需要结合测试数据集才能够实现剪枝,因此就可能导致剪枝过度的情况。为了避免剪枝过程中使用测试数据集便产生了悲观剪枝法,下面介绍该方法的实现原理和过程。

悲观剪枝法

该方法的剪枝过程恰好与误差降低剪枝法相反,它是自顶向下的剪枝过程。虽然不再使用独立的测试数据集,但是简单地将中间节点换成叶节点肯定会导致误判率的提升,为了能够对比剪枝前后的叶节点误判率,必须给叶节点的误判个数加上经验性的惩罚系数0.5。所以,剪枝前后叶节点的误判率可以表示成:

其中,

表示剪枝后中间节点被换成叶节点的误判率;

表示中间节点剪枝前其对应的所有叶节点的误判率;

为中间节点处的误判个数;·

为节点下的所有叶节点误判个数;L表示中间T节点对应的所有叶节点个数;N表示中间节点的样本个数;

表示各叶节点中的样本个数,其实

对比剪枝前后叶节点误判率的标准就是,如果剪枝后叶节点的误判率期望在剪枝前叶节点误判率期望的一个标准差内,则认为剪枝是合理的,否则不能剪枝。可能读者在理解这种剪枝方法时比较困惑,这里举一个例子加以说明,一个剪枝示意图如下图所示。

假设以

节点为例,剪枝前对应了3个叶节点,误判个数分别为3,2,0;如果将其所有叶节点都剪掉,

便成为了

的叶节点,误判样本数为7。按照上方的计算公式,可以得到:

现在的问题是,误判率

的标准差该如何计算。由于误判率属于0-1分布,即每个节点中只有正确分类和错误分类两种情况,因此根据0-1分布的期望(

)和方差(

)公式,可以得到

的与

的期望及

的方差:

最后,根据剪枝的判断标准

,可以判断

节点是否可以被剪枝:

很明显,上面所计算的不等式是满足条件的,所以可以认定

节点是需要进行剪枝、将其转换成叶节点的。通过上面的举例,相信读者应该理解悲观剪枝法的思路,接下来介绍一种基于目标函数的剪枝方法,即代价复杂度剪枝法。

代价复杂度剪枝法

从字面理解,该剪枝方法涉及两则信息,一则是代价,是指将中间节点替换为叶节点后误判率会上升;另一则是复杂度,是指剪枝后叶节点的个数减少,进而使模型的复杂度下降。为了平衡上升的误判率与下降的复杂度,需要加入一个系数a,故可以将代价复杂度剪枝法的目标函数写成:

其中,

表示

节点下第

个叶节点;

为第

个叶节点的样本量;

为第

个叶节点的信息熵;

为节点

对应的所有叶节点个数;a就是调节参数。问题是参数a该如何计算呢?可以通过下式推导所得:

节点

剪枝前的目标函数值为:

节点

剪枝后的目标函数值为:

,得到:

通过上面的公式,可以计算出所有非叶子节点的a值,然后循环剪去最小a值所对应的节点树。下面结合图来说明代价复杂度剪枝的详细过程。

(1)对于一棵充分生长的树,不妨含有4个非叶子节点和5个叶子节点,根据计算a值的公式,可以得到所有非叶子节点对应的a值。

(2)挑选出最小的a值,不妨为

,然后对

进行剪枝,使其成为叶子节点,便得到一棵新树。

(3)接下来重新计算剩余非叶子节点所对应的a值。

(4)不断重复(2)和(3),直到决策树被剪枝成根节点,最终得到

棵新树。

(5)将测试数据集运用到

棵新树中,再从中挑选出误判率最低的树作为最佳的决策树。

如上介绍的三种决策树后剪枝方法都是比较常见的,其思路也比较通俗易懂,可惜的是sklearn模块并没有提供后剪枝的运算函数或“方法”。这并不意味着sklearn模块中的决策树算法没有实际的落地意义,因为它提供了决策树的预剪枝技术,如果预剪枝不够理想,读者还可以使用集成的随机森林算法,该算法综合了多棵决策树,可以很好地避免单棵决策树过拟合的可能。关于随机森林的思想和实战可以查看《》一文。

结语

OK,关于决策树剪枝的理论知识我们就分享到这里,如果你有任何问题,欢迎在公众号的留言区域表达你的疑问。同时,也欢迎各位朋友继续转发与分享文中的内容,让更多的人学习和进步。

每天进步一点点:数据分析1480

长按扫码关注我

本文分享自微信公众号 - 数据分析1480(lsxxx2011),作者:刘顺祥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 大数据之脚踏实地学16--Scala列表、元组与映射

    在上一期的《大数据之脚踏实地学15--Scala的数组操作》分享中,介绍了Scala的数组相关知识,借助于Array函数可以构造定长数组(即数组一旦定义好长度,...

    1480
  • 协同过滤的原理及Python实现

    作者:李小文,先后从事过数据分析、数据挖掘工作,主要开发语言是Python,现任一家小型互联网公司的算法工程师。

    1480
  • 决策树学习笔记(二):剪枝,ID3,C4.5

    推荐导读:本篇为树模型系列第二篇,旨在从最简单的决策树开始学习,循序渐进,最后理解并掌握复杂模型GBDT,Xgboost,为要想要深入了解机器学习算法和参加数据...

    1480
  • 【星球知识卡片】模型剪枝有哪些关键技术,如何对其进行长期深入学习

    大家好,欢迎来到我们的星球知识小卡片专栏,本期给大家分享模型剪枝的关键技术以及一些学习资料。

    用户1508658
  • YOLOv3剪枝再升级!

    该项目也说明在使用YOLOv3进行单类目标检测时,模型存在大量冗余,剪枝可以较好的减少参数、提高速度。

    CV君
  • AAAI 2020 | 滴滴&东北大学提出自动结构化剪枝压缩算法框架,性能提升高达120倍

    近年来,随着深度神经网络模型性能不断刷新,模型的骨干网络参数量愈发庞大,存储和计算代价不断提高,从而导致难以部署在资源受限的嵌入式平台上。滴滴 AI Labs ...

    机器之心
  • 【AI不惑境】模型剪枝技术原理及其发展现状和展望

    进入到不惑境界,就是向高手迈进的开始了,在这个境界需要自己独立思考。如果说学习是一个从模仿,到追随,到创造的过程,那么到这个阶段,应该跃过了模仿和追随的阶段,进...

    用户1508658
  • 决策树算法那些事--CART|机器学习

    一、树算法介绍 当前数据挖掘领域中存在10个火热的算法、它们涉及到数据的聚类、分类、关联规则、排序等方面。今天就跟大家说说基于树的分类算法--决策树,决策树有非...

    陆勤_数据人网
  • 模型算法基础——决策树剪枝算法(二)

    在上一篇模型算法基础——决策树剪枝算法(一)中,我们介绍了误差降低剪枝(REP),今天我们继续介绍另一种后剪枝算法——悲观错误剪枝(PessimisticErr...

    企鹅号小编
  • 性能提升最高达120倍!滴滴实习生提出自动结构化减枝压缩算法框架 | AAAI 2020

    这就是滴滴实习生提出的自动结构化减枝压缩算法框架带来的性能提升,名为AutoCompress。

    量子位

扫码关注云+社区

领取腾讯云代金券