输出是连续变量的是回归树，输出是离散变量的是分类树。

CART决策树是一个二叉树。

回归树：

输入空间划分为M个单元  ，单元  对应输出  ，  是其对应的输入空间。

输出  取  上所有输出的均值：

下面，看输入空间的划分方法。

假设最优切分变量  ，最优切分点  ，输入空间被划分为两部分：

它们的输出是各自输入空间中样本标签值  的均值  和  。

因此，优化目标为：

穷举  ，找到最优切分变量  和切分点  。

之后，分治递归直到满足终止条件（例如误差小于某阈值、样本个数小于某阈值、没有更多特征等）。

分类树：

一个样本集合  的基尼指数（值越大，不确定性越大）：

其中，  是属于第  类的样本子集。

将样本集合  划分为 和  的两部分  和  ，对这种划分定义基尼指数：

它表征了经分割后，样本集合D的不确定性，同样地，基尼指数越小，样本不确定性越小。

选择使  最小的  。

之后，分治递归直到满足终止条件即可。