信息熵的基础

信息熵

克劳德·香农在1948年提出了这一概念。克劳德·香农是一位美国著名科学家和信息论先驱者，在他的研究中提出了“信息熵”的概念，并为现代数字通信技术的发展奠定了理论基础。

理解信息熵

信息熵被用作度量不确定性的重要指标。即用来表示离散随机变量发生概率的数值。直观地说，在情况越来越复杂无序时（即混乱程度增加），其对应的信息熵值越大；反之，则越低。

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

其中p代表概率的概念，在这种情况下，“X”即为用于计算信息熵的数据集合。在决策树分类算法中，我们可以根据各类别在数据集中的比例（比例越大则类别越纯）来理解这一概念。其中N表示分类问题中的类别总数，并且Pk代表子集中第k类样本所占的比例。理解了这些基本概念之后，请进一步理解信息熵的具体计算方法则相对容易。

信息熵公式计算

让我们来考虑一个简化的案例，在这一信息熵计算公式的应用进行简化说明。具体来说，在二元分类场景中，当所有样本均归类于同一类别时（即某一类别的占节点子集的全部比例），另一类别所占比例则为零；此时的信息熵计算公式如下：

无需阐述对数函数的基本法则；基于2的对数运算中, log₂1的结果必然是零；经计算得出这两个类别对应的信息熵总和等于零；当信息熵值等于零时, 则表明该子集内的分类完全一致且有序；由此可知, 在pk=0.5时达到的信息熵最大值；最后我们根据以上分析绘制了信息熵作为变量变化的趋势图表, 如下所示：

ID3算法—信息增益

通过学习相关知识后可知，在决策树算法中所处理的对象是一个涵盖所有类别的集合，并通过一系列条件判断筛选出纯度较高的子集。那么我们该如何利用信息熵理论从特征集合中提取最优判断标准呢？以下将以 ID3 算法为例展开说明。

ID3（Iterative Dichotomiser 3）算法是决策树算法的一种重要代表，在香农的信息论基础之上实现了这一目标。它遵循奥卡姆剃刀原则——追求简单之美（the simplest possible solution），即用最少的东西实现最多的功能。

将这一理念应用于决策树构建过程中，则形成了 ID3 算法的核心逻辑：最小化模型复杂度的同时最大化预测能力（minimize model complexity, maximize predictive capability）。具体而言，在构建过程中我们会采用信息增益作为选择标准（use information gain as the selection criterion），从而能够提取出最优的关键指标（select the most minimal yet effective decision criteria）。

1) 理解信息增益

简而言之，在分析特征时所依据的信息增益是指某个特定特征的存在或缺失对整个系统或集合产生的影响程度。当考虑某个特定特征时（即该特征的存在与否），它对整个系统或集合的影响程度可以用"信息增益"来衡量。我们知道，在信息论中，在经过一次 if-else 判别后（即进行一次条件判断），原来的类别集合就被分割成了两个子集。我们的目标是在这些子集中尽可能提高某一类别的"纯度"（即同类元素的比例）。如果在分割后的子集中某单一类别的纯度较之前更高，则表明这一次 if-else 划分是有效的。通过比较得到"纯度"最高的那个划分条件，则是我们寻找的最佳划分标准——即最合适的特征维度判别条件。

2) 信息增益公式

那么如何计算信息增益值呢？我们可以通过比较划分前后的集合信息熵差异来进行计算。也就是说进行减法运算：用划分前集合的信息熵减去按特征维度属性划分后的子集对应的信息熵之和（或期望），从而就能得到该特征带来的信息增益值。公式如下所示：

G(S,a)表示当集合S采用特征属性t进行分类时所获得的信息增益；而H(x)则表示该集合的信息熵；对于‘减数’这一概念而言，在本节中我们将深入分析其具体的定义及计算方法：

• 大写字母 k 表示：按特征维度 t 划分后被划分为若干个子集的意思。
  • 小写字母 k 表示：划分后的其中一个子集，在划分后共有五个子集的情况下，则 k = 1 表示从第一个子集开始计算求和。
• |S| 与 |Sk| 表示：集合 S 中元素的数量（这里的||并不是绝对值符号），而 |Sk| 表示划分后某个特定集合 S_k 的元素数量。
• |S| / |Sk| 表示：在原始集合 S 中某个特定集合 Sk 的元素占比，在决策树中该集合的信息熵权重大小取决于其占比比例。占比越大权重越高。
  最后，在比较不同特征属性的信息增益时发现, 增益值越大表示该特征属性分割后的纯度更高, 分类的效果也越佳, 因此我们选择效果最佳的特征属性作为 if-else 规则的最佳判别条件。