决策树为什么要进行剪枝处理和决策树的剪枝策略，以及后剪枝方法——代价复杂度(CCP)算法剪枝系数的计算_决策树为什么要剪枝-程序员宅基地

技术标签：后剪枝方法——代价复杂度算法决策树为什么要进行剪枝处理机器学习决策树的剪枝策略预剪枝和后剪枝的常用方法剪枝系数的计算

决策树的剪枝处理

为什么要进行决策树的剪枝处理呢？

决策树的过拟合的风险很大，因为理论上来说可以将数据完全分的开，如果树足够大，每个叶子节点就剩下了一个数据。那么，这就会造成模型在训练集上的拟合效果很好，但是泛化能力很差，对新样本的适应能力不足。所以，对决策树进行剪枝，可以降低过拟合的风险。

决策树的剪枝策略

决策树的剪枝策略分为预剪枝和后剪枝

预剪枝

预剪枝就是边建立决策时边进行剪枝的操作。在决策树生成的过程中，对每个节点在划分前向首先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶子节点。

预剪枝可以：限制树的深度，叶子节点个数，叶子节点的样本数，信息增益量等。

后剪枝

当建立完决策树后再进行剪枝操作。后剪枝是先从训练集生成一棵完整的决策树，然后自底向上地对非叶子节点进行考察，若将该节点对应的子树替换为叶子节点能够带来决策树泛化性能的提升，将该子树替换为叶子节点。

通过一定的衡量标准。这里讲的是CART算法的后剪枝方法——代价复杂度算法，即CCP算法。

CART算法请参考博文

$T$ 表示树

$C (T)$ 表示当前损失

$T_{leaf}$ 表示分裂后的叶子节点数

$\alpha\ge0$ 为参数

$C_\alpha(T)$ 表示损失函数的正则化

$\alpha|T_{leaf}|$ 实际上是损失函数的正则项

下面是代价复杂度算法的基本思想：

$C_\alpha(T) = C(T)+\alpha|T_{leaf}|$

$C (T)$ 表示当前损失,实际上就是求分类后叶子节点的经验熵期望，计算方式为当前叶节点的样本数与当前叶结点的熵值的乘积。也就是说，叶子节点含有的样本数越多，那么这个分类效果就越混乱，损失值越大。

熵的计算参考我的博文

$\begin{aligned}C(T) =\sum_{t=1}^{|T_{leaf}|} N_tH_t(T)\end{aligned}$

$N_t$ 表示该叶结点含有的样本点个数

那么， $\begin{aligned}C_\alpha(T) = \sum_{t=1}^{|T_{leaf}|} N_tH_t(T)+\alpha|T_{leaf}|\end{aligned}$

$\alpha|T_{leaf}|$ 是修正项，它是基于复杂度的考虑。当叶节点分裂后与不分裂的熵值相等，实际上没有进行任何分类，但是我们认为不分类的情况更好，因为，分类后树的复杂度会更高。加了修正项后，如果 $\alpha=0$ 表示未剪枝的树损失更小，也就是熵更小，如果 $\alpha \to \infty$ 表示剪枝到根节点更好，因为叶结点的个数占了主导地位。修正项 $\alpha|T_{leaf}|$ 可以避免过拟合。 $\alpha$ 值的设置可以更好的避免出现完全树和根节点这种极短情况，所以可以避免过拟合。

剪枝系数 $\alpha$ 的计算

假设当前对以 $t$ 为根节点的子树 $T_t$ 剪枝，剪枝后只保留 $t$ 本身，而删除掉所有的子节点

剪枝后的损失函数为 $C_\alpha(t)=C(t)+\alpha$

剪枝前的损失函数为 $C_\alpha(T_t) = C(T_t)+\alpha|T_{leaf}|$

令二者相等可得到 $\begin{aligned}\alpha = \frac{C(t)-C(T)}{|T_{leaf}|-1}\end{aligned}$ ，因为损失相同，那么就取复杂度小的，所以就可以剪枝。 $\alpha$ 就是节点 $t$ 的剪枝系数。

本文链接：https://blog.csdn.net/weixin_44451032/article/details/100055886

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

c# 调用c++ lib静态库_c#调用lib-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib

deepin/ubuntu安装苹方字体-程序员宅基地

文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang

html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地

文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些

PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地

文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器

【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地

文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距

docker — 容器存储_docker 保存容器-程序员宅基地

文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器

随便推点

网络拓扑结构_网络拓扑csdn-程序员宅基地

文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn

JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地

文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios