Cart回归树是许多树模型所用到的基本树，GBDT是一种集成提升树，使用加法模型与前向分布算法，XGBoost是boosting算法的一种，这个算法具有广泛的应用，能够对模型的准确率有一个较大的提升。
1.Cart回归树
通过不断将特征进行分裂，寻找最优划分特征构建树节点。
对第j个特征值小于s的划分为左子树，大于s的划分为右子树。CART树实质是特征维度进行划分，而这种划分优化是NP难问题，实际中常采用启发式方法解决。当CART回归树的目标函数采用平方误差时，目标函数为
因此，只要遍历所有特征的切分点，就可以找到最优的切分特征和切分点。
2.梯度提升树GBDT
采用加法模型与前向分布算法，以决策树为基学习器，多个决策树集成提升的方法。GBDT的一般模型：
M为树的个数，T表示决策树。
- GBDT选取特征划分节点的依据不再是熵、信息增益或是Gini指标等纯度指标，二十通过最小化每个节点的损失函数来进行每个节点处的分裂。
- GBDT算法采用平方误差作为损失函数，每一棵回归书学习之前所有决策树累加起来的残差，拟合当前的残差决策树，使用加法模型，所有的树共同决策。
训练过程
使用前向分布算法：
给定第m-1棵树的结果fm-1(x),求解第m棵树的参数估计值：
当采用平方误差损失函数时，损失函数变为：
其中r=y-fm-1(x)是当前模型拟合数据的残差，因此，求解目标参数值即拟合残差。
算法流程
1.初始化决策树，估计一个使损失函数最小化的常数构建一个只有根节点的树。
2.不断提升迭代：
a. 计算当前模型中损失函数的负梯度值，作为残差的估计值；
b. 估计回归树中叶子节点的区域，拟合残差的近似值；
c. 利用线性搜索估计叶子节点的区域的值，使损失函数极小化
d. 更新决策树
- 经过若干轮的提升迭代，输出最终模型
3.XGBoost
算法思想
XGBoost里，每棵树是不断加入，每加一棵树希望效果能够得到提升。实质上，每添加一棵树其实是学习一个新函数去拟合上次预测的残差，最后预测结果是每棵树样本所在的叶子节点的分数之和。
fk(xi)是第i个样本在第k个决策树上的预测分数。
如图所示，f(小孩)=2+0.9=2.9，f(老人)=-1-0.9=-1.9
训练过程
XGBoost的目标函数：
第一项是Training Loss，即预测值和真实值的差距，第二项是正则化项，防止模型的过拟合。正则化项有两项：
很明显，我们的目标是寻找ft最小化目标汉萨胡，XGBoost使用ft在0处的二阶泰勒展开式近似，最后简化的目标函数为：
其中，gi和hi都是通过前一个样本的梯度数据计算而来。
分裂节点
基于特征空间分裂节点是一个NP难问题，因此XGBoost使用了贪婪算法，遍历所有特征划分点，使用目标函数值作为评价函数，同时为了限制树的增长过深，还添加了阈值，只有当增益大于该阈值才进行分裂。
防止过拟合
此外，XGBoost为了防止过拟合提出了两种方法。
- 在每次迭代中给叶子节点的分数呈上一个缩减权重，使得每一棵树的影响力不会太大，留下更大的空间给后面生成树去优化模型
- 按层进行特征采样，类似于随机森林，选择分裂特征点时，随机选择部分特征。
XGBoost的优点
1.防止过拟合
2.目标函数的优化使用了待求函数的二阶导数
3.支持并行化，树与树之间虽然是串行的，但同层节点可以并行，训练速度块。
4.添加了对稀疏数据的处理。
XGBoost和随机森林的区别
XGBoost是逐个添加树，逐个提升，是一种Boosting算法，每一次树的添加必然会提升预测结果，最终得到最精确的预测结果。
随机森林是随机生成多个树，多个树共同进行决策，是一种Bagging算法。
