决策树是试图最大化信息获取还是熵？

Question

据我所知，决策树试图将高熵的分类器放在决策树上。然而，信息的获取是如何发挥作用的呢？

信息增益被定义为：

InformationGain = EntropyBefore - EntropyAfter

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

对不起，我只是有点糊涂。谢谢!

Answer 1

情况正好相反。对于使用信息增益的决策树，算法选择提供最大信息增益的属性(这也是导致最大熵约简的属性)。

考虑一个简单的两类问题，在这个问题中，您有相同数量的来自C_1和C_2类的训练观察，在本例中，您是从熵开始的(因为从样本中随机抽取任何一个类的概率是0.5)。现在考虑属性A，它的值为A_1和A_2。也假设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完美地分类了)。

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

Answer 2

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

如果您有一个具有(例如)五个属性的表，那么必须首先计算这五个属性中每个属性的信息，然后选择信息增益最高的属性。此时，您应该将正在开发的决策树视为具有最高节点的根，以及从该属性值中提取子表的子表。例如，如果它是一个二进制属性，那么您将有两个子属性；每个子属性将具有其余的四个属性；一个子元素将拥有与选择属性对应的所有元素为true，另一个将包含与false对应的所有元素。

现在，对于每个子节点，再次遍历并选择最高信息增益的属性，直到不能继续。

这样，你就有了一棵树，它总是告诉你在考虑到你已经做出的决定的同时，要根据一个变量做出决定，这个变量会给你提供最多的信息。