CART 算法

定义

CART(Classification and Regression Trees,分类与回归树)由 Breiman、Friedman、Olshen、Stone 于 1984 年在同名专著中提出,是应用最广的决策树算法之一,scikit-learn 的树实现即以其为基础。

原理

CART 构建严格的二叉树:每个内部节点选择一个特征及其切分点,把数据一分为二。分类树以基尼指数(Gini impurity)作为分裂准则,回归树以平方误差最小化选择切分;叶节点分别输出多数类或均值。树长成后通过代价复杂度剪枝(cost-complexity pruning),在训练误差与树规模之间权衡,配合交叉验证选出最优子树。

与 ID3/C4.5 对比

CART 支持回归任务、只做二叉分裂、使用基尼指数而非信息增益,且对连续特征与剪枝有系统化处理。

意义

CART 是随机森林与梯度提升树的标准基学习器,其方法论深刻影响了整个树模型family的发展。