CART 决策树的生成是递归地构建二叉树的过程。对回归树用平方误差最小化>准则,对分类树用基尼指数最小化>准则。
给定训练集 $D\ ={(x_1,\ y_1),\ (x_2,y_2),\ ...(x_N,y_N)}$ 考虑如何生成回归树。
假如数据空间被划分为 $R_1$~$R_m$ 单元,每个单元有一个固定的输出值 $C_m$。
CART 回归树模型表达式:
$$
f(x)\ =\ \sum_{m=1}^{M}{C_m\ I(x\ \epsilon\ R_m)}
$$
这样可以计算模型输出值与真实值的误差:
$$
\sum_{x_i\ \epsilon\ R_m}{(y_i\ -\ f(x_i))}^2
$$
为了是平方误差最小话,易知当 $C_m$为相应单元上所有实际值的均值时,达到最优:
$$
\widehat{C_m}\ =\ ave(y_i|\ x_i\in\ R_m)
$$