【Python机器学习】信息熵和在决策树中的运用(附源码)

之前在【Python机器学习】系列五决策树非线性回归与分类(深度详细附源码)一期中, 我们提到了用熵来度量信息的不确定性和信息增益。今天我们来详细解读一下什么是信息熵及其相关概念,以及如何进行信息增益的计算和它在decision tree中的运用。

信息熵与热力学熵

学过化学或热力学的同学可能了解热力学熵。 熵的概念由德国物理学家克劳修斯提出,其定义为:在一个可逆性程序里,被用在恒温的热的总数。宏观上,热力学熵主要用于研究热机,微观上,玻尔兹曼将其赋以统计学意义用以描述系统的混乱程度。而信息熵也称为香农熵, 香农于1948年将热力学中的熵的概念引入到信息论中,来度量信息中的信息量。与信息量相关的是信息的不确定性,如果一条信息中不确定性越大, 我们就希望获得更多的信息去消除不确定性并了解信息所想要表达的真正意思。因此对信息量的量化也可以理解为对一则信息不确定性的量化。

在吴军老师的《数学之美》一书中有这样的例子: 假如你totally错过了2010年的世界杯, 如果有人问你此届世界杯的冠军是谁,在没有任何提示下,你需要从32支队伍中猜出谁夺得了大力神杯。每猜一次需要花费1bit信息量,而提问者会回答:是或否。 如果你对32个球队一无所知(比如以为皇马也来参加了世界杯。。)并假定32支队伍夺冠几率相同,你可能会采取二分法来逐渐缩小范围。这样你总共需要花费5 bit 信息量,因为log 32 = 5。 而假如你对足球有一定的了解,会知道每个球队夺冠的概率是不一样的。那么根据香农熵的公式,准确信息量将应该是

条件熵(conditional entropy)

因为相关信息的存在也可以消除不确定性, 比如在自然语言模型中,相比于一元语言模型,二元语言模型除了参考词语本身的概率之外还要借助上下文的信息,因此结果更为准确。 假如说我们想要知道随机变量X的信息熵,同时我们已知在随机变量Y出现时X出现的概率(条件概率)和X,Y同时出现的概率(联合概率)这些信息, 那么我们计算在Y的条件下X的熵为:

这个熵不同于H(X), 被称为条件熵。 在X和Y不相互独立的时候,因为我们得到了Y的信息,我们确定X所需要的信息熵就下降了。 因此 H(X)>=H(X|Y)。

互信息(mutual information)

互信息是用来量化两个变量X,Y相关性的量。它的定义为:

互信息的意义为:由于事件X发生与事件Y发生相关联而提供的信息量。 I(X|Y)同时也是H(X)与条件熵H(X|Y)之间的差。

相对熵(Kullback-Leibeler Divergence)

相对熵又称KL散度,用来衡量两个取值为正数的函数的相关性。他的定义为:

相对熵具有如下性质:

1. 相对熵始终大于等于0,两个完全相同的函数相对熵为0

2. 相对熵不对称, 即KL(A||B)不等于KL(B||A)

2. 相对熵越大,函数差异越大

3. 相对熵可以度量两个随机分布之间的距离

相对熵常用来做文本相似度分析,以及在多指标系统中用来进行指标权重分配。

我们可以比较互信息和相对熵的概念,发现互信息是在求KL(P(x,y)||P(x)P(y))。当X 与Y相互独立时,P(x,y)=P(x)P(y)。所以当X与Y相互独立时互信息为0。从上面的韦恩图中也可以看出。

信息增益(Information Gain)

信息增益表示在条件a下,信息不确定性减少的量。与互信息不同的是,互信息衡量的是两个变量之间的相关性,而信息增益衡量的是系统分类后增加的信息量,a指的是分类方式。

算法

介绍完基本概念后,我们可以了解在决策树中常用的算法。算法主要有三种: ID3, C4.5以及CART。再此主要介绍ID3和C4.5.

ID3

ID3 是基于以信息熵和信息增益为衡量标准来选取属性进行分类的方式。其基本思路如下:

在决策树中,结点可以分为:根结点,内部结点,叶结点。在选取根结点和内部结点时,我们选择信息增益最大的属性。比如我们拥有一个training set数据集S其类别集合为{0,1},参与分类的属性集合为{A,B,C,D},那我们分别计算IG(S, A), IG(S,B), IG(S,C), IG(S,D)。按照上面的公式:IG(S,A)=H(S)-H(S|A) ,求得最大IG最大的属性,即可作为本次划分的结点。划分直至终结条件满足后,决策树构建完成。

终结条件主要分两种:

1 划分出的类为同类

2 所有属性已被考虑,不再有属性可供再分

在Machine Learning in Action 一书中有ID3的详细代码(python)

C4.5

C4.5是在ID3基础上的扩展,不同的是,C4.5用的是信息增益率来进行属性选择。信息增益率定义如下:

其中 Gain(S,A)=IG(S,A),就是信息增益

SplitInfo(S,A)指的是按照属性A对S的信息分裂值,用以将信息增益规范化,因此避免了ID3中指标偏向分支多的属性的倾向。C4.5算法框架如下:

参考文献: 《数学之美》-吴军[著] Machine Learning in Action --Peter Harrington http://blog.csdn.net/google19890102/article/details/28611225 http://shiyanjun.cn/archives/417.html http://isilic.iteye.com/blog/1844097

原文发布于微信公众号 - 量化投资与机器学习(ZXL_LHTZ_JQXX)

原文发表时间:2016-08-08

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

深度学习领域引用量最多的前20篇论文简介

20550
来自专栏机器之心

资源 | 吴恩达deeplearning.ai五项课程完整笔记了解一下?

机器之心整理 机器之心编译 参与:思源、路雪 自吴恩达发布 deeplearning.ai 课程以来,很多学习者陆续完成了所有专项课程并精心制作了课程笔记,在此...

50570
来自专栏机器之心

学界 | 稳定、表征丰富的球面变分自编码器

近期的研究为 NLP 的一系列任务建立了深度生成模型的有效性,包括文本生成(Hu et al., 2017; Yu et al., 2017)、机器翻译(Zha...

15050
来自专栏木东居士的专栏

【Andrew Ng 机器学习】Week 1(一):基本概念和线代基础

20720
来自专栏自然语言处理

一起走进条件随机场3(NLP重点理论)

注意:标记变量y是结构型变量,如在自然语言处理的句子标注任务中,观测数据为句子,标记为相应的词性序列,具有线性序列结构,在语法分析中,输出标记是语法树,具有树形...

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

推荐|深度学习领域引用最多的20篇论文,建议收藏!

深度学习是机器学习和统计学交叉领域的一个子集,在过去的几年里得到快速的发展。强大的开源工具以及大数据爆发使其取得令人惊讶的突破进展。本文根据微软学术(acade...

19950
来自专栏段石石的专栏

自然语言处理第一番之文本分类器

文本分类应该是自然语言处理中最普遍的一个应用,这篇文章主要从传统和深度学习两块来解释下我们如何做一个文本分类器。

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

【陆勤阅读】深度学习、自然语言处理和表征方法

简介 过去几年,深度神经网络在模式识别中占绝对主流。它们在许多计算机视觉任务中完爆之前的顶尖算法。在语音识别上也有这个趋势了。 虽然结果好,我们也必须思考……它...

319100
来自专栏段石石的专栏

基于深度学习和经典方法的文本分类

文本分类应该是自然语言处理中最普遍的一个应用,例如文章自动分类、邮件自动分类、垃圾邮件识别、用户情感分类等等,在生活中有很多例子,这篇文章主要从传统和深度学习两...

6.9K20
来自专栏数据派THU

一文读懂机器学习概率图模型(附示例和学习资源)

来源:机器之心 本文长度为10085字,建议阅读15分钟 本文结合基础应用示例系统性的为你讲解概率图模型。 概率图模型是人工智能领域内一大主要研究方向。近日,数...

1.8K90

扫码关注云+社区

领取腾讯云代金券