模型算法基础——决策树剪枝算法(一)

在决策树生成以后,常常出现过拟合的问题。这是因为如果决策树过于复杂,训练样本的每个属性(变量)都被详细的加以考虑,决策树的每个叶节点所覆盖的样本都是或接近“纯”的。这种情况下,决策树往往对训练样本拟合的很好,但是拟合验证样本时效果却大打折扣。

举一个栗子可以加深对过拟合的理解:在上学的时候,有一些同学准备考试的方法是“背题”,仅仅靠背解题过程却无法掌握其中规律性的的东西,如果题目都押中了这类同学就可以考得很好,但是对于大多数情况他们却以失败告终;还有一些同学,他们擅长在题目中寻找规律,即使题目千变万化他们也能得到高分。模型也是一样,我们更希望它能够体现规律性的东西,而不是训练样本中的细节。

这时,对决策树进行剪枝就成为了一个必不可少的步骤。其实对决策树而言,相对于树的生成过程,剪枝的过程更为重要。今天介绍一种后剪枝算法——误差降低剪枝(Reduced Error Pruning/REP)

误差降低剪枝是最简单粗暴的剪枝方法。首先用训练样本生成决策树后,自下而上对于每个节点决定是否修剪该节点。先假设我们要删除该节点下的子树使其成为叶子节点并赋予训练样本最常见的分类,再用验证样本比较修剪前后的错分率,当修剪后的错分率不比修剪前的高时便真正删除该节点下的子树。

举个栗子,假设有个训练样本产生的决策树长这样(目标变量可分类为1或):

其中T4节点中13和7表示该节点覆盖的样本中目标变量为1和的个数。再假设用这个决策树拟合验证样本后的结果长这样:

自下而上,按照T5、T6、T4的顺序来决定每个节点是否需要被修剪:

在判断T4是否修剪前,T7、T8节点已被删除,T5成为新的叶子节点。可以看到最终T4节点下的全部子树都被删除。

误差降低剪枝使用了和训练样本独立的验证样本,由于验证样本没有参与决策树的生成过程,因此一定程度上可以解决过拟合问题,但也可能会产生过剪枝的问题。

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

layer定义 | 深度学习caffe框架

首先让我们回顾一下caffe的代码层次: blob,layer, net和solver.

861
来自专栏云时之间

Tensorflow 笔记:搭建神经网络

1623
来自专栏张俊红

Sklearn参数详解--决策树

1.2K8
来自专栏用户2442861的专栏

CNN卷积神经网络原理简介+代码详解

@blog:http://blog.csdn.net/u012162613/article/details/43225445

2193
来自专栏有趣的Python

16- OpenCV+TensorFlow 入门人工智能图像处理- Hog特征识别小狮子

3805
来自专栏文武兼修ing——机器学习与IC设计

Deep-compression阅读笔记基本步骤相关分析总结

以上是Deep compression中所述的神经网络压缩方法,主要包括三个步骤:

1522
来自专栏菩提树下的杨过

机器学习笔记(5):多类逻辑回归-手动添加隐藏层

了解神经网络原理的同学们应该都知道,隐藏层越多,最终预测结果的准确度越高,但是计算量也越大,在上一篇的基础上,我们手动添加一个隐藏层,代码如下(主要参考自多层感...

2066
来自专栏生信小驿站

使用R语言进行机器学习特征选择①

特征选择是实用机器学习的重要一步,一般数据集都带有太多的特征用于模型构建,如何找出有用特征是值得关注的内容。

3044
来自专栏烂笔头

曲线点抽稀算法-Python实现

目录[-] 何为抽稀 在处理矢量化数据时,记录中往往会有很多重复数据,对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间,另一方面造成所要...

4736
来自专栏用户2442861的专栏

Logistic回归与梯度下降法

http://blog.csdn.net/acdreamers/article/details/44657979

951

扫码关注云+社区