CART算法框架

最小二乘回归树生成算法

输入: 训练数据集D
输出: 回归树f(x)
在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树:
(1) 选择最优切分变量j和切分点s，求解 min[min∑(yi-c1)^2+min∑(yi-c2)^2],
遍历变量j，对固定的切分变量j扫描切分点s，选择使上式最小的j,s;
(2) 用选定的对(j,s)划分区域并决定相应的输出值:
R1(j,s)={x|x(j)≤s}, R2(j,s)={x|x(j)>s}, cm=∑yi/Nm, x∈Rm, m=1,2;
(3) 继续对两个子区域调用步骤(1)(2)，直至满足停止条件;
(4) 将输入空间划分为M个区域R1, R2, ..., Rm，生成决策树: f(x)=∑cm * I(x ∈ Rm);

分类树生成算法

输入: 训练数据集D，停止计算的条件；
输出: CART分类树
根据训练数据集，从根结点开始递归的对每个结点进行以下操作，构建二叉决策树:
(1) 设结点的训练数据集为D，计算现有特征对该数据集的基尼指数，此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割为D1和D2两部分，计算A=a时的基尼指数Gini(D, A)；
(2) 在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子节点，将训练数据集依特征分配到两个子结点中；
(3) 对两个子结点递归的调用(1)(2)，直至满足停止条件；
(4) 生成CART决策树

算法停止计算的条件是:
(1) 结点中的样本个数小于预定阈值;
(2) 样本集的基尼指数小于预定阈值(认为样本基本属于同一类);
(3) 没有更多特征;

分类问题中，假设有K个类，样本点属于第k类的概率为p_k，则概率分布的基尼指数为：

Gini(p)=∑p_k(1-p_k)=1-∑p_k²

对于给定样本集合D，其基尼指数为：

Gini(D)=1-∑(|C_k| / |D|)²

在特征A的情况下，集合D被划分为D1, D2，则集合D在A条件下的基尼指数为：

Gini(D, A)=|D₁|/|D|Gini(D₁)+|D₂|/|D|Gini(D₂)