决策树后剪枝算法（一）代价复杂度剪枝CPP-程序员宅基地
技术标签： 算法 python 机器学习 剪枝 决策树 数据挖掘
决策树后剪枝算法（一）代价复杂度剪枝CPP
决策树后剪枝算法（二）错误率降低剪枝REP
决策树后剪枝算法（三）悲观错误剪枝PEP
决策树后剪枝算法（四）最小错误剪枝MEP
剪枝，是一个“用准确性换取简单性”的思想。它允许决策树对训练集过拟合，再通过删除对泛化精度无贡献的子分支，从而修剪出一颗较小的树。以下列出几种较常见的后剪枝算法，及其机制对比：
| CCP | REP | PEP | MEP | |
|---|---|---|---|---|
| 剪枝方式 | 自底向上 | 自底向上 | 自顶向下 | 自底向上 |
| 计算复杂度 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) |
| 误差估计 | 标准误差 | 剪枝集上误差 | 连续性矫正 | 概率估计 |
| 是否需要额外剪枝集 | 否 | 是 | 否 | 否 |
（1）代价复杂度剪枝（CCP）
CCP算法为子树 T t T_t Tt定义了代价和复杂度，以及一个衡量代价与复杂度之间关系的参数 α \alpha α。大致流程为，从决策树 T 0 T_0 T0开始不断剪枝直到 T 0 T_0 T0的根节点，形成一个子树序列{ T 0 , T 1 , . . . , T n T_0, T_1,...,T_n T0,T1,...,Tn}; 然后经过交叉验证法在独立验证集上逐个测试评估, 从而选出最优子树。
（1.1）数学推导
评价标准:
R α ( T ) = R ( T ) + α ∣ f ( T ) ∣ R ( T ) = ∑ t ∈ f ( T ) r ( t ) . p ( t ) = ∑ t ∈ f ( T ) R ( t ) R_\alpha(T) = R(T) + \alpha|f(T)|\\ R(T)=\sum_{t\in f(T)}r(t).p(t)=\sum_{t\in f(T)}R(t) Rα(T)=R(T)+α∣f(T)∣R(T)=t∈f(T)∑r(t).p(t)=t∈f(T)∑R(t)
解读：
- R α ( T ) R_{\alpha}(T) Rα(T)即为一棵树好坏的评价标准。
- R ( T ) R(T) R(T)是决策树训练集误差(代价)， ∣ f ( T ) ∣ |f(T)| ∣f(T)∣表示决策树的叶子节点数量(复杂度)。
- α \alpha α是正则化参数，用以权衡训练数据的拟合程度与模型复杂度。
- ∑ t ∈ f ( T ) R ( t ) \sum_{t\in f(T)}R(t) ∑t∈f(T)R(t)表示每个叶子节点所产生的错误分类的误差和。
- p ( t ) p(t) p(t)为叶子节点权重（ = n ( t ) n =\frac{n(t)}{n} =nn(t)）， r ( t ) r(t) r(t)为叶子结点误分类率（ = e r r o r ( t ) n ( t ) =\frac{error(t)}{n(t)} =n(t)error(t)）。
进一步推导，对于一个固定的 α \alpha α值, 一定存在一颗使得 C α ( T ) C_{\alpha}(T) Cα(T)最小的子树 T α T_{\alpha} Tα, 即在固定 α \alpha α下的最优剪枝策略。现在考虑 α \alpha α变化，考虑极端情况: 当 α = 0 \alpha=0 α=0时, 有 R α ( T ) = R ( T ) R_\alpha(T) = R(T) Rα(T)=R(T), 即不考虑复杂度, 易知完整树即为最优；当 α → ∞ \alpha\rightarrow\infty α→∞，复杂度权重无穷大，易知单节点树为最优。及 α \alpha α从 0 → ∞ 0\rightarrow\infty 0→∞， α \alpha α对应的最优树 T α T_{\alpha} Tα从繁变简。
再结合 B r e i m a n Breiman Breiman等人的证明: 将 α \alpha α从小增大, 0 = α 0 < α 1 < . . . < α n < ∞ 0=\alpha_0<\alpha_1<...<\alpha_n<\infty 0=α0<α1<...<αn<∞, 产生一系列的区间 [ a i , a i + 1 ) [a_i, a_{i+1}) [ai,ai+1)， i = 0 , 1 , 2 , . . . , n i=0,1,2,...,n i=0,1,2,...,n; 剪枝得到的子树序列对应着区间 α ∈ [ a i , a i + 1 ) , i = 0 , 1 , 2... n \alpha\in{[a_i, a_{i+1})},~i=0,1,2...n α∈[ai,ai+1), i=0,1,2...n的最优子树序列{ T 0 , T 1 , . . . , T n T_0, T_1, ...,T_n T0,T1,...,Tn}，序列中的子树是嵌套的, 即 T 0 T_0 T0爷爷/ T 1 T_1 T1父亲/ T 2 T_2 T2儿子/ T 3 T_3 T3孙子…以此类推。
那么如何选取每一阶段的 α \alpha α, 这里引入剪枝整体损失函数减少程度指标 g ( t ) = R ( t ) − R ( T t ) ∣ T t ∣ − 1 g(t)=\frac{R(t)-R(T_t)}{|T_t|-1} g(t)=∣Tt∣−1R(t)−R(Tt)，其具体含义如下：
当 R α ( T t ) = R α ( t ) 时 , 即剪枝后误差增长率为 0 R α ( T t ) = R α ( T t ) + ∣ f ( T t ) ∣ R α ( t ) = R α ( t ) + 1 解得 α ’ = R ( t ) − R ( T t ) ∣ T t ∣ − 1 , 即剪枝临界点 ( 必定剪枝 ) 当R_\alpha(T_t)=R_\alpha(t)时,即剪枝后误差增长率为0\\ R_\alpha(T_t)=R_\alpha(T_t)+|f(T_t)|\\ R_\alpha(t)=R_\alpha(t)+1\\ 解得\alpha’=\frac{R(t)-R(T_t)}{|T_t|-1},即剪枝临界点(必定剪枝) 当Rα(Tt)=Rα(t)时,即剪枝后误差增长率为0Rα(Tt)=Rα(Tt)+∣f(Tt)∣Rα(t)=Rα(t)+1解得α’=∣Tt∣−1R(t)−R(Tt),即剪枝临界点(必定剪枝)
且可证得 g ( t ) g(t) g(t)与误差增长率成正比:
KaTeX parse error: Expected 'EOF', got '&' at position 75: …T-T_t)|-|f(T)|)&̲\\ =[R(else)+R(…
根据以上推导结论, 对于特定 α \alpha α区间，要求最优 T α T_\alpha Tα需寻求误差增长率最小, 即 g ( t ) g(t) g(t)最小。故我们所需要做的, 就是每轮迭代中遍历所有非叶子节点， T i − 1 T_{i-1} Ti−1剪枝 g ( t ) g(t) g(t)最小的节点生成下一颗最优子树 T i T_i Ti，从而生成子树序列。
最后基于独立验证集, 对子树序列 T 0 , T 1 , . . . , T n T_0, T_1, ...,T_n T0,T1,...,Tn中的平方误差或基尼系数逐个计算, 再作评估选择即可。
（1.2）算法流程
- 输入：CART算法生成的决策树 T 0 T_0 T0
- 输出：最优决策树 T α T_\alpha Tα
- （1）设 k = 0 , T = T 0 k=0, T=T_0 k=0,T=T0
- （2）设 α = + ∞ \alpha=+\infin α=+∞
- （3）自下而上地对各内部结点 t t t计算 R ( T t ) R(T_t) R(Tt)， ∣ f ( T t ) ∣ |f(T_t)| ∣f(Tt)∣以及:
g ( t ) = R ( t ) − R ( T t ) ∣ T t ∣ − 1 α = m i n ( α , g ( t ) ) g(t)=\frac{R(t)-R(T_t)}{|T_t|-1}\\ \alpha=min(\alpha, g(t)) g(t)=∣Tt∣−1R(t)−R(Tt)α=min(α,g(t))
- （4）对 g ( t ) = α g(t)=\alpha g(t)=α的内部结点 t t t进行剪枝, 并对叶结点构成的树，回到步骤（2）；否则令 T k = T n T_k=T_n Tk=Tn。
- （7）采用交叉验证法在子树序列 T 0 , T 1 , . . . , T n T_0, T_1, ...,T_n T0,T1,...,Tn中选取最优子树 T α T_\alpha Tα（分类：基尼系数 \ 回归：平均误差）。
（1.3）例题计算
#### (一)原始决策树
#### (二)第一次迭代
INPUT: α = 0 , T 1 = t 1 , t 2 , t 3 \alpha=0,~ T^1={t_1,t_2,t_3} α=0, T1=t1,t2,t3
OUTPUT: α 2 = min g 1 ( t ) = 1 8 , t = t 2 或 t 3 \alpha^2=\min{g_1(t)}=\frac{1}{8},~t=t_2或t_3 α2=ming1(t)=81, t=t2或t3
#### (三)第二次迭代
INPUT： a l p h a 2 = 1 8 , T 2 = t 1 , t 2 alpha^2=\frac{1}{8},T^2={t_1, t_2} alpha2=81,T2=t1,t2
OUTPUT： α 3 = min g 2 ( t ) = 1 8 , t = t 2 \alpha^3=\min{g_2(t)=\frac{1}{8}}, t=t_2 α3=ming2(t)=81,t=t2
#### (四)第三次迭代
INPUT: T 3 = t 1 T^3={t1} T3=t1
OUTPUT: α 4 = g 3 ( t 1 ) = 8 16 − 4 16 2 − 1 = 1 4 \alpha^4=g_3(t_1)=\frac{\frac{8}{16}-\frac{4}{16}}{2-1}=\frac{1}{4} α4=g3(t1)=2−1168−164=41
即子树序列 T 0 , T 1 , . . . , T n T_0, T_1, ...,T_n T0,T1,...,Tn及其参数 α \alpha α的计算, 接下来进行交叉验证即可选择最优子树即可。
（1.4）代码实现
手写实现 + sklearn实现
链接：https://pan.baidu.com/s/1gskUIAHfv9lZ6Mtq7r7I1Q
提取码：wo7m
代码参考:http://www.hzcourse.com/web/refbook/detail/9970/226
——————————————————————————————————————————-—————————————————
参考资料：
[1] 现代决策树模型及其编程实践 黄智濒 编著
[2] 统计学习方法(第二版) 李航 著
[3] https://blog.csdn.net/WANGWUSHAN/article/details/108556371
智能推荐
python金融量化——股票数据分割+计算单支股票利益率曲线（代码）_python 股票循环计算-程序员宅基地
文章浏览阅读719次。【代码】python金融量化——股票数据分割+计算单支股票利益率曲线（代码）_python 股票循环计算
Elasticsearch Java API 的使用（22）—实现桶聚合_es中聚合添加过滤条件 javaapi-程序员宅基地
文章浏览阅读2.3k次，点赞2次，收藏3次。分组聚合 使用terms时间分组集合public class EsTermsAgg throws UnknownHostException{ public void TermsAgg(TransportClient client){ AggregationBuilder agg = AggregationBuilders.terms("terms").field("ag..._es中聚合添加过滤条件 javaapi
SQL Server 2000常用命令_sql2000数据库检查命令-程序员宅基地
文章浏览阅读1.3k次。SQL Server 2000常用命令 (1) 数据记录筛选：sql="select * from 数据表 where 字段名=字段值 order by 字段名 [desc]"sql="select * from 数据表 where 字段名 like '%字段值%' order by 字段名 [desc]"sql="select top 10 * from 数据表 where 字段名 order by 字段名 [desc]"sql="select _sql2000数据库检查命令
mininet，一个超级实用的 Python 库！-程序员宅基地
文章浏览阅读930次，点赞27次，收藏19次。Python Mininet是一个开源工具，用于创建、配置和仿真计算机网络。它允许用户在单个计算机上创建多个虚拟网络主机（Hosts）和交换机（Switches），并模拟它们之间的连接和通信。网络仿真：Mininet允许用户模拟网络中的实际数据流量，以测试和评估网络应用和协议的性能。这对于网络协议的开发和测试至关重要。自定义网络拓扑：Mininet提供了Python API，使用户能够以编程方式定义网络拓扑，包括主机、交换机、链路等。这意味着可以根据需要创建各种不同类型的网络。实验环境。
智慧旅游建设智能化景区管理系统方案_景区智慧管理系统方案-程序员宅基地
文章浏览阅读2.7k次。智慧旅游是应用新一代网络信息技术和装备，充分精确及时感知和应用各种旅游信息内容，进而完成旅游服务、旅游管理、旅游推广、旅游体验的智能化系统，推动旅游商圈向综合型和结合型转型发展提高，是旅客市场的需求与当代信息科技驱动旅游业自主创新发展的源动力和新发展趋势，是全方位提高旅游业发展水准、推动旅游业转型发展、提升旅游满意率的关键着力点，针对把旅游业建设成为人民大众更为满意的智能化服务行业，具备十分关键的实际意义。目前在我国的百分之八十的5A级景区能够在手机App和网上预订门票，占比创历史上新纪录。伴随着互联网_景区智慧管理系统方案
To display the conditions report re-run your application with ‘debug‘ enabled-程序员宅基地
文章浏览阅读7.2k次。SpringBoot初学者笔记当启动时遇到To display the conditions report re-run your application with ‘debug’ enabled.只需要在启动类上的注解@SpringBootApplication中加(exclude = {DataSourceAutoConfiguration.class})即可@SpringBootApplication(exclude = {DataSourceAutoConfiguration.class})_to display the conditions report re-run your application with 'debug' enable
随便推点
bug: nerdtree 显示图标乱码-程序员宅基地
文章浏览阅读2.3k次。bug 复现。选择：nerd font解决原因是字体。droidsansmono nerd font book_nerdtree 显示图标
mitmproxy+Appium+安卓模拟器 抓取https请求失败的解决办法_安卓 mitmproxy证书有问题-程序员宅基地
文章浏览阅读1k次。最近学习爬虫时按照《python3 网络爬虫开发实战》步骤使用mitmproxy时，发现https请求无法抓取，部分app甚至一条请求都看不到。百度一手解决办法寥寥无几，实测并没有卵用。几天探索，发现问题还是出在证书上。 问题出现的原因：尽管可能你已经把证书导入手机，但是这始终是第三方证书，属于用户凭据。许多app都只信任系统证书，更有甚者只信任自带的证书。 解决办法：我们直接将第三方mitmproxy证书转为系统证书导入（需要ROOT权限）。 ..._安卓 mitmproxy证书有问题
如何在CSDN中免费下载资料_csdnvip文章怎么看不充vip-程序员宅基地
文章浏览阅读10w+次，点赞152次，收藏70次。如何在CSDN中免费下载资料下载积分攻略：1. 个人设置里进行手机绑定CSDN账户 奖励50分 （右上角设置-账户安全-手机绑定）2. 完成任务送若干分积分 http://task.csdn.net/3. 上传有效资源获取积分（上传非法，广告资源用户，将被扣除一定积分，严重者封号）。· 上传自己设分资源被下载，下载量×资源分，100分封顶。· 上传0分资源被下载，下载量×系统..._csdnvip文章怎么看不充vip
tron(波场）trc20离线签名广播交易(Java版本)_tron离线签名-程序员宅基地
文章浏览阅读4.6k次，点赞4次，收藏10次。前言由于在项目中需要，我们又为了节省服务器资源，决定不同步节点数据。也就说说，很多的一些API，我们是不能直接用的了，最直接的有创建地址、签名交易等等相关API修改地址生成TronUtils.java /** * 离线创建地址 * * @return */ public static Map<String, String> createAddress() { ECKey eCkey = new ECKey(random); String privateKey_tron离线签名
Altium Designer 20（AD20）新手小白详细教程-程序员宅基地
文章浏览阅读3.9w次，点赞90次，收藏651次。关于AD20的基础操作，小白可以学一学，方便操作_ad20
QML 基本类型_qml表示double-程序员宅基地
文章浏览阅读148次。QML 有许多基本类型，例如整型int或字符串类型string，这和 QML 对象类型形成对比，QML 对象类型是指具有属性、信号、方法等的对象，与对象类型不同的是，基本类型不能用于声明 QML 对象，例如不能声明 int{}对象或size{}对象。与对象类型的属性不同，基本类型的属性不提供它们自己的属性更改信号。相反，对象类型的属性发出它们自己的属性更改信号，并且仅在将属性重新分配给不同的对象值时才调用对象类型属性的属性更改信号处理程序。在 Qt 的全局对象提供有用的功能，用于操作基本类型的值。_qml表示double