Cart算法

Cart是Classification and regression tree的缩写，即分类回归树。它和前面的ID3， C4.5等算法思想一致都是通过对输入空间进行递归划分并确定每个单元上预测的概率分布，进而进行回归和分类任务。只不过由于任务的不同， 所以回归树和分类树的划分准则并不相同。

Cart生成

回归树

上面说到，我们将特征空间划分为一个个小的单元，假设共有 \(M\) 个，那么对于回归任务来说，每个单元就应该对于一个数值，我们分别记作 \(R_i\) 和 \(c_i\) 。那么决策树模型就可以表示为

即同一个所属同一个单元内的样本的值相同。
那么我们的每个单元上的预测误差就可以用下面的式子表示

令 \(L^{\prime}=0\) ，我们可以得到

但问题的难点在于如何对决策空间进化划分，文中给出了一种启发式的方法。

划分方法

选择第 \(j\) 个变量 \(x^{(j)}\) 和它的取值s，作为切分变量和切分点，并定义两个区域(两个划分集合)
\(R_1(j, s)=\{x|x^{(j)} \leq s\}\) 以及 \(R_2(j, s)=\{x|x^{(j)} > s\}\)
这样我们可以通过求解下式来找到每次最佳划分变量和切分点。

其中 \(j\) 从1到所有存在的特征， \(s\) 取遍 \(x^{(j)}\) 所有可能的取值。

生成算法

Step1：求解公式(1)得到切分变量与切分点
Step2：划分子区域 \(R_1(j, s)=\{x|x^{(j)} \leq s\}\) 以及 \(R_2(j, s)=\{x|x^{(j)} > s\}\) ，并决定子区域的输出值
Step3：递归调对子区域递归调用上述步骤，直至满足停止条件
Step4：划分为 \(M\) 个子区域，生成决策树完毕。

分类树

Cart分类树和前面的ID3以及C4.5大致相同，主要不同的地方在于划分方法(特征选择)有所区别，我们将重点对此部分进行阐述。

划分方法

Cart分类树使用基尼指数选择最有特征(表示集合 \(D\) 的不确定性，成正相关)，同时决定该特征的最优二值切分点。
样本的基尼指数计算如下：

定义在特征 \(A\) 的条件下，集合 \(D\) 的基尼指数为：

生成算法

Step1：对现有数据集的每个特征的每个取值计算其基尼指数并选择最小的特征 \(A\) 及其取值 \(A=a\) 作为切分点。
Step2：依照切分点将数据集划分为两个部分 \(D_1\) 和 \(D_2\) 。
Step3：继续对两个子集进行递归操作，直至达到停止条件(样本数小于阈值，样本基本属于同一类等等)。