第一节 信息、熵及信息增益的概念
一、信息及其度量
克劳德·艾尔伍德·香农，美国数学家、电子工程师和密码学家，被誉为信息论的创始人。他发表了划时代的论文——通信的数学原理，奠定了现代信息论的基础。不仅如此，香农还被认为是数字计算机理论和数字电路设计理论的创始人。香农对信息的描述是“信息是用来消除随机不确定性的东西”。
信息是消息中包含的有效内容，那么如何度量离散消息中所含的信息量？其度量的基本原则有三点，一是能度量任何消息，并与消息的种类无关；二是度量方法应该与消息的重要程度无关；三是消息中所含信息量和消息内容的不确定性有关。
例如，《儒林外史》中范进中举后发疯。为什么会发疯，因为范进中举是小概率事件，小概率事件越成为现实，表明其信息含量越大，故使得范进认为这是天外之喜，喜极而疯。如果消息是“今天下雨”，那么这句话的信息含量极低，因为下不下雨已成现实，无需提及。
如果用数学语言来表述，度量信息量的方法可表示如下：
设为消息发生的概率，为消息中所含的信息量。则和之间应该有如下关系：
①是的函数：
②大，则小；小，则大；，；，。
③。
那么同时满足以上三个要求的函数关系是什么呢？香农给出的定义是，如果带分类的事物集合可以划分为多个类别当中，则某个类的信息可以定义如下：
那么，为什么一件事发生后所携带的信息量要表示成事件发生概率的对数？简单来讲，和之间的性质②决定了信息量和概率之间一定是减函数的关系，性质③要求他们之间是对数关系，因为只有对数关系才能使此式成立：。
由以上论述可以感悟②②的是，大数据技术中数学建模的重要性，同样重要的还有数学的抽象思维。比如根据性质前①②点，可知和应是负相关关系，根据③性质可基本联想到对数公式的加法运算，同学们可以试着用此模式建模一些社会问题，也许才是机器学习真正的趣味所在。
对于，作为上式的底，其含义为：
若，信息量的单位称为比特[bit]，可简记为；
若，信息量的单位称为奈特[nat]；
若，信息量的单位称为哈特莱[Hartley]。通常广泛使用的单位是比特。
二、信息熵
香农定义的信息熵的计算公式如下：
其中表示随机变量，随机变量的取值为，表示发生的概率，且有，信息熵的单位为bit。
从香农给出的数学公式可以看出，信息熵其实是一个随机变量信息量的数学期望。
当熵中的概率由数据估计（特别是最大似然估计）得到时，所对应的熵称为经验熵（empirical entropy）。所谓数据估计，是指通过训练数据计算得出的分类概率值，比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据已有的数据数出来的。
设训练数据集为，则训练数据集的经验熵为，表示样本容量，即样本个数。设有个类，，为属于类的样本个数，则经验熵可以写为：
例如，假设有天气状态与是否打球关系的数据集，其数据集为：
| outlook | temperature | humidity | windy | play |
| sunny | hot | high | FALSE | no |
| sunny | hot | high | TRUE | no |
| overcast | hot | high | FALSE | yes |
| rainy | mild | high | FALSE | yes |
| rainy | cool | normal | FALSE | yes |
| rainy | cool | normal | TRUE | no |
| overcast | cool | normal | TRUE | yes |
| sunny | mild | high | FALSE | no |
| sunny | cool | normal | FALSE | yes |
| rainy | mild | normal | FALSE | yes |
| sunny | mild | normal | TRUE | yes |
| overcast | mild | high | TRUE | yes |
| overcast | hot | normal | FALSE | yes |
| rainy | mild | high | TRUE | no |
本数据集共14条数据，最终分类结果分为两类，即打球（yes）和不打球（no）。根据数据统计可知，在14个数据中，9个数据的结果为打球，5个数据的结果为不打球。所以数据集的经验熵为：
经过计算可知，数据集的经验熵的值为0.9403。
三、条件熵、信息增益及信息增益比
条件熵表示在已知随机变量的条件下随机变量的不确定性，随机变量给定的条件下随机变量Y的条件熵（conditional entropy），定义给定条件下的条件概率分布的熵对的数学期望为：
其中，
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令。
以上述数据集为例，目标变量，特征变量
,则的条件熵的计算步骤为：
由于特征变量在数据集中又分为三类，分别为，需要分别计算。根据条件熵定义，则计算公式为：
首先计算，则数据子集为：为：
| 为： | 为： | 为： | 为： | 为： |
| 为： | 为： | 为： | 为： | 为： |
| 为： | 为： | 为： | 为： | 为： |
| 为： | 为： | 为： | 为： | 为： |
| 为： | 为： | 为： | 为： | 为： |
| 为： | 为： | 为： | 为： | 为： |
。
数据子集为：
| outlook | temperature | humidity | windy | play |
| overcast | hot | high | FALSE | yes |
| overcast | cool | normal | TRUE | yes |
| overcast | mild | high | TRUE | yes |
| overcast | hot | normal | FALSE | yes |
，条件熵为0，代表无随机性，确定性很强，均为打球（yes）。
数据子集为：
| outlook | temperature | humidity | windy | play |
| rainy | mild | high | FALSE | yes |
| rainy | cool | normal | FALSE | yes |
| rainy | cool | normal | TRUE | no |
| rainy | mild | normal | FALSE | yes |
| rainy | mild | high | TRUE | no |
则
信息增益：信息增益是相对于特征而言的。所以，特征对训练数据集的信息增益，定义为集合的经验熵与特征给定条件下的经验条件熵之差，即：
根据以上计算，特征对训练数据集的信息增益为：
信息增益比：特征对训练数据集的信息增益比定义为其信息增益与训练数据集的经验熵之比：