决策树ID3算法多类别场景下熵与信息增益计算问题

计算错误核心原因 #

你计算属性X的信息增益时，对属性X的取值子集划分逻辑完全错误，不符合ID3算法的计算规则。

正确计算步骤 #

我们先明确你的样本中AttrX的实际分布：

• AttrX共有a、b、c、d、e 5种独立取值，每种取值在10条样本中各出现2次
• 每个AttrX取值对应的2条样本里，Result为0和1的各占1条

1. 父节点熵你的计算是正确的：-(5/10)*log2(5/10) - (5/10)*log2(5/10) = 1
2. 计算按AttrX划分后的条件熵：
   每个AttrX取值的出现概率为2/10=0.2，每个取值对应子集的熵为：-(1/2)*log2(1/2) - (1/2)*log2(1/2) = 1
   总条件熵 = 5个取值的（概率 * 子集熵）之和 = 5*(0.2*1) = 1
3. 信息增益 = 父节点熵 - 条件熵 = 1 - 1 = 0

你的错误来源 #

你错误地将AttrX的样本随意拆成了两个各5条的子集，还混淆了属性取值和目标列类别，错误假设子集里的Result有5种不同取值，完全不符合样本实际分布，才会算出负数的错误结果。信息增益本质是父节点熵减去子节点加权平均熵，根据熵的性质结果不可能为负，出现负数一定是计算逻辑有误。

内容的提问来源于stack exchange，提问作者Abhiram Natarajan