什么是 CART 修剪算法？

CART 是著名的决策树算法，由 Leo Breiman、Jerome Friedman、Richard Olshen 和 Charles Stone 在 1984 年首次提出。CART 代表分类和回归树。CART 算法改进了二叉树并继续划分，考虑到可以找到提高纯度的新拆分。

有一些更简单的子树，每个子树都定义了模型复杂度和训练组误分类率之间的不同权衡。CART 算法将一组这样的子树识别为候选模型。这些候选子树用于验证组，并选择具有最小验证集误分类率的树作为最后一个模型。

CART 算法通过重复剪枝过程识别候选子树。目标是首先修剪那些支持每片叶子预测能力最少的分支。它可以识别这些最不利的分支，CART 基于一个称为调整错误率的概念。

这是一种提高每个节点在训练集上的错误分类成本的措施，其复杂性惩罚取决于树中的多个叶子。调整后的错误率可以识别弱分支（那些错误分类率不足以克服惩罚的分支）并指示它们进行修剪。

下一个任务是从候选子树池中选择在新记录上运行最佳的子树。每个候选子树都可以定义验证集中的数据。以最低的完全错误率实现此任务的树被定义为获胜者。获胜的子树已被充分修剪以消除过度训练的影响，但不会丢失有价值的数据。

因为这个剪枝算法依赖于错误分类率，没有考虑每个分类的概率，它恢复了一些子树，这些子树的叶子都创建了相同的分类，而公共父级也创建了该分类。

目标是选择一小部分数据（例如前 1% 或 10%），这种剪枝算法可能会损害树的实现，因为一些被淘汰的叶子包括目标类的非常高的区域. 有多种工具，包括 SAS Enterprise Miner，使用户能够针对此类方法优化修剪树。

获胜子树是根据其在用于定义验证集中数据的任务时的完全错误率来选择的。可以预期，当用于多个数据集时，所选子树将继续是最佳实现子树，生成它的错误率可能会稍微夸大其强度。