计算决策树中的熵

Question

我发现在存在多个可能 class 且父 class 的熵低于子项的情况下，很难计算 ID3 的熵和信息增益。让我以此为例：

Attr Y AttrX  Result
4       a         0
3       b         0
4       c         0
4       d         0
3       e         0
4       a         1
3       b         1
3       c         1
4       d         1
4       e         1

现在，我相信第一步是计算原始数据集的熵，在本例中为 Result。这将是结果为+1 和 0 的负对数之和。即 -(5/10)*log(5/10) - (5/10)*log(5/10) 以 2 为底的日志。这等于 1 的熵。

现在对于属性 Y，信息增益可以计算为 1 - 每个可能结果的熵 * 结果发生的概率或 1 - 5/10[-(2/5)*log(2/5)- 3/5*log(3/5)] - 5/10[-(2/5)*log(2/5) -(3/5)*log(3/5)] = 0.029

我的问题是，对于属性 X，信息增益为 1 - 每个结果的熵 * 每个结果的概率或 1 - (5/10)*(-1/5log(1/5)-1 /5log(1/5)-1/5log(1/5)-1/5log(1/5)-1/5log(1/5)) - 5/10*(-1/5log(1/5) -1/5log(1/5)-1/5log(1/5)-1/5log(1/5)-1/5log(1/5)) = -1.32?

但是信息增益不是必须总是正的吗？我哪里错了？

Answer 1

增益的正确公式是：

Entropy(S) - sum_i(|Si|/|S| * Entropy(Si))

和

Entropy(S) = -p1 * log(p1) -p0 * log(p0)
Si 是 class i
p0（或p1）S中结果=0（或1）的元素的比例。

因此在 AttrX 的情况下，每个 class 出现 2/10 次，因此 |Si|/|S| = 1/5。

一旦我们知道 class (a, b, c, ...) 结果中有 1 或 0 的概率为 1/2。

所以每个class的熵是-1/2 * log(1/2) -1/2 * log(1/2) = 1 所以增益是 1 - 1/5 * 1 * 5 = 0

其实你可以直观地看到这个结果：不管class是什么，结果都是有50%的概率是1或者0，所以知道AttrX的信息增益是0。

计算决策树中的熵

Calculating Entropy in a decision tree

algorithm

machine-learning

decision-tree