6

我知道决策树试图将具有高熵的分类器放在决策树上。然而，信息增益是如何发挥作用的呢？

信息增益定义为：

InformationGain = EntropyBefore - EntropyAfter

决策树是否尝试将信息增益低的分类器放在树的顶部？那么熵总是最大化而信息增益总是最小化？

对不起，我只是有点困惑。谢谢！

4

2 回答 2

4

恰恰相反。对于使用信息增益的决策树，算法选择提供最大信息增益的属性（这也是导致熵最大减少的属性）。

考虑一个简单的二分类问题，其中您有来自 C_1 和 C_2 类的相同数量的训练观察。在这种情况下，您从 1.0 的熵开始（因为从样本中随机抽取任一类的概率为 0.5）。现在考虑具有值 A_1 和 A_2 的属性 A。还假设 A_1 和 A_2 都对应于两个类的相等概率 (0.5)：

P(C_1|A_1) = 0.5
P(C_2|A_1) = 0.5
P(C_1|A_2) = 0.5
P(C_2|A_2) = 0.5

该属性的整体熵没有变化，因此信息增益为 0。现在考虑属性 B，其值为 B_1 和 B_2，并假设 B 将完美地分离类别：

P(C_1|B_1) = 0
P(C_2|B_1) = 1
P(C_1|B_2) = 1
P(C_2|B_2) = 0

由于 B 完美地分离了类，在 B 上分裂后的熵为 0（即信息增益为 1）。因此，对于本示例，您将选择属性 B 作为根节点（并且无需选择其他属性，因为数据已经被 B 完美分类）。

决策树算法是“贪婪的”，因为它们总是选择能够为当前节点（分支）产生最大信息增益的属性，而不会在添加后续子分支后重新考虑该属性。所以回答你的第二个问题：决策树算法试图将具有最大信息增益的属性放在树的底部附近。请注意，由于算法的贪心行为，决策树算法不一定会产生一棵树，它可以提供最大可能的整体熵减少。

于 2013-12-19T15:05:14.773 回答
2

不，您总是将具有高信息增益的节点放在树的顶部。但请记住，这是一个递归算法。

如果您有一个包含（比如说）五个属性的表，那么您必须首先计算这五个属性中每一个的信息并选择具有最高信息增益的属性。此时，您应该将正在开发的决策树视为具有最高节点的根，以及具有从该属性值获取的子表的子表。例如，如果它是二元属性，您将有两个孩子；每个都有剩余的四个属性；一个孩子将拥有对应于选择属性的所有元素为真，另一个所有元素对应于假。

现在对于这些子节点中的每一个，您再次遍历并选择最高信息增益的属性，递归直到您无法继续。

这样一来，您就有了一棵树，它总是告诉您根据一个变量做出决定，该变量预计会为您提供最多信息，同时考虑您已经做出的决定。

于 2013-12-19T15:07:11.023 回答