machine-learning - 在 ID3 实现中，此时算法中的递归应该停止

Question

在 ID3 实现中，算法中的递归应该停止。

score 2 · Accepted Answer

当没有要分类的示例或没有要分类的属性时，分支就会停止。维基百科上的算法描述很容易理解，那里也有很多例子和讨论的链接。

score 0 · Accepted Answer

好吧，只要满足拆分标准，您就可以继续拆分（从现有节点形成两个新节点）。

分裂标准通常是父节点信息增益，也就是熵，（或方差，如果变量是离散的而不是分类的）和推定子节点的加权平均 IG 加权平均信息增益之间的差异的负值：

if weighted_mean(IG_child1, IG_child2) < IG_parent :
    createNodes(IG_child1, IG_child2)
else :
    continue

所以这是一个微不足道的答案，但你的问题背后可能有一个更复杂的意图，如果你不介意，我会稍微改一下，只要满足分割标准，你应该继续创建节点吗？

如果您正在编写 ID3 算法，您可能刚刚发现，应用没有约束的拆分标准通常会导致过度拟合（即，您从训练数据构建的树不能很好地概括，因为它没有t 将噪声与真实模式区分开来）。

所以这更有可能是您问题的答案：“约束”节点拆分（并因此处理过度拟合问题）的技术都属于两个类别之一 -自上而下或自下而上。自顶向下的一个例子：设置一些阈值（例如，如果子节点的加权平均值低于5％以下，则不分裂）？

自下而上的一个例子：修剪。剪枝意味着只要满足分裂标准就让算法分裂，然后在它停止后，从最底层的节点开始，并“取消分裂”任何子节点与父节点之间的 IG 差异小于某个值的节点临界点。

这两种方法没有相同的效果，实际上剪枝是更好的技术。原因：如果您自上而下强制执行拆分阈值，那么当然会阻止一些拆分；然而，如果它被允许发生，下一次分裂（两个子节点中的一个或两个成为孙节点）可能是有效的分裂（即，高于阈值），但该分裂永远不会发生。修剪当然可以解决这个问题。

2 回答 2