GBDT、随机森林(RF)、Xgboost、LightGBM
1.CART树
损失函数参考上一章
算法流程：
Step1：对于数据集D，遍历所有特色，依据Gini(D,A)找到A，用A对D进行划分
Step2：反复步骤1，为每个节点找寻到最佳特色直到：1）节点样本数小于阈值2）Gini(D,A)小于阈值3）没有更多的特征值
2.随机森林（bagging）
初始化：决策树的个数n，每个决策树里每次决裂所选取的特色个数k，$k = {\log _2}n$
森林函数：$f(x) = \frac{1}{n}\sum\limits_i^n {{\varphi _i}(x)}$
算法流程：
Step1：从原始数据集中有放回的抽n次，每次m个样本
Step2：$k = {\log _2}n$，对每一组m个数据进行训练CART树，特色是从原始特色中随机抉择k个
Setp3：每个树决裂上来，直到进行条件（参考CART树）
3.AdaBoost（Boosting）
AdaBoost是boosting的想法，由一个弱学习器一直学习失去强学习器。AdaBoost次要增大了被分错样本的权重，扭转的是样本的权重。
算法流程：
Input：训练数据集$T = \{ ({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\}$
Output: 最终的分类器$G(x)$
1.初始化样本权重${D_0} = ({w_{0,1}},{w_{0,2}},...,{w_{0,N}})$
2.对设置要训练的M棵树(学习器)
- 应用${D_m}$的权重样本数据进行训练，失去一个分类器${G_m}(x)$
- 依据${G_m}(x)$计算分类误差：${e_m} = \sum\limits_{i = 1}^N {{w_{mi}}} I({G_m}({x_i}) \ne {y_i})$
- 计算${G_m}(x)$的系数：${\alpha _m} = \frac{1}{2}\log \frac{{1 - {e_m}}}{{{e_m}}}$
- 更新训练样本的权重：
$$\begin{array}{l}{D_m} = ({w_{m,1}},{w_{m,2}},...,{w_{m,N}})\\{w_{m,i}} = \frac{{{w_{m - 1,i}}}}{{{z_m}}}\exp ( - {\alpha _m}{y_i}{G_m}({x_i}))\end{array}$$
- 构建最终分类器的线性组合：
$$G(x) = sign(\sum\limits_{m = 1}^M {{\alpha _m}{G_m}(x)} )$$
其中权重有以下特点：
- ${e_m}$越小，${\alpha _m}$越大
- 分类谬误的${w_{m,i}}$ > 分类正确的${w_{m,i}}$
4.GBDT(Gradient Boost Decision Tree)梯度晋升树
GBDT是以回归树为基学习器的算法，采纳Boosting思维。GBDT的外围在于：每一棵树学的都是之前所有树叠加后的残差。利用损失函数的负梯度在以后模型的值作为回归树的残差近似值。
算法流程：
Input:训练数据集$T = \{ ({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\}$
Output:回归树$\widehat f(x)$
1.初始化：${f_0}(x) = \mathop {\arg \min }\limits_c \sum\limits_{i = 1}^N {L({y_i},c)}$
2.对设置M棵树m=1,2,...,M:
- 对i=1,2,...,N个样本，计算：${r_{mi}} = - {\left[ {\frac{{\partial L({y_i},f({x_i}))}}{{\partial f({x_i})}}} \right]_{f(x) = {f_{m - 1}}(x)}}$
- 对${r_{mi}}$拟合一棵回归树，失去第m棵树的结点最优区域${R_{mj}},j = 1,2,...,J$。这个J是J个类别（分类树），叶子节点个数，能够了解为y的值个数（回归树）
- 求解最优j区域（特色）的阈值，计算${C_{mj}} = \min \sum\limits_{{x_i} \in {R_{mj}}} {L({y_i},{f_{m - 1}}({x_i}) + c)}$
- 更新${f_m}(x) = {f_{m - 1}}(x) + \sum\limits_{j = 1}^J {{C_{mj}}I(x \in {R_{mj}})}$
3.失去回归树：${f_m}(x) = \sum\limits_{m = 1}^M {\sum\limits_{j = 1}^J {{C_{mj}}I(x \in {R_{mj}})} }$
这里须要提一点，如果设置树的深度为5，每次2决裂，那么J=10个叶子节点。有J个叶子节点就有J个判断条件。
5.Xgboost
GBDT的升级版，从下面GBDT的算法流程中能够看出在负梯度中是一阶导数，并且在求解Cmj的时候是一个线性搜寻，Xgboost把Rmj和Cmj合在一起求解，并且在损失函数中退出正则项
算法流程：
Input:训练数据集$T = \{ ({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\}$
Output:回归树$\widehat f(x)$
1.初始化：${f_0}(x) = \mathop {\arg \min }\limits_c \sum\limits_{i = 1}^N {L({y_i},c)}$
2.对设置M棵树m=1,2,...,M：
- 对i=1,2,...,N个样本，计算一阶导数合${G_t} = \sum\limits_{i = 1}^N {{g_{ti}}} $以及二阶导数合${H_t} = \sum\limits_{i = 1}^N {{h_{ti}}} $,其中：
$$\begin{array}{l}{g_{ti}} = \frac{{\partial L({y_i},{f_{t - 1}}({x_i}))}}{{\partial {f_{t - 1}}({x_i})}},{h_{ti}} = \frac{{{\partial ^2}L({y_i},{f_{t - 1}}({x_i}))}}{{\partial {f_{t - 1}}^2({x_i})}}\end{array}$$
- 求解最优j=1,2,...,J区域（特色）以及区域j阈值，依据${G_{tj}} = \sum\limits_{xi \in {R_{tj}}}^{} {{g_{ti}}} ,{H_{tj}} = \sum\limits_{xi \in {R_{tj}}}^{} {{h_{ti}}}$，求解叶子节点最优解：${\omega _{tj}} = - \frac{{{G_{tj}}}}{{{H_{tj}} + \lambda }}$,这个相似于GBDT的区域求解。
- 对于k=1,2,...,K个特色，每个k特色线性划分不同阈值进行线性搜寻。初始化${\rm{score = 0}},{G_L} = 0,{G_R} = 0$，对每个i样本，求左右树的一阶导数合二阶导数：
$$\begin{array}{l}{G_L} = {G_L} + {g_{ti}},{G_R} = G - {G_L}\\{H_L} = {H_L} + {h_{ti}},{H_R} = H - {H_L}\end{array}$$
- 计算$score = \max (score,\frac{1}{2}(\frac{{G_L^2}}{{{H_L} + \lambda }} + \frac{{G_R^2}}{{{H_R} + \lambda }} - \frac{{{{({G_L} + {G_R})}^2}}}{{{H_L} + {H_R} + \lambda }}) - \gamma )$
3.基于最大的score进行决裂
4.失去回归树：${f_m}(x) = \sum\limits_{m = 1}^M {\sum\limits_{j = 1}^J {{C_{mj}}I(x \in {R_{mj}})} }$
参考https://ranmaosong.github.io/...
6.LightGBM
具体算法参见https://zhuanlan.zhihu.com/p/...
优化点：
- 特色对不同取值进行直方图分bin
- 带深度限度的叶子节点决裂，Xgboost在决裂叶子节点时候是对同一层的所有叶子节点无差别决裂，权重雷同。这个是不适合的，因为每个叶子节点的决裂增益各不相同。ligtgbm对每一层只找到决裂增益最大的一个叶子节点进行决裂。
- 对每个样本进行权重加成
- 稠密特色合并。
这里比拟下GBDT合Xgboost的10个区别：
- GBDT是机器学习算法，Xgboost是工程实现
- Xgboost退出了正则项来避免过拟合
- Xgboost采纳一阶和二阶泰勒开展损失函数
- Xgboost反对多种基学习器
- Xgboost对缺失值进行了解决
- Xgboost退出了Shrinkage（缩减），每棵树乘上一个学习率，这样的话能够多学习几轮。
- Xgboost反对叶子节点决裂的并行操作。
- Xgboost采纳贪婪算法，也就是对每次决裂都是最大增益，而不是一个总的最小损失函数
- Xgboost对特色当时排序了
- Xgboost反对列抽样，参考随机森林的特色抽样