信息量的直观概念

现在我们来猜一个古人，给你三句话，你来比较一下他们的信息量：
1、他是《水调歌头(明月几时有)》的作者。
2、他是唐宋八大家之一。
3、他是宋朝人。
这几句话谁的信息量大，谁的信息量少呢？第一句话可以确定这个人是谁，第二句话确定不了，但是有八个人符合条件，而第三句话，符合条件的人就太多了。直觉上，我们觉得第一句话信息量最大，第二句话差一点，但是比第三句话的信息量要多。
现在，我们就有了一个对于信息量的比较的直观概念，那就是，符合这个描述的对象的个数越多，则其提供的信息也就越少。如果将x作为符合这个信息的可能的对象的个数，用f(x)来表示这个信息的信息量，目前直观上，我们能知道f(x)是一个减函数。
但我们不满足于这样一个性质，我们很希望这个f(x)是可以量化的，可以有一个函数表达式的。

混乱度的直观概念

为了量化信息量，我们来思考一下，问题2和问题3的区别是什么。问题1肯定是最好的状态，即：立刻就可以猜出这个人是谁。而问题2和问题3都不能立刻猜出，他们的区别在于，我们如果得到2的信息，我们可以在少量几次追问就可以判断这个人了，而得到3的信息，我们可能需要更多的追问。
因此，我们定义混乱度的一个直观概念为：为了确定这个信息具体的描述对象，我们需要多少次追问。
敏锐的同学可能很快就能依靠直觉得出答案，从n个描述对象中找到正确的对象，平均追问次数最少的方案是二分法，追问次数为。在敏锐的同学得出答案的同时，稳重的同学已经拿出纸笔去严格证明这个结论了。本文面向的对象是不太敏锐又不太稳重的那部分同学，这部分人既不爱背公式也不爱枯燥的严格证明。因此我们不需要证明二分法对所有策略都是最优的，只大致比较一下二分策略与“一个一个问”的策略的优劣就行了。一个一个问时，最优情况是立刻就问对了，但是这种情况的概率也很低，最差情况是问到最后一个才问对。平均需要问n/2次。而二分法，平均只需要问次，从直觉上来说，二分法就是最优的。
回到猜人的问题上，问题1的复杂度为,也就是不需要再问了。问题2的复杂度为,也就是说为了保证确定的一个人，还需要再问3个问题才行。而对于问题3，需要问的问题就更多了。

熵的直观概念

有了混乱度的直观概念，熵其实可以定义为某种状态下的平均混乱度，或者说，这个状态下平均要问多少次可以得到确切答案。
如果一个状态A在一个系统中发生的概率是p(x), 比如说，1/8，那么直观上我们认为这个确切值在"一个一个问"的策略下，平均8次可以问出来，也就是说，1/p(x)次。然后，我们用二分法的话，也就是, 即。也就是说，如果状态A真的发生了，我们需要次追问就可以确定了。但是这个状态本身发生概率是,所以这个数要乘上这种情况发生的概率。也就是应用全概率公式，对于系统中所有可能发生的状态，总的平均需要追问的次数为：

这就是熵的定义了，确切地说，是信息熵。数据一致性越高，熵就越低，数据越乱七八糟，熵就越高。熵就是数据的混乱程度的度量。

决策树用熵来干啥

数据集D如果有n个属性，第i个属性有种可能的取值，那么，只要构建一个高为n的决策树，每一层随机挑选一个属性进行子结点划分，最后产生一颗拥有个叶子结点的子树。根据叶子结点对应的属性在数据集D中的标签比较最高的作为该叶子结点的标签，这样的决策树称为完全决策树。
很显然，所有完全决策树对于分类问题来说是等价的，而且任一分支的属性先后顺序对结果是没有影响的。
那么，决策树用熵这个概念到底来做什么？
聪明的同学可能已经发现了，完全决策树虽然是可用的，但是通常它比较大，很多时候分到某个程度以后，整个数据集都只有一个标签了，没必要再细分了，也就是剪枝。而在某个完全决策树上位置不相邻的两个叶子结点，也可能拥有相同的标签，并且这两个叶子结点在其他的某个完全决策树上因为属性的先后顺序不同可能是相邻的，这种“通过调整属性判断的先后顺序，将相同但不相邻的两个叶子结点调整到一起，并且剪枝”的做法，称为属性顺序调整。
决策树用熵的公式，就是来做这两件事的。
对于剪枝，我们可以用熵来判断这个数据还有没有比较继续分下去了，如果低于某个阈值，我们就认为可以剪枝了。
对于属性顺序调整，我们是采取了贪心算法，即：我们每次都要求选用那个对混乱度总度量降低最有效的那个属性。
比如，我们当前的混乱度为H(X), 我们希望某个属性将我们的数据分成份，然后他们的平均混乱度比当前的混乱度低，并且算出来低多少的。然后比较待选属性中用谁来拆分数据能够降得更低，即我们要选的属性。

条件熵

现在将当前的数据集按照标签X分，混乱度表示为：

如果当前的数据集先按照属性Y分，对于每一个具体地分支y，我们有
, 再用一下全概率公式，我们有

这个东西就叫条件熵。
它度量了先按照Y来分，在每个具体的y中按照X来得到混乱度，然后再用y的出现的概率来做全概率公式。
条件熵是先用属性Y来分得到的，如果不用属性Y来分，那么我们就会用其他属性来分，可能得到不同的条件熵，决策树是找到其中最小的那个对应的属性来区分数据，这样也就体现了贪心算法。

联合熵

我们之前说过，从直觉上来看，对于完全决策树来说，属性的顺序的变更跟结果应该是无关的。
条件熵对X和Y是有先后顺序的，所以其实H（X|Y）和H(Y|X)是不同的，但是，我们知道按照（X，Y）一起分类，得到的结果一样与（Y，X）是一致的，也就是所谓的联合熵：

它们之间的关系

根据上面的定义，其实很多公式等式都可以证明了，比如：


这两个公式的现实解释也很好理解，那就是，由X引入的混乱度加上“在X已经存在的基础上添加Y引入的混乱度”，就是X和Y一起的混乱度。
还有另外一个等式也是可以被推导的：

我们将这个恒等式两边的结果记为, 显然，它表示了没有Y为前提下分析X和有Y为前提下分析X的混乱度之差。
由上面几个式，我们可以得出：

为了形象方便地记住这些公式，我们可以用韦恩图来表示他们的数量关系：

信息熵、条件熵、联合熵、互信息的关系
从图中我们可以看出，对于X来说，某个Y与它的互信息越大，则这个Y条件下，X越集中，H(X|Y)就越小，如果X完全由Y来决定，那么经过Y拆分后，其每个拆分过的数据都有完全一致的X的值，那么H(X|Y)=0.
换句话说，I(X,Y)度量了Y对X的决定程度。

似乎还是觉得缺了点啥？

我猜你并没有真的拿起笔，按照定义一步一步地证明上一段的所有公式都是正确的。
即使你这样做了，你一定还是心里不太满足，总觉得缺了点啥。。
这是巧合么？计算步骤这么繁琐，有没有更直观的方式来理解呢？能否找到更加简洁的证明过程呢？
当然有，我这里就有一个绝妙的证明方式。当然，我这里提供的证明在本质上也还是那个复杂的证明，只不过通过一些列新概念，或者说记号，提高了证明的可读性。
我要引入两个新的标记。
第一个标记，是算子, 它可以用来简化算法, 来表示一个用全概率公式求期望的过程。
当算子的对象仅含x的时候，我们有，，这是由于p(x)本身就是p(x,y)的边际概率。
第二个标记，是函数, 相应的，, 此时，由于条件概率公式, 易得
这样，我们有：




相关结论一目了然。
韦恩图的“巧合”，本质上是条件概率的定义以及熵的定义将乘除法换为加减法的结果。

互信息的直接算法

利用上面的标记，我们可以得出互信息的计算公式：

这时候聪明的小伙伴已经跳起来了，当X，Y独立的时候，p(x,y)=p(x)p(y), 互信息就为0
也就是说，对于X来说，有没有Y是一个样的。
当X能够完全决定Y的时候，x发生时一定得到x,y同时发生，此时p(x,y)=p(x), I(X,Y)=H(Y),从图中看出H(Y|X)=0,即，在x发生的前提下，y是一定会发生的，其熵为0，纯度打满。
反之亦然。
所以，I(X,Y)显示了X与Y互相的决定程度。
这时候，脑子活跃的小伙伴可能就又有新想法了，到底是X决定Y多一点，还是Y决定X多一点呢？从韦恩图中，我们很容易想要看交集在相应的集合中的比例，如果I(X,Y)=H(Y)<H(X), 我们就知道X完全决定Y，但Y不能完全决定X。因此我们会想要用
来度量X对Y的决定程度。

回头再看决策树

所谓的信息增益，就是互信息
所谓的信息增益率，就是