专栏首页讲编程的高老师一篇文章搞懂机器学习中决策树的那些事儿

一篇文章搞懂机器学习中决策树的那些事儿

决策树是一颗好树,是一颗可以帮我们做决策的树。

所有的机器学习算法中,决策树应该是最友好的了。它呢,在整个运行机制上可以很容易地被翻译成人们能看懂的语言,也因此被归为“白盒模型”。

它不像神经网络这类算法喜欢用隐藏层搞暗箱操作,它呢相对较为磊落,最后训练出来的树,比较容易为人所理解。

01

直观理解

假设我们开个小店,我们想看看我们小店某一天的销量的高低到底和什么事情有关系?

我们凭经验觉得销量高低可能会和天气好坏、是否周末、是否有促销活动这几个方面有关联,我们把这些数据记录下来,如下图所示。

那如果要人工分析这个事,该怎么办呢?

我们先从是否周末入手,按“是否周末”分成的两类;然后在是周末的所有的里面再看天气好坏,如果发现是周末、并且天气好这两个条件同时满足的情况下,销量一定好。

更进一步地,就可以得到下面这样一个图。

上图中,有圆角矩形、矩形、线段。

你看那个圆角矩形,它就已经是最后的结果了,不再往下了,这一类东西呢,在决策树里叫做叶节点

那个矩形呢,总是要往下分,并不是最终的结果,它叫做中间节点(或内部节点)。

那些带有文字的线段(一般使用有箭头的有向线段),线的一端连的是中间节点、另一端连的是另一个中间节点或叶节点,然后线段上还有文字,它叫做

到这里,你可能已经看出来了。所有的内部节点都是自变量、叶节点是因变量的值,而边呢是自变量可能的取值。有了这棵树,那我们知道了明天天气情况、是否周末、是否有促销活动我们就可以预测明天的销量高低,可以提前备货。或者说,如果我们库存有积压,我们应该怎样提高销量尽快把货销出去。

自变量的取值可能不止两种,比如判断一个学生是不是好学生,他的成绩就是一个比较重要的自变量,而成绩的可能取值是[0,100]。那成绩节点就会有100条边出来么?也不一定,前面的文章我们说过,这个时候需要对成绩这个量进行离散化,可能会分成“不及格”D、“及格”C、“良好”B、“优秀”A等。

Python实现KMeans算法

数据离散化及其KMeans算法实现的理解

那,我们整理上面图里那样的决策树的时候,发现还有两个问题:

  1. 我们选哪个作为根节点?
  2. 根节点选定后,我们怎样再选中间节点?
  3. 最后的叶节点又是怎样确认的?到什么程度呢?
  4. 我们怎样把这个事弄的更细致,能够让计算机来实现。

02

算法描述

从01中的描述知道,决策树从根节点到叶节点,越往下,最后那个因变量的取值越单一。也就是说,越往下的节点它因变量取某一个值的可能性越大,到达叶节点的时候这个可能性达到最大。

我们用最直接、最笨拙的步骤可以实现这个事:

  1. 选择一个自变量作为节点,从一个边引出一个取值(属性值)看这个值对应的变量的值若为空或者单一值,边的另一端生出一个叶结点;
  2. 否则,对生出一个内部结点,即测试结点;
  3. 在2的基础上选择新属性进行划分,直至得到条件1。

大家可以对照上面步骤的说法,把01中介绍的例子画成决策树的样子。

上面这种朴素的算法很容易想到,但是太容易得到的它往往不够美好。如果自变量很多的时候,我们该选哪个作为根节点呢?选定了根节点后,树再往下生长接下来的内部节点该怎么选呢?针对这些问题,衍生了很多决策树算法。

我们常见的有ID3、C4.5、C5.0等不同的算法来绘制决策树,如下图所示:

限于篇幅,我们只讲ID3算法,不过你理解了ID3其它的也就很容易看明白了。

03

ID3算法

ID3算法在02中介绍的那种朴素的决策树算法(CLS)的基础上解决了属性选择的问题。

内部节点的每个属性值都会引出一条边来,那到底哪个好呢?这里要引入一个叫“信息增益“的概念。

信息增益这个事可以用一大堆公式来说明,也可以先有个感性的认识。要记住,我们的目标呢就是希望让节点在去某个属性的时候能更快生长出叶节点。换句话说,就是节点的某个属性能让我们更有信心预测因变量的取值。以01中的例子来说,如果”是否周末“这个节点取”是“能让我们更容易得出销量高这个结论,那它的信息增益就高。

如果再往下深究,要想了解信息增益还要知道熵的概念。

这个公式看着挺麻烦的,其实就是为了定量地描述一件事实:一个事情它的随机性越大就越难预测。具体来说这个概率p越小,最后熵就越大(也就是信息量越大),如果极端情况一件事情概率为1,它的熵就变成0了。

熵越大,随机性越大,如果能准确预测它的取值意义就越大;反之,就没啥意义了。比如,你如果能预测一个彩票的中奖号码就发达了;但是,如果你能预测明天太阳从东边升起来则毫无价值。这样衡量一个信息价值的事,就可以由熵来表示。

那如果我们在进行决策树绘制的时候,如果能够迅速的让这个熵变小,是不是就意味着我们可以迅速的找到那个概率接近1的叶节点了呢?事实就是这样,就是好所谓的信息增益最大的那条路。

那这个增益是谁和谁的差呢?它是自变量在取确定的值之前的熵与取确定值之后的熵的这个差值。好比,在不知道明天是否天气好的情况下熵是H1,知道了明天天气好坏之后的熵为H2,那么H1-H2就是这个信息增益。条件熵的计算公式为:

其中,H(X|yi)为后验熵,它们的具体算法看下面的例子。

再来看一个更容易理解的例子:假设我们记录了某个学校14届校运会按时举行或取消的记录,举行或者取消的概率分别为:9/14、5/14,那么它的信息熵为:

我们同时记录了当天的天气情况,发现天气好坏和校运会举行还是取消有关。14天中,5次晴天(2次举行、3次取消)、5次雨天(3次举行、2次取消)、4次阴天(4次举行)。相对应的晴天、阴天、雨天的后验熵

那知道天气情况后校运会的条件熵为:

那么相对应的在有没有天气情况这个条件前后的信息增益就是:

那相对应的ID3的算法很容易就可以想出来了:

  1. 在所有的自变量里面找一个信息增益最大的作为节点;
  2. 节点的每种取值看它的熵,如果熵为零,对应一个叶子节点

比如下面这样的一个过程,可以画出决策树(参考1)。

04

总结

有几个比较有意思的概念:熵(先验熵)、后验熵、条件熵、信息增益。以及对应的ID3算法。

参考:

  1. https://blog.csdn.net/robin_Xu_shuai/article/details/74011205
  2. https://zhuanlan.zhihu.com/p/26486223

本文分享自微信公众号 - 讲编程的高老师(codegao),作者:石头

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-10

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 神经网络用来解决什么问题的?—ML Note 44

    “Neural Networks: Representation——Non-linear hypotheses”。

    讲编程的高老师
  • 了解一下“算法”,每个人都要掌握的编程知识

    假设我们有一个难题需要解决,那怎么解决呢?解决的步骤怎样呢?如果有一样东西能把这个解决这个难题的步骤描述出来,那就叫做这个问题的算法。

    讲编程的高老师
  • 与大脑有关的一些让人震惊的实验—ML Note45

    “Neural Networks: Representation——Neurons and the brain”。

    讲编程的高老师
  • AQS : waitStatus = Propagate 的作用解析 以及读锁无法全获取问题

    当然,下面这篇文章也需要读者对源码有一定了解,本文不贴大量源码,因为本文不是源码解析。

    执生
  • 架构设计之「 CAP 定理 」

    在计算机领域,如果是初入行就算了,如果是多年的老码农还不懂 CAP 定理,那就真的说不过去了。CAP可是每一名技术架构师都必须掌握的基础原则啊。

    奎哥
  • Zookeeper基本功能和应用场景

    Zookeeper是一个开源的分布式的,为分布式应用提供协调服务的Apache项目。是大数据Hadoop生态体系中用的非常广泛的基础组件

    用户1212940
  • 手把手:四色猜想、七桥问题…程序员眼里的图论,了解下?(附大量代码和手绘)

    大数据文摘
  • redis实战第二篇 哨兵 redis sentinel

    redis sentinel解决主从复制高可用问题 非高可用状态下故障处理 一个主节点、两个从节点 1)主节点发生故障,客户端连接主节点失败,两个从节点和...

    我是李超人
  • Zookeeper 分布式协调服务介绍

    分布式系统的简单定义:分布式系统是一个硬件或软件组件分布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的系统。

    小旋锋
  • 重温数据结构:树 及 Java 实现

    数据结构,指的是数据的存储形式,常见的有线性结构(数组、链表,队列、栈),还有非线性结构(树、图等)。 今天我们来学习下数据结构中的 树。 什么是树 线性结构中...

    张拭心 shixinzhang

扫码关注云+社区

领取腾讯云代金券