boost算法总结

boosting算法是集成的方式之一，使用前向分部算法(Forward stagewise additive modeling)构建一个加法模型，每次迭代时根据模型与标签值的误差创建一个基分类器叠加到模型上，逐步减少模型的偏差。前向分部是一种贪心算法，下面的Adaboost和GBDT也是基于这个算法进行的。流程如下

第三步L(yi,fm−1(xi)+βb(xi;γ))$L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma ))$中，L$L$是模型与标签之间误差造成的损失，这一步通过最小化误差得到两个参数β$\beta$，γ$\gamma$,最终的模型如（3）所示。

• Adaboost
  Adaboost针对的是二分类问题，使用的是对数损失，前向分部算法中的β$\beta$ 在这里是模型权重 αt${\alpha }_t$, γ$\gamma$在这里是样本的权重Dt$D_t$（图中像D的希腊字母不知道怎么读…）
  
  先对样本赋一个初始的权重1/m$1/m$, 根据预测的错误率计算模型权重αt=12ln(1−ϵtϵt)${\alpha }_t=\frac{1}{2}ln(\frac{1-{ϵ}_t}{{ϵ}_t})$这个表达式最小化对数损失推导出来的，详见参考 [2]。并重新计算每个样本的权重 ，错误率小的权重低反之权重高。

• GBDT
  gradient boosting decision tree梯度提升树，基分类器使用CART树。这一个使用均方误差作为损失函数的算法流程，基回归树F0$F_0$初始化用的是样本均值,梯度是标签值与预测值做差。
  
  第三步是求损失函数对模型的梯度，由于梯度方向损失下降最快所以总模型要沿梯度方向变化，每个基分类（回归）器去拟合梯度就好了。注意损失是标签值与当前模型预测值的损失。
  第四步就是构建一棵树拟合第三步的梯度
  第五步是计算回归树的预测值（取叶子节点平均值）作为树的输出直接加到模型上。

总的来说这里用的gradient boosting和梯度下降是一样的，梯度下降中让参数沿着梯度方向变化，所以参数增量是学习率*梯度，在这里每个回归树相当于加法模型的增量，所以回归树拟合的也是梯度。在实际使用中最后一步是把回归树乘以学习率加在模型上的。
Fm(x)=Fm−1(x)+η∑Jj=1γjmI$F_m(x)=F_{m-1}(x)+\eta \sum _{j=1}^J{\gamma }_{jm}I$
GBDT例子见参考 [3]， 讲解很清晰。

• 决策树简要介绍
  训练过程就是构建树的过程，节点的构建是选择分割属性，也就是样本特征，对应特征值小于或大于分割属性的样本分为两类。对分割属性的选择指标通常有熵，信息增益和gini指标，熵是指信息的混乱程度，所以在选择分割属性时遍历所有特征，哪个特征分类后的熵值低就用其作为分割属性，使用熵做指标的算法有C4.5、ID3。信息增益是根据分割属性分类前后熵值的变化，增益大的特征作为分割属性。gini指标也是描述不纯度的一种指标，对应着CART树算法。
  CART树是最常用的一种决策树，全称分类回归树，做分类时使用gini不纯度作为分裂指标回归是使用均方误差作为分裂指标，哪个特征分类后两类的均方误差和低就当做分割属性。用树做回归时其预测值是叶子节点的均值。对于连续值会将其划分为区间离散化，所以回归树拟合的曲线是阶梯状的。

参考文献
[1] https://blog.****.net/dark_scope/article/details/24863289
[2] https://zhuanlan.zhihu.com/p/25096501?refer=data-miner
[3] https://blog.****.net/qq_22238533/article/details/79185969