[b]一、信息及其度量[br][br][br][/b] 克劳德·艾尔伍德·香农，美国数学家、电子工程师和密码学家，被誉为信息论的创始人。他发表了划时代的论文——通信的数学原理，奠定了现代信息论的基础。不仅如此，香农还被认为是数字计算机理论和数字电路设计理论的创始人。香农对信息的描述是“信息是用来消除随机不确定性的东西”。[br][br] 信息是消息中包含的有效内容，那么如何度量离散消息中所含的信息量？其度量的基本原则有三点，一是能度量任何消息，并与消息的种类无关；二是度量方法应该与消息的重要程度无关；三是消息中所含信息量和消息内容的不确定性有关。[br][br] 例如，《儒林外史》中范进中举后发疯。为什么会发疯，因为范进中举是小概率事件，小概率事件越成为现实，表明其信息含量越大，故使得范进认为这是天外之喜，喜极而疯。如果消息是“今天下雨”，那么这句话的信息含量极低，因为下不下雨已成现实，无需提及。

如果用数学语言来表述，度量信息量的方法可表示如下：[br][br]设[math]p\left(x\right)[/math]为消息发生的概率，[math]I[/math]为消息中所含的信息量。则[math]\:p\left(x\right)[/math]和[math]I[/math]之间应该有如下关系：[br][br] ①[math]I[/math]是[math]p\left(x\right)[/math]的函数：[math]I=I\left[p\left(x\right)\right][/math][br][br] ②[math]p\left(x\right)[/math]大，则[math]I[/math]小；[math]p\left(x\right)[/math]小，则[math]I[/math]大；[math]p\left(x\right)=1[/math]，[math]I=0[/math]；[math]p\left(x\right)=0[/math]，[math]I=\infty[/math]。[br][br] ③[math]I\left[p\left(x_1\right)p\left(x_2\right)...\right]=I\left[\:p\left(x_1\right)\right]+I\left[p\left(x_2\right)\right]+...[/math]。

那么同时满足以上三个要求的函数关系是什么呢？香农给出的定义是，如果带分类的事物集合可以划分为多个类别当中，则某个类[math]x_i[/math]的信息可以定义如下：[br][br] [math]I\left(X=x_i\right)=-log_ap\left(x_i\right)[/math][br][br] 那么，为什么一件事发生后所携带的信息量要表示成事件发生概率的对数？简单来讲，[math]p\left(x\right)[/math]和[math]I[/math]之间的性质②决定了信息量和概率之间一定是减函数的关系，性质③要求他们之间是对数关系，因为只有对数关系才能使此式成立：[math]log_2\left(p\left(x_1\right)p\left(x_2\right)\right)=log_2p\left(x_1\right)+log_2p\left(x_2\right)[/math]。

由以上论述可以感悟②②的是，大数据技术中数学建模的重要性，同样重要的还有数学的抽象思维。比如根据性质前①②点，可知[math]p\left(x\right)[/math]和[math]I[/math]应是负相关关系，根据③性质可基本联想到对数公式的加法运算，同学们可以试着用此模式建模一些社会问题，也许才是机器学习真正的趣味所在。

对于[math]I\left(X=x_i\right)=-log_ap\left(x_i\right)[/math]，[math]a[/math]作为上式的底，其含义为：[br][br] 若[math]a=2[/math]，信息量的单位称为比特[bit]，可简记为[math]b[/math]；[br][br] 若[math]a=e[/math]，信息量的单位称为奈特[nat]；[br][br] 若[math]a=10[/math]，信息量的单位称为哈特莱[Hartley]。通常广泛使用的单位是比特。

[b] 二、信息熵[br][br][/b][br] 香农定义的信息熵的计算公式如下：[br][br] [math]H\left(x\right)=-\sum p\left(x_i\right)log\left(p\left(x_i\right)\right)[/math][math]\left(i=1,2,...,n\right)[/math][br][br] 其中[math]x[/math]表示随机变量，随机变量的取值为[math]\left(x_{1,}x_2,...,x_n\right)[/math]，[math]p\left(x_i\right)[/math]表示[math]x_i[/math]发生的概率，且有[math]\sum p\left(x_i\right)=1[/math]，信息熵的单位为bit。

从香农给出的数学公式可以看出，信息熵其实是一个随机变量信息量的数学期望。[br][br] 当熵中的概率由数据估计（特别是最大似然估计）得到时，所对应的熵称为经验熵（empirical entropy）。所谓数据估计，是指通过训练数据计算得出的分类概率值，比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据已有的数据数出来的。

设训练数据集为[math]D[/math]，则训练数据集[math]D[/math]的经验熵为[math]H\left(D\right)[/math]，[math]|D|[/math]表示样本容量，即样本个数。设有[math]K[/math]个类[math]C_k[/math]，[math]K=1,2,3...,k[/math]，[math]\mid C_k\mid[/math]为属于类[math]C_k[/math]的样本个数，则经验熵可以写为：[br] [br] [math]H\left(D\right)=-\sum\frac{\mid C_k\mid}{\mid D\mid}log_2\frac{\mid C_k\mid}{\mid D\mid}[/math][br][br] 例如，假设有天气状态与是否打球关系的数据集，其数据集[math]D[/math]为：

[center][/center][table][tr][td]outlook[/td][td]temperature[/td][td]humidity[/td][td]windy[/td][td]play[/td][/tr][tr][td]sunny[/td][td]hot[/td][td]high[/td][td]FALSE[/td][td]no[/td][/tr][tr][td]sunny[/td][td]hot[/td][td]high[/td][td]TRUE[/td][td]no[/td][/tr][tr][td]overcast[/td][td]hot[/td][td]high[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]mild[/td][td]high[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]cool[/td][td]normal[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]cool[/td][td]normal[/td][td]TRUE[/td][td]no[/td][/tr][tr][td]overcast[/td][td]cool[/td][td]normal[/td][td]TRUE[/td][td]yes[/td][/tr][tr][td]sunny[/td][td]mild[/td][td]high[/td][td]FALSE[/td][td]no[/td][/tr][tr][td]sunny[/td][td]cool[/td][td]normal[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]mild[/td][td]normal[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]sunny[/td][td]mild[/td][td]normal[/td][td]TRUE[/td][td]yes[/td][/tr][tr][td]overcast[/td][td]mild[/td][td]high[/td][td]TRUE[/td][td]yes[/td][/tr][tr][td]overcast[/td][td]hot[/td][td]normal[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]mild[/td][td]high[/td][td]TRUE[/td][td]no[/td][/tr][/table]

本数据集共14条数据，最终分类结果分为两类，即打球（yes）和不打球（no）。根据数据统计可知，在14个数据中，9个数据的结果为打球，5个数据的结果为不打球。所以数据集[math]D[/math]的经验熵[math]H\left(D\right)[/math]为：[br][br] [math]H\left(D\right)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.9403[/math][br] [br] 经过计算可知，数据集[math]D[/math]的经验熵[math]H\left(D\right)[/math]的值为0.9403。

[b] 三、条件熵、信息增益及信息增益比[br][br][/b][br] 条件熵[math]H\left(Y\mid X\right)[/math]表示在已知随机变量[math]X[/math]的条件下随机变量[math]Y[/math]的不确定性，随机变量[math]X[/math]给定的条件下随机变量[math]Y[/math]Y的条件熵（conditional entropy）[math]H\left(Y\mid X\right)[/math]，定义[math]X[/math]给定条件下[math]Y[/math]的条件概率分布的熵对[math]X[/math]的[color=#0000ff]数学期望为：[/color][br][br] [math]H\left(Y\mid X\right)=[/math][br] [br] 其中， [math]p_i=P\left(X=x_i\right)[/math]

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令[math]0log_20=0[/math]。

以上述数据集[math]D[/math]为例，目标变量[math]Y=\left\{play\right\}[/math]，特征变量[br][br][math]X=\left\{outlook,temperature,humidity,windy\right\}[/math],则[math]X_{outlook}[/math]的条件熵[math]H\left(Y_{play}\mid X_{outlook}\right)[/math]的计算步骤为：[br][br] 由于[math]outlook[/math]特征变量在数据集中又分为三类，分别为[math]sunny,overcast,rainy[/math]，需要分别计算。根据条件熵定义，则计算公式为：[br][br] [math]H\left(Y_{play}\mid X_{outlook}\right)=P_{sunny}H\left(Y_{play}\mid X_{sunny}\right)+P_{overcast}H\left(Y_{play}\mid X_{overcast}\right)+P_{rainy}H\left(Y_{play}\mid X_{rainy}\right)[/math][br][br] 首先计算[math]H\left(Y_{play}\mid X_{sunny}\right)[/math]，则数据子集为：[math]D_{outlook-sunny}[/math]为：

[center][/center][table][tr][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][/tr][tr][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][/tr][tr][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][/tr][tr][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][/tr][tr][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][/tr][tr][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][td]为：[/td][/tr][/table]

[math]H\left(Y_{play}\mid X_{sunny}\right)=-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.971[/math]。[br][br]数据子集[math]D_{outlook-overcast}[/math]为：

[center][/center][table][tr][td]outlook[/td][td]temperature[/td][td]humidity[/td][td]windy[/td][td]play[/td][/tr][tr][td]overcast[/td][td]hot[/td][td]high[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]overcast[/td][td]cool[/td][td]normal[/td][td]TRUE[/td][td]yes[/td][/tr][tr][td]overcast[/td][td]mild[/td][td]high[/td][td]TRUE[/td][td]yes[/td][/tr][tr][td]overcast[/td][td]hot[/td][td]normal[/td][td]FALSE[/td][td]yes[/td][/tr][/table]

[math]H\left(Y_{play}\mid X_{overcast}\right)=-\frac{4}{4}log_2\frac{4}{4}=0[/math]，条件熵为0，代表无随机性，确定性很强，均为打球（yes）。[br]数据子集[math]D_{outlook-rainy}[/math]为：

[center][/center][table][tr][td]outlook[/td][td]temperature[/td][td]humidity[/td][td]windy[/td][td]play[/td][/tr][tr][td]rainy[/td][td]mild[/td][td]high[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]cool[/td][td]normal[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]cool[/td][td]normal[/td][td]TRUE[/td][td]no[/td][/tr][tr][td]rainy[/td][td]mild[/td][td]normal[/td][td]FALSE[/td][td]yes[/td][/tr][tr][td]rainy[/td][td]mild[/td][td]high[/td][td]TRUE[/td][td]no[/td][/tr][/table]

[math]H\left(Y_{play}\mid X_{rainy}\right)=-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.971[/math][br][br]则[math]H\left(Y_{play}\mid X_{outlook}\right)=\frac{5}{14}\ast0.971+\frac{4}{14}\ast0+\frac{5}{14}\ast0.971=0.6935[/math]

[b] 信息增益：[/b]信息增益是相对于特征而言的。所以，特征[math]X[/math]对训练数据集[math]D[/math]的信息增益[math]\:\:g\left(D,X\right)[/math]，定义为集合[math]D[/math]的经验熵[math]H\left(D\right)[/math]与特征[math]X[/math]给定条件下[math]D[/math]的经验条件熵[math]H\left(D\mid X\right)[/math]之差，即：[br][br] [math]g\left(D,X\right)=H\left(D\right)-H\left(D\mid X\right)[/math][br] 根据以上计算，特征[math]\:outlook[/math]对训练数据集[math]D[/math]的信息增益为：[br] [br] [math]g\left(D,X_{outlook}\right)=0.9403-0.6935=0.2468[/math]

[b] 信息增益比：[/b]特征[math]X[/math]对训练数据集[math]D[/math]的信息增益比[math]g_R\left(D,X\right)[/math]定义为其信息增益[math]g\left(D,X\right)[/math]与训练数据集[math]D[/math]的经验熵之比：[br][br][math]g_R\left(D,X\right)=\frac{g\left(D,X\right)}{H\left(D\right)}[/math]