XGBoost: A Scalable Tree Boosting System.

XGBoost (eXtreme Gradient Boosting)是一种高效、灵活、大规模的分布式梯度提升库，是梯度提升决策树GBDT算法的工程实现。

XGBoost和GBDT的主要区别在于：

  GBDT XGBoost
基学习器 CART回归树 支持多种类型的基学习器，比如决策树或线性模型
损失函数 使用损失函数的一阶导数信息，当前基学习器拟合损失函数的负梯度 使用损失函数的一阶和二阶导数信息，当前基学习器最小化损失函数的二阶泰勒近似
正则项 没有显式引入正则项 使用叶结点数量和叶结点权重的L2范数作为正则项
缺失值处理 手动对缺失值进行填充 通过稀疏感知算法为每个结点学习出特征划分的缺省方向

XGBoost的主要优点包括：

XGBoost的主要缺点是预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应的样本索引，占用了两倍的内存。

1. XGBoost的建模

XGBoost是由$K$个基学习器组成的加法模型，学习过程采用前向分布算法。假设第$t$次迭代时训练的基学习器是$f_t(x)$，则样本的当前预测结果为：

\[\hat{y}^{(t)} = \sum_{k=1}^t f_k(x) = \hat{y}^{(t-1)}+f_t(x)\]

XGBoost的目标函数由损失函数$l$（衡量模型的偏差）和正则化项$\Omega$（防止过拟合）共同组成:

\[Obj = \sum_{i=1}^n l(y_i,\hat{y}_i) + \sum_{k=1}^K \Omega(f_k)\]

则第$t$次迭代时的目标函数为：

\[\begin{aligned} Obj^{(t)} &= \sum_{i=1}^n l(y_i,\hat{y}^{(t)}_i) + \sum_{k=1}^t \Omega(f_k) \\ &= \sum_{i=1}^n l(y_i,\hat{y}^{(t-1)}_i+f_t(x_i)) +\Omega(f_t) + Const. \end{aligned}\]

XGBoost对损失函数$l(y_i,\hat{y}^{(t-1)}_i+f_t(x_i))$在点$f_t(x_i)$处进行二阶泰勒展开：

\[l(y_i,\hat{y}^{(t-1)}_i+f_t(x_i)) ≈ l(y_i,\hat{y}^{(t-1)}_i) + g_i f_t(x_i) +\frac{1}{2}h_i f_t^2(x_i)\]

其中$g_i,h_i$分别是损失函数的一阶导数和二阶导数：

\[\begin{aligned} g_i &= \frac{\partial l(y_i,\hat{y}^{(t-1)}_i)}{\partial \hat{y}^{(t-1)}_i} \\ h_i &= \frac{\partial^2 l(y_i,\hat{y}^{(t-1)}_i)}{\partial (\hat{y}^{(t-1)}_i)^2} \end{aligned}\]

因此XGBoost在第$t$次迭代时的目标函数为：

\[\begin{aligned} Obj^{(t)} &≈ \sum_{i=1}^n [l(y_i,\hat{y}^{(t-1)}_i) + g_i f_t(x_i) +\frac{1}{2}h_i f_t^2(x_i)] +\Omega(f_t) + Const. \\ & \propto \sum_{i=1}^n [ g_i f_t(x_i) +\frac{1}{2}h_i f_t^2(x_i)] +\Omega(f_t) \end{aligned}\]

在每一次迭代中，只需要求出当前损失函数的一阶导数值和二阶导数值，然后最优化上述目标函数，就可以得到当前迭代的基学习器$f_t(x)$，最后根据加法模型得到一个整体模型。

2. 使用决策树的XGBoost模型

XGBoost的基学习器不仅支持决策树，还支持线性模型。本节主要讨论基于决策树的XGBoost模型。

一颗决策树可以由叶结点的权重向量$w$和样本到叶结点的映射关系$q$描述:

\[f(x) = w_{q(x)}, w \in \Bbb{R}^J, q: \Bbb{R}^d \to \{1,2,...,J\}\]

其中$J$为叶结点的个数，$J$越小则模型越简单，因此可以衡量决策树的复杂度；此外叶结点也不应含有过高的权重。因此正则化项$\Omega$由生成的决策树$f$的叶结点数量和所有叶结点权重的L2范数共同决定：

\[\Omega(f) = \gamma J + \frac{1}{2}\lambda \sum_{j=1}^J w_j^2\]

把属于第$j$个叶结点的所有样本$x_i$划入到一个叶子结点的样本集合中：$I_j = {i | q(x_i)=j}$。XGBoost在第$t$次迭代时的目标函数可以写成：

\[\begin{aligned} Obj^{(t)} & \propto \sum_{i=1}^n [ g_i f_t(x_i) +\frac{1}{2}h_i f_t^2(x_i)] +\Omega(f_t) \\ &= \sum_{i=1}^n [ g_i w_{q(x_i)} +\frac{1}{2}h_i w^2_{q(x_i)}] +\gamma J + \frac{1}{2}\lambda \sum_{j=1}^J w_j^2 \\ &= \sum_{j=1}^J [ (\sum_{i \in I_j}g_i) w_{j} +\frac{1}{2}(\sum_{i \in I_j}h_i +\lambda)w^2_{j}] +\gamma J \end{aligned}\]

其中第二个等式是遍历所有样本后求每个样本的损失函数；第三个等式是遍历所有叶结点，获取每个叶结点上的样本集合后再求损失函数；由于最终每个样本会落在某一个叶结点上，因此两式是等价的。

记$G_j = \sum_{i \in I_j}g_i$为叶结点$j$所包含样本的一阶偏导数累加之和，$H_j = \sum_{i \in I_j}h_i$为叶结点$j$所包含样本的二阶偏导数累加之和。由于$G_j,H_j$是根据前$t-1$步计算的结果，因此是常量。XGBoost在第$t$次迭代时的最终目标函数为：

\[Obj^{(t)} = \sum_{j=1}^J [ G_j w_{j} +\frac{1}{2}(H_j +\lambda)w^2_{j}] +\gamma J\]

注意到上式左半部分为$w_j$的一元二次函数，当$w_j=-\frac{G_j}{H_j +\lambda}$时取极小值，因此总目标函数可以化简为：

\[Obj^{(t)} = -\frac{1}{2}\sum_{j=1}^J \frac{G_j^2}{H_j +\lambda} +\gamma J\]

3. XGBoost的工程实现

(1) 结点划分算法 Split Finding

在实际训练过程中，当建立第$t$棵树时需要找到叶结点的最优切分点，XGBoost支持两种划分数据的方法：贪心算法和近似算法。

⚪ 贪心算法

贪心算法是构造决策树的通用算法，可以得到最优解。从树的深度为$0$开始，贪心算法的步骤如下：

  1. 对每个叶结点枚举所有可用的特征；
  2. 针对每个特征，把属于该结点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
  3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该结点上分裂出左右两个新的叶结点，并为每个新结点关联对应的样本集；
  4. 递归执行1-3直到满足特定条件为止。

通过对特征值进行升序排列，可以通过一次线性扫描枚举出所有分割的$G,H$组合。分裂前后的目标函数分别为：

\[\begin{aligned} Obj_1 & =-\frac{1}{2} \frac{(G_L+G_R)^2}{H_L+H_R +\lambda} +\gamma \\ Obj_2 & =-\frac{1}{2}(\frac{G_L^2}{H_L +\lambda} + \frac{G_R^2}{H_R +\lambda}) +2\gamma \end{aligned}\]

因此分裂收益计算为：

\[Gain = \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\]

其中惩罚项$\gamma$给出了分裂收益的阈值，如果划分结点后的收益没有超过这个阈值，则对其进行剪枝。

⚪ 近似算法

当数据量太大时贪心算法无法把数据读入内存进行计算。对于数据的每个特征，近似算法通过只考察特征的几个分位点给出近似最优解，从而减少计算复杂度。

分位点(quantile)的选择有两种策略：

  1. global：预先给定候选的分位点，学习每棵树时都采用这种分割；这种策略通常需要设置更多的候选分位点才能得到满意的性能。
  2. local：在每次拆分时重新指定候选的分位点；每次可以设置较少的分位点，但是需要更多的计算步骤。

XGBoost以二阶导数值$h_i$作为样本的权重划分分位点，通过加权分位缩略图(Weighted Quantile Sketch)实现。下图给出了选择三分位点的例子：

下面说明为何用二阶导数值$h_i$划分分位点。对目标函数做如下变换（不考虑正则化项）：

\[\begin{aligned} Obj^{(t)} & \propto \sum_{i=1}^n [ g_i f_t(x_i) +\frac{1}{2}h_i f_t^2(x_i)] \\& = \sum_{i=1}^n \frac{1}{2}h_i[ \frac{2g_i f_t(x_i)}{h_i} + f_t^2(x_i)]\\& = \sum_{i=1}^n \frac{1}{2}h_i[ \frac{2g_i f_t(x_i)}{h_i} + f_t^2(x_i) + (-\frac{g_i}{h_i})^2-(-\frac{g_i}{h_i})^2] \\& = \sum_{i=1}^n \frac{1}{2}h_i[ f_t^2(x_i) - (-\frac{g_i}{h_i})]^2-\sum_{i=1}^n \frac{1}{2}\frac{g_i^2}{h_i} \end{aligned}\]

因此$h_i$相当于平方损失函数中的样本权重。

(2) 稀疏感知算法 Sparsity-aware

实际工程中一般会出现输入值稀疏的情况，比如数据特征的缺失。XGBoost在构建树的结点的过程中只对特征为非缺失值的数据进行遍历，同时为每个结点增加一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。

学习缺省方向的方法是分别把特征缺省的样本划分到左右分支后计算增益，选择增益最大的方向即为最优缺省方向。

(3) 特征并行学习 Parallel Learning

在树的生成过程中最耗时的步骤之一是在每次寻找最佳分裂点时都需要对特征的值进行排序。XGBoost在训练之前会根据特征对数据进行排序，并把每一个特征排序后的值以及对应样本的索引存储到由稀疏矩阵存储格式 (Compressed Sparse Columns Format, CSC)定义的块结构中。

在训练的过程中通过顺序访问排序后的块，以遍历样本特征的取值，可以大大减小计算量。此外分块存储后不同特征之间互不干涉，可以实现分布式或者多线程同时对不同的特征进行切分点查找，即特征的并行化处理。

(4) 缓存访问算法 Cache-aware Access

在顺序访问特征值时，访问的是一块连续的内存空间；但通过特征值持有的样本索引访问样本获取一阶、二阶导数时，这个访问操作访问的内存空间并不连续，这样可能造成cpu缓存命中率低，影响算法效率。

为了解决缓存命中率低的问题，XGBoost提出了缓存访问算法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就实现了非连续空间到连续空间的转换，提高了算法效率。此外适当调整块大小，也可以有助于缓存优化。

(5) 核外块计算 Blocks for Out-of-core Computation

当数据量非常大时，不能把所有的数据都加载到内存中。此时必须将一部分数据先存放在硬盘中，当需要时再加载进内存。这样操作具有很明显的计算瓶颈，即硬盘的IO操作速度远远低于内存的处理速度，导致存在大量等待硬盘IO操作的情况。

针对这个问题XGBoost提出了“核外”计算的优化方法。具体操作为，将数据集分成多个块存放在硬盘中，使用一个独立的线程专门从硬盘读取数据，加载到内存中，这样算法在内存中处理数据就可以和从硬盘中读取数据同时进行。

此外，XGBoost还用了两种方法来降低硬盘的读写开销：

4. XGBoost的代码实现

pip install xgboost

(1) XGBoost的主要参数

下面介绍xgboost库中定义的XGBoost模型的主要参数：

⚪ 通用参数 General Parameters

⚪ 决策树参数 Parameters for Tree Booster

⚪ 学习任务参数 Learning Task Parameters

(2) 使用XGBoost原生接口进行多分类

下面以IRIS鸢尾花分类数据集为例，介绍使用XGBoost原生接口进行多分类任务的例子：

import xgboost as xgb
# 设置XGBoost的参数
params = {
    'booster': 'gbtree',
    'objective': 'multi:softmax', 
    'num_class': 3,
    'gamma': 0.1,
    'max_depth': 6,
    'lambda': 2,
    'subsample': 0.7,
    'colsample_bytree': 0.7,
    'min_child_weight': 3,
    'eta': 0.1,
}

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
# 准备数据集
iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# 训练XGBoost
dtrain = xgb.DMatrix(X_train, y_train)
num_rounds = 500
model = xgb.train(params, dtrain, num_rounds)

from sklearn.metrics import accuracy_score
# 对测试集进行预测
dtest = xgb.DMatrix(X_test)
ans = model.predict(dtest)
print("Accuracy : " + str(accuracy_score(ans, y_test)))

from xgboost import plot_importance
from matplotlib import pyplot as plt
# 显示重要特征
plot_importance(model)
plt.show()

(3) 使用基于Scikit-learn接口的XGBoost进行回归

本节以kaggle竞赛中的House Prices回归问题为例，介绍使用基于Scikit-learn接口的XGBoost进行回归的方法。

该数据集一共有81列，第一列是id，最后一列是标签，中间79列是特征。这79列特征中，有43列是分类型变量，33列是整数变量，3列是浮点型变量。训练数据集中存在缺失值。

import pandas as pd
# 1.读文件
data = pd.read_csv('./dataset/train.csv')
data.dropna(axis=0, subset=['SalePrice'], inplace=True)

# 2.切分数据 (输入：特征) (输出：预测目标变量)
y = data.SalePrice
X = data.drop(['SalePrice'], axis=1).select_dtypes(exclude=['object'])

from sklearn.model_selection import train_test_split
# 3.切分训练集、测试集, 切分比例75 : 25
train_X, test_X, train_y, test_y = train_test_split(X.values, y.values, test_size=0.25)

from sklearn.impute import SimpleImputer
# 4.空值处理，默认方法：使用特征列的平均值进行填充
my_imputer = SimpleImputer()
train_X = my_imputer.fit_transform(train_X)
test_X = my_imputer.transform(test_X)

import xgboost as xgb
# 5.调用XGBoost模型，使用训练集数据进行训练
my_model = xgb.XGBRegressor(
    objective='reg:squarederror',
    verbosity=2)
# 对应的xgb.XGBClassifier()为分类模型
my_model.fit(train_X, train_y, verbose=False)

# 6.使用模型对测试集数据进行预测
predictions = my_model.predict(test_X)

from sklearn.metrics import mean_absolute_error
# 7.对模型的预测结果进行评判（平均绝对误差）
print("Mean Absolute Error : " + str(mean_absolute_error(predictions, test_y)))