目录
上一章讲了使用Bagging去优化模型，Bagging思想的实质是：通过Bootstrap 的方式对全样本数据集进行抽样得到抽样子集，对不同的子集使用同一种基本模型进行拟合，然后投票得出最终的预测。我们也从前面的探讨知道：Bagging主要通过降低方差的方式减少预测误差。
那么，本章介绍的Boosting是与Bagging截然不同的思想，Boosting方法是使用同一组数据集进行反复学习，得到一系列简单模型，然后组合这些模型构成一个预测性能十分强大的机器学习模型。显然，Boosting提高最终的预测效果是通过不断减少偏差的形式，与Bagging有着本质的不同。在Boosting这一大类方法中，主要介绍两类常用的Boosting方式：Adaptive Boosting （自适应增强）和 Gradient Boosting（梯度增强） ，以及它们的变体Xgboost、LightGBM。
1.?Boosting原理
"强可学习"和"弱可学习"：
- 弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）
- 强学习：识别准确率很高并能在多项式时间内完成的学习算法
强可学习和弱可学习的错误率都小于1/2。
在PAC(概率近似正确)学习的框架下，强可学习和弱可学习是等价的。在学习中，如果已经发现了弱可学习算法，能否将他提升至强可学习算法。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器(基本分类器)，然后通过一定的形式去组合这些弱分类器构成一个强分类器。
大多数的Boosting方法都是通过改变训练数据集的概率分布(训练数据不同样本的权值)，针对不同概率分布的数据调用弱分类算法学习一系列的弱分类器，组合形成强分类器。简单说：1）反复训练预测错误的“错题”样本；2）多个模型的综合判断比单个模型更准确。
2. Adaboost算法
对于Boosting方法来说，有两个问题需要给出答案：第一个是每一轮学习应该如何改变数据的概率分布，第二个是如何将各个弱分类器组合起来。
对于Adaboost来说，解决上述的两个问题的方式是：1. 提高那些被前一轮分类器错误分类的样本的权重，而降低那些被正确分类的样本的权重。这样一来，那些在上一轮分类器中没有得到正确分类的样本，由于其权重的增大而在后一轮的训练中“备受关注”。2. 各个弱分类器的组合是通过采取加权多数表决的方式，具体来说，加大分类错误率低的弱分类器的权重，因为这些分类器能更好地完成分类任务，而减小分类错误率较大的弱分类器的权重，使其在表决中起较小的作用。
Adaboost算法：
?对于步骤(3)，线性组合𝑓(𝑥)实现了将M个基本分类器的加权表决，系数𝛼𝑚标志了基本分类器𝐺𝑚(𝑥)的重要性，值得注意的是：所有的𝛼𝑚之和不为1。𝑓(𝑥)的符号决定了样本x属于哪一类。
I(X)函数：当条件X成立时，I=1；反之为0. sign(x)函数：x>0记为1，x<0时记为-1，这里用于聚合模型的表决结果。
3. 前向分布算法
回看Adaboost，我们需要通过计算M个基本分类器，每个分类器的错误率、样本权重以及模型权重。我们可以认为：Adaboost每次学习单一分类器以及单一分类器的参数(权重)。接下来，我们抽象出Adaboost算法的整体框架逻辑，构建集成学习的一个非常重要的框架----前向分步算法。
损失函数L是线性可加模型，可以用贪心算法的思想，每一步求出一个函数的最优值，逐步逼近目标函数。
4. 梯度提升算法
4.1 GBDT
(1)?基于残差学习的提升树：
回归问题如何解决呢？前面第二章我们已经学过了回归树的基本原理，树算法最重要是寻找最佳的划分点，分类树用纯度来判断最佳划分点使用信息增益（ID3算法），信息增益比（C4.5算法），基尼系数（CART分类树）。但是在回归树中的样本标签是连续数值，可划分点包含了所有特征的所有可取的值。所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。
提升树算法：
总结：提升树利用加法模型和前向分步算法实现学习的过程，当损失函数为平方损失和指数损失时，每一步优化是相当简单的，就是提升树算法和Adaboost算法。当一般的损失函数很难求出最优解时，学习困难，使用梯度计算就比较简单。
(2) GBDT(梯度提升决策树算法)：?
针对一般的损失函数，Freidman提出了梯度提升算法(gradient boosting)，这是利用最速下降法的近似方法，利用损失函数的负梯度在当前模型的值
作为回归问题提升树算法中的残差的近似值，拟合回归树。与其说负梯度作为残差的近似值，不如说残差是负梯度的一种特例。
GBDT算法：
?
4.2 Xgboost
XGBoost是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进。XGBoost是一个优化的分布式梯度增强库，旨在实现高效，灵活和便携。 它在Gradient Boosting框架下实现机器学习算法。 XGBoost提供了并行树提升（也称为GBDT，GBM），可以快速准确地解决许多数据科学问题。?
Xgboost以CART决策树为子模型，通过Gradient Tree Boosting实现多棵CART树的集成学习，得到最终模型。详细见第五章https://github.com/datawhalechina/ensemble-learning。
XGBoost思想：
- 不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数f(x)，去拟合上次预测的残差。
- 当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数
- 最后只需要将每棵树对应的分数加起来就是该样本的预测值。
算法：
(1) 构造目标函数
(2) 叠加式的训练(Additive Training)
(3) 使用泰勒级数近似目标函数
(4) 树的构造：
??
(5) 树的分裂标准：使用目标函数的变化来作为分裂节点的标准
- 精确贪心分裂算法
- 基于直方图的近似算法
4.3 LightGBM
LightGBM也是像XGBoost一样，是一类集成算法，他跟XGBoost总体来说是一样的，算法本质上与Xgboost没有出入，只是在XGBoost的基础上进行了优化，因此就不对原理进行重复介绍，在这里我们来看看几种算法的差别：
- 优化速度和内存使用
- 降低了计算每个分割增益的成本。
- 使用直方图减法进一步提高速度。
- 减少内存使用。
- 减少并行学习的计算成本。
- 稀疏优化
- 用离散的bin替换连续的值。如果#bins较小，则可以使用较小的数据类型（例如uint8_t）来存储训练数据 。
- 无需存储其他信息即可对特征数值进行预排序 。
- 精度优化
- 使用叶子数为导向的决策树建立算法而不是树的深度导向。
- 分类特征的编码方式的优化
- 通信网络的优化
- 并行学习的优化
- GPU支持
总结：
本章中，我们主要探讨了基于Boosting方式的集成方法，其中主要讲解了基于错误率驱动的Adaboost，基于残差改进的提升树，基于梯度提升的GBDT，基于泰勒二阶近似的Xgboost以及LightGBM。在实际的比赛或者工程中，基于Boosting的集成学习方式是非常有效且应用非常广泛的。
作业：
1.Adaboost的基本思路？
经过多轮学习，不断提升分类错误的样本的比例(权重)，以得到更好的训练。组合弱分类器时，加大分类正确率高的分类器权重，减小分类错误率大的分类器权重，使最终的分类器精度更高。
2.Adaboost与GBDT的联系与区别？
联系：两者都是重复选择一个表现一般的模型，并且每次基于先前模型的表现进行调整。
区别：AdaBoost是通过提升错分数据点的权重来定位模型的不足而Gradient Boosting是通过算梯度（gradient）来定位模型的不足。
3.Boosting与Bagging的区别，以及如何提升模型的精度？
Bagging主要通过降低方差的方式减少预测误差，方法包括bootstraps随机取样、特征选取(随机森林)；Boosting是通过不断减少偏差提高最终的预测效果，方法包括增加预测错误样本的权重，不断调整模型，根据模型正确率给定改模型权重，最后进行线性组合得到更好模型。
4.使用基本分类模型和Boosting提升的模型，并画出他们的决策边界。
5.尝试使用XGboost模型完成一个具体的分类任务，并进行调参。
代码：
import time
import xgboost as xgb
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report, classification
# 使用sklearn加载数据集，并进一步拆分
digits = datasets.load_digits()
data, labels = digits.data, digits.target
x_train, x_test, y_train, y_test = train_test_split(data, labels, test_size=0.2, random_state=7)
print("x_train: {}, x_test: {}, classes: {}".format(x_train.shape, x_test.shape, len(set(labels))))
dtrain = xgb.DMatrix(x_train, y_train) # 训练集
dtest = xgb.DMatrix(x_test, y_test) # 验证集
evals = [(dtrain, 'train'), (dtest, 'val')] # 训练过程中进行验证
# 参数设置
params = {
'tree_method': "gpu_hist",
'booster': 'gbtree',
'objective': 'multi:softmax',
'num_class': 10,
'max_depth': 6,
'eval_metric': 'merror',
'eta': 0.01,
'verbosity': 0,
'gpu_id': 0
}
s_time = time.time()
train_res = {}
model = xgb.train(params, dtrain, num_boost_round=100,
evals=evals,
evals_result=train_res)
print("模型训练耗时: {}".format(time.time() - s_time))
# 模型预测
pred_data = model.predict(dtest)
res = classification_report(y_test, pred_data)
print(res)