math - ID3 和 C4.5 : How Does "Gain Ratio" Normalize "Gain"?

Question

ID3 算法使用“信息增益”度量。

C4.5 使用“增益比”度量，即信息增益除以 SplitInfo，而 SplitInfo 对于记录在不同结果之间平均分配的拆分而言很高否则低。

我的问题是:

这如何帮助解决信息增益偏向于有许多结果的 split 的问题？我看不出原因。 SplitInfo 甚至不考虑结果的数量，只考虑拆分中记录的分布。

很可能结果数量较少(例如 2 个)，并且记录在这 2 个结果之间平分。在这种情况下，SplitInfo 高，增益比低，并且 C4.5 不太可能选择结果很少的拆分。

另一方面，可能结果数量较少，但分布很不均匀。在这种情况下，SplitInfo 较低，Gain Ratio 较高，并且更有可能选择具有许多结果的拆分。

我错过了什么？

Answer 1

SplitInfo doesn't even take into account the number of outcomes, just the distribution of records in the split.

但它确实考虑了结果的数量。 (即使它也依赖于分布，如您所述)。您的比较是在结果数量相同(“低”)的两种情况之间进行的，因此它无法说明 SplitInfo 如何随着结果数量的变化而变化。

考虑以下 3 种情况，为了比较简单，所有情况都均匀分布:

• 10 个均匀分布的可能结果

  SplitInfo = -10*(1/10*log2(1/10)) = 3.32

• 100 个均匀分布的可能结果

  SplitInfo = -100*(1/100*log2(1/100)) = 6.64

• 1000 种均匀分布的可能结果

  SplitInfo = -1000*(1/1000*log2(1/1000)) = 9.97

因此，如果您必须在 3 种可能的拆分方案之间进行选择，如 ID3 中那样仅使用 Information Gain，则会选择后者。但是，在 GainRatio 中使用 SplitInfo，应该清楚的是，随着选择的数量增加，SplitInfo 也会上升，GainRatio 会下降。

所有这些都是在平均分布的假设下解释的。然而，即使分布不均匀，上述情况仍然成立。 SplitInfo 会随着可能结果的数量增加而增加。是的，如果我们保持可能结果的数量不变并改变结果分布，那么 SplitInfo 将有一些差异......但是 Information Gain 也会有差异。