artificial-intelligence - 构建决策树时的终止标准

Question

我正在为决策树编写自己的代码。我需要决定何时终止树构建过程。我可以考虑限制树的高度，但这似乎微不足道。谁能给我一个关于如何实现我的终止功能的更好的想法。

在我的树构建算法中。

Answer 1

您的问题几乎没有上下文，但我假设您正在从大量数据中构建一棵树？在这种情况下，除了“LearnSet”之外，还有一个解决方案是采用“StopSet”示例并定期验证您在此 StopSet 上的决策过程。如果质量下降，这表明您在 LearnSet 上过度训练。

我故意使用“StopSet”而不是“TestSet”，因为在此之后您应该在 TestSet 上应用您的决策树来评估真实质量。

Answer 2

由于决策树产生不平衡的分裂，树的一部分可能比另一部分重。因此，使用树的高度是不明智的，因为它在同一水平处处处停止。更好的是使用拆分搜索所需的最少观察次数。这在http://zyxo.wordpress.com/2011/07/04/how-to-use-the-settings-to-control-the-size-of-decision-trees/中有更详细的说明

Answer 3

这是一个有点老的问题，但我认为我可以改进答案。理论是当拆分是纯的（即杂质 = 0）或左侧或右侧节点中的所有成员都是相同的输出值时，您会停止。例如，如果您尝试预测心脏病发作与否，并且在给定的拆分中，如果一个组有所有心脏病发作或没有心脏病发作，那么您可以安全地停止对该组的拆分，因为一切都是一样的，您可以安全地预测共同价值。修剪过程支持该理论，因为您可以构建一棵非常高的树，如果一个节点对准确性没有贡献，它就会被修剪。

现在很少有你得到完全纯粹的分裂。通常为了将数据拆分为完全纯的集合，您会拆分很多数据，使集合越来越小，直到您在每个节点中得到一个观察结果。高大的树木通常无法在修剪过程中存活下来，而且您很可能会过度拟合训练数据。因此，通常的做法是在修剪算法中为自己节省额外的时间，以简单地限制您愿意拆分的观察数量，并从结果拆分中设置一个最小值。您不会保留导致 1 和 999 个观测值的拆分。那是一个糟糕的分裂，再试一次。

因此，您为节点中的最小观察数（即拆分后）和拆分所需的最小节点数（拆分前）添加了一个配置参数，用户可以对其进行调整。

最后的标准也是如果你的分裂没有从最后一次纯度测量中得到改善。如果一个节点不能被分割以产生一个比以前更纯的集合。你可以停下来，因为你走错了方向。这实质上意味着如果 I(s) 是您要拆分的节点的纯度测量值。I(s[l]) 是左分割集的纯度，I(s[r]) 是右分割集的纯度，p(s) 是该集到父集的部分：

Gain = I(s) - p(s[r]) * I(s[r]) - p(s[l]) * I(s[l])

如果该增益 < 0，您将停止，因为您不再通过拆分它来获得纯度。

Answer 4

我们有 3 个一般终止条件： 1. 分区中的所有元组都属于同一类 2. 没有剩余的属性可以对元组进行进一步分区。3. 给定分支没有元组。

当然，您可以设置一些其他条件，例如最大深度或其他条件。