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

相关文章

来自专栏机器之心

LSTM、GRU与神经图灵机:详解深度学习最热门的循环神经网络

选自MachineLearningMastery 作者:Jason Brownlee 机器之心编译 参与:熊猫 循环神经网络是当前深度学习热潮中最重要和最核心的...

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

【算法】xgboost算法

小编邀请您,先思考: 1 XGBoost和GDBT算法有什么差异? XGBoost的全称是 eXtremeGradient Boosting,2014年2月诞生...

3209
来自专栏JasonhavenDai

统计学习方法之K近邻法1.k近邻法(k-nearest neighbor,k-NN)2.k近邻模型3.k近邻算法的实现

1.k近邻法(k-nearest neighbor,k-NN) k近邻算法是一个基本分类和回归方法,k-NN的输入时实例的特征向量,对应于特征空间的点,输出是...

2775
来自专栏智能算法

GBDT(梯度提升决策树)算法(详细版)

一、前言 通过之前的文章GBDT算法(简明版)对GBDT的过程做了大概的讲解,我们可以了解到GBDT是一种迭代的决策树算法,由多棵决策树组成,所有树的结论累加起...

42511
来自专栏marsggbo

论文笔记系列-Neural Architecture Search With Reinforcement Learning

神经网络在多个领域都取得了不错的成绩,但是神经网络的合理设计却是比较困难的。在本篇论文中,作者使用 递归网络去省城神经网络的模型描述,并且使用 增强学习训练RN...

843
来自专栏CDA数据分析师

Python环境下的8种简单线性回归算法

本文中,作者讨论了 8 种在 Python 环境下进行简单线性回归计算的算法,不过没有讨论其性能的好坏,而是对比了其相对计算复杂度的度量。 GitHub 地址:...

1609
来自专栏人工智能LeadAI

零基础入门深度学习 |最终篇:递归神经网络

无论即将到来的是大数据时代还是人工智能时代,亦或是传统行业使用人工智能在云上处理大数据的时代,作为一个有理想有追求的程序员,不懂深度学习(Deep Learni...

4455
来自专栏AI科技大本营的专栏

实战 | 速度快3倍,大小仅1/4,这项技术教你多快好省搭建深度学习模型

一般来说,神经网络层数越深、参数越多,所得出的结果就越精细。但与此同时,问题也来了:越精细,意味着所消耗的计算资源也就越多。这个问题怎么破?这就要靠剪枝技术了。...

34614
来自专栏编程

Python环境下的8种简单线性回归算法

选自Medium 作者:Tirthajyoti Sarkar 机器之心编译 参与:晏奇、刘晓坤 本文中,作者讨论了 8 种在 Python 环境下进行简单线性回...

1899
来自专栏北京马哥教育

Python环境下的8种简单线性回归算法

GitHub 地址:https://github.com/tirthajyoti/PythonMachineLearning/blob/master/Linea...

990

扫描关注云+社区