机器学习 度量 信息熵 相对熵 交叉熵 基尼系数

信息熵

​ 在信息论或概率统计中，用熵（entropy）度量随机变量的不确定性。熵值越大，随机变量的不确定性就越大。而这个东西与我们决策树有什么关系呢？其实我们就是希望决策树的分支结点所包含的样本尽可能属于同一类别，即这个结点的“纯度”越来越高，而信息熵（information entropy）是度量样本集合纯度最常用的一种指标。

​ 设 $X$ 是一个取有限个数的离散随机变量，其概率分布为：
$$P(X=x_i)=p_i,i=1,2,\cdots ,n$$
​ 则随机变量 $X$ 的熵定义为：
$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$
​ 这是一个定义，我们可以让 $p_i=0$，则定义 $0\log 0=0$，若 $p_i=1$，则定义 $1\log 1=0$。并且由定义可以看出，熵只依赖于 $X$ 的分布，而与 $X$ 的取值无关，所以也可将 $X$ 的熵记作 $H(p)$，即：
$$H(p)=-\sum _{i=1}^n{p}_i\log p_i$$
​ 当随机变量只取两个值，例如 1，0 时，则 $X$ 的分布为：
$$P(X=1)=p,P(X=0)=1-p,0\le p\le 1$$
熵为：
$$H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$$
这时，熵 $H(p)$ 随概率 $p$ 变化的曲线如下图所示（单位为比特）。

我们可以看出，熵越小，则不确定性就越小，可以说 $p=0$ 或 $p=1$ 时不确定性为 0。

​

信息增益

​ 信息增益是划分前样本数据集的不纯程度（熵）和划分后样本数据集的不纯程度（熵）的差值。
​
​ 特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即
$$g(D,A)=H(D)-H(D|A)$$
​ 信息增益 $g(D,A)$ 表示得知特征 $A$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。

信息增益的算法（算法5.1）

​ 输入：训练数据集 $D$ 和 特征 $A$;
​
​ 输出：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$。
​
​ （1）计算数据集 $D$ 的经验熵 $H(D)$
$$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|C|}$$
​ （2）计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$
$$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{D_i}{\log }_2\frac{|D_{ik}|}{|D_i|}$$
​ （3）计算信息增益
$$g(D,A)=H(D)-H(D|A)$$
例子 对表1所给的训练数据集 $D$，根据信息增益准则选择最优特征。

解 首先计算经验熵 $H(D)$。

​ 在表 1 中，目标类别：是否发放贷款，将 9 个“发”归为一类，剩余 6 个不发放归为一类，这样进行分类的信息熵为：
$$H(D)=-\frac{9}{15}{\log }_2\frac{9}{15}-\frac{6}{15}{\log }_2\frac{6}{15}=0.971$$
​ 然后计算各特征对数据集 $D$ 的信息增益。分别以 $A_1,A_2,A_3,A_4$ 表示年龄、有工作、有自己的房子和信贷情况 4 个特征，则
​
​ （1）按照年龄属性（记为 $A_1$）划分：青年（$D_1$表示），中年（$D_2$表示），老年（$D_3$表示）

​ （2）按照是否有工作（记为 $A_2$）划分：有工作（$D_1$表示），无工作（$D_2$表示）

​ （3）按照是否有自己房子（记为$A_3$）划分：有自己房子（$D_1$表示），无自己房子（$D_2$表示）

​ （4）同理，根据信贷情况这最后一个特征：
$$g\left(D,A_4\right)=0.971-0.608=0.363$$
​ 最后，比较各特征的信息增益值，由于特征 $A_3$（有自己的房子）的信息增益值最大，所以选择特征 $A_3$ 作为最优特征。

信息增益比

​ 特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_A(D)$ 之比，即：

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
其中，$H_A(D)=-{\sum }_{i=1}^n\frac{D_i}{D}lo{g}_2\frac{D_i}{D}$，$n$ 是特征 $A$ 取值的个数。

信息增益和信息增益比的区别

​ 以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归构建决策树。

​ 信息增益比（增益率）对可取值数目较少的属性有所偏好，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益率高于平均水平的属性，再从中选择增益率最高的。

基尼系数

​ 分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为
$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$
对于二类分类问题，若样本点属于第 1 个类的概率是 $p$，则概率分布的基尼指数为
$$Gini(p)=2p(1-p)$$
对于给定的样本集合 $D$，其基尼指数为
$$Gini(D)=1-\sum _{k=1}^K(\frac{|C_k|}{|D|}{)}^2$$
这里，$C_k$ 是 $D$ 中属于第 $k$ 类的样本子集，$K$ 是类的个数。

​ 如果样本集合 $D$ 根据特征 $A$ 的是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，即
D={(x,y)∈D∣A(x)=a},D2=D−D1 D=\{(x,y)\in D|A(x)=a\},\quad D_2=D-D_1 D={(x,y)∈D∣A(x)=a},D2​=D−D1​
则在特性 $A$ 的条件下，集合 $D$ 的基尼指数定义为
$$Gini(D,A)=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2)$$
基尼系数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼系数 $Gini(D,A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼系数值越大，样本集合的不确定性也就越大，这一点与熵相似。

​ 图 5.7 显示二类分类问题中基尼系数 $Gini(p)$、熵（单位比特）之半 $\frac{H(p)}{2}$ 和分类误差率的关系。横坐标表示概率 $p$，纵坐标表示损失。可以看出基尼系数和熵之半的曲线很接近，都可以近似地代表分类误差率。

条件熵（conditional entropy）

条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$的不确定性。条件熵 $H(Y|X)$ 定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：

条件熵 $H(Y|X)$ 相当于联合熵 $H(X,Y)$ 减去单独的熵 $H(X)$，即 $H(Y|X)=H(X,Y)-H(X)$，证明如下：

举个例子，比如环境温度是低还是高，和我穿短袖还是外套这两个事件可以组成联合概率分布 $H(X,Y)$，因为两个事件加起来的信息量肯定是大于单一事件的信息量的。假设 $H(X)$ 对应着今天环境温度的信息量，由于今天环境温度和今天我穿什么衣服这两个事件并不是独立分布的，所以在已知今天环境温度的情况下，我穿什么衣服的信息量或者说不确定性是被减少了。当已知 $H(X)$ 这个信息量的时候，H(X,Y) 剩下的信息量就是条件熵：
$$H(Y|X)=H(X,Y)-H(X)$$

相对熵(KL散度)

设 $p(x)$、$q(x)$ 是 离散随机变量 $X$ 中取值的两个概率分布，则 $p$ 对 $q$ 的相对熵是：
$$D_{KL}(p\Vert q)=\sum _{x}p(x)\log \frac{p(x)}{q(x)}=E_{p(x)}\log \frac{p(x)}{q(x)}$$
性质：
1、如果 $p(x)$ 和 $q(x)$ 两个分布相同，那么相对熵等于0
2、$D_{XL}(p||q)\ne D_{KL}(q||p)$，相对熵具有不对称型。
3、$D_{KL}(p||q)\ge 0$

**总结：**相对熵可以用来衡量两个概率分布之间的差异，上面公式的意义就是求 $p$ 与 $q$ 之间的对数差在 $p$ 上的期望值。

交叉熵（Cross entropy）

现在有关于样本集的两个概率分布 $p(x)$ 和 $q(x)$，其中 $p(x)$ 为真实分布， $q(x)$ 非真实分布。如果用真实分布 $p(x)$ 来衡量识别别一个样本所需要编码长度的期望（平均编码长度）为:
$$H(p)=\sum _{x}p(x)\log \frac{1}{p(x)}$$
交叉熵的公式：
$$H(p,q)=\sum _{x}p(x)\log \frac{1}{q(x)}=-\sum _{x}p(x)\log (q(x))$$

交叉熵=信息熵+相对熵

在机器学习中，我们希望在训练数据上模型学到的分布P(model)和真实数据分布P(real)越接近越好，所以我们可以使其相对熵最小。交叉熵可以用来计算学习模型分布与训练分布之间的差异。交叉熵广泛用于逻辑回归的Sigmoid和Softmax函数中作为损失函数使用。

总结

• 信息熵是衡量随机变量分布的混乱程度，是随机分布各事件发生的信息量的期望值，随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大。当随机分布为均匀分布时，熵最大；信息熵推广到多维领域，则可得到联合信息熵；条件熵表示的是在 $X$ 给定条件下，$Y$ 的条件概率分布的熵对 $X$ 的期望。
• 相对熵可以用来衡量两个概率分布之间的差异。
• 交叉熵可以来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。