encoding - 决策树中的香农熵测度

Question

为什么在决策树分支中使用香农熵度量？

熵(S) = - p(+)log( p(+) ) - p(-)log( p(-) )

我知道这是对否的衡量标准。编码信息所需的比特数；分布越均匀，熵越大。但我不明白为什么它如此频繁地应用于创建决策树（选择分支点）。

Answer 1

因为你想问能给你最多信息的问题。目标是尽量减少树中决策/问题/分支的数量，因此您从能给您提供最多信息的问题开始，然后使用以下问题填写详细信息。

Answer 2

为了决策树，忘记位数，只关注公式本身。考虑一个二进制 (+/-) 分类任务，您的训练数据中有相同数量的 + 和 - 示例。最初，熵将为 1，因为p(+) = p(-) = 0.5。您希望在最能降低熵的属性上拆分数据（即，使类的分布最不随机）。如果选择一个与类完全无关的属性 A1，那么在将数据除以 A1 的值之后，熵仍然为 1，因此熵没有减少。现在假设另一个属性 A2 完美地分隔了类（例如，类总是+为A2="yes"并且总是-为A2="no"。在这种情况下，熵为零，这是理想情况。

在实际情况下，属性通常不能完美地对数据进行分类（熵大于零）。因此，您选择“最佳”对数据进行分类的属性（提供最大的熵减少）。一旦以这种方式分离数据，则以类似方式为来自第一次拆分的每个分支选择另一个属性，以进一步减少沿该分支的熵。继续这个过程来构建树。

Answer 3

您似乎了解该方法背后的数学原理，但这里有一个简单的示例，可能会让您对为什么使用这种方法有一些直觉：想象您在一个有 100 名学生的教室里。每个学生都坐在一张课桌前，课桌被组织成 10 行 10 列。100 名学生中有 1 名有奖品，但你必须猜出是哪个学生才能获得奖品。问题是，每次您猜测时，奖品的价值都会减少。您可以先单独询问每个学生是否有奖品。但是，最初，您只有 1/100 的机会猜对，而且很可能当您找到奖品时，它已经毫无价值（将每个猜测都视为决策树中的一个分支）。反而，您可以提出广泛的问题，从而大大减少每个问题的搜索空间。例如“学生是否在第 1 行到第 5 行？” 无论答案是“是”还是“否”，您都将树中潜在分支的数量减少了一半。