如何实现可靠的通信？怎样做出更好的决策？浅谈信息论之美( 二 ) _信息论

文章插图

直觉告诉我们，对于每一个可能的答案，我们会获得一定的信息量 log p (x?)，这意味着如果我们得到答案发生该事件概率实际上相当低的话(即我们问这个角色有没有一个很少见的特征，并且答案是 yes 的话)，那么获得的信息量就要比发生高概率的情况下更大。
另一方面，熵与不确定性有关。例如，如果我们掷硬币，p = 0.5 时结果的不确定性比 p 的任何其他值都要高。在我们的例子中，不确定性越大越好。为什么？如果我们选择一个无法使人口分布均匀的问题，假设分布为 0.7 和 0.3，很可能我们的角色是在 70%的角色中，丢弃剩下 30%的回答 no 的团体，但随着更平均的分布(因此不确定性更高)，我们总是倾向于放弃 50%的人口，这从全局而言是更优选择。也就意味着最好的问题是那些能最大化熵，即不确定性较高的问题。
决策树(Decision Trees)熵的一个常见用途是在决策树中，决策树的工作原理也与"猜猜我是谁"类似，通过使用一组特征(将数据分割成不相交集合的特征)来为分类问题构建决策流程图（决策树）。
一般的，一棵决策树包含一个根节点、若干个内部结点和若干叶子结点。叶子结点对应于决策结果，其他结点则对应于一个特征的测试。根结点包含所有样本，每个结点包含的样本集合根据特征测试的结果被划分到子结点中。从根结点到叶子结点的路径对应了一个决策的测试序列。例如，下图是挑西瓜的决策树。

文章插图

出自周志华老师. 机器学习 [M]. 清华大学出版社, 2016. 73~79
在这里，一个常见的问题是：我们怎样找到发挥决定性作用的特征，并按照什么顺序“应用”这些特征才能更好地划分数据？一种可能的解决方案是始终递归地使用最大化信息增益的特性。假设我们处理的数据集为 S ，我们选取的特征为 X ，那么在 S 上应用特征 X 所获得的信息增益为 I(S,X) （ I(S,X) 也称为S与X的互信息），计算如下:

文章插图

其中 H(S|X) 是给定 X 的情况下 S 的条件熵。直观地，I(S,X) 就是我们知道特征 X 的取值后数据集 S 熵的减少量。因此，选择 X 的特性使这个值最大化是有意义的，因为他们将最大程度地减少不确定性，有效地获取最佳的数据集划分。
考虑每个节点上的信息增益来选择下一个特征的算法被称为贪婪算法。这些算法并没有考虑到总体信息增益，可能会导致一些情况下的次优查询，但它们表现良好，而且有一个简单的实现方法。
安德森鸢尾花卉数据集，也称鸢尾花卉数据集，是一类多重变量分析的数据集。它最初是埃德加·安德森从加拿大加斯帕半岛上的鸢尾属花朵中提取的形态学变异数据，后由罗纳德·费雪作为判别分析的一个例子，运用到统计学中。其数据集包含了150个样本，都属于鸢尾属下的三个亚属，分别是山鸢尾、变色鸢尾和维吉尼亚鸢尾。四个特征被用作样本的定量分析，它们分别是花萼和花瓣的长度和宽度。基于这四个特征的集合，费雪发展了一个线性判别分析以确定其属种。
例如，考虑下图，在著名的安德森鸢尾花卉数据集上使用决策树方法并选择两个特征，花瓣宽度，首先设置阈值为 0.8 cm ，然后是 1.75 厘米。先不考虑这些特定的特性是怎么选择的，我们先思考为什么要先使用 ≤0.8 ？通过计算上文所述的信息增益，我们可以找到答案。我们将以花瓣宽度 0.8 厘米为阈值的特征称为 X，另一个为 Y 。

文章插图

注：图中使用的Gini系数与互信息类似，也是信息增益的度量，下文我们将用互信息作为信息增益的度量进行对决策树的进一步说明。
首先应用特征 X 划分 150 个数据点(通常训练集和测试集是分开的，在这里为了简单我们使用整个集合)为两组: 一个包含整个山鸢尾类 (50 个点，对应于花瓣宽度≤0.8 cm)，另一个包含其余部分。在这种情况下，计算收益:

文章插图

另一方面，若先使用特征 Y 划分数据点，得到的两组：花瓣宽度≤1.75 cm组有50 个山鸢尾，49 个变色鸢尾和 5 个维吉尼亚鸢尾；另一组没有山鸢尾，1 个变色鸢尾和 45 个维吉尼亚鸢尾。这给我们带来的收益为: