2.2　CART算法

CART（Classification And Regression Trees）即分类和回归树［1］，是第一种比较经典的决策树算法，由Leo Breiman、Jerome Friedman、Richard Olshen和Charles Stone于1984年正式提出，可用于分类或回归预测建模问题。

CART算法总是创建一棵二元树（二叉树），这意味着每个非终端节点有两个子节点。CART的构建过程与人类的决策方式非常相似，因此，人们很容易理解和接受CART决策过程得出的结果。这种直观的可解释能力是CART以及决策树方法非常重要的一个原因。CART另一个非常吸引人的地方是，它允许多样化的输入数据类型，这与许多线性组合方法（如逻辑回归或支持向量机）不同。可以混合连续数值变量，如价格或面积，也可以混合标称分类或枚举变量，如房屋类型或位置。这种灵活性使得CART成为各种应用中的首选工具。CART使用代价复杂度剪枝（Cost Complexness Pruning，CCP）方法，将不可靠的分支从决策树移除，以提高准确率。

从CART算法的名字中可以看出，它支持构建分类（决策）树和回归（决策）树。所谓分类树，是指目标变量是标称分类或枚举值数据类型，用于确定目标变量可能属于的“类”别。所谓回归树，是指目标变量是连续的数值数据类型，用来预测目标变量的值。图2.1展示了分类与回归的区别。