机器学习:对决策树剪枝

昨天推送中介绍了决策树的基本思想,包括从众多特征中找出最佳的分裂点,刚开始大家都是用选择这个特征后带来的信息增益为基本方法,后来发现它存在一个严重的bug,因此提出来了信息增益率(即还要除以分裂出来的那些节点对应的自身熵的和),再后来,又提出来一个与熵概念类似的基尼系数,根据这些理论和训练数据可以构建出一颗大树了。但是这颗大树的泛化能力一般,需要进行剪枝操作才能提升泛化能力,那么常用的剪枝策略都有哪些呢。

01 这真的好吗?

一个在训练数据集上可以取得100%的准确率的分类器,一定很好吗?未必好,因为它在测试集上的测试结果未必好,又因为分类器的好坏最重要的是要看在测试集上的表现效果。

那么问题来了,为什么它在测试集上的效果就不好呢? 试想这样一种极端情况,我们手上有100个水果,其中包括三类:香蕉,苹果,杏,它们常用的区分特征比如:形状,大小,外观等,假如我们启用了一个非常特殊的特征,恰好把这100个水果样本对应到了100个叶子节点,也就是说每个叶子都还有唯一的一个样本,这在训练集上的准确率一定是100%呀,但是在测试集上呢,第101个水果在这个极其特殊的特征上,都有可能不在原100个特征取值内,所以你根本找不到它的对应,所以它不属于这100个叶子中之一。

当然,这个极端的例子虽然未必能在实际训练测试中遇到,但是它却很好的解释了选择合适的特征,并且避免叶子节点过多,同时防止过多的叶子节点包含的样本数过少的现象,才是决策树在测试集上表现良好的重要考量。

同时,还有一个因素也得考量,昨天推送分析过,决策树本质上是 if-else的多层嵌套,每个递归构建的新的分裂点(节点)都会不断地降低不纯度(熵),最终在叶子节点上,不纯度降为0,但是,一个叶子节点的深度如果很大,说明经过的 if 就非常多,这样就需要苛刻的条件才能满足这个很深的叶子节点(即这个类别),言外之意,它缺少必要的泛化能力,测试集的数据有可能不会走到这里。

为了解决以上通过训练构建出的决策树的深度过大,叶子节点过多,叶子节点含有的样本数过少的问题(实际上就是一棵树多余的树枝),就需要想办法剪去这些树枝,从而得到一棵不高不胖的决策树。

02 怎么剪枝

上面谈到了决策树剪枝的必要性,通过剪枝提高,测试集上的数据在构建好的决策树上找到自己对应所属的叶子节点,即找到自己的对应分类。

应该怎么做剪枝呢? 一种思路是在众多特征中贪心地选择最佳的信息增益率的那个特征作为根节点,依次递归地进行这种操作,在进行到某步操作时,发现树的深度大于指定的深度了,此时这一枝递归返回;

或者发现此时已形成的叶子节点已经达到指定的最多叶子节点数,也递归返回;

或者发现某个分裂点(节点)的样本数已经小于了指定的节点含有的最少样本数时,也递归返回。

以上就是常用的在构建决策树时的同时,进行剪枝操作,因为是同时做,时间复杂度小,这种做法称为:预剪枝。

还有,等决策树建立好了,我再修修补补一下,怎么修补?看看那些叶子节点的父节点,好,如果我这个父节点不分裂,是不是泛化误差会更小些呢,如果是这样,我就没有必要分裂了吧。

那么这种情况下,该父节点是否分裂有没有量化的公式呢:

其中 Tleaf 表示叶子节点的数目;

C(Node)表示某个节点的基尼系数乘以样本数。

这样比较下分裂Or不分裂谁的C值小,就选择谁,这种方法就是后剪枝,显然这种算法是在决策树构建完后,再花时间去剪枝,时间上肯定没有一边建立树,一边剪枝的效率高。

03 可视化决策树

下面我们在sklearn中,可视化决策树,同时关键是要理解以上几种剪枝策略。

我们直接用sklearn提供的一个数据集首先生成一棵不带剪枝策略的树,代码如下:

#导入iris数据集

from sklearn.datasets import load_iris

from sklearn import tree

iris = load_iris()

#创建决策树分类器

clf = tree.DecisionTreeClassifier()

#训练

clf = clf.fit(iris.data, iris.target)

#graphviz 可视化树

import graphviz

dot_data = tree.export_graphviz(clf, out_file=None,

feature_names=iris.feature_names,

class_names=iris.target_names,

filled=True, rounded=True,

special_characters=True)

graph = graphviz.Source(dot_data)

生成的决策树如下所示,每个节点包括的数据结构如下:

  • 分类的不等式
  • 基尼系数
  • 样本个数
  • 每个类别的样本数list
  • 这个节点的类别

我们看到这棵树,树的深度,叶子节点数都很大,每个叶子节点含有的样本数有的只有1个样本,明显需要剪枝,下面看下剪枝参数如何设置。

04 剪枝决策树

clf = tree.DecisionTreeClassifier()这个构建决策树的构造函数,带有参数常用的包括如下:

  • criterion='gini', 选用基尼系数作为选择特征的分裂点
  • max_depth=None, 树的最大深度
  • min_samples_split=2, 分裂点的样本个数
  • min_samples_leaf =1, 叶子节点的样本个数
  • max_leaf_nodes=None,最大的叶子节点数

可以看到这个构造函数的参数,都包括了以上阐述的预剪枝的策略,sklearn强大。

如果参数的max_depth = 4,那么得到的决策树如下所示:

05 总结

以上我们分析了为什么需要对决策树剪枝,以及常见的剪枝策略都有哪些,以及在sklearn中如何可视化决策树,以及如何利用超参数剪枝决策树。

目前决策树都是用于数据集的分类的,那么决策树可不可以用于回归呢?

在用决策树回归时,存在以上所谓的剪枝操作或者有没有过拟合的风险呢?又怎么避免? 欢迎关注明天的推送。

让我们看一下远边的大海,和巍峨的高山,放松一下吧!

本文分享自微信公众号 - 算法channel(alg-channel)

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

原始发表时间:2017-11-20

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据处理

推导svm约束条件为等式求极值下面看看不等式约束,求极值,可行域变大了推导svmSVM—线性不可分—核函数

22540
来自专栏IT派

入门 | 关于神经网络:你需要知道这些

我们简单回顾一下神经网络的发展历程,如果你想了解更多关于其发展历程的信息,请看这篇维基百科的文章(https://en.wikipedia.org/wiki/A...

12320
来自专栏大数据文摘

手把手 | 30行JavaScript代码,教你分分钟创建神经网络

19030
来自专栏机器之心

入门 | 关于神经网络:你需要知道这些

20220
来自专栏AI2ML人工智能to机器学习

矩有四子

在讨论一些方法的几何意义之前需要理解一下线性代数的一个基础知识,就是矩阵和它代表的空间的含义。

14830
来自专栏人工智能LeadAI

文本与序列的深度模型 | 深度学习笔记

Rare Event 与其他机器学习不同,在文本分析里,陌生的东西(rare event)往往是最重要的,而最常见的东西往往是最不重要的。 语法多义性 一个东西...

491100
来自专栏量化投资与机器学习

【Python机器学习】系列之从线性回归到逻辑回归篇(深度详细附源码)

第1章 机器学习基础 将机器学习定义成一种通过学习经验改善工作效果的程序研究与设计过程。其他章节都以这个定义为基础,后面每一章里介绍的机器学习模型都是按照这个...

691100
来自专栏AILearning

【Scikit-Learn 中文文档】集成方法 - 监督学习 - 用户指南 | ApacheCN

1.11. 集成方法 注意,在本文中 bagging 和 boosting 为了更好的保留原文意图,不进行翻译estimator->估计器 base e...

86090
来自专栏智能算法

到底该如何选择损失函数?

机器学习中的所有算法都依赖于最小化或最大化某一个函数,我们称之为“目标函数”。最小化的这组函数被称为“损失函数”。损失函数是衡量预测模型预测期望结果表现的指标。...

38050
来自专栏用户3246163的专栏

2.1 统计基础

主要用在线性回归的时候来估计b1 unbiasedness: 估计的残差是随机的 efficiency:对比其他估计样本残差最小 consistency:样本增...

31030

扫码关注云+社区

领取腾讯云代金券