机器学习算法——集成学习

一、集成学习思想

1.概念

• 概念：集成学习是机器学习中的一种思想，它通过多个模型的组合形成一个精度更高的模型，参与组合的模型成为弱学习器。训练时，使用训练集依次训练出这些弱学习器，对未知样本进行预测时，使用这些弱学习器联合进行预测（是在预测的时候综合结果）
• 训练单个模型会导致 能力过强，则容易过拟合；训练多个简单模型，再将他们集成，则能力变强，不易过拟合

2.分类

• Bagging：随机森林（算法）
• Boosting：Adaboost，GBDT，XGBoost（最重要），LightGBM

（1）Bagging思想

• 有放回的抽样 产生不同的训练集（需保证特征是一样的），从而训练各自的基学习器
• 通过平权投票，多数表决的方式决定预测结果
• 弱学习器可以并行训练

（2）Boosting思想

• 每一个训练器重点关注前一个训练器的不足的地方进行训练
• 通过加权投票的方式，得出预测结果
• 串行的训练方式（学习有先后顺序）

特点：随着学习的积累从弱到强，每加入一个弱学习器，整体能力就会得到提升

二、随机森林算法

1.基础

• 随机森林是基于Bagging思想实现的一种集成学习算法，采用决策树模型作为每一个弱学习器

• 随机森林步骤

  • 随机选m条数据
  • 随机选取k个数据特征
  • 训练决策树（尽量选择CART树，计算量小，既能解决分类，也能解决回归问题）
  • 重复上面步骤构造n个弱决策树
  • 平权投票集成n个弱决策树

2.API

sklearn.ensemble.RandomForestClassifier()

• n_estimators:决策树数量（default = 10）
• Criterion:entropy（C4.5）或者gini(CART树)(default = gini)
• max_depth:指定树的最大深度（default = None表示树会尽可能的生长）
• max_features = "auto"，决策树构建时使用的最大特征数量
  • auto:max_features = sqrt(n_feature)
  • sqrt:max_features = sqrt(n_featrue)
  • log2:max_features = log2(n_feature)
  • None:max_features = n_features(只采样，不采特征，所有特征都用)
• bootstrap：是否采用有放回抽样，如果为False将会使用全部训练样本（default = True）
• mini_samples_split:节点分裂所需最小样本数（default = 2）
  • 如果节点样本数少于min_samples_split,则不会再进行划分
  • 如果样本量不大，不需要设置这个值
  • 如果样本数量级非常大，则推荐增大这个值
• mini_samples_leaf:叶子节点的最小样本数（default = 1）
  • 如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝
  • 较小的叶子节点样本数量使模型更容易捕捉训练数据中的噪声
• mini_impurity_split:节点划分最小不纯度
  • 如果这个节点的不纯度（基尼系数，均方差）小于这个阈值，则该节点不再生成子节点
  • 一般不推荐改动默认值1e-7

三、Adaboost算法

主要是提高泛化能力

• 核心思想：通过逐步提高那些被前一步分类错误的样本的权重来训练一个强分类器

• 算法推导

  • 初始化训练数据权重相等（$\frac{1}{n}$：n为样本数量），训练第一个学习器
    • 根据预测结果找一个错误率最小的分类点，计算，更新：样本权重，模型权重
  • 根据新权重的样本集训练第2个学习器
    • 根据预测结果找一个错误率最小的分类点，计算，更新：样本权重，模型权重
  • 迭代训练在前一个学习器的基础上，根据新的样本权重训练当前学习器，知道训练出m个弱学习器
  • m个弱学习器集成预测公式：$H(x)=sign({\sum }_{i=1}^m{a}_i{h}_i(x))$
    • $h_i(x)$：每一个机器学习的预测结果
    • $a_i$：最终加权求和的各个权重
    • 做二分类任务时，结果大于0，归为正类；结果小于0，归为负类

• 在上面步骤中，我们需要计算模型权重和样本权重

  • 模型权重计算公式：$a_t=\frac{1}{2}In(\frac{1-{ϵ}_t}{{ϵ}_t})$
    • ${ϵ}_t$：表示第t个弱学习器的错误率
    • 正确率大的模型，前面的权重要大一些
  • 样本权重计算公式：$D_{t+1}(x)=\frac{D_t(x)}{Z_t}\ast \{\begin{array}{ll}{e}^{-a_t},& \text{预测值}=\text{真实值}\\ e^{a_t},& \text{预测值}\not\approx \text{真实值}\end{array}$
    • $Z_t$为归一化值（所有样本权重总和）
    • $D_t(x)$为样本权重
    • $a_t$为模型权重
    • 当预测错误，即$预测值\not\approx 真实值$，将相应内容的权重放大，则$D_{t+1}(x)$增大

• 示例

构建第一个弱学习器

1. 寻找最优分裂点
   • 对特征值进行排序，确定分裂点为：0.5，1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5
   • 当以0.5为分裂点时，有5个样本分类错误（0.5左边应该为1，全部划分正确；右边应该为-1，有五个为1，则有五个划分错误）
   • 当以1.5为分裂点时，有4个样本分类错误
   • 当以2.5为分裂点时，有3个样本分类错误
   • 当以3.5为分裂点时，有4个样本分类错误
   • 4.5……4
   • 5.5……4
   • 6.5……4
   • 7.5……4
   • 8.5……3
   • 最终选择以3.5作为分裂点，计算得出其学习器错误率为0.3
2. 计算模型权重：1/2 * np.log((1-0.3)/0.3) = 0.4236
3. 更新样本权重
   • 分类正确样本为：0，1，2，3，4，5，9，计算公式为$e^{-a_t}$，则正确样本权重变化系数为$e^{-0.4236}=0.6547$，当前权重$0.1\ast 0.6547=0.06547$
   • 分类错误样本为：6，7，8，计算公式为$e^{a_t}$，则错误样本权重变化系数为$e^{0.4236}=1.5275$，当前权重$0.1\ast 1.5275=\mathrm{0..15275}$
   • 将上面所有权重进行归一化，则分类正确样本最终权重为0.07143；分类错误样本最终权重为0.1667

构造第二个弱学习器

1. 寻找最优分裂点
   • 对特征值进行排序，确定分裂点为：0.5，1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5
   • 当以1.5为分裂点时，有4个样本分类错误，错误率为0.07143*1+0.16667 *3
   • 当以2.5为分裂点时，有3个样本分类错误，错误率为0.16667*3 = 0.57144
   • ………………
   • 当以8.5为分裂点时，有3个样本分类错误，错误率为0.07143*3 = 0.21429
   • 最终选择错误率最小的，选择以8.5作为分裂点，计算出基学习器错误率为：0.21429
2. 计算模型权重：0.64963
3. 计算样本权重
   • 分类正确样本权重（样本1，2，3，9为0.0373，样本6，7，8权重为0.087）
   • 分类错误样本权重为0.1368
4. 进行归一化得最终权重
   • 样本1，2，3，9为0.0455
   • 样本6，7，8为0.1060
   • 样本3，4，5为0.1667

在最终获取强学习器$H(x)=sign(0.4236\ast h_1(x)+0.64963\ast h_2(x))$

若$H(x)$的值大于0则归于正类，小于0则归为负类

四、GBDT算法

1.BDT（残差提升树）

• 思想：通过拟合残差的思想来进行提升（残差：真实值-预测值）

2.GBDT（梯度残差提升树）

• 思想：梯度提升树不再拟合残差，而是利用梯度下降的近似方法，利用损失函数（在模型训练的时候使用）的负梯度作为提升树算法中的残差近似值

  1. 前一轮迭代得到的强学习器是：$f_{i-1}(x)$

  2. 损失函数的平方损失是：$L(y,f_{i-1}(x))$

  3. 本轮迭代的目标是找到一个弱学习器：$h_i(x)$让本轮的损失最小化$L(y,f_i(x))=L(y,f_{i-1}(x)+h_i(x))=(y-f_{i-1}(x)-h_i(x){)}^2$

  4. 则要拟合的负梯度为：$\frac{\partial L(y,f(x_i))}{\partial f(x_i)}=f(x_i)-y_i$

     $-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]=y_i-f(x_i)$

• 示例

  • 已知

  x	1	2	3	4	5	6	7	8	9	10
  目标值	5.56	5.70	5.91	6.40	6.80	7.05	8.90	8.70	9.00	9.05

  • 初始化弱学习器（CART树）：找到一个模型预测值使得第一个弱学习器的平方误差最小（即：求损失函数对$f(x_i)$的导数，并令导数为0）

  • $L(y,f(x))=\frac{1}{2}{\sum }_{i=1}^n(y_i-f_i(x){)}^2$求平方误差最小

    $\frac{\partial L(y,f(x))}{\partial f(x_i)}={\sum }_{i=1}^n(y_i-f_i(x))\ast (y_i-f(x_i){)}^{\prime }=\sum -{i=1}^n(y_i-f(x_i))\ast (-1)={\sum }_{i=1}n(-y_i+f(x_i))=0$

    $nf(x_i)={\sum }_{i=1}^n{y}_i$，整理得：$f(x_i)=\frac{{\sum }_{i=1}^n{y}_i}{n}=7.31$

    从公式可得：初始化树桩输出值为目标值的均值时，可使得第一个弱学习器的平方误差最小

  • 构建第1个弱学习器，根据负梯度的计算方法得到下表：

  x	1	2	3	4	5	6	7	8	9	10
  目标值	5.56	5.70	5.91	6.40	6.80	7.05	8.90	8.70	9.00	9.05
  预测值	7.31	7.31	7.31	7.31	7.31	7.31	7.31	7.31	7.31	7.31
  负梯度	-1.75	-1.61	-1.40	-0.91	-0.51	-0.26	1.59	1.39	1.69

五、XGBoost算法

1.公式推导

它是极端梯度提升树，集成学习方法的王牌

• 构建思想

  1. 构建模型的方法是最小化训练数据的损失函数：$mi{n}_f\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))$，训练的模型复杂度高，易过拟合（使用的决策树）
  2. 在损失函数中加入正则项，$min\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))+\Omega (f)$提高对未知测试数据的泛化能力
     • 正则化项（控制决策树的复杂度，越小越好）用来降低模型的复杂度：$\Omega (f)=\gamma T+\frac{1}{2}\lambda ||w|{|}^2$
       • $\gamma T$中的T表示一棵树的叶子结点数量（越小越好，树模型简单）
       • $\lambda ||w|{|}^2$中的$w$表示叶子结点输出值的组成问题，$||w||$向量的模；$\lambda$对该项的调节系数

• XGBoost是对GBDT的改进，并且在损失函数中加入了正则化：$obj(\theta )={\sum }_i^{n}L(y_i,{\hat{y}}_i)+{\sum }_{k=1}^K\Omega (f_k)$

  进行t次迭代的学习模型的目标函数如下：$ob{j}^{(t)}={\sum }_{i=1}^{n}L(y_i,{\widehat{y_i}}^{(t)})+{\sum }_{k=1}^t\Omega (f_k)={\sum }_{i=1}^{n}L(y_i,{\widehat{y_i}}^{(t-1)}+f_t(x_i))+{\sum }_{k=1}^{t-1}\Omega (f_k)+\Omega (f_t)$

  • 解释：

    ${\sum }_{i=1}^{n}L(y_i,{\widehat{y_i}}^{(t)})$：第t棵树的损失函数值

    ${\sum }_{i=1}^{n}L(y_i,{\widehat{y_i}}^{(t-1)}+f_t(x_i))$：前t个机器学习构成的强学习器的预测结果加上第t次的预测结果

    ${\sum }_{k=1}^t\Omega (f_k)$：t棵树的正则化系数，它就等于前t棵树的正则化系数加上第t棵树的正则化系数${\sum }_{k=1}^{t-1}\Omega (f_k)+\Omega (f_t)$

    要找损失函数最小值，则后面${\sum }_{k=1}^{t-1}\Omega (f_k)+\Omega (f_t)$可以直接省略
    将${\sum }_{i=1}^{n}L(y_i,{\widehat{y_i}}^{(t-1)}+f_t(x_i))$展开成前一次的预测结果，前一次的损失函数，应该使用泰勒展开

  • 泰勒展开（目的：使用t-1个若学习器构成的集成模型损失求解当前t个弱学习器的损失）

    $ob{j}^{(t)}\approx {\sum }_{i=1}^m[L(y_i,{\widehat{y_i}}^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+{\sum }_{k=1}^{t-1}\Omega (f_k)+\Omega (f_t)$

    其中$g_i$和$h_i$分别为损失函数的一阶导，二阶导

    $g_i={\partial }_{{\hat{y}}^{(t-1)}}L(y_i,{\hat{y}}^{(t-1)})$

    $h_i={\partial }_{{\hat{y}}_i^{(t-1)}}^{2}L(y_i,{\hat{y}}^{(t-1)})$

    观察目标函数，发现下面两项（$L(y_i,{\widehat{y_i}}^{(t-1)})$ ${\sum }_{k=1}^{t-1}\Omega (f_k)$）表示t-1个弱学习器构成学习器的目标函数，都是常数，我们可以将其去掉

    $$\begin{gathered} ob{j}^{(t)}\approx {\sum }_{i=1}^m[L(y_i,{\widehat{y_i}}^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+{\sum }_{k=1}^{t-1}\Omega (f_k)+\Omega (f_t) \\ \approx {\sum }_{i=1}^m[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\Omega (f_t) \\ \approx {\sum }_{i=1}^m[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\gamma T+\frac{1}{2}\lambda ||w|{|}^2 \end{gathered}$$

  • 角度转换：从样本角度转为按照叶子节点输出角度，优化损失函数最终为$ob{j}^{(t)}\approx {\sum }_{i=1}^m[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\gamma T+\frac{1}{2}\lambda ||w|{|}^2$（$f_t(x_i)$：表示样本的预测值）

    目标函数中各项可以做以下变换

    • $g_i{f}_t(x_i)$表示样本的预测值，表示为：${\sum }_{i=1}^m{g}_i{f}_t(x_i)={\sum }_{j=1}^T({\sum }_{i\in i_j}^T{g}_i)w_j$
    • $h_i{f}_t(x_i{)}^2$转换成叶子结点的问题，表示为：${\sum }_{i=1}^m\frac{1}{2}{h}_i{f}_t^2(x_i)=\frac{1}{2}{\sum }_{j=1}^T({\sum }_{i\in I_j}{h}_i)w_j^2$
    • $\lambda ||w|{|}^2$由于本身就是从叶子角度来看，表示为：$\frac{1}{2}\lambda ||w|{|}^2=\frac{1}{2}\lambda {\sum }_{i=1}^T{w}_i^2$

    最终：

    $$\begin{gathered} ob{j}^{(t)}\approx {\sum }_{i=1}^m[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\gamma T+\frac{1}{2}\lambda ||w|{|}^2 \\ ={\sum }_{j=1}^T[({\sum }_{i\in I_j}{g}_i)w_j+\frac{1}{2}({\sum }_{i\in I_j}{h}_i)w_j^2]+\gamma T+\frac{1}{2}\lambda {\sum }_{j=1}^T{w}_j^2 \\ ={\sum }_{j=1}^T[({\sum }_{i\in I_j}{g}_i)w_j+\frac{1}{2}({\sum }_{i\in I_j}{h}_i)w_j^2+\frac{1}{2}\lambda w_j^2]+\gamma T \\ ={\sum }_{j=1}^T[({\sum }_{i\in I_j}{g}_i)w_j+\frac{1}{2}({\sum }_{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T \end{gathered}$$

    令$G_i={\sum }_{i\in I_j}{g}_i$表示所有样本的一阶导之和；$H_i={\sum }_{i\in I_j}{h}_i$表示所有样本的二阶导之和

    最终，$ob{j}^{(t)}={\sum }_{i=1}^T[G_i{w}_i+\frac{1}{2}(H_i+\lambda )w_i^2]+\gamma T$

  • 求损失函数最小值$ob{j}^{(t)}={\sum }_{i=1}^T[G_i{w}_i+\frac{1}{2}(H_i+\lambda )w_i^2]+\gamma T$对w求导并令其等于0，可得到w的最优值$w_i=-\frac{G_i}{H_i+\lambda }$，最优w，代入公式可求目标函数的最小值

    $$\begin{gathered} ob{j}^{(t)}={\sum }_{i=1}^T[G_i(-\frac{G_i}{H_I+\lambda })+\frac{1}{2}(H_i+\lambda )(-\frac{G_i}{H_i+\lambda }{)}^2]+\gamma T \\ ={\sum }_{i=1}^T[-\frac{G_i^2}{H_i+\lambda }+\frac{1}{2}(\frac{G_i^2}{H_i+\lambda })]+\gamma T \\ =-\frac{1}{2}{\sum }_{i=1}^T(\frac{G_i^2}{H_i+\lambda })+\gamma T \end{gathered}$$

  • 最终的目标函数是$ob{j}^{(t)}=-\frac{1}{2}{\sum }_{i=1}^T(\frac{G_i^2}{H_i+\lambda })+\gamma T$，该公式也叫做打分函数，从损失函数，数的复杂度两个角度来衡量一棵树的优劣，当我们构建树的时，可以用来选择树的划分点

    $$\begin{gathered} Gain=Ob{j}_{L+R}-(Ob{j}_L+Ob{j}_R) \\ =[-\frac{1}{2}\frac{(G_L+G_R{)}^2}{H_L+H_R+\lambda }+\gamma T]-[-\frac{1}{2}(\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda })+\gamma (T+1)] \\ =\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 \end{gathered}$$

    根据上面的$Gain$值（分类前-分裂后的分数）

    • 对树中的每个叶子结点尝试进行分类
    • 如果$gain>0$，则分裂之后树的损失更小，会考虑此次分裂；如果$gain<0$，则说明分裂之后的分数比分裂之前的分数大，此时不建议分裂
    • 当触发以下条件时停止分裂：1、达到最大深度 2、叶子节点数量低于某个阈值 3、所有的结点再分裂不能降低损失

2.API

bst = XGBClassifier(n_estimators,max_depth,learning_rate,objective)
- objective目标函数（损失函数）

相关参数：

• n_estimators：子学习器个数
• learning_rate：学习率，用于限制子学习器的过拟合，提高模型的泛化能力
• verbosity：是否输出详细信息，2是输出详细信息，1是偶尔输出，0是不输出
• subsample：样本子采样数，用于限制学习器的过拟合，提高模型的泛化能力
• max_depth：树的最大深度，对基学习器函数空间的正则化，一种预修剪手段
• objective：损失函数，常见方法包括线性回归‘reg:linear’、逻辑回归‘reg:logistic’、二分类逻辑回归‘binary:logistic’、多分类'multi:softmax'、平方误差‘reg:squarederror’
• booster：基学习器类型（defualt=gbtree，一般不用修改），xgboost中采用的基学习器，如梯度提升树'gbtree'，梯度提升线性模型‘gblinear’
• gamma：分裂阈值，即最小损失分裂，用来控制分裂遵循的结构分数提升下限阈值（在分裂之后，提升的损失不是特别大的话，没有超过gamma值，则不会再进行分裂）
• in_child_weight：叶子节点最小权重，即节点中所有样本的二阶导数值之和，可视为是对叶子节点的正则化，是一种后剪枝的手段（叶子最小权重必须比它大才行，比它小会被我们剪掉）
• reg_alpha：L1正则化系数，对集成模型进行L1正则化（以子节点的个数为约束）的系数
• reg_lambda：L2正则化系数
• nthread：最大并发线程数
• random_state：随机种子，控制模型的随机性