《机器学习》笔记-决策树(4)

作者:刘才权

编辑:黄俊嘉

写在最前面

如今机器学习和深度学习如此火热,相信很多像我一样的普通程序猿或者还在大学校园中的同学,一定也想参与其中。不管是出于好奇,还是自身充电,跟上潮流,我觉得都值得试一试。对于自己,经历了一段时间的系统学习(参考《机器学习/深度学习入门资料汇总》),现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书,并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录,同时,也会增加自己的理解,包括过程中的疑问,并尽量的和实际的工程应用和现实场景进行结合,使得知识不只是停留在理论层面,而是能够更好的指导实践。记录笔记,一方面,是对自己先前学习过程的总结和补充。 另一方面,相信这个系列学习过程的记录,也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

  • 基本流程
  • 划分选择
  • 减枝处理
  • 连续与缺失值
  • 多变量决策树

1

基本流程

一般的,一颗决策树包含一个根节点,若干个内部节点和若干个叶子节点;叶子节点对应决策结果,其他每个节点对应一个属性测试;每个节点包含的样本集合根据属性测试的结果被划分到子节点中;根节点包含样本全集,从根节点到每个叶子节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强,即处理未见示例能力强的决策树,基本形式如下图所示(判别习惯是否为好瓜的决策树):

2

划分选择

决策树学习的关键,是如何选择最优划分属性。一般而言,随着划分过程的不断进行,我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”越来越高。

信息增益

2.1

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。假定当前集合D中第k类样本所占的比例为pk(k=1,2,...,|y|),则D的信息熵定义为,

Ent(D)的值越小,则D的纯度越高。假定离散属性a有V个可能的取值,

若使用a来对样本集合D进行划分,则会产生V个分支节点,其中第v个分支点包含了D中所有在属性a上取值为a(v)的样本,记为D(v)。根据信息熵可计算出属性a对样本集D进行划分所获得的“信息增益”(information gain),

一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此,我们可用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性的。

增益率

2.2

信息增益准则对可取值数目较多的属性有所偏好,为了减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益,而使用“增益率”(gain ratio)来选择最优划分属性。增益率定义为,

其中,

基尼指数

2.3

CART决策树使用“基尼指数”(Gini index)来选择划分属性,

直观说,Gini(D)反应了从数据集D中随机抽取两个样本,其类别标记不一致的概率。因此,Gini(D)越小,则数据集D的纯度越高。

3

剪枝处理

剪枝(pruning)是决策树学习算法对付”过拟合“的主要手段。

决策树剪枝的基本策略有”预剪枝“(prepruning)和”后剪枝“(post-pruning)。预剪枝是指在决策树生成过程中,对每个节点在划分前进行估计,若当前的划分不能带来决策树泛化性能提升,则停止划分并将当前节点标记为叶节点;后剪枝是先从训练集生成一颗完整的决策树,然后自底向上的对非叶节点进行考察,若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升,则将该子树替换为叶节点。

剪枝处理降低了”过拟合“风险,但也带来了”欠拟合“的风险。

一般情形下,后剪枝决策树欠拟合风险较小,泛化性能往往优于预剪枝决策树。但后剪枝训练开销比未剪枝决策树和预剪枝决策树都要大很多。

4

连续与缺失值

到目前为止我们讨论了基于离散属性来生成决策树。现实学习任务中常会遇到连续属性。此时 ,连续属性离散化技术可派上用场。最简单的策略是采用二分法(bi-partition)。

现实任务中常会遇到不完整样本,即样本的某些属性值缺失。我们需要解决两个问题:

  • 如何在属性值缺失的情况下进行划分属性选择?
  • 给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?

5

多变量决策树

若我们把每个属性视为坐标空间的一个坐标轴,则d个属性描述的样本就对应了d维空间的一个数据点,对样本分类则意味着在这个坐标空间中寻找不同样本之间的分类边界。决策树所形成的分类边界有一个明显的特点:轴平行(axis-parallel),即它的分类边界由若干个与坐标轴平行的分段组成。

显然,分类边界的每一段都与坐标轴平行的。这样的分类边界使得学习结果又较好的可解释性,因为每一段划分都直接对应了某个属性取值。但在学习任务的真实分类边界比较复杂时,必须使用很多段划分才能取得较好的近似,此时的决策树会相当复杂,由于要进行大量的属性测试,预测时间开销会很大。

若能使用斜的划分边界,则决策树模型将大为简化。“多变量决策树”(multivariate decision tree)就是能实现这样的“斜划分”甚至更负责划分的决策树。如下图所示,

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2018-02-07

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏磐创AI技术团队的专栏

粒子群优化算法(PSO)之基于离散化的特征选择(FS)(二)

前面我们介绍了特征选择(Feature Selection,FS)与离散化数据的重要性,总览的介绍了PSO在FS中的重要性和一些常用的方法。今天讲一讲FS与离散...

3155
来自专栏Petrichor的专栏

论文阅读: FPN

基于深度网络的检测算法出来之前,检测算法基本都是基于这种scale handling;后来出现的SNIP、SNIPER也是基于Image Pyramid。 ...

1112
来自专栏数说工作室

logistic回归:从生产到使用【下:生产篇】

logistic回归:从生产到使用【下:生产篇】 上篇介绍了logistic模型的原理,如果你只是想使用它,而不需要知道它的生产过程,即拟合方法及编程实现,那么...

2855
来自专栏派森公园

机器学习101(译)

2247
来自专栏专知

【最新前沿】Facebook何恺明等大神最新论文提出非局部神经网络(Non-local Neural Networks)

【导读】Facebook何恺明和RGB两位大神最近提出非局部操作non-local operations为解决视频处理中时空域的长距离依赖打开了新的方向。文章采...

3684
来自专栏磐创AI技术团队的专栏

使用Keras进行深度学习:(五)RNN和双向RNN讲解及实践

1673
来自专栏计算机视觉战队

CVPR 2018 论文简单笔记 II

该文章主要是在detection当中引入了relation的信息,个人感觉算是个很不错的切入点,而且motivation是源自NLP的,某种方面也说明了知识宽度...

913
来自专栏AI研习社

用GAN来做图像生成,这是最好的方法

前言 对于图像问题,卷积神经网络相比于简单地全连接的神经网络更具优势。 本文将继续深入 GAN,通过融合卷积神经网络来对我们的 GAN 进行改进,实现一个深...

3104
来自专栏和蔼的张星的图像处理专栏

DSST详解

有一段时间没有看tracking了,前面一个月老师没有找,我也没有看文章,主要去看c++和cs231n去了。上周一老师找了我一次,于是赶紧把tracking又拾...

882
来自专栏Petrichor的专栏

深度学习: Nonlinear (非线性)

902

扫码关注云+社区