预剪枝是什么？决策树边长边判断要不要继续分

预剪枝（Pre-pruning）是决策树防止过拟合的一种剪枝策略：在决策树生长的过程中，每当准备对一个节点进行划分之前，先判断这次划分是否真的有用，如果不能提升模型的泛化能力，就停止划分，直接把这个节点作为叶子节点。与之相对的是后剪枝，它先让树完整地生长，再从下往上进行修剪。

为什么要剪枝

决策树在生长时，会不断地根据特征把训练数据划分得越来越细。如果不加限制，它可能会一直划分下去，直到每个叶子节点中的样本都属于同一个类别，甚至每个叶子只包含一两个样本。这样的树在训练数据上几乎不犯错，但它很可能把训练数据中的噪声和偶然的规律也学了进去，在新的数据上表现很差，这就是过拟合。剪枝就是要控制树的规模，只保留那些真正有用的分支。

基于验证集的预剪枝

周志华《机器学习》中介绍了一种基于验证集的预剪枝方法：把数据分为训练集和验证集，用训练集来生成决策树，用验证集来评估划分的效果。在每个节点上，先根据信息增益等标准选出最好的划分属性，然后比较两种情况在验证集上的准确率：一种是不划分，把这个节点直接作为叶子节点，用其中样本最多的那个类别作为预测；另一种是按照选出的属性进行划分，每个子节点用各自样本最多的类别作为预测。如果划分之后验证集上的准确率没有提高，就放弃划分，停止生长；如果有所提高，才进行划分，然后在子节点上继续同样的判断。

基于条件的提前停止

在实际使用中，预剪枝更常见的形式是设定一些停止生长的条件，这些条件也是决策树最常调节的超参数：树的最大深度，比如不超过 10 层；一个节点至少要有多少个样本才允许继续划分；划分之后每个叶子节点至少要包含多少个样本；划分带来的信息增益或基尼指数的下降如果小于某个阈值，就不再划分；叶子节点的最大数量。scikit-learn 等工具库中的决策树就提供了这些参数。在梯度提升树中，通常也通过限制每棵树的最大深度、叶子数量和最小增益来控制每棵树的复杂度。

优点和缺点

预剪枝的优点是：很多分支在生长出来之前就被阻止了，树的规模较小，训练和预测的时间开销都比较小；而且实现简单。它的主要缺点是存在欠拟合的风险，原因在于它是“贪心”的：它只看当前这一次划分能否带来提升，而有些划分虽然当下看起来没有什么用处，甚至会让验证集上的准确率暂时下降，但在它的基础上继续进行后续的划分，却可能带来明显的提升。预剪枝会因为“目光短浅”而错过这样的机会，过早地停止生长。一个经典的例子是“异或”关系：单独用任何一个特征进行划分都看不出任何效果，只有用两个特征先后进行划分，才能完全把数据分开，预剪枝可能在第一步就停下来了。

与后剪枝的比较

后剪枝先生成一棵完整的决策树，再自底向上地考察每一个节点，把那些对提升泛化能力没有帮助的子树替换为叶子节点。由于它是在看到完整的树之后再做决定的，能够考虑到深层的划分所带来的效果，所以通常保留的有用分支更多，欠拟合的风险更小，泛化性能往往优于预剪枝。但后剪枝需要先生成完整的树，再逐个地考察大量的节点，训练的时间开销要大得多。在实践中，两种方法常常结合使用：先用一些宽松的停止条件限制树的规模，再进行后剪枝。