Peter教你谈情说AI | 07决策树(上)—既能回归又能分类的模型

决策树

前面我们讲了线性回归模型和朴素贝叶斯分类模型。前者只能做回归,后者只能做分类。但本文中要讲的决策树模型,却既可以用于回归,又可以用于分类。

什么是决策树:

决策树是一种非常基础又常见的机器学习模型。

一棵决策树是一个树结构,每个非叶节点对应一个特征,该节点的每个分支代表这个特征的一个取值,而每个叶节点存放一个类别或一个回归函数。使用决策树进行决策的过程就是从根节点开始,提取出待分类项中相应的特征,按照其值选择输出分支,依次向下,直到到达叶子节点,将叶子节点存放的类别或者回归函数的运算结果作为输出(决策)结果。

下图是一个决策树的例子:

这棵树的作用,是对要不要接受一个 Offer 做出判断。

我们看到,这棵树一共有7个节点,其中有4个叶子节点和3个非叶子节点。它是一棵分类树,每个叶子节点对应一个类别。从图中我们也可以看出,总共只有2个类别:accept offer(接受)和 decline offer(拒绝)。

以上例而言,拿到一个 Offer 后,要判断三个条件:(1)年薪;(2)通勤时间;(3)免费咖啡。这三个条件的重要程度显然是不一样的,最重要的是根节点,越靠近根节点,也就越重要——如果年薪低于5万美元,也就不用考虑了,直接 say no;当工资足够时,如果通勤时间大于一个小时,也不去那里上班;就算通勤时间不超过一小时,还要看是不是有免费咖啡,没有也不去。

该树按照根节点向下的顺序筛选一个个条件,直到到达叶子为止。到达的叶子所对应的类别就是预测结果。

这三个非叶子节点,统称决策节点,每个节点对应一个条件判断,这个条件判断的条件,我们叫做特征。上例是一个有三个特征的分类树。

构建决策树:

前面我们讲了,获得一种模型的过程叫训练,那么我们如何训练可以得到一棵决策树呢?

简单讲,有以下几步:

  1. 准备若干的训练数据(假设 m 个样本);
  2. 标明每个样本预期的类别;
  3. 人为选取一些特征(即决策条件);
  4. 为每个训练样本对应所有需要的特征生成相应值——数值化特征;
  5. 将通过上面的1-4步获得的训练数据输入给训练算法,训练算法通过一定的原则,决定各个特征的重要性程度,然后按照决策重要性从高到底,生成决策树。

那么训练算法到底是怎么样的?决定特征重要程度的原则又是什么呢?

常用算法

在讲算法前,我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性,越不确定的事物,它的熵就越大。具体的,随机变量X的熵的表达式如下:

其中n代表X的n种不同的离散取值。而pi代表了X取值为i的概率,log为以2或者e为底的对数。

熟悉了一个变量X的熵,很容易推广到多个个变量的联合熵,这里给出两个变量X和Y的联合熵表达式:

有了联合熵,又可以得到条件熵的表达式H(X|Y),条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下:

现在我们知道H(X)度量了X的不确定性,条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性,那么H(X)-H(X|Y)呢?从上面的描述大家可以看出,它度量了X在知道Y以后不确定性减少程度,这个度量我们在信息论中称为互信息,记为I(X,Y)。在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大,则越适合用来分类。

ID3 算法:

ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树,用计算出的信息增益最大的特征来建立决策树的当前节点。这里我们举一个信息增益计算的具体的例子。比如我们有15个样本D,输出为0或者1。其中有9个输出为1, 6个输出为0。 样本中有个特征A,取值为A1,A2和A3。在取值为A1的样本的输出中,有3个输出为1, 2个输出为0,取值为A2的样本输出中,2个输出为1,3个输出为0, 在取值为A3的样本中,4个输出为1,1个输出为0。

样本D的熵为:

样本D在特征下的条件熵为:

对应的信息增益为:

I(D,A)=H(D)−H(D|A)=0.083

下面我们看看具体算法过程大概是怎么样的。

输入的是m个样本,样本输出集合为D,每个样本有n个离散特征,特征集合即为A,输出为决策树T。

  1. 初始化信息增益的阈值ϵ
  2. 判断样本是否为同一类输出Di,如果是则返回单节点树T。标记类别为Di
  3. 判断特征是否为空,如果是则返回单节点树T,标记类别为样本中输出类别D实例数最多的类别。
  4. 计算A中的各个特征(一共n个)对输出D的信息增益,选择信息增益最大的特征Ag
  5. 如果Ag的信息增益小于阈值ϵ,则返回单节点树T,标记类别为样本中输出类别D实例数最多的类别。
  6. 否则,按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。
  7. 对于所有的子节点,令D=Di,A=A−{Ag}递归调用2-6步,得到子树Ti并返回。

ID3 算法的不足:

ID3算法虽然提出了新思路,但是还是有很多值得改进的地方。

  1. ID3没有考虑连续特征,比如长度,密度都是连续值,无法在ID3运用。这大大限制了ID3的用途。
  2. ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现,在相同条件下,取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值,各为1/2,另一个变量为3个值,各为1/3,其实他们都是完全不确定的变量,但是取3个值的比取2个值的信息增益大。如果校正这个问题呢?
  3. ID3算法对于缺失值的情况没有做考虑
  4. 没有考虑过拟合的问题

可以看出ID3算法有四个主要的不足,一是不能处理连续特征,第二个就是用信息增益作为标准容易偏向于取值较多的特征,最后两个是缺失值处理的问和过拟合问题。

但是C4.5算法在这几个方面进行了弥补,我们下一节来看看C4.5算法。

原文发布于微信公众号 - 人人都是极客(rrgeek)

原文发表时间:2018-10-31

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据派THU

从零开始教你训练神经网络(附公式、学习资源)

来源:机器之心 作者:Vitaly Bushaev 本文长度为8900字,建议阅读15分钟 本文从神经网络简单的数学定义开始,沿着损失函数、激活函数和反向传播等...

217100
来自专栏专知

【干货】走进神经网络:直观地了解神经网络工作机制

【导读】1月4日,Mateusz Dziubek发布了一篇基础的介绍神经网络的博文,作者用一种直观的方法来解释神经网络以及其学习过程,作者首先探讨了导致神经网络...

388130
来自专栏SIGAI学习与实践平台

循环神经网络综述-语音识别与自然语言处理的利器

循环神经网络是一种具有记忆功能的神经网络,适合序列数据的建模。它在语音识别、自然语言处理等领域取得了成功。是除卷积神经网络之外深度学习中最常用的一种网络结构。在...

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

深度学习理论系列之——模型方法

深度学习的模型方法及应用 上一次我发了关于深度学习基本理论与方法的文章,大家反响还不错,今天继续 上次的知识,对深度学习再做一些基础性的理论介绍,希望大家多多指...

26860
来自专栏专知

【计算机视觉】检测与分割详解

【导读】神经网络在计算机视觉领域有着广泛的应用。只要稍加变形,同样的工具和技术就可以有效地应用于广泛的任务。在本文中,我们将介绍其中的几个应用程序和方法,包括语...

16630
来自专栏企鹅号快讯

几种循环神经网络介绍

基于图展开和参数共享的思想,我们可以设计各种循环神经网络。 ? 计算循环网络(将 x值的输入序列映射到输出值 o 的对应序列) 训练损失的计算图。损失L 衡量每...

38990
来自专栏书山有路勤为径

目标检测(Object detection)

这次我们学习构建神经网络的另一个问题,定位分类问题。这意味着我们不仅需要判断图片中是不是一辆车,还要在图片中将他标记出来。“定位”的意思是判断汽车在图片中的具体...

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

你看到的最直白清晰的,神经网络中的反向传播法讲解

最近在看深度学习的东西,一开始看的吴恩达的UFLDL教程,有中文版就直接看了,后来发现有些地方总是不是很明确,又去看英文版,然后又找了些资料看,才发现,中文版的...

32750
来自专栏石瞳禅的互联网实验室

【TensorFlow实战——笔记】第3章:TensorFlow第一步_TensorFlow实现Softmax Regression识别手写数字

MNIST(Mixed National Institute of Standards and Technology database)是一个非常简单的机器视觉...

7600
来自专栏人工智能

从零开始教你训练神经网络

来源:机器之心 作者:Vitaly Bushaev 本文长度为8900字,建议阅读15分钟 本文从神经网络简单的数学定义开始,沿着损失函数、激活函数和反向传播等...

32390

扫码关注云+社区

领取腾讯云代金券