从熵概念到决策树算法

源 / 顶级程序员 文 / 数据挖掘机

一、 熵

熵可以认为是对无序的一种度量,熵越大越无序,熵越小越有序。

信息熵是将熵的理论应用于信息混乱度的描述,在随机变量中可以描述随机变量不确定性的程度,在机器学习的样本集合中,可以用于描述样本集合的纯度。

假定样本集合D中第k类样本所包含的样本数所占总样本数的比例为则D的信息熵可以定义为:

此文,可以以一个实际例子来做说明,该样本集合较简单,样本如下:

从上述样本集合中可以看出,该样本共有四个属性,分别为outlook、temperature、humidity、windy,最终分类结果只有两个,yes和no,即建模的目的就是根据天气情况来判断当前是否适合出去运动。那么,根据前面介绍的方法,就可以利用熵这个指标来描述一下当前样本集合D的混乱程度,本文的计算将全部使用python语言来描述:

所以,训练集合D在未进行分类的情况下,其样本集合的熵为0.94。

二、 决策树算法

了解了熵的概念以后,就可以引出今天我们主要的话题,决策树算法了,决策树算法是机器学习算法中较常用的一种算法,该算法最常用于分类问题,比如根据西瓜的根蒂、纹理来判断该瓜是熟瓜还是不熟瓜等,决策树算法较为简单、易于理解,并且其结果最终又可以总结成规则,是一种应用十分广泛的算法。

首先,先介绍一下决策树算法,然后再展开具体讲每个细节,决策树算法最终生成的结果是一颗树,其中节点是属性,节点间的分支是该属性对应的值,从根到叶子结点就是一个判断的流程。

决策树学习的基本算法如下:

输入:训练集D={(x1,y1),(x2,y2),(x3,y3),…,(xm,ym)}

属性集A={a1,a2,a3,…,ad}

过程:函数TreeGenerate(D,A)

1、 生成节点node

2、 如果D中样本全部属于同一个类别C then将node标记为C类叶节点并 返回

3、 如果A=或者D中样本在A上的取值均相同,则将node标记为叶节点, 其类别标记为D中样本最多的类

4、 如果上面两个条件不存在,在需要根据属性来划分,从A中选择最优 划分属性(如何找到最优划分属性后面讲解),对于中的每一个属性 里面的值都可以将样本集合D生成一个分支,且可以用来表示在上取 值为的样本子集

5、 如果为空,则将该分支节点标记为叶节点,其类别标记为D中样本最 多的类(因为为空,没有类别,用父类别)

6、 如果不为空,则继续递归执行TreeGenerate(,A\{})

根据上面的步骤就可以构造出一颗决策树,不过,里面有一点也是非常重要的一点就是如何去不断找到最优属性,也就是此时需要有一个衡量标准,能够根据这个标准来衡量那个属性可以作为最优属性,此时就引入了信息增益的概念:

上面的公式就是决策树算法的信息增益。

其中D表示样本集D,假定属性a有v个可能的取值(离散或连续){a1,a2,a3,a4,…,aV},在选择最优划分属性的时候,比如先找到了a属性,然后接着需要计算下并比较下a属性是否是最优划分属性,也就是需要给属性a一个打分,属性a判断完成后,接着再判断下一个属性,给每个属性都一个打分,然后选择得分最高的那个作为最优划分属性,于是,当拿到属性a的时候,根据a的不同取值(1到v)就可以把样本集D划分成v个样本子集,然后每个值对应的样本子集又有一个或者多个类别,就可以计算出这个值的样本子集所对应的熵,将所有值对应的样本子集的熵相加就变成了这个属性a的熵,即,又因为不同的取值所分成的样本集合数量不同,越多的,说明此种情况更容易出现,所以可以给每个值对应的熵加上一个所占比例的权重,用来表示,则属性a划分数据集D的熵就是,此时a的熵越小,说明划分能力越强,然后此时可以用一个减少量去衡量,即使用上面公式来衡量,因为对于数据集D而言,Ent(D)是固定的,所以减去的数值越小就越大,即减少量就越大,即就可以用于衡量该属性划分能力的强弱,且该值越大,划分能力越强,于是通过该值可以对所有属性进行选择了,不过这只是ID3算法的标准,本文将以最简单的ID3为例子讲解。

好了,到这里决策树基本算法的东西就讲完了,这样看来决策树算法还是很简单易懂的,不过后面还有剪枝和调参数的很多东西,此时,可以先根据上面的理论得到前面天气数据集的最优划分属性:

从上面的计算结果可以看出,四个属性分别计算了其信息增益后,outlook的值最大,可以作为最优划分属性,于是就是该决策树的根节点root。

接着,再根据上面的算法来找到不同分支的子节点:

此时,用属性outlook划分样本后,三个属性值把样本集合D分成了三部分,分别为D-sunny,D-overcast、D-rainy,

其中,D-sunny为:

此时,再用另外三个属性划分这个小样本集D-sunny

计算各自信息增益:

所以,该数据集再进行划分的时候,选择的最优属性为humidity,

使得humidity=sunny时,数据集变成如下,此时可以看到最终分类结果均为同一种类别,无需划分,此时humidity=normal时为叶子结点

同样的,humidity=high时:

该节点同样属于同一类别,无需划分,即humidity完成了D-sunny的划分,生成了如下分支:

outlook = sunny
|   humidity = high: no (3.0)
|   humidity = normal: yes (2.0)

然后,D-overcast数据集就变成了:

此时,满足上面所讲算法的步骤2,此时D-overcast属于同一类别,将该节点标志为叶子节点,并且类别为样本最多的类别,即yes:

outlook = overcast: yes (4.0)

然后,D-rainy为:

好了,从这里可以看出,使用outlook进行划分的时候,前两个值,sunny和overcast已经都形成了最终分支,此时只需对这个数据集划分完成,一颗决策树就形成了,所以,依旧按照前面的方法求信息增益:

所以,此时最优划分属性变成了windy,上面属性集又可以根据windy的不同取值变成两个子集:

从上面可以看出,windy=False和windy=True的时候,这两个子集都把原来的集合划分成了两个同一类别,即满足了算法中2的步骤,即生成了如下分支:

outlook = rainy
|   windy = TRUE: no (2.0)
|   windy = FALSE: yes (3.0)

Bingo!到此为止,所有分支都按照算法的步骤生成完成,最终的分类树如下:

outlook = sunny
|   humidity = high: no (3.0)
|   humidity = normal: yes (2.0)
outlook = overcast: yes (4.0)
outlook = rainy
|   windy = TRUE: no (2.0)
|   windy = FALSE: yes (3.0)
Number of Leaves  : 5
Size of the tree : 8

即最终决策树为:

这就是今天要讲的ID3决策树算法,也就是最基本的决策树算法,后面随着算法改进又出现了C4.5、CART等算法,这些算法将再以后继续讲解。

-END-

原创声明:本文由「顶级程序员」原创

原文发布于微信公众号 - 顶级程序员(TopCoding)

原文发表时间:2018-04-28

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

开发 | 深度学习自动编码器还能用于数据生成?这篇文章告诉你答案

AI 科技评论按:本文作者廖星宇,原载于作者知乎专栏,经授权发布。 什么是自动编码器 自动编码器(AutoEncoder)最开始作为一种数据的压缩方法,其特...

2234
来自专栏WD学习记录

机器学习 学习笔记(10)序列最小最优化算法

序列最小最优化算法(Sequential minimal optimization)

1432
来自专栏人工智能LeadAI

花式解释AutoEncoder与VAE

什么是自动编码器 自动编码器(AutoEncoder)最开始作为一种数据的压缩方法,其特点有: 1、跟数据相关程度很高,这意味着自动编码器只能压缩与训练数据相似...

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

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

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

2769
来自专栏AI研习社

深度学习自动编码器还能用于数据生成?这篇文章告诉你答案

什么是自动编码器 自动编码器(AutoEncoder)最开始作为一种数据的压缩方法,其特点有: 跟数据相关程度很高,这意味着自动编码器只能压缩与训练数据相似...

3706
来自专栏PPV课数据科学社区

这是一份文科生都能看懂的线性代数简介

选自Medium 作者:Niklas Donges 机器之心编译 参与:Tianci LIU、思源 线性代数的概念对于理解机器学习背后的原理非常重要,尤其是在深...

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

梯度提升树GBDT原理

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

4146
来自专栏杂文共赏

深度学习图像标注

图像标注(Image Captioning)是产生图像文字描述的过程。使用了自然语言处理和计算机视觉去产生描述。

4504
来自专栏人工智能

机器学习实战之决策树

一、简介 决策树是一类常见的机器学习方法,以二分类任务为例,我们希望从给定训练数据集学得一个模型用以对新数据进行分类,比如通过一组数据通过模型训练得到以下的决策...

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

机器学习(25)之K-Means聚类算法详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 前言 K-Means算法是无监督的聚...

6658

扫码关注云+社区

领取腾讯云代金券