数据的信息

本文首先简要地说明一下决策树生成算法背后的数学基础和思想、然后再叙述具体的算法。往大了说、决策树的生成可以算是信息论的一个应用，但它其实只用到了信息论中一小部分的思想。不过，先对信息论有个概括性的认知还是有必要的、因为这样我们就可以有个更宽的视野

信息论简介

（注：本节有许多内容节选、修改、总结自维基百科）
被誉为信息论创始人的是克劳德·艾尔伍德·香农（Claude Elwood Shannon，1916.4.30－2001.2.26），他是美国数学家、电子工程师和密码学家，是密歇根大学学士、麻省理工学院博士。他在 1948 年发表的划时代的论文——“通信的数学原理”奠定了现代信息论的基础

信息论（Information Theory）涉及的领域相当多，包括但不限于信息的量化、存储和通信、统计推断、自然语言处理、密码学等等。信息论的主要内容可以类比人类最广泛的交流手段——语言来阐述。一种简洁的语言（以英语为例）通常有如下两个重要特点：

• 最常用的一些词汇（比如“a”、“the”、“I”）应该要比相对而言不太常用的词（比如“Python”、“Machine”、“Learning”）要短一些
• 如果句子的某一部分被漏听或者由于噪声干扰（比如身处闹市）而被误听，听者应该仍然可以抓住句子的大概意思

其中第二点被称作为“鲁棒性（Robustness）”。如果把电子通信系统比作一种语言的话，这种鲁棒性（Robustness）不可或缺。信息论的基本研究课题是信源编码和信道编码（通俗一点来讲就是怎么发出信息和怎么传递信息），将鲁棒性引入通信正是通过其中的信道编码来完成的，由此可见信息论的重要性

注意这些内容同消息的重要性之间是毫不相干的。例如，像“你好；再见”这样的话语和像“救命”这样的紧急请求，在说起来或写起来所花的时间是差不多的，然而明显后者更重要也更有意义。信息论却不会考虑一段消息的重要性或内在意义，因为这些属于信息的质量的问题而不是信息量和可读性方面上的问题，后者只是由概率这一因素单独决定的

既然我们我们关注的是信息量，我们就需要有一个度量方法。决策树生成算法背后的思想正是利用该度量方法来衡量一种“数据划分”的优劣、从而生成一个“判定序列”。具体而言，它会不断地寻找数据的划分方法、使得在该划分下我们能够获得的信息量最大（更详细的叙述会在后文给出）

不确定性

在决策树的生成中，获得的信息量的度量方法是从反方向来定义的：若一种划分能使数据的“不确定性”减少得越多、就意味着该划分能获得越多信息。这是很符合直观的，关键问题就在于应该如何度量数据的不确定性（或说不纯度，Impurity）。常见的度量标准有两个：信息熵（Entropy）和基尼系数（Gini Index），接下来我们就说说它们的定义和性质

信息熵

先来看看它的公式：

$$H\left( y \right) = - \sum_{k = 1}^{K}{p_{k}\log p_{k}}$$

对于具体的、随机变量$y$生成的数据集$D = \{ y_{1},\ldots,y_{N}\}$而言，在实际操作中通常会利用经验熵来估计真正的信息熵：

$$H\left( y \right) = H\left( D \right) = - \sum_{k = 1}^{K}{\frac{|C_{k}|}{|D|}\log\frac{|C_{k}|}{|D|}}$$

这里假设随机变量$y$的取值空间为$\{ c_{1},\ldots,c_{K}\}$，$p_{k}$表示$y$取$c_{k}$的概率：$p_{k} = p(y = c_{k})$；$|C_{k}|$代表由随机变量$y$中类别为$c_{k}$的样本的个数、$|D|$代表$D$的总样本个数（亦即$\left| D \right| = N$）。可以看到，经验公式背后的思想其实就是“频率估计概率”

通常来说，公式中对数的底会取为 2、此时信息熵$H(y)$的单位叫作比特（bit）；如果把底取为$e$（亦即取自然对数）的话，$H(y)$的单位就称作纳特（nat）

接下来说明为何上式能够度量数据的不确定性。可以证明（详细推导可参见相关数学理论），当：

$$p_{1} = p_{2} = \ldots = p_{K} = \frac{1}{K}$$

时，$H(y)$达到最大值$- \log\frac{1}{K}$、亦即$\log K$。由于$p_{k} = p(y = c_{k})$，上式即意味着随机变量$y$取每一个类的概率都是一样的、亦即$y$完全没有规律可循，想要预测它的取值只能靠运气。换句话说，由$y$生成出来的数据$\{ y_{1},\ldots,y_{N}\}$的不确定性是在取值空间为$\{ c_{1},\ldots,c_{K}\}$、样本数为 N 的数据中最大的（想象预测 N 次正 K 面体骰子的结果）

我们的目的是想让$y$的不确定性减小、亦即想让$y$变得有规律以方便我们预测。稍微严谨地来说，就是$y$取某个类的概率特别大、取其它类的概率都特别小。极端的例子自然就是存在某个$k^{*}$、使得$p\left( {y = c}_{k^{*}} \right) = 1$、$p\left( y = c_{k} \right) = 0,\forall k \neq k^{*}$、亦即y生成的样本总属于$c_{k^{*}}$类。带入$H(y)$的定义式，可以发现此时$H\left( y \right) = 0$、亦即$y$生成的样本没有不确定性

注意：由于$p\log p \rightarrow 0\ (p \rightarrow 0)$、所以认为$0\log 0 = 0$

特殊的情况就是二类问题、亦即$K = 2$的情况。先不妨设$y$只取 0、1 二值，再设：

$$p\left( y = 0 \right) = p,\ \ p\left( y = 1 \right) = 1 - p,\ \ 0 \leq p \leq 1$$

那么此时的信息熵$H(y)$即为：

$$H\left( y \right) = - \operatorname{plog}p - \left( 1 - p \right)\log{(1 - p)}$$

由此可得$H(y)$随$p$变化的函数曲线。底为 2 时函数图像如下图所示：

如前文所述，在$p = 0.5$时$H(y)$取得最大值 1。底为$e$时函数图像则如下图所示：

虽然最大值仍在$p = 0.5$时取得，但是此时$H(y)$仅有 0.693（$\ln 2$）左右

如果对上述二类问题稍作推广：$y \in \{ Y_{1},Y_{2}\}$、其中$Y_{1}$、$Y_{2}$都是一个集合，那么此时信息熵的定义式即为：

$$H\left( y \right) = - p\left( y \in Y_{1} \right)\log{p\left( y \in Y_{1} \right)} - p\left( y \in Y_{2} \right)\log{p(y \in Y_{2})}$$

且易知：

$$p\left( y \in Y_{1} \right) + p\left( y \in Y_{2} \right) = 1$$

如无特殊说明，今后谈及二类问题时讨论的范围都包括推广后的二类问题。

以上的叙述说明了，$y$越乱意味着$H(y)$越大、$y$越有规律意味着$H(y)$越小，亦即$H(y)$确实可以作为不确定性的度量标准

基尼系数

基尼系数的定义会更简洁一些：

$$\text{Gini}\left( y \right) = \sum_{k = 1}^{K}{p_{k}(1 - p_{k})} = 1 - \sum_{k = 1}^{K}p_{k}^{2}$$

同样可以利用经验基尼系数来进行估计：

$$\text{Gini}\left( y \right) = \text{Gini}\left( D \right) = 1 - \sum_{k = 1}^{K}\left( \frac{\left| C_{k} \right|}{\left| D \right|} \right)^{2}$$

以及同样可以证明，当

$$p_{1} = p_{2} = \ldots = p_{K} = \frac{1}{K}$$

时，$\text{Gini}(y)$取得最大值$1 - \frac{1}{K}$；当存在$k^{*}$使得$p_{k^{*}} = 1$时、$\text{Gini}\left( y \right) = 0$。特别地、当$K = 2$时，可以导出：

$$\text{Gini}\left( y \right) = 2p(1 - p)$$

此时$\text{Gini}(y)$的函数图像如下图所示：

虽然最大值仍在$p = 0.5$时取得，但是此时$\text{Gini}(y)$仅有 0.5。我们同样可以对二类问题进行推广、此时有：

$$\text{Gini}\left( y \right) = 1 - p^{2}\left( y \in Y_{1} \right) - p^{2}(y \in Y_{2})$$

且

$$p\left( y \in Y_{1} \right) + p\left( y \in Y_{2} \right) = 1$$

以上的叙述说明了$\text{Gini}(y)$也可以用来度量不确定性

信息的增益

在定义完不确定性的度量标准之后，我们就可以看看什么叫“获得信息”、亦即信息的增益了。从直观上来说，信息的增益是针对随机变量$y$和描述该变量的特征来定义的，此时数据集$D = \{\left( x_{1},y_{1} \right),\ldots,(x_{N},y_{N})\}$，其中$x_{i} = \left( x_{i}^{\left( 1 \right)},\ldots,x_{i}^{\left( n \right)} \right)^{T}$是描述$y_{i}$的特征向量、n 则是特征个数。我们可以先研究单一特征的情况（$n = 1$）：不妨设该特征叫$A$、数据集$D = \{\left( A_{1},y_{1} \right),\ldots,(A_{N},y_{N})\}$；此时所谓信息的增益，反映的就是特征$A$所能给我们带来的关于$y$的“信息量”的大小

可以引入条件熵$H(y|A)$的概念来定义信息的增益，它同样有着比较好的直观：

• 所谓条件熵，就是根据特征$A$的不同取值$\{ a_{1},\ldots,a_{m}\}$对$y$进行限制后，先对这些被限制的$y$分别计算信息熵、再把这些信息熵（一共有 m 个）根据特征取值本身的概率加权求和、从而得到总的条件熵。换句话说，条件熵是由被$A$不同取值限制的各个部分的$y$的不确定性以取值本身的概率作为权重加总得到的

所以，条件熵$H(y|A)$越小、意味着$y$被$A$限制后的总的不确定性越小、从而意味着A更能够帮助我们做出决策

接下来就是数学定义：

$$H\left( y \middle| A \right) = \sum_{j = 1}^{m}{p\left( A = a_{j} \right)H(y|A = a_{j})}$$

其中

$$H\left( y \middle| A = a_{j} \right) = - \sum_{k = 1}^{K}{p\left( y = c_{k} \middle| A = a_{j} \right)\log{p(y = c_{k}|A = a_{j})}}$$

同样可以用经验条件熵来估计真正的条件熵：

$$H\left( y \middle| A \right) = H\left( y \middle| D \right) = \sum_{j = 1}^{m}{\frac{\left| D_{j} \right|}{\left| D \right|}\sum_{k = 1}^{K}{\frac{|D_{\text{jk}}|}{|D_{j}|}\log\frac{|D_{\text{jk}}|}{|D_{j}|}}}$$

这里的$D_{j}$表示在$A = a_{j}$限制下的数据集。通常可以记$D_{j}$中的样本$y_{i}$满足$y_{i}^{A} = a_{j}$，亦即：

$$y_{i}^{A} = a_{j} \Leftrightarrow \left( A_{i},y_{i} \right) \in Y_{j} \Leftrightarrow A_{i} = a_{j}$$

而公式中的$|D_{\text{jk}}|$则代表着$D_{j}$中第 k 类样本的个数

从条件熵的直观含义，信息的增益就可以自然地定义为：

$$g\left( y,A \right) = H\left( y \right) - H(y|A)$$

这里的$g(y,A)$常被称为互信息（Mutual
Information），决策树中的 ID3 算法即是利用它来作为特征选取的标准的（相关定义会在后文给出）。但是，如果简单地以$g(y,A)$作为标准的话，会存在偏向于选择取值较多的特征、也就是 m 比较大的特征的问题。我们仍然可以从直观上去理解为什么会偏向于选取 m 较大的特征以及为什么这样做是不尽合理的：

• 我们希望得到的决策树应该是比较深（又不会太深）的决策树，从而它可以基于多个方面而不是片面地根据某些特征来判断
• 如果单纯以$g(y,A)$作为标准，由于$g(y,A)$的直观意义是$y$被$A$划分后不确定性的减少量，可想而知，当$A$的取值很多时，$y$会被$A$划分成很多份、于是其不确定性自然会减少很多、从而 ID3 算法会倾向于选择$A$作为划分依据。但如果这样做的话，可以想象、我们最终得到的决策树将会是一颗很胖很矮的决策树，这并不是我们想要的

为解决该问题、我们可以给 m 一个惩罚，由此我们可以得到信息增益比（Information
Gain Ratio）的概念，该概念对应着 C4.5 算法：

$$g_{R}(y,A) = \frac{g(y,A)}{H_{A}(y)}$$

其中$H_{A}(y)$是$y$关于$A$的熵，它的定义为：

$$H_{A}\left( y \right) = - \sum_{j = 1}^{m}{p\left( y^{A} = a_{j} \right)\log{p(y^{A} = a_{j})}}$$

同样可以用经验熵来进行估计：

$$H_{A}\left( y \right) = H_{A}\left( D \right) = - \sum_{j = 1}^{m}{\frac{\left| D_{j} \right|}{\left| D \right|}\log\frac{\left| D_{j} \right|}{\left| D \right|}}$$

该定义式和信息熵的定义式很像，它们的性质也有相通之处

需要指出的是，只需要类比上述的过程、我们同样可以使用基尼系数来定义信息的增益。具体而言，我们可以先定义条件基尼系数：

$$\text{Gini}\left( y \middle| A \right) = \sum_{j = 1}^{m}{p\left( A = a_{j} \right)\text{Gini}(y|A = a_{j})}$$

其中

$$\text{Gini}\left( y \middle| A = a_{j} \right) = 1 - \sum_{k = 1}^{K}{p^{2}\left( y = c_{k} \middle| A = a_{j} \right)}$$

同样可以用经验条件基尼系数来进行估计：

$${\text{Gini}\left( y \middle| A \right) = \text{Gini}(y|D) = \sum_{j = 1}^{m}{\frac{\left| D_{i} \right|}{\left| D \right|}\left\lbrack 1 - \sum_{k = 1}^{K}\left( \frac{\left| D_{\text{jk}} \right|}{\left| D_{j} \right|} \right)^{2} \right\rbrack}\backslash n}{= 1 - \sum_{j = 1}^{m}\frac{\left| D_{j} \right|}{\left| D \right|}\sum_{k = 1}^{K}\left( \frac{\left| D_{\text{Jk}} \right|}{\left| D_{j} \right|} \right)^{2}}$$

信息的增益则自然地定义为（不妨称之为“基尼增益”）：

$$g_{\text{Gini}}\left( y,A \right) = \text{Gini}\left( y \right) - \text{Gini}\left( y \middle| A \right)$$

决策树算法中的CART算法通常会应用这种定义