百家号原创文章，与2017年1月5日，由 "mlearn小研"发布;未经允许，禁止转载，谢谢合作

1.cart树

树模型分为两种类型：分类树输出是样本的标签(如0,1)，回归树输出是与样本相关的一个实数(如身高172.5，体重50.6)。

Cart(classification and regression tree)树是分类回归决策树，可以同时处理上述两种问题。

任何一个模型的训练过程都是使得某种误差最小，cart在处理分类问题时使用基尼指数作为目标函数，在处理回归问题时使用均方误差作为目标函数。

2.模型误差

模型的误差Error = Bias + Variance + Noise，一般而言我们只考虑前两项。简单模型具有大的Bias和小的Variance，模型比较稳定；复杂模型具有小的Bias和大的Variance，模型不稳定，在不同的数据集上预测结果差异较大，也就是通常所说的过拟合。

其中y_0是样本点的标签，f_hat(x_0)是预测值，f(x_0)是最优模型的预测值。Bias衡量的是学习的模型f_hat和最优模型f之间的差别，Variance衡量的是学习的模型f_hat自身的泛化能力。

通过boosting可以有效的降低Bias，从而获得更好的性能。

3.gradient boosting

属于boosting算法的一种，每次模型都建立在前一个模型损失函数梯度的方向，沿梯度下降最快。通用的gradient boosting算法框架

4.gbdt

Gbdt(gradient boosting decision tree)建立在gradient boosting框架下，使用的模型是树模型，通常是cart树。使用logit作为损失函数处理分类问题，使用均方误差作为损失函数处理回归问题。

5.xgboost

Xgboost是对gbdt的一种高效、分布式的实现。主要解决了两个问题，1.叶子节点的函数值；2.中间节点的特征选取和分裂数值。 同时为了分布式实现，对均损失函数进行二阶泰勒展开，利用了函数的二阶导数信息。

5.1)叶子节点的函数值

使用泰勒展开

将损失函数

转换为

在第t步时实际为

利用最小二乘算法可以很容易的得到最优的f_t

5.2)中间节点的特征和分裂值选取

贪心算法：贪心枚举所有特征所有可能的分裂值，找到使得增益最大的那一个。

逼近算法：将每一个维度的特征进行排序，线性扫描，计算数据分布的百分比，选出最优的分裂值。

此外xgboost的实现还有很多的优化，比如

1)同时支持CART和支持线性分类器作为基本分离器，。

2)支持自定义代价函数，要求函数二阶可导。

3)xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项降低了模型的variance，防止过拟合。

4)Shrinkage（缩减），在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。

5) column subsampling，从实践上看效果要优于使用全部的特征。

对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。

6)对缺失值、category值，稀疏数值的处理，从其余特征中学到default分类方向。