当前位置：网站首页>信息熵的基础

信息熵的基础

2022-07-03 00:46:00 【The code family】

信息熵

信息熵这一概念由克劳德·香农于1948 年提出。香农是美国著名的数学家、信息论创始人，他提出的“信息熵”的概念，为信息论和数字通信奠定了基础。

理解信息熵

信息熵是用于衡量不确定性的指标，也就是离散随机时间出现的概概率，简单来说“情况越混乱，信息熵就越大，反之则越小。”

伟大数学家香农给出了信息熵的计算公式，如下所示：

$H(X) = -\sum_{k=1}^{N}p_{k}log_{2}p_{k}$

其中, p 代表概率的意思，这里 “X” 表示进行信息熵计算的集合。在决策树分类算法中，我们可以按各个类别的占比（占比越高，该类别纯度越高）来理解，其中 N 表示类别数目，而 Pk 表示类别 K 在子集中的占比。理解了上述含义，再理解信息熵的计算过程就非常简单了，分为三次四则运算，即相乘、求和最后取反。

信息熵公式计算

下面我们举一个简单的例子，对上述信息熵计算公式进行简单的应用，在二元分类问题中，如果当前样本全部属于 k 类别，那么该类别在子集节点中的占比达到 100%（而另一个类别占比为 0），即 pk = 1，此时信息熵的计算公式如下：

$H(1) = -(1*log_{2}(1)+(0)) =0$

关于对数函数的运算法则这里不再赘述，以 2 为底 1 的对数为 0，因此最终两个类别的信息熵求和结果为 0。信息熵为 0 说明子集内的类别一致“整齐有序”。由此也可以得知 pk=0.5 时候信息熵的取得最大值。下面根据上述信息，我们绘制信息熵的函数图像，如下所示：

ID3算法—信息增益

通过前面知识的学习，我们知道决策树算法是以包含所有类别的集合为计算对象，并通过条件判别，从中筛选出纯度较高的类别，那么我们如何利用信息熵从特征集合中选择决策条件呢？下面我们以 ID3 算法为例进行说明。
ID3（Iterative Dichotomiser 3，迭代二叉树3代）算法是决策树算法的其中一种，它是基于奥卡姆剃刀原理实现的，这个原理的核心思想就是“大道至简，用尽量少的东西去做更多的事情”。
把上述原理应用到决策树中，就有了 ID3 算法的核心思想：越小型的决策树越优于大的决策树，也就是使用尽可能少的判别条件。ID3 算法使用了信息增益实现判别条件的选择，从香农的“信息论”中可以得知，ID3 算法选择信息增益最大的特征维度进行 if -else 判别。

1) 理解信息增益

简单地说，信息增益是针对一个具体的特征而言的，某个特征的有无对于整个系统、集合的影响程度就可以用“信息增益”来描述。我们知道，经过一次 if-else 判别后，原来的类别集合就被被分裂成两个集合，而我们的目的是让其中一个集合的某一类别的“纯度”尽可能高，如果分裂后子集的纯度比原来集合的纯度要高，那就说明这是一次 if-else 划分是有效过的。通过比较使的“纯度”最高的那个划分条件，也就是我们要找的“最合适”的特征维度判别条件。

2) 信息增益公式

那么如何计算信息增益值，这里我们可以采用信息熵来计算。我们通过比较划分前后集合的信息熵来判断，也就是做减法，用划分前集合的信息熵减去按特征维度属性划分后的信息熵，就可能够得到信息增益值。公式如下所示：

$G(S,t) = H(x) - \sum_{k=1}^{K}\tfrac{\left | S^{k} \right |}{\left | S \right |}H(S^{k})$

G(S,a) 表示集合 S 选择特征属性 t 来划分子集时的信息增益。H(x) 表示集合的信息熵。上述的“减数”看着有点复杂，下面重点讲解一下减数的含义：

大写字母 K 表示：按特征维度 t 划分后，产生了几个子集的意思，比如划分后产生了 5 个子集吗，那么 K = 5。
小写字母 k 表示：按特征维度 t 划分后，5 个子集中的某一个子集，k = 1 指的是从第一个子集开始求和计算。
|S| 与 |Sk| 表示：集合 S 中元素的个数，这里的||并不是绝对值符号，而 |Sk| 表示划分后，某个集合的元素个数。
|S| /|Sk| 表示：一个子集的元素个数在原集合的总元素个数中的占比，指该子集信息熵所占的权重，占比越大，权重就越高。
最后，比较不同特征属性的信息增益，增益值越大，说明子集的纯度越高，分类的效果就越好，我们把效果最好的特征属性选为 if-else 的最佳判别条件。