vllbc02树回归
参考：https://cuijiahua.com/blog/2017/12/ml_13_regtree_1.html
1、ID3算法的弊端
回忆一下，决策树的树构建算法是ID3。ID3的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有4种取值，那么数据将被切分成4份。一旦按某特征切分后，该特征在之后的算法执行过程中将不会再起作用，所以有观点认为这种切分方式过于迅速。
除了切分过于迅速外，ID3算法还存在另一个问题，它不能直接处理连续型特征。只有事先将连续型特征离散化，才能在ID3算法中使用。但这种转换过程会破坏连续型变量的内在特性。
2、CART算法
与ID3算法相反，CART算法正好适用于连续型特征。CART算法使用二元切分法来处理连续型变量。而使用二元切分法则易于对树构建过程进行调整以处理连续型特征。具体的处理方法是：如果特征值大于给定值就走左子树，否则就走右子树。
CART算法有两步：
- 决策树生成：递归地构建二叉决策树的过程，基于训练数据集生成决策树，生成的决策树要尽量大；自上而下从根开始建立节点，在每个节点处要选择一个最好的属性来分裂，使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义”最好”：
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。
决策树剪枝我们先不管，我们看下决策树生成。
在决策树的文章中，我们先根据信息熵的计算找到最佳特征切分数据集构建决策树。CART算法的决策树生成也是如此，实现过程如下：
- 使用CART算法选择特征
- 根据特征切分数据集合
- 构建树
推导
选择最优切分变量j与切分点s：遍历变量j，对规定的切分变量j扫描切分点s，选择使下式得到最小 值时的(j,s)对。其中Rm是被划分的输入空间， \(\mathrm{cm}\) 是空间Rm对应的固定输出值。
\[ \min_{j, s}\left[\min_{c_{1}} \sum_{x_{i} \in R_{i}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min_{c_{2}} \sum_{x_{i} \in R_{i}(j, s)}\left(y_{i}-c_{1}\right)^{2}\right] \]
用选定的(j,s)对，划分区域并决定相应的输出值
\[ \begin{gathered} R_{1}(j, s)={x \mid x^{(j)} \leq s}, R_{2}(j, s)={x \mid x^{(j)}>s} \\\\ \hat{c}_{m}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i} \\\\ x \in R_{m}, m=1,2 \end{gathered} \]
继续对两个子区域调用上述步骤，将输入空间划分为 \(M\) 个区域R1,R2,..,Rm，生成决策树。
\[ f(x)=\sum_{m=1}^{M} \hat{c}_{m} I\left(x \epsilon R_{m}\right) \]
当输入空间划分确定时，可以用平方误差来表示回归树对于训练数据的预测方法，用平方误差最小 的准则求解每个单元上的最优输出值。