《机器学习》笔记-决策树(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 条评论
登录 后参与评论

相关文章

来自专栏UAI人工智能

轻松读论文——层规范化技术 Layer Normalisation

1713
来自专栏大数据挖掘DT机器学习

机器学习算法总结(面试用到)

找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习...

6769
来自专栏算法channel

机器学习逻辑回归:原理解析及代码实现

? 前到现在为止,我们通过大约1周的时间初步对机器学习是怎么一回事算是有一些基本的理解了,从最基本的线性回归入手,讨论了如何在拿到一堆数据时,先进行数据预处理...

2707
来自专栏IT派

常见面试之机器学习算法思想简单梳理

导语:今天小编从别的地方推送一篇更广泛的文章供你们学习参考,总结的常见机器学习算法(主要是一些常规分类器)大概流程和主要思想,希望对大家找机器学习岗位时有点帮助...

3577
来自专栏数据科学与人工智能

机器学习算法总结(面试用到)

找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据挖掘之类,且...

6808
来自专栏深度学习计算机视觉

神经网络学习之M-P模型

概念 所谓M-P模型,其实是按照生物神经元的结构和工作原理构造出来的一个抽象和简化了的模型,它实际上就是对单个神经元的一种建模。 ? 生物神经元模型 1. ...

3845
来自专栏机器之心

入门 | 一文了解什么是语义分割及常用的语义分割方法有哪些

2177
来自专栏机器学习算法与Python学习

干货 | 机器学习算法大总结(ML岗面试常考)

键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 找工作时(IT行业),除了常见的软件...

3726
来自专栏大数据挖掘DT机器学习

机器学习算法总结(面试用到)

找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据...

3745
来自专栏个人分享

最大期望算法 Expectation Maximization概念

在统计计算中,最大期望(EM,Expectation–Maximization)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中...

1122

扫码关注云+社区