4 Boosting
4.1 什么是boosting
随着学习的积累从弱到强
简而言之：每新加入一个弱学习器，整体能力就会得到提升
代表算法：Adaboost，GBDT，XGBoost，LightGBM
4.2 实现过程
1.训练第一个学习器
2.调整数据分布
3.训练第二个学习器
4.再次调整数据分布
5.依次训练学习器，调整数据分布
6.整体过程实现
4.3 bagging与boosting的区别
- 区别一:数据方面
- Bagging：对数据进行采样训练；
- Boosting：根据前一轮学习结果调整数据的重要性。
- 区别二:投票方面
- Bagging：所有学习器平权投票；
- Boosting：对学习器进行加权投票。
- 区别三:学习顺序
- Bagging的学习是并行的，每个学习器没有依赖关系；
- Boosting学习是串行，学习有先后顺序。
- 区别四:主要作用
- Bagging主要用于提高泛化性能（解决过拟合，也可以说降低方差）
- Boosting主要用于提高训练精度 （解决欠拟合，也可以说降低偏差）
4.4 AdaBoost介绍
4.4.1 构造过程细节
- 步骤一：初始化训练数据权重相等，训练第一个学习器。
该假设每个训练样本在基分类器的学习中作用相同，这一假设可以保证第一步能够在原始数据上学习基本分类器H1(x)
步骤二：AdaBoost反复学习基本分类器，在每一轮m=1,2,…,M 顺次的执行下列操作：
- （a） 在权值分布为Dt的训练数据上，确定基分类器；
- （b） 计算该学习器在训练数据中的错误率：
- \varepsilon _t = P(h_t(x_t)\neq y_t)ε**t=P(h**t(x**t)≠y**t)
- （c） 计算该学习器的投票权重：
- \alpha _t=\frac{1}{2}ln(\frac{1-\varepsilon _t}{\varepsilon _t})α**t=21l**n(ε**t1−ε**t)
- （d） 根据投票权重，对训练数据重新赋权
将下一轮学习器的注意力集中在错误数据上
- 重复执行a到d步，m次；
- 步骤三：对m个学习器进行加权投票
4.4.2 关键点剖析
如何确认投票权重？
如何调整数据分布？
4.4.3 案例介绍
给定下面这张训练数据表所示的数据，假设弱分类器由xv产生，其阈值v使该分类器在训练数据集上的分类误差率最低，试用Adaboost算法学习一个强分类器。
问题解答：
步骤一：初始化训练数据权重相等，训练第一个学习器：
D_1=(w_{11},w_{12},…,w_{110},)D1=(w11,w12,…,w110,)
w_{1i}=0.1, i=1,2,…,10w1i=0.1,i=1,2,…,10
步骤二：AdaBoost反复学习基本分类器，在每一轮m=1,2,…,M顺次的执行下列操作：
当m=1的时候：
（a）在权值分布为D1的训练数据上，阈值v取2.5时分类误差率最低，故基本分类器为:
6,7,8被分错
（b）计算该学习器在训练数据中的错误率：\varepsilon _1 = P(h_1(x_1)\neq y_1)=0.3ε1=P(h1(x1)≠y1)=0.3
（c）计算该学习器的投票权重：\alpha _1=\frac{1}{2}ln(\frac{1-\varepsilon _1}{\varepsilon _1})=0.4236α1=21l**n(ε11−ε1)=0.4236
（d）根据投票权重，对训练数据重新赋权:
D_2=(w_{21},w_{22},…,w_{210},)D2=(w21,w22,…,w210,)
根据下公式，计算各个权重值
经计算得，D2的值为：
D_2=(0.07143,0.07143,0.07143,0.07143,0.07143, 0.07143,0.16667,0.16667,0.16667,0.07143)D2=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)
计算过程：
H_1(x)=sign[0.4236h_1(x)]H1(x)=sig**n[0.4236h1(x)]
分类器H1(x)在训练数据集上有3个误分类点。
当m=2的时候：
（a）在权值分布为D2的训练数据上，阈值v取8.5时分类误差率最低，故基本分类器为:
3,4,5被分错
（b）计算该学习器在训练数据中的错误率：\varepsilon _2 = P(h_2(x_2)\neq y_2)=0.2143ε2=P(h2(x2)≠y2)=0.2143
（c）计算该学习器的投票权重：\alpha _2=\frac{1}{2}ln(\frac{1-\varepsilon _2}{\varepsilon _2})=0.6496α2=21l**n(ε21−ε2)=0.6496
（d）根据投票权重，对训练数据重新赋权:
经计算得，D3的值为：
D_3=(0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.1667, 0.1060, 0.1060, 0.1060,0.0455)D3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)
H_2(x)=sign[0.4236h_1(x)+0.6496h_2(x)]H2(x)=sig**n[0.4236h1(x)+0.6496h2(x)]
分类器H2(x)在训练数据集上有3个误分类点。
当m=3的时候：
（a）在权值分布为D3的训练数据上，阈值v取5.5时分类误差率最低，故基本分类器为:
（b）计算该学习器在训练数据中的错误率：\varepsilon _3 = 0.1820ε3=0.1820
c）计算该学习器的投票权重：\alpha _3=0.7514α3=0.7514
（d）根据投票权重，对训练数据重新赋权:
经计算得，D2的值为：
D_4=(0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)
H_3(x)=sign[0.4236h_1(x)+0.6496h_2(x)+0.7514h_3(x)]H3(x)=sig**n[0.4236h1(x)+0.6496h2(x)+0.7514h3(x)]
分类器H3(x)在训练数据集上的误分类点个数为0。
步骤三：对m个学习器进行加权投票,获取最终分类器
H_3(x)=sign[0.4236h_1(x)+0.6496h_2(x)+0.7514h_3(x)]H3(x)=sig**n[0.4236h1(x)+0.6496h2(x)+0.7514h3(x)]
4.4.4 api
- from sklearn.ensemble import AdaBoostClassifier
- api链接:https://scikit-
- learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html#sklearn.ensemble.AdaBoostClassifier
4.5 小结
- 什么是Boosting 【知道】
- 随着学习的积累从弱到强
- 代表算法：Adaboost，GBDT，XGBoost，LightGBM
- bagging和boosting的区别【知道】
- 区别一:数据方面
- Bagging：对数据进行采样训练；
- Boosting：根据前一轮学习结果调整数据的重要性。
- 区别二:投票方面
- Bagging：所有学习器平权投票；
- Boosting：对学习器进行加权投票。
- 区别三:学习顺序
- Bagging的学习是并行的，每个学习器没有依赖关系；
- Boosting学习是串行，学习有先后顺序。
- 区别四:主要作用
- Bagging主要用于提高泛化性能（解决过拟合，也可以说降低方差）
- Boosting主要用于提高训练精度 （解决欠拟合，也可以说降低偏差）
- AdaBoost构造过程【知道】
- 步骤一：初始化训练数据权重相等，训练第一个学习器;
- 步骤二：AdaBoost反复学习基本分类器;
- 步骤三：对m个学习器进行加权投票
5 GBDT介绍
GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树，在传统机器学习算法中，GBDT算的上TOP3的算法。
想要理解GBDT的真正意义，那就必须理解GBDT中的Gradient Boosting 和Decision Tree分别是什么？
5.1 CART回归树
首先，GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。
- 为什么不用CART分类树呢？
- 因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。
对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。
在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。
5.1.1 回归树生成算法（复习）
- 输入：训练数据集D:
- 输出：回归树f(x).
- 在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
- （1）选择最优切分特征j与切分点s，求解
遍历特征j,对固定的切分特征j扫描切分点s,选择使得上式达到最小值的对 (j,s).
- （2）用选定的对(j,s)划分区域并决定相应的输出值：
- （3）继续对两个子区域调用步骤（1）和（2），直至满足停止条件。
- （4）将输入空间划分为M个区域R1,R2,……,Rm, 生成决策树：
5.2 拟合负梯度
梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法，所以在讲梯度提升树之前先来说一下提升树。
先来个通俗理解：假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。
提升树算法：
- （1）初始化:f_0(x)=0f0(x)=0
- （2）对m=1,2,…,M
- （a）计算残差:r_{mi}=y_i-f_{m-1}(x),i=1,2,…,Nrmi=y**i−f**m−1(x),i=1,2,…,N
- （b）拟合残差rmi 学习一个回归树，得到hm(x)
- （c）更新:f_m(x) = f_{m-1}+h_m(x)f**m(x)=f**m−1+h**m(x)
- （3）得到回归问题提升树：f_M(x)=\sum_{m=1}^Mh_m(x)f**M(x)=∑m=1Mhm(x)
上面伪代码中的残差是什么？
在提升树算法中，
- 假设我们前一轮迭代得到的强学习器是：f_{t-1}(x)f**t−1(x)
- 损失函数是：L(y,f_{t-1}(x))L(y,f**t−1(x))
- 我们本轮迭代的目标是找到一个弱学习器：h_t(x)h**t(x)
- 最小化让本轮的损失：L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x))L(y,f**t(x))=L(y,f**t−1(x)+h**t(x))
- 当采用平方损失函数时：
- 这里，
是当前模型拟合数据的残差（residual）。
- 所以，对于提升树来说只需要简单地拟合当前模型的残差。
回到我们上面讲的那个通俗易懂的例子中，第一次迭代的残差是10岁，第二 次残差4岁,
当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易。
针对这一问题，Friedman提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。
那么负梯度长什么样呢？
- 第t轮的第i个样本的损失函数的负梯度为：
- 此时不同的损失函数将会得到不同的负梯度，如果选择平方损失：
- 负梯度为：
此时我们发现GBDT的负梯度就是残差，所以说对于回归问题，我们要拟合的就是残差。
那么对于分类问题呢？
- 二分类和多分类的损失函数都是logloss。
本文以回归问题为例进行讲解。
5.3 GBDT算法原理
上面两节分别将Decision Tree和Gradient Boosting介绍完了，下面将这两部分组合在一起就是我们的GBDT了。
GBDT算法：
- （1）初始化弱学习器
- （2）对m=1,2,…,M有：
- （a）对每个样本i=1,2,…,N，计算负梯度，即残差
（b）将上步得到的残差作为样本新的真实值，并将数据(x_i,r_{im}), i=1,2,…N(x**i,rim),i=1,2,…N作为下棵树的训练数据，得到一颗新的回归树fm(x)其对应的叶子节点区域为R_{jm}, j =1,2,…, JRjm,j=1,2,…,J 其中J为回归树t的叶子节点的个数。
- （c）对叶子区域j=1,2,…J计算最佳拟合值
- （d）更新强学习器
- （3）得到最终学习器
5.4 实例介绍
5.4.1 数据介绍
根据如下数据，预测最后一个样本的身高。
| 编号 | 年龄(岁) | 体重（kg） | 身高(m)(标签值) |
| 0 | 5 | 20 | 1.1 |
| 1 | 7 | 30 | 1.3 |
| 2 | 21 | 70 | 1.7 |
| 3 | 30 | 60 | 1.8 |
| 4(要预测的) | 25 | 65 | ？ |
5.4.2 模型训练
5.4.2.1 设置参数：
- 学习率：learning_rate=0.1
- 迭代次数：n_trees=5
- 树的深度：max_depth=3
5.4.2.2 开始训练
（1）初始化弱学习器:
损失函数为平方损失，因为平方损失函数是一个凸函数，直接求导，倒数等于零，得到c。
令导数等于0
所以初始化时，c取值为所有训练样本标签值的均值。
c=(1.1+1.3+1.7+1.8)/4=1.475c=(1.1+1.3+1.7+1.8)/4=1.475此时得到初始学习器f0(x)：
f_0(x)=c=1.475f0(x)=c=1.475
（2）对迭代轮数m=1,2,…,M:
由于我们设置了迭代次数：n_trees=5，这里的M=5。
计算负梯度，根据上文损失函数为平方损失时，负梯度就是残差，再直白一点就是 y与上一轮得到的学习器fm-1的差值：
残差在下表列出：
| 编号 | 真实值 | f_{0} (x)f0(x) | 残差 |
| 0 | 1.1 | 1.475 | -0.375 |
| 1 | 1.3 | 1.475 | -0.175 |
| 2 | 1.7 | 1.475 | 0.225 |
| 3 | 1.8 | 1.475 | 0.325 |
此时将残差作为样本的真实值来训练弱学习器f1(x)，即下表数据
| 编号 | 年龄(岁) | 体重（kg） | 标签值 |
| 0 | 5 | 20 | -0.375 |
| 1 | 7 | 30 | -0.175 |
| 2 | 21 | 70 | 0.225 |
| 3 | 30 | 60 | 0.325 |
接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。
从年龄特征的5开始，到体重特征的70结束，分别计算分裂后两组数据的平方损失（Square Error），
SEl左节点平方损失，SEr右节点平方损失，找到使平方损失和:SE_{sum}=SE_l+SE_rSEsum=SEl+SEr
最小的那个划分节点，即为最佳划分节点。
例如：以年龄21为划分节点，将小于21的样本划分为到左节点，大于等于21的样本划分为右节点。左节点包括x0, x1 ，右节点包括样本x2, x3，
SE_l = 0.02,SE_r=0.005,SE_{sum}=0.025,SEl=0.02,SEr=0.005,SEsum=0.025,
SE_l = [-0.375-(-0.275)]2+[-0.175-(-0.275)]2 = 0.02SEl=[−0.375−(−0.275)]2+[−0.175−(−0.275)]2=0.02
SE_r = [0.225-0.275]2+[0.325-0.275]2 = 0.005SEr=[0.225−0.275]2+[0.325−0.275]2=0.005
所有可能划分情况如下表所示：
| 划分点 | 小于划分点的样本 | 大于等于划分点的样本 | SE_lSEl | SE_rSEr | SE_{sum}SEsum |
| 年龄5 | / | 0，1，2，3 | 0 | 0.327 | 0.327 |
| 年龄7 | 0 | 1，2，3 | 0 | 0.14 | 0.14 |
| 年龄21 | 0，1 | 2，3 | 0.02 | 0.005 | 0.025 |
| 年龄30 | 0，1，2 | 3 | 0.187 | 0 | 0.187 |
| 体重20 | / | 0，1，2，3 | 0 | 0.327 | 0.327 |
| 体重30 | 0 | 1，2，3 | 0 | 0.14 | 0.14 |
| 体重60 | 0，1 | 2，3 | 0.02 | 0.005 | 0.025 |
| 体重70 | 0，1，3 | 2 | 0.26 | 0 | 0.26 |
以上划分点是的总平方损失最小为0.025有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选 年龄21 现在我们的第一棵树长这个样子：
我们设置的参数中树的深度max_depth=3，现在树的深度只有2，需要再进行一次划分，这次划分要对左右两个节点分别进行划分：
对于左节点，只含有0,1两个样本，根据下表我们选择年龄7划分
| 划分点 | 小于划分点的样本 | 大于等于划分点的样本 | SE_lSEl | SE_rSEr | SE_{sum}SEsum |
| 年龄5 | / | 0，1 | 0 | 0.02 | 0.02 |
| 年龄7 | 0 | 1 | 0 | 0 | 0 |
| 体重20 | / | 0，1 | 0 | 0.02 | 0.02 |
| 体重30 | 0 | 1 | 0 | 0 | 0 |
对于右节点，只含有2,3两个样本，根据下表我们选择年龄30划分（也可以选体重70）
| 划分点 | 小于划分点的样本 | 大于等于划分点的样本 | SE_lSEl | SE_rSEr | SE_{sum}SEsum |
| 年龄21 | / | 2，3 | 0 | 0.005 | 0.005 |
| 年龄30 | 2 | 3 | 0 | 0 | 0 |
| 体重60 | / | 2，3 | 0 | 0.005 | 0.005 |
| 体重70 | 3 | 2 | 0 | 0 | 0 |
现在我们的第一棵树长这个样子：
此时我们的树深度满足了设置，还需要做一件事情，给这每个叶子节点分别赋一个参数 r ，来拟合残差。 
这里其实和上面初始化学习器是一个道理，平方损失，求导，令导数等于零，化简之后得到每个叶子节点的参数 r ，其实就是标签值的均值。这个地方的标签值不是原始的 y，而是本轮要拟合的标残差 y - f0(x).
根据上述划分结果，为了方便表示，规定从左到右为第1,2,3,4个叶子结点
此时的树长这个样子：
此时可更新强学习器，需要用到参数学习率：learning_rate=0.1，用 lr 表示。 
为什么要用学习率呢？这是Shrinkage的思想，如果每次都全部加上（学习率为1）很容易一步学到位导致过拟合。
重复此步骤，直到 m>5 结束，最后生成5棵树。 
结果中，0.9倍这个现象，和其学习率有关。这是因为数据简单每棵树长得一样，导致每一颗树的拟合效果一样，而每棵树都只学上一棵树残差的0.1倍，导致这颗树只能拟合剩余0.9了。
（3）得到最后的强学习器：
（4）预测样本：
- f_0(x)=1.475f0(x)=1.475
- 在f1(x)中，样本4的年龄为25，大于划分节点21岁，又小于30岁，所以被预测为0.2250;
- 在f2(x)中，样本4的…此处省略…所以被预测为0.2025;
- 在f3(x)中，样本4的…此处省略…所以被预测为0.1823;
- 在f3(x)中，样本4的…此处省略…所以被预测为0.1640;
- 在f5(x)中，样本4的…此处省略…所以被预测为0.1476.
最终预测结果：
f(x)=1.475+0.1\ast(0.225+0.2025+0.1823+0.164+0.1476)=1.56714f(x)=1.475+0.1∗(0.225+0.2025+0.1823+0.164+0.1476)=1.56714
5.5 小结
GBDT算法原理【知道】
- （1）初始化弱学习器
- （2）对m=1,2,…,M有：
- （a）对每个样本i=1,2,…,N，计算负梯度，即残差
（b）将上步得到的残差作为样本新的真实值，并将数据(x_i,r_{im}), i=1,2,…N(x**i,rim),i=1,2,…N作为下棵树的训练数据，
- 得到一颗新的回归树fm(x)其对应的叶子节点区域为R_{jm}, j =1,2,…, JRjm,j=1,2,…,J 其中J为回归树t的叶子节点的个数。
- （c）对叶子区域j=1,2,…J计算最佳拟合值
- （d）更新强学习器
- （3）得到最终学习器
