CART 是什么？既能分类又能回归的二叉决策树

分类与回归树（Classification and Regression Tree，CART）是一种经典的决策树算法，由 Leo Breiman、Jerome Friedman、Richard Olshen 和 Charles Stone 在 1984 年出版的同名著作中系统提出。顾名思义，它既可以用来做分类，预测离散的类别，也可以用来做回归，预测连续的数值。

它的特点：永远一分为二

CART 生成的是二叉树：每个内部节点只问一个“是或否”的问题，把样本分成两部分。对于数值特征，问题形如“年龄是否小于等于 30”；对于类别特征，问题形如“城市是否属于{北京、上海}”。这与 ID3、C4.5 等算法不同，后者在类别特征上会按每个取值分出多个分支。二叉划分让树的结构统一，也便于实现和剪枝。

如何选择划分

在每个节点上，CART 会遍历所有特征和所有可能的切分点，选出让划分后结果最“纯”的那一个。分类树使用基尼指数来衡量纯度：从一个节点中随机抽取两个样本，它们类别不同的概率，越小说明节点越纯。选择让划分后两个子节点的加权基尼指数最小的切分。回归树使用平方误差：每个叶子节点用其中样本目标值的平均数作为预测，选择让两个子节点内平方误差之和最小的切分。这种回归树也叫最小二乘回归树。

剪枝

完全生长的树容易过拟合。CART 采用代价复杂度剪枝：定义一个综合指标，等于树在训练集上的误差加上一个系数乘以叶子节点的数量。随着这个系数从零逐渐增大，依次剪掉“性价比”最低的子树，得到一串由大到小的候选树，再用交叉验证或验证集选出最好的一棵。

影响

CART 的优点是直观易懂、可以处理数值和类别特征、对特征的尺度不敏感、能处理缺失值（通过“替代划分”）。它的缺点是单棵树不稳定，数据稍有变化，树的结构就可能大变。正因为这种不稳定性，它特别适合作为集成学习的基学习器：随机森林由许多棵 CART 组成，梯度提升树、XGBoost、LightGBM 中的每一棵树也都是 CART 回归树。scikit-learn 中的决策树就是基于 CART 实现的。