共计 3692 个字符，预计需要花费 10 分钟才能阅读完成。
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 反对列抽样，参考随机森林的特色抽样
