artificial-intelligence - 决策树是试图最大化信息增益还是熵？

Question

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

信息增益定义为:

InformationGain = EntropyBefore - EntropyAfter

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

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

Answer 1

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

考虑一个简单的二类问题，其中来自类 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 上 split 后的熵为 0(即信息增益为 1)。因此，对于此示例，您将选择属性 B 作为根节点(并且无需选择其他属性，因为数据已被 B 完美分类)。

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