全面总结机器学习项目和面试中几乎绕不开的决策树

定义

决策树是一种常见的机器学习算法,它的思想十分朴素,类似于我们平时利用选择做决策的过程。

例如有人给我们介绍新的对象的时候,我们就要一个个特点去判断,于是这种判断的过程就可以画成一棵树,例如根据特点依次判断:

如上,决策的形式以树的形式进行示意和编码,就形成了决策树。

结构

显然,决策树在逻辑上以树的形式存在,包含根节点、内部结点和叶节点

  • 根节点:包含数据集中的所有数据的集合
  • 内部节点:每个内部节点为一个判断条件,并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果,内部节点对应的数据的集合别分到两个或多个子节点中。
  • 叶节点:叶节点为最终的类别,被包含在该叶节点的数据属于该类别。

简而言之,决策树是一个利用树的模型进行决策的多分类模型,简单有效,易于理解。

伪代码

决策树算法的伪代码(参照了python语法)如下图所示:

 1# D = {(x1,y1)、(x2,y2)......(xm,yn)} 是数据集
 2# A = {a1、a2、a3.} 是划分节点的属性集
 3# 节点node有两个主要属性:content代表该节点需要分类的训练集,type代表叶节点的决策类型
 4def generateTree(D,A):
 5    newNode = 空 #生成新的节点
 6    # 如果当前数据集都为一个种类,则设为一个叶节点并返回
 7    if D 中数据皆属于类别 C:
 8        newNode.content = D
 9        newNode.type = C
10        return    
11    # 如果已经没有属性了或者数据集在剩余属性中表现相同(属性无法区分)
12    if A = 空集 or D中数据在A中取值相同:
13        newNode.content = D
14        newNode.type = D中最多的类
15        return
16    #从A中选取最优的属性a
17    a=selectBestPorperty(A)
18    #为a的每一个取值生成一个节点,递归进行处理
19    for a的每一个取值 res[i]:
20        生成新的分支节点 node[i]
21        D[i] = D中取值为res[i]的数据
22        node[i].content = D[i]
23        if node[i].content == null:
24            node[i].type = D中最多的类
25        else:
26            generateTree(D[i],A - {a})
27    return        

划分选择

可以看到,在伪代码中,大部分步骤都是简单而明确的,而最重要的步骤在于从A中选取最优的属性a,可以说,属性选择的质量,决定了决策树的预测准确度。这很容易理解,例如我们看一个学生聪明与否可以看他的成绩,但是如果依靠他的身高预测他是否聪明,显然得不到好的结果。

一般的原则是,希望通过不断划分节点,使得一个分支节点包含的数据尽可能的属于同一个类别,即“纯度“越来越高。

这里列出三种常用的准则。

信息增益准则

我们先对一个节点的纯度进行定义,我们将其称之为信息熵

其中

代表当前节点D的数据中第k类样本所占的比例。

观察该信息熵的定义,有以下几个特点:

都属于[0,1],Ent(D)必定为正值,值越大说明纯度越低

  • Ent(D)在k=1=1时取值最小值0,

时取值最大值

  • 信息熵是一个节点的固有性质,和该节点选取什么属性进行下一步的划分无关

在定义了信息熵之后,对信息增益进行定义,假设选取属性a有V个取值,

,按照决策树的规则,D将被划分为V个不同的节点数据集,

代表其中第v个节点:

观察该式,有以下几点说明:

  • Ent(D)是确定的,和选取的属性a无关,我们可以将之看为定值

表示分支节点所占的比例大小,显然数据集越大的分支节点权重越高

  • 分支节点整体纯度越大,则后一项越小,信息增益Gain变得越大,所以我们的目标是如何最大化信息增益

由此,我们得到了一种选择划分属性的方法,计算以每个属性进行划分子节点得到的信息增益,选择其中最大的作为选择的属性。

信息增益率准则

信息增益原则对于每个分支节点,都会乘以其权重,也就是说,由于权重之和为1,所以分支节点分的越多,即每个节点数据越小,纯度可能越高。这样会导致信息熵准则偏爱那些取值数目较多的属性

为了解决该问题,这里引入了信息增益率,定义如下:

相当于引入了修正项IV(a),它是对于属性a的固有值。

需要注意的是,信息增益率原则可能对取值数目较少的属性更加偏爱,为了解决这个问题,可以先找出信息增益在平均值以上的属性,在从中选择信息增益率最高的

基尼指数准则

在CART决策树中,使用基尼指数来选择属性,首先定义数据集D的基尼值:

形象的说,基尼值代表了从D中随机选择两个样本,其类别不一致的概率。

有了基尼值后,可以在此基础上定义基尼指数:

其的含义和之前相同,可以看出基尼指数越小,说明纯度越高,我们可以通过选择基尼指数小的属性来划分子节点。

剪枝

剪枝是应该决策树过拟合的一种重要方法,主要分为以下两种:

  • 预剪枝:该策略就是在对一个节点进行划分前进行估计,如果不能提升决策树泛化精度,就停止划分,将当前节点设置为叶节点。那么怎么测量泛化精度,就是留出一部分训练数据当做测试集,每次划分前比较划分前后的测试集预测精度。
  • 优点:降低了过拟合风险,降低了训练所需的时间。
  • 缺点:预剪枝是一种贪心操作,可能有些划分暂时无法提升精度,但是后续划分可以提升精度。故产生了欠拟合的风险。
  • 后剪枝:该策略是首先正常建立一个决策树,然后对整个决策树进行剪枝。按照决策树的广度优先搜索的反序,依次对内部节点进行剪枝,如果将某以内部节点为根的子树换成一个叶节点,可以提高泛化性能,就进行剪枝。
  • 优先:降低过拟合风险,降低欠拟合风险,决策树效果提升比预剪枝强
  • 缺点:时间开销大得多

特殊值处理

连续值处理

在之前进行选择属性的时候,我们仅仅讨论了属性值为离散值的情况,例如身高分为“极高、高、较高、中等、较矮”五个选项,但是如果数据集中身高为连续值,例如140-210cm,我们该如何处理呢?

这里可以采用二分的思想,将连续值化为离散值。由于我们的数据集是有限的,即使是连续值,属性a在数据集中也只出现了有限个确定的值,记为

,且

取n个值的中点,令

我们得到了n-1个中点,

,任取一个值

可以将数据集D分为两个,

表示D中大的数据,

表示D中小的数据集合,这样,我们便可以同离散值一样进行处理了

接下来的问题是,选取哪一个t呢?显然在信息增益准则下,应该选择使得信息增益最大的t:

经过稍加改造的信息增益公式就可以选择最好的t来进行划分。

缺失值处理

缺失值处理较为复杂,设计到较多的公式,在这里给出链接,读者可以参考阅读

https://blog.csdn.net/u012328159/article/details/79413610

其主要思想是

  • 在选择属性时,仅使用不缺失该属性的数据来计算信息增益,最后乘以一个代表缺失数据比例的比例系数
  • 在对某个属性进行划分子节点时,对于不缺失该属性的数据正常划分,对于缺失该属性的数据,按不同的权重划分进行每个子节点

多变量决策树

实际上大部分机器学习的分类算法,都是将一个具有n个属性的数据,看成一个在n维空间的一个点,分类的过程就是在n维空间或者更高维度空间中找到超平面,将这些点进行划分

而普通的决策树算法有一个特点,由于它每个节点的划分条件都是单独的,明确的,所以决策树的决策边界是平行于空间的坐标轴的。如下图所示:

这对其拟合特性有一定的影响,当数据比较复杂时,需要较多的属性才能得到较好的划分,而多变量决策树就可以解决该问题。

在多变量决策树的学习过程中,不是为每个非叶结点寻找一个最优划分属性,而是试图建立一个合适的线性分类器。 如下图所示:

多变量决策树较复杂,如果想进一步了解,可以阅读这个领域的论文。

查看更多

作者:陈浩然,欢迎阅读她的博客:chrer.com,她的机器学习系列笔记:

北大才女总结:机器学习的概念、历史和未来

北大才女笔记:这样学习线性回归和梯度下降(上篇)

北大陈浩然笔记:特征缩放和泛化能力(下篇)

logistics判别与线性模型中的4个问题

原文发布于微信公众号 - Python与机器学习算法频道(alg-channel)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

分类回归树算法---CART

一、算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相...

4359
来自专栏Astropeak

基于隐马尔科夫模型的中文分词方法

本文主要讲述隐马尔科夫模及其在中文分词中的应用。 基于中文分词语料库,建立中文分词的隐马尔科夫模型,最后用维特比方法进行求解。

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

梯度提升树GBDT原理

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 作者:雪伦_ 链接:http://b...

4106
来自专栏智能算法

分类回归树算法---CART

一、算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相...

6838
来自专栏小鹏的专栏

为什么很多做人脸的Paper会最后加入一个Local Connected Conv?

Deep face:论文。 a. 人脸检测,使用6个基点 b. 二维剪切,将人脸部分裁剪出来 c. 67个基点,然后Delaunay三角化,在轮廓处添加三角形来...

3415
来自专栏机器之心

深度 | 从各种注意力机制窥探深度学习在NLP中的神威

作者 Antoine Tixier 表示整篇综述笔记也是他学习过程的一部分,所以这一文章还会在 arXiv 上继续更新。为了完成整篇文章,作者主要借鉴了各种卷积...

1053
来自专栏老秦求学

基于Keras的imdb数据集电影评论情感二分类

二分类可能是机器学习最常解决的问题。我们将基于评论的内容将电影评论分类:正类和父类。

3333
来自专栏机器学习、深度学习

物体计数--Learning To Count Objects in Images

Learning To Count Objects in Images NIPS 2010 http://www.robots.ox.ac.uk/~v...

2669
来自专栏desperate633

小白也能看懂的BP反向传播算法之Surpass Backpropagation

上篇文章小白也能看懂的BP反向传播算法之Further into Backpropagation中,我们小试牛刀,将反向传播算法运用到了一个两层的神经网络结构中...

1642
来自专栏机器之心

教程 | 基础入门:深度学习矩阵运算的概念和代码实现

选自Medium 机器之心编译 参与:蒋思源 本文从向量的概念与运算扩展到矩阵运算的概念与代码实现,对机器学习或者是深度学习的入门者提供最基础,也是最实用的教...

43713

扫码关注云+社区

领取腾讯云代金券