决策树入门教程


1 数学基础

    1.1 概率论入门

    1.2 Bootstrap抽样方法

    1.3 对数的深刻认识

    1.4 信息与信息熵

    1.5 偏差与方差

    1.6 信息增益

    1.7 基尼不纯度

2 决策树基础知识

    2.1 决策树概述

    2.2 ID3算法简介

    2.3 C4.5算法简介

    2.4 CART算法简介

信息与信息熵

创建时间:2022-04-01 | 更新时间:2022-04-20 | 阅读次数:1663 次

1、什么是信息?

信息这个概念分为广义和狭义,这是理解信息论的关键第一步,混淆了广义和狭义,则后面的理解将会变得非常难。

广义的信息,指是我们能看到的图片和文字,以及能听到的声音等,泛指人类社会传播的一切内容。狭义的信息,专指通信系统中的被传输的信号。这是理解香农的信息论的基础。

香农的伟大之处在于将信息这个东西,从狭义的角度出发,给出了数学化的分析。而且,这个数学分析的角度也是极其狭窄:信息是用来消除随机不定性的东西。在香农的眼睛里,信息就是用来表示“有”和“无”的东西。这就是为什么信息的度量是以2为底的$log$函数。能够将信息的定义,简化到如此程度,也只有香农一个人做到了。在香农之前,也有人提出了类似的关于信息的计算公式,但是没有人像香农一样,将信息的定义和内涵做得如此简单,所以香农能开创一个时代,而其他人都没有与之比肩。

我们不能以广义的角度去理解信息,因为我们看到的图片和文字都有可以度量的方式,这种度量的方式(几张图片、几个字符等),与信息论中的信息熵是没有任何关系的。

另外,我们不能把信号当做信息。信号在电子系统是通过开关系统实现的,是通过0和1来实现的。但是,这个0和1不等于信息论中的比特bit。

2、 信息熵

人类对自然世界的认知迈出了三大步:质量、能量和信息量。

人们很早就知道用秤或者天平计量物质的质量,而对能力的认知则是到了19世纪中叶,随着热力学和动力学的发展,以及能量守恒定律的建立才逐渐清楚。能量一词就是热和功的总称,而能量的计量则通过“卡里路、焦耳”等新单位的出现而得到解决。

备注:卡是卡路里的简称,我们往往将卡路里与食品联系在一起,但实际上它们适用于含有能量的任何物质。路里的定义是将1克水在一个大气压下,温度升高1摄氏度所需要的能量或热量。由于后来科学家发现水在不同温度下的比热容不同,也就是说不同温度的水升高同样1度,需要的热量并不相同,因此,卡的定义就不准确了。取而代之的焦耳,焦耳的定义是1牛顿的力作用在力的方向上移动1米距离所作的功。焦耳和卡可以换算, 1 卡 = 4.184 焦耳。

然而,关于文字、数字、图画、声音的知识已有几千年历史了,但是它们的总称是什么,它们如何统一地计量,直到19世纪末还没有被正确地提出来,更谈不上如何去解决了。

20世纪初期,随着电报、电话、照片、电视、无线电、雷达等的发展,如何计量信号中信息量的问题被隐约地提上日程。

1928年哈特利考虑到从$D$个彼此不同的符号中取出N个符号并且组成一个“词”的问题。如果各个符号出现的概率相同,而且是完全随机选取的,就可以得到$D^N$个不同的词。从这些词里取了特定的一个就对应一个信息量I。哈特利建议用$N log D$这个量表示信息量,即$I=N log D$。这里的$log$表示以$10$为底的对数。

后来,香农横空出世,在他的通信数学模型中,清楚地提出信息的度量问题,他把哈特利的公式扩大到概率$p_i$不同的情况,得到了著名的计算信息熵H的公式:

$$H(X)=-\sum p_ilog_2p_i$$

香农在进行信息的定量计算的时候,明确地把信息量定义为随机不定性程度的减少。这就表明了他对信息的理解:信息是用来减少随机不定性的东西。

3、信息熵公式为什么底数为2?

正如上文所示,香农的伟大之处在于将信息这个东西,从狭义的角度出发,给出了数学化的分析。而且,这个数学分析的角度也是极其狭窄:信息是用来消除随机不定性的东西。在香农的眼睛里,信息就是用来表示“有”和“无”的东西。这就是为什么信息的度量是以2为底的$log$函数。

4、香农理论的局限性

虽然香农的信息概念比以往的认识有了巨大的进步,但仍存在局限性,这一概念同样没有包含信息的内容和价值,只考虑了随机型的不定性,没有从根本上回答"信息是什么"的问题。

事实上,香农最初的动机是把电话中的噪音除掉,他给出通信速率的上限,这个结论首先用在电话上,后来用到光纤,截止2013年又用在无线通信上。我们能够清晰地打越洋电话或卫星电话,都与通信信道质量的改善密切相关。

5、信息熵应用举例

信息论最初所处理的问题是数据压缩与传输领域中的问题,其处理方法利用了熵和互信息等基本量,它们是通信过程的概率分布的函数。

如果随便变量$X$的概率密度函数为$p(x)$,那么$X$的熵的定义为

$H(X)=-\sum\limits_{x}p(x)log_2p(x)$

使用以2为底的对数函数,熵的单位是比特。熵可以看做是随机变量的平均不确定度的度量。在平均意义下,它是为了描述该随机变量所需要的比特数。

假设有8匹马参加一场赛马比赛,设8匹马的获胜概率分布为$( \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{64}, \frac{1}{64}, \frac{1}{64}, \frac{1}{64})$。我们可以计算出该场赛马的熵为:

$$H(X)=-\frac{1}{2}log_2\frac{1}{2}-\frac{1}{4}log_2\frac{1}{4}-\frac{1}{8}log_2\frac{1}{8}-\frac{1}{16}log_2\frac{1}{16}-4\frac{1}{64}log_2\frac{1}{64}=2 bits $$