2020机器学习决策树(2)

作者: zidea | 来源:发表于2020-03-16 19:50 被阅读0次

machine_learning.jpg

上一次分享给出决策树划分几种算法，如下。

信息增益
$Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$
信息增益率
$Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$

但是为什么这样按特征对数据划分就可以达到分类或回归的效果呢? 今天我们就尝试来回答这个问题。
我们对数据了解程度决定了我们是否可以对数据进行分类和预测。数据对于我们是一些信息，在决策树我们是通过一些列方法让我们更了解这些数据，也就是数据提供给我们更多信息。

所以我们通过对数据某个特征对数据进行划分来不断了解数据，我们同过了解数据特征，更加了解数据。我们可以根据特征对数据进行划分，降低我们对数据不确定性。数据的不确定性是通过信息熵可以衡量。降低数据信息熵就等同于降低数据不确定性。那么我们将要尽快了解数据，就要找到可以让信息熵下降最快的特征作为我们划分数据的依据。

今天我们会首先介绍信息熵，接下来介绍在给定条件(就是已知什么条件下）数据下的条件熵。衡量连个对同一个数据不同概率分布之间的距离(差异性)的交叉熵。这些都是为证明互信息的公式。互信息就是信息增益，也就是我们今天主要分享的内容。

entropy_venn.png

图中很直观表示了互信息 $I(X,Y)$ 和条件熵 $H(X|Y$ 以及联合熵 $H(X,Y)$ 他们之间关系。

信息熵

熵概念最早是在物理热力学中提出概念后来也被在统计学中使用，表示提出了信息熵的概念，用以度量信息的不确定性。以及信息熵关系。我们先说介绍一下事件，什么是事件呢?例如太阳从东方升起就是一个事件、老板告诉你升职了也是一个事件。这些事件发生都是有一定概率的，例如太阳升起的概率是 100%，而老板告诉你升职却是一个小概率事件。然后这些事件也是带有一定信息量，如果你告诉朋友太阳会从东方升起，朋友会感觉你无聊，没话找话。因为这个这个事件对于他的信息量几乎为 0。

然后用概率表示事件发生可能性，我们用熵来衡量信息量大小。通过上面例子我们已经了解到信息熵越大则概率越小，概率为 1 时信息熵为 0。好现在我们先给出熵计算公式，然后再给出合理解释为什么熵公式长成这个样子
$H(p) = -\sum_{i=1}^N p_i \log p_i$
计算均匀分布信息熵
$p_i = \frac{1}{N} \, i \in \{1,2,\dots,N\}$
$H(p) = - \sum_{i=1}^N \frac{1}{N} \log \frac{1}{N} = \log \frac{1}{N}$

条件熵

之前已经学习过条件概率， $P(Y|X)$ 就是在 X 事件发生前提下，发生 Y 事件的概率。那么什么是条件熵呢?这里用 $H(Y|X)$ 来表示在 X 发生前提下，Y 的信息熵的值，
$\begin{aligned} H(Y|X) = H(Y,X) - H(X) \\ =- \sum_{x,y}p(x,y)\log p(x,y) - \left(- \sum_{x}p(x) \log p(x)\right) \\ =- \sum_{x,y}p(x,y)\log p(x,y) + \sum_{x}p(x) \log p(x) \\ = - \sum_{x,y}p(x,y)\log p(x,y) + \sum_x \left( \sum_y p(x,y) \log p(x) \right) \\ = - \sum_{x,y}p(x,y)\log p(x,y) - \left( - \sum_{x,y} p(x,y) \log p(x) \right)\\ = - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)}\\ = - \sum_{x,y} p(x,y) \log p(y|x) \end{aligned} \tag{1}$
通过推导我们得出 $H(Y|X) = -\sum_{x,y} p(x,y) \log p(y|x)$ ,这里我们可能会感觉有点不舒服就是，如果根据信息熵定义应该是 $H(Y|X) = - \sum_{x,y} p(y|x) \log p(y|x)$

相对熵

相对熵，又称互熵、交叉熵，鉴别信息，Kullback 熵或则 Kullback_Leible 散度。我们假设有 $p(x)$ 和 $q(x)$ 分别是 X 中取值的两个概率分布，则 p 相对于 q 的相对熵为

$D(p||q) = \sum_x p(x) \log \frac{p(x)}{q(x)} = E_{p(x)} \log \frac{p(x)}{q(x)}$

在 p 概率分布上求 $\log \frac{p(x)}{q(x)}$ 的期望。那么相对熵也就是可以衡量两个概率分布 $p(x)$ 和 $q(x)$ 之间的距离。我们知道KL散度可以用于进行分类问题。

互信息

上面介绍相对熵就是为了介绍互信息，两个随机变量 X,Y 的互信息，定义为 X,Y 的联合分布和独立分布乘积的相对熵。
$I(X,Y) = D(P(X,Y) || P(X)P(Y))$
$I(X,Y) = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x),p(y)}$
如果两个随机变量 $p(x)$ 和 $p(y)$ 是相互独立那么，就是 $\frac{p(x,y)}{p(x),p(y)} = 1$ 也就是 $I(X,Y) = 0$ 如果两个随机变量的互信息为 0 就是说明两个随机变量是相互独立，反之就是大于 0。

有了互信息我们想证明一件事
$\begin{aligned} H(Y) - I(X,Y) = - \sum_y p(y) \log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \\ = -\sum_y \left( \sum_x p(x,y) \right)\log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \\ - \sum_{x,y} p(x,y) \log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}\\ - \sum_{x,y} p(x,y) \log \frac{p(y)p(x,y)}{p(x)p(y)}\\ - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)} \\ H(Y|X) \end{aligned} \tag{2}$