关于python:6GBDT随机森林RFXgboostLightGBM

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 反对列抽样，参考随机森林的特色抽样

GBDT、随机森林(RF)、Xgboost、LightGBM