无限深的决策树能保证二值分类任务100%的准确率吗？

Question

那么，在二进制分类任务上无限深的决策树是否能保证在有N个示例的训练集上达到100%的准确率，这样就没有相同特征值的示例，而存在不同的类标记？

Answer 1

是的，可以创建这样的决策树。它也不需要无限深--只是ceil(log(2, N))级别深，其中N是示例数。假设每个训练实例都有一个唯一的特征值集，那么该模型就可以获得100%的准确率。

然而，这样的决策树可能会泛化得很糟糕。该模型实质上是记住每个训练示例。对于不属于原始培训集的例子，其准确性可能会相当糟糕。这就是为什么决策树模型通常要么设置最小的分割大小(例如，不要用少于10个示例分割任何叶子)，要么使用随机森林来训练许多不同的树并平均它们的预测值。