Boosting

简介

在前面的学习中，我们探讨了一系列简单而实用的回归和分类模型，同时也探讨了如何使用集成学习家族中的Bagging思想去优化最终的模型。Bagging思想的实质是：通过Bootstrap 的方式对全样本数据集进行抽样得到抽样子集，对不同的子集使用同一种基本模型进行拟合，然后投票得出最终的预测。我们也从前面的探讨知道：Bagging主要通过降低方差的方式减少预测误差。那么，本章介绍的Boosting是与Bagging截然不同的思想，Boosting方法是使用同一组数据集进行反复学习，得到一系列简单模型，然后组合这些模型构成一个预测性能十分强大的机器学习模型。显然，Boosting思想提高最终的预测效果是通过不断减少偏差的形式，与Bagging有着本质的不同。在Boosting这一大类方法中，笔者主要介绍两类常用的Boosting方式：Adaptive Boosting 和 Gradient Boosting 以及它们的变体Xgboost、LightGBM以及Catboost。

Boosting方法的基本思路

在正式介绍Boosting思想之前，我想先介绍两个例子：

第一个例子：不知道大家有没有做过错题本，我们将每次测验的错的题目记录在错题本上，不停的翻阅，直到我们完全掌握(也就是能够在考试中能够举一反三)。

第二个例子：对于一个复杂任务来说，将多个专家的判断进行适当的综合所作出的判断，要比其中任何一个专家单独判断要好。实际上这是一种“三个臭皮匠顶个诸葛亮的道理”。

这两个例子都说明Boosting的道理，也就是不错地重复学习达到最终的要求。

Boosting的提出与发展离不开Valiant和 Kearns的努力，历史上正是Valiant和 Kearns提出了”强可学习”和”弱可学习”的概念。那什么是”强可学习”和”弱可学习”呢？在概率近似正确PAC学习的框架下：

  • 弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）
  • 强学习：识别准确率很高并能在多项式时间内完成的学习算法

非常有趣的是，在PAC 学习的框架下，强可学习和弱可学习是等价的，也就是说一个概念是强可学习的充分必要条件是这个概念是弱可学习的。这样一来，问题便是：在学习中，如果已经发现了弱可学习算法，能否将他提升至强可学习算法。因为，弱可学习算法比强可学习算法容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器(又称为基本分类器)，然后通过一定的形式去组合这些弱分类器构成一个强分类器。大多数的Boosting方法都是通过改变训练数据集的概率分布(训练数据不同样本的权值)，针对不同概率分布的数据调用弱分类算法学习一系列的弱分类器。

对于Boosting方法来说，有两个问题需要给出答案：第一个是每一轮学习应该如何改变数据的概率分布，第二个是如何将各个弱分类器组合起来。关于这两个问题，不同的Boosting算法会有不同的答案，我们接下来介绍一种最经典的Boosting算法——Adaboost，我们需要理解Adaboost是怎么处理这两个问题以及为什么这么处理的。

Adaboost基本思路

对于Adaboost来说，解决上述的两个问题的方式是：1. 提高那些被前一轮分类器错误分类的样本的权重，而降低那些被正确分类的样本的权重。这样一来，那些在上一轮分类器中没有得到正确分类的样本，由于其权重的增大而在后一轮的训练中“备受关注”。2. 各个弱分类器的组合是通过采取加权多数表决的方式，具体来说，加大分类错误率低的弱分类器的权重，因为这些分类器能更好地完成分类任务，而减小分类错误率较大的弱分类器的权重，使其在表决中起较小的作用。

现在，我们来具体介绍Adaboost算法：(参考李航老师的《统计学习方法》)

假设给定一个二分类的训练数据集：

其中每个样本点由特征与类别组成。

特征：

类别：

$\mathcal{X}$ 是特征空间，$ \mathcal{Y}$ 是类别集合，输出最终分类器 $G(x)$。Adaboost算法如下：

1.初始化训练数据的分布：

2.对于m=1,2,…,M

  • 使用具有权值分布$D_m$的训练数据集进行学习，得到基本分类器：

  • 计算 $G_m(x)$ 在训练集上的分类误差率

  • 计算 $G_m(x)$ 的系数:(这里的log是自然对数ln)

  • 更新训练数据集的权重分布

    这里的 $Zm$ 是规范化因子，使得 $D{m+1}$ 称为概率分布，

3.构建基本分类器的线性组合

得到最终的分类器。

下面对Adaboost算法做如下说明：

对于步骤 1，假设训练数据的权值分布是均匀分布，是为了使得第一次没有先验信息的条件下每个样本在基本分类器的学习中作用一样。

对于步骤(2)，每一次迭代产生的基本分类器$G_m(x)$在加权训练数据集上的分类错误率：

代表了在 $G_m(x)$ 中分类错误的样本权重和，这点直接说明了权重分布 $D_m$ 与 $G_m(x)$ 的分类错误率$e_m$有直接关系。同时，在步骤(2)中，计算基本分类器$G_m(x)$的系数：

它表示了$G_m(x)$在最终分类器的重要性程度，$\alpha_m$的取值由基本分类器$G_m(x)$的分类错误率有直接关系，当

时，

并且$\alpha_m$随着$e_m$的减少而增大，因此分类错误率越小的基本分类器在最终分类器的作用越大！

最重要的，对于步骤(2)中的样本权重的更新：

因此，从上式可以看到：被基本分类器$G_m(x)$错误分类的样本的权重扩大，被正确分类的样本权重减少，二者相比相差

倍。

对于步骤(3)，线性组合$f(x)$实现了将M个基本分类器的加权表决，系数$\alpha_m$标志了基本分类器$G_m(x)$的重要性，值得注意的是：所有的$\alpha_m$之和不为1。$f(x)$的符号决定了样本x属于哪一类。

实践案例

下面，我们使用一组简单的数据来手动计算Adaboost算法的过程：(例子来源：http://www.csie.edu.tw)

训练数据如下表，假设基本分类器的形式是一个分割$xv$表示，阈值v由该基本分类器在训练数据集上分类错误率$e_m$最低确定。

解：
初始化样本权值分布

对m=1:

  • 在权值分布$D_1$的训练数据集上，遍历每个结点并计算分类误差率$e_m$，阈值取v=2.5时分类误差率最低，那么基本分类器为

  • $G_1(x)$ 在训练数据集上的误差率为

  • 计算$G_1(x)$的系数：

  • 更新训练数据的权值分布：

对于m=2：

  • 在权值分布$D_2$的训练数据集上，遍历每个结点并计算分类误差率$e_m$，阈值取v=8.5时分类误差率最低，那么基本分类器为：
  • $G_2(x)$在训练数据集上的误差率为$e_2 = 0.2143$
  • 计算$G_2(x)$的系数：$\alpha_2 = 0.6496$
  • 更新训练数据的权值分布：

对m=3：

  • 在权值分布$D_3$的训练数据集上，遍历每个结点并计算分类误差率$e_m$，阈值取v=5.5时分类误差率最低，那么基本分类器为：
  • $G_3(x)$在训练数据集上的误差率为$e_3 = 0.1820$
  • 计算$G_3(x)$的系数：$\alpha_3 = 0.7514$
  • 更新训练数据的权值分布：

于是得到：

分类器

在训练数据集上的误分类点的个数为0。

于是得到最终分类器为：

Boosting案例实践

下面，我们使用sklearn对Adaboost算法进行建模：

本次案例使用一份UCI的机器学习库里的开源数据集：葡萄酒数据集，该数据集可以在 ( https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data )上获得。该数据集包含了178个样本和13个特征，从不同的角度对不同的化学特性进行描述，我们的任务是根据这些数据预测红酒属于哪一个类别。(案例来源《python机器学习(第二版》)

1
2
3
4
5
6
7
# 引入数据科学相关工具包：
import numpy as np
import pandas as pd 
import matplotlib.pyplot as plt
plt.style.use("ggplot")
%matplotlib inline
import seaborn as sns
1
2
3
4
# 加载训练数据：         
wine = pd.read_csv("https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",header=None)
wine.columns = ['Class label', 'Alcohol', 'Malic acid', 'Ash', 'Alcalinity of ash','Magnesium', 'Total phenols','Flavanoids', 'Nonflavanoid phenols', 
                'Proanthocyanins','Color intensity', 'Hue','OD280/OD315 of diluted wines','Proline']
1
2
3
# 数据查看：
print("Class labels",np.unique(wine["Class label"]))
wine.head()
Class label Alcohol Malic acid Ash Alcalinity of ash Magnesium Total phenols Flavanoids Nonflavanoid phenols Proanthocyanins Color intensity Hue OD280/OD315 of diluted wines Proline
0 1 14.23 1.71 2.43 15.6 127 2.80 3.06 0.28 2.29 5.64 1.04 3.92 1065
1 1 13.20 1.78 2.14 11.2 100 2.65 2.76 0.26 1.28 4.38 1.05 3.40 1050
2 1 13.16 2.36 2.67 18.6 101 2.80 3.24 0.30 2.81 5.68 1.03 3.17 1185
3 1 14.37 1.95 2.50 16.8 113 3.85 3.49 0.24 2.18 7.80 0.86 3.45 1480
4 1 13.24 2.59 2.87 21.0 118 2.80 2.69 0.39 1.82 4.32 1.04 2.93 735

下面对数据做简单解读：

  • Class label：分类标签
  • Alcohol：酒精
  • Malic acid：苹果酸
  • Ash：灰
  • Alcalinity of ash：灰的碱度
  • Magnesium：镁
  • Total phenols：总酚
  • Flavanoids：黄酮类化合物
  • Nonflavanoid phenols：非黄烷类酚类
  • Proanthocyanins：原花青素
  • Color intensity：色彩强度
  • Hue：色调
  • OD280/OD315 of diluted wines：稀释酒OD280 OD350
  • Proline：脯氨酸

数据预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 数据预处理
# 仅仅考虑2，3类葡萄酒，去除1类
wine = wine[wine['Class label'] != 1]
y = wine['Class label'].values
X = wine[['Alcohol','OD280/OD315 of diluted wines']].values

# 将分类标签变成二进制编码：
from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
y = le.fit_transform(y)

# 按8：2分割训练集和测试集
from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=1,stratify=y)  # stratify参数代表了按照y的类别等比例抽样

决策树建模预测

1
2
3
4
5
6
7
8
9
10
# 使用单一决策树建模
from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(criterion='entropy',random_state=1,max_depth=1)
from sklearn.metrics import accuracy_score
tree = tree.fit(X_train,y_train)
y_train_pred = tree.predict(X_train)
y_test_pred = tree.predict(X_test)
tree_train = accuracy_score(y_train,y_train_pred)
tree_test = accuracy_score(y_test,y_test_pred)
print('Decision tree train/test accuracies %.3f/%.3f' % (tree_train,tree_test))
1
Decision tree train/test accuracies 0.916/0.875

以决策树作为基学习器进行Boosting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 使用sklearn实现Adaboost(基分类器为决策树)
'''
AdaBoostClassifier相关参数：
base_estimator：基本分类器，默认为DecisionTreeClassifier(max_depth=1)
n_estimators：终止迭代的次数
learning_rate：学习率
algorithm：训练的相关算法，{'SAMME'，'SAMME.R'}，默认='SAMME.R'
random_state：随机种子
'''
from sklearn.ensemble import AdaBoostClassifier
ada = AdaBoostClassifier(base_estimator=tree,n_estimators=500,learning_rate=0.1,random_state=1)
ada = ada.fit(X_train,y_train)
y_train_pred = ada.predict(X_train)
y_test_pred = ada.predict(X_test)
ada_train = accuracy_score(y_train,y_train_pred)
ada_test = accuracy_score(y_test,y_test_pred)
print('Adaboost train/test accuracies %.3f/%.3f' % (ada_train,ada_test))

结果分析：单层决策树似乎对训练数据欠拟合，而Adaboost模型正确地预测了训练数据的所有分类标签，而且与单层决策树相比，Adaboost的测试性能也略有提高。然而，为什么模型在训练集和测试集的性能相差这么大呢？我们使用图像来简单说明下这个道理！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 画出单层决策树与Adaboost的决策边界：
x_min = X_train[:, 0].min() - 1
x_max = X_train[:, 0].max() + 1
y_min = X_train[:, 1].min() - 1
y_max = X_train[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),np.arange(y_min, y_max, 0.1))
f, axarr = plt.subplots(nrows=1, ncols=2,sharex='col',sharey='row',figsize=(12, 6))
for idx, clf, tt in zip([0, 1],[tree, ada],['Decision tree', 'Adaboost']):
    clf.fit(X_train, y_train)
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    axarr[idx].contourf(xx, yy, Z, alpha=0.3)
    axarr[idx].scatter(X_train[y_train==0, 0],X_train[y_train==0, 1],c='blue', marker='^')
    axarr[idx].scatter(X_train[y_train==1, 0],X_train[y_train==1, 1],c='red', marker='o')
    axarr[idx].set_title(tt)
axarr[0].set_ylabel('Alcohol', fontsize=12)
plt.tight_layout()
plt.text(0, -0.2,s='OD280/OD315 of diluted wines',ha='center',va='center',fontsize=12,transform=axarr[1].transAxes)
plt.show()

从上面的决策边界图可以看到：Adaboost模型的决策边界比单层决策树的决策边界要复杂的多。也就是说，Adaboost试图用增加模型复杂度而降低偏差的方式去减少总误差，但是过程中引入了方差，可能出现过拟合，因此在训练集和测试集之间的性能存在较大的差距，这就能简单地回答的刚刚问题。

值的注意的是：与单个分类器相比，Adaboost等Boosting模型增加了计算的复杂度，在实践中需要仔细思考是否愿意为预测性能的相对改善而增加计算成本，而且Boosting方式无法做到现在流行的并行计算的方式进行训练，因为每一步迭代都要基于上一步的基本分类器。

向前分步算法

回看Adaboost的算法内容，我们需要通过计算M个基本分类器，每个分类器的错误率、样本权重以及模型权重。我们可以认为：Adaboost每次学习单一分类器以及单一分类器的参数(权重)。接下来，我们抽象出Adaboost算法的整体框架逻辑，构建集成学习的一个非常重要的框架——前向分步算法，有了这个框架，我们不仅可以解决分类问题，也可以解决回归问题。

(1) 加法模型：
在Adaboost模型中，我们把每个基本分类器合成一个复杂分类器的方法是每个基本分类器的加权和，即：

其中：

即基本分类器，$\gamma{m}$ 为基本分类器的参数，$\beta_m$ 为基本分类器的权重，显然这与第二章所学的加法模型十分相似。为什么这么说呢？大家把 $b(x ; \gamma{m})$ 看成是即函数即可。

在给定训练数据以及损失函数 $L(y, f(x))$ 的条件下，学习加法模型$f(x)$就是：

通常这是一个复杂的优化问题，很难通过简单的凸优化的相关知识进行解决。前向分步算法可以用来求解这种方式的问题，它的基本思路是：因为学习的是加法模型，如果从前向后，每一步只优化一个基函数及其系数，逐步逼近目标函数，那么就可以降低优化的复杂度。具体而言，每一步只需要优化：

(2) 前向分步算法：
给定数据集

损失函数 $L(y, f(x))$，基函数集合 ${b(x ; \gamma)}$ ，我们需要输出加法模型$f(x)$。

  • 初始化：$f_{0}(x)=0$

  • 对m = 1,2,…,M:

    • (a) 极小化损失函数：得到参数 $\beta{m}$ 与 $\gamma{m}$

    • (b) 更新：

  • 得到加法模型：

这样，前向分步算法将同时求解从m=1到M的所有参数$\beta{m}$，$\gamma{m}$ 的优化问题简化为逐次求解各个 $\beta{m}$ ，$\gamma{m}$ 的问题。

(3) 前向分步算法与Adaboost的关系：
由于这里不是我们的重点，我们主要阐述这里的结论，不做相关证明，具体的证明见李航老师的《统计学习方法》第八章的3.2节。Adaboost算法是前向分步算法的特例，Adaboost算法是由基本分类器组成的加法模型，损失函数为指数损失函数。

梯度提升决策树(GBDT)

(1) 基于残差学习的提升树算法：
在前面的学习过程中，我们一直讨论的都是分类树，比如Adaboost算法，并没有涉及回归的例子。在上一小节我们提到了一个加法模型+前向分步算法的框架，那能否使用这个框架解决回归的例子呢？答案是肯定的。接下来我们来探讨下如何使用加法模型+前向分步算法的框架实现回归问题。

在使用加法模型+前向分步算法的框架解决问题之前，我们需要首先确定框架内使用的基函数是什么，在这里我们使用决策树分类器。

前面我们已经学过了回归树的基本原理，树算法最重要是寻找最佳的划分点，分类树用纯度来判断最佳划分点使用信息增益（ID3算法），信息增益比（C4.5算法），基尼系数（CART分类树）。但是在回归树中的样本标签是连续数值，可划分点包含了所有特征的所有可取的值。所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。

基函数确定了以后，我们需要确定每次提升的标准是什么。回想Adaboost算法，在Adaboost算法内使用了分类错误率修正样本权重以及计算每个基本分类器的权重，那回归问题没有分类错误率可言，也就没办法在这里的回归问题使用了，因此我们需要另辟蹊径。模仿分类错误率，我们用每个样本的残差表示每次使用基函数预测时没有解决的那部分问题。因此，我们可以得出如下算法：

输入数据集

，输出最终的提升树 $f_{M}(x)$

  • 初始化 $f_0(x) = 0$

  • 对m = 1,2,…,M：

    • 计算每个样本的残差:

      ​

    • 拟合残差$r_{mi}$学习一棵回归树，得到

    • 更新

  • 得到最终的回归问题的提升树： 下面我们用一个实际的案例来使用这个算法：(案例来源：李航老师《统计学习方法》)
    训练数据如下表，学习这个回归问题的提升树模型，考虑只用树桩作为基函数。

.png)

.png)

.png)

.png)

至此，我们已经能够建立起依靠加法模型+前向分步算法的框架解决回归问题的算法，叫提升树算法。那么，这个算法还是否有提升的空间呢？

(2) 梯度提升决策树算法(GBDT)：

提升树利用加法模型和前向分步算法实现学习的过程，当损失函数为平方损失和指数损失时，每一步优化是相当简单的，也就是我们前面探讨的提升树算法和Adaboost算法。但是对于一般的损失函数而言，往往每一步的优化不是那么容易，针对这一问题，我们得分析问题的本质，也就是是什么导致了在一般损失函数条件下的学习困难。对比以下损失函数：

观察Huber损失函数：

针对上面的问题，Freidman提出了梯度提升算法(gradient boosting)，这是利用最速下降法的近似方法，利用损失函数的负梯度在当前模型的值

作为回归问题提升树算法中的残差的近似值，拟合回归树。与其说负梯度作为残差的近似值，不如说残差是负梯度的一种特例。

以下开始具体介绍梯度提升算法：
输入训练数据集$T=\left{\left(x{1}, y{1}\right),\left(x{2}, y{2}\right), \cdots,\left(x{N}, y{N}\right)\right}, x{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}, y{i} \in \mathcal{Y} \subseteq \mathbf{R}$和损失函数$L(y, f(x))$，输出回归树$\hat{f}(x)$

  • 初始化

    ​

  • 对于m=1,2,…,M：

    • 对i = 1,2,…,N计算：

    • 对 $r{mi}$ 拟合一个回归树，得到第m棵树的叶结点区域 $R{m j}, j=1,2, \cdots, J$

    • 对j=1,2,…J，计算：

      ​

    • 更新

  • 得到回归树：

下面，我们来使用一个具体的案例来说明GBDT是如何运作的(案例来源：https://blog.csdn.net/zpalyq110/article/details/79527653 )：

下面的表格是数据：

.png)

学习率：learning_rate=0.1，迭代次数：n_trees=5，树的深度：max_depth=3
平方损失的负梯度为：

学习决策树，分裂结点：

对于左节点，只有0，1两个样本，那么根据下表我们选择年龄7进行划分：

对于右节点，只有2，3两个样本，那么根据下表我们选择年龄30进行划分：

因此根据：

这里其实和上面初始化学习器是一个道理，平方损失，求导，令导数等于零，化简之后得到每个叶子节点的参数$\Upsilon$,其实就是标签值的均值。最后得到五轮迭代：

最后的强学习器为：

预测结果为：

为什么要用学习率呢？这是Shrinkage的思想，如果每次都全部加上（学习率为1）很容易一步学到位导致过拟合。

GBDT案例实践

下面我们来使用sklearn来使用GBDT：
https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingRegressor.html#sklearn.ensemble.GradientBoostingRegressor

https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingClassifier.html?highlight=gra#sklearn.ensemble.GradientBoostingClassifier

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from sklearn.metrics import mean_squared_error
from sklearn.datasets import make_friedman1
from sklearn.ensemble import GradientBoostingRegressor

'''
GradientBoostingRegressor参数解释：
loss：{‘ls’, ‘lad’, ‘huber’, ‘quantile’}, default=’ls’：‘ls’ 指最小二乘回归. ‘lad’ (最小绝对偏差) 是仅基于输入变量的顺序信息的高度鲁棒的损失函数。. ‘huber’ 是两者的结合. ‘quantile’允许分位数回归（用于alpha指定分位数）
learning_rate：学习率缩小了每棵树的贡献learning_rate。在learning_rate和n_estimators之间需要权衡。
n_estimators：要执行的提升次数。
subsample：用于拟合各个基础学习者的样本比例。如果小于1.0，则将导致随机梯度增强。subsample与参数n_estimators。选择会导致方差减少和偏差增加。subsample < 1.0
criterion：{'friedman_mse'，'mse'，'mae'}，默认='friedman_mse'：“ mse”是均方误差，“ mae”是平均绝对误差。默认值“ friedman_mse”通常是最好的，因为在某些情况下它可以提供更好的近似值。
min_samples_split：拆分内部节点所需的最少样本数
min_samples_leaf：在叶节点处需要的最小样本数。
min_weight_fraction_leaf：在所有叶节点处（所有输入样本）的权重总和中的最小加权分数。如果未提供sample_weight，则样本的权重相等。
max_depth：各个回归模型的最大深度。最大深度限制了树中节点的数量。调整此参数以获得最佳性能；最佳值取决于输入变量的相互作用。
min_impurity_decrease：如果节点分裂会导致杂质的减少大于或等于该值，则该节点将被分裂。
min_impurity_split：提前停止树木生长的阈值。如果节点的杂质高于阈值，则该节点将分裂
max_features{‘auto’, ‘sqrt’, ‘log2’}，int或float：寻找最佳分割时要考虑的功能数量：

如果为int，则max_features在每个分割处考虑特征。

如果为float，max_features则为小数，并 在每次拆分时考虑要素。int(max_features * n_features)

如果“auto”，则max_features=n_features。

如果是“ sqrt”，则max_features=sqrt(n_features)。

如果为“ log2”，则为max_features=log2(n_features)。

如果没有，则max_features=n_features。
'''

X, y = make_friedman1(n_samples=1200, random_state=0, noise=1.0)
X_train, X_test = X[:200], X[200:]
y_train, y_test = y[:200], y[200:]
est = GradientBoostingRegressor(n_estimators=100, learning_rate=0.1,
    max_depth=1, random_state=0, loss='ls').fit(X_train, y_train)
mean_squared_error(y_test, est.predict(X_test))
1
5.009154859960321
1
2
3
4
5
6
7
8
9
from sklearn.datasets import make_regression
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.model_selection import train_test_split
X, y = make_regression(random_state=0)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, random_state=0)
reg = GradientBoostingRegressor(random_state=0)
reg.fit(X_train, y_train)
reg.score(X_test, y_test)
1
0.432751576681638

与GradientBoostingClassifier函数的各个参数的意思！参考文档：

GradientBoostingRegressor部分参数意思

loss: 选择损失函数，默认值为ls(least squres)

learning_rate: 学习率，模型是0.1

n_estimators: 弱学习器的数目，默认值100

max_depth: 每一个学习器的最大深度，限制回归树的节点数目，默认为3

min_samples_split: 可以划分为内部节点的最小样本数，默认为2

min_samples_leaf: 叶节点所需的最小样本数，默认为1

具体可参考：https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingRegressor.html#sklearn.ensemble.GradientBoostingRegressor

GradientBoostingClassifier部分参数意思

min_ samples_split

  • 定义了树中一个节点所需要用来分裂的最少样本数。
  • 可以避免过度拟合(over-fitting)。如果用于分类的样本数太小，模型可能只适用于用来训练的样本的分类，而用较多的样本数则可以避免这个问题。
  • 但是如果设定的值过大，就可能出现欠拟合现象(under-fitting)。因此我们可以用CV值（离散系数）考量调节效果。

min_ samples_leaf

  • 定义了树中终点节点所需要的最少的样本数。
  • 同样，它也可以用来防止过度拟合。
  • 在不均等分类问题中(imbalanced class problems)，一般这个参数需要被设定为较小的值，因为大部分少数类别（minority class）含有的样本都比较小。

min weight fraction_leaf

  • 和上面min samples leaf很像，不同的是这里需要的是一个比例而不是绝对数值：终点节点所需的样本数占总样本数的比值。
  • min samples leaf和min weight fraction_leaf只需要定义一个就行了

max_ depth

  • 定义了树的最大深度。
  • 它也可以控制过度拟合，因为分类树越深就越可能过度拟合。
  • 当然也应该用CV值检验。

max leaf nodes

  • 定义了决定树里最多能有多少个终点节点。
  • 这个属性有可能在上面max_ depth里就被定义了。比如深度为n的二叉树就有最多2^n个终点节点。
  • 如果我们定义了max leaf nodes，GBM就会忽略前面的max_depth。

max_ features

  • 决定了用于分类的特征数，是人为随机定义的。
  • 根据经验一般选择总特征数的平方根就可以工作得很好了，但还是应该用不同的值尝试，最多可以尝试总特征数的30%-40%.
  • 过多的分类特征可能也会导致过度拟合。

参考链接：https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingClassifier.html?highlight=gra#sklearn.ensemble.GradientBoostingClassifier

调参参考博客：https://blog.csdn.net/geduo_feng/article/details/79561571

XGBoost

XGBoost是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进，被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并取得了不错的成绩。

XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致，所以叫X (Extreme) GBoosted，包括前面说过，两者都是boosting方法。XGBoost是一个优化的分布式梯度增强库，旨在实现高效，灵活和便携。 它在Gradient Boosting框架下实现机器学习算法。

XGBoost提供了并行树提升（也称为GBDT，GBM），可以快速准确地解决许多数据科学问题。 相同的代码在主要的分布式环境（Hadoop，SGE，MPI）上运行，并且可以解决超过数十亿个样例的问题。

XGBoost利用了核外计算并且能够使数据科学家在一个主机上处理数亿的样本数据。最终，将这些技术进行结合来做一个端到端的系统以最少的集群系统来扩展到更大的数据集上。Xgboost以CART决策树为子模型，通过Gradient Tree Boosting实现多棵CART树的集成学习，得到最终模型。下面我们来看看XGBoost的最终模型构建：
引用陈天奇的论文，我们的数据为：

1.构造目标函数：

假设有K棵树，则第i个样本的输出为$\hat{y}{i}=\phi\left(\mathrm{x}{i}\right)=\sum{k=1}^{K} f{k}\left(\mathrm{x}{i}\right), \quad f{k} \in \mathcal{F}$，其中，

因此，目标函数的构建为：

其中，

为loss function，

为正则化项。
(2) 叠加式的训练(Additive Training)：

给定样本：

(初始预测)，

…….以此类推，可以得到：

其中，

为前K-1棵树的预测结果，$ f_K(x_i)$ 为第K棵树的预测结果。

因此，目标函数可以分解为：

由于正则化项也可以分解为前K-1棵树的复杂度加第K棵树的复杂度，因此：

由于

在模型构建到第K棵树的时候已经固定，无法改变，因此是一个已知的常数，可以在最优化的时候省去，故：

(3) 使用泰勒级数近似目标函数：

其中，

在这里，我们补充下泰勒级数的相关知识：
在数学中，泰勒级数（英语：Taylor series）用无限项连加式——级数来表示一个函数，这些相加的项由函数在某一点的导数求得。具体的形式如下：

由于$\sum{i=1}^{n}l\left(y{i}, \hat{y}^{(K-1)}\right)$在模型构建到第K棵树的时候已经固定，无法改变，因此是一个已知的常数，可以在最优化的时候省去，故：

  1. 如何定义一棵树

为了说明如何定义一棵树的问题，我们需要定义几个概念：第一个概念是样本所在的节点位置$q(x)$，第二个概念是有哪些样本落在节点j上

，第三个概念是每个结点的预测值 $w{q(x)}$，第四个概念是模型复杂度 $\Omega\left(f{K}\right)$，它可以由叶子节点的个数以及节点函数值来构建，则：

如下图的例子：

因此，目标函数用以上符号替代后：

由于我们的目标就是最小化目标函数，现在的目标函数化简为一个关于w的二次函数：

根据二次函数求极值的公式：$y=ax^2 bx c$ 求极值，对称轴在 $x=-\frac{b}{2 a}$，极值为 $y=\frac{4 a c-b^{2}}{4 a}$，因此：

以及

5.如何寻找树的形状：

不难发现，刚刚的讨论都是基于树的形状已经确定了计算$w$和$L$，但是实际上我们需要像学习决策树一样找到树的形状。因此，我们借助决策树学习的方式，使用目标函数的变化来作为分裂节点的标准。我们使用一个例子来说明：

例子中有8个样本，分裂方式如下，因此:

因此，从上面的例子看出：分割节点的标准为

即：

(6.1) 精确贪心分裂算法：

XGBoost在生成新树的过程中，最基本的操作是节点分裂。节点分裂中最重 要的环节是找到最优特征及最优切分点, 然后将叶子节点按照最优特征和最优切 分点进行分裂。

选取最优特征和最优切分点的一种思路如下：首先找到所有的候 选特征及所有的候选切分点, 一一求得其 $\mathcal{L}{\text {split }}$, 然后选择 $\mathcal{L}{\mathrm{split}}$ 最大的特征及 对应切分点作为最优特征和最优切分点。我们称此种方法为精确贪心算法。该算法是一种启发式算法, 因为在节点分裂时只选择当前最优的分裂策略, 而非全局最优的分裂策略。精确贪心算法的计算过程如下所示：

(6.2) 基于直方图的近似算法：

精确贪心算法在选择最优特征和最优切分点时是一种十分有效的方法。它计算了所有特征、所有切分点的收益, 并从中选择了最优的, 从而保证模型能比较好地拟合了训练数据。但是当数据不能完全加载到内存时，精确贪心算法会变得 非常低效，算法在计算过程中需要不断在内存与磁盘之间进行数据交换，这是个非常耗时的过程, 并且在分布式环境中面临同样的问题。为了能够更高效地选 择最优特征及切分点, XGBoost提出一种近似算法来解决该问题。 基于直方图的近似算法的主要思想是：对某一特征寻找最优切分点时，首先对该特征的所有切分点按分位数 (如百分位) 分桶, 得到一个候选切分点集。特征的每一个切分点都可以分到对应的分桶; 然后，对每个桶计算特征统计G和H得到直方图, G为该桶内所有样本一阶特征统计g之和, H为该桶内所有样本二阶特征统计h之和; 最后，选择所有候选特征及候选切分点中对应桶的特征统计收益最大的作为最优特征及最优切分点。基于直方图的近似算法的计算过程如下所示：

1) 对于每个特征 $k=1,2, \cdots, m,$ 按分位数对特征 $k$ 分桶 $\Theta,$ 可得候选切分点,：

2) 对于每个特征 $k=1,2, \cdots, m,$ 有：

3) 类似精确贪心算法，依据梯度统计找到最大增益的候选切分点。

下面用一个例子说明基于直方图的近似算法：

假设有一个年龄特征，其特征的取值为18、19、21、31、36、37、55、57，我们需要使用近似算法找到年龄这个特征的最佳分裂点：

​

近似算法实现了两种候选切分点的构建策略：全局策略和本地策略。全局策略是在树构建的初始阶段对每一个特征确定一个候选切分点的集合, 并在该树每一层的节点分裂中均采用此集合计算收益, 整个过程候选切分点集合不改变。本地策略则是在每一次节点分裂时均重新确定候选切分点。全局策略需要更细的分桶才能达到本地策略的精确度, 但全局策略在选取候选切分点集合时比本地策略更简单。

在XGBoost系统中, 用户可以根据需求自由选择使用精确贪心算法、近似算法全局策略、近似算法本地策略, 算法均可通过参数进行配置。

LightGBM

关于LightGBM的介绍，及它与GBDT、XGBoost的区别笔者之前总结在下面这篇文章里了，感兴趣的小伙伴可以看看：

https://zhuanlan.zhihu.com/p/156041266