XGBoost

机器学习 - 这篇文章属于一个选集。

§ 1: 线性回归与逻辑回归

§ 2: 随机森林

§ 3: 本文

1. XGBoost 原理
#

XGBoost（eXtreme Gradient Boosting）是一种基于梯度提升（Gradient Boosting）的机器学习算法，具有高效、灵活和可扩展的特点。

它通过构建多个弱学习器（通常是决策树），并结合这些弱学习器的预测结果来提高模型的准确性和鲁棒性。下面详细介绍 XGBoost 的核心原理。

1.1. 梯度提升的基本概念
#

梯度提升是一种集成学习方法，通过逐步构建模型并结合多个模型的预测结果来提高整体模型的性能。每个新模型都试图纠正或学习前一个模型的错误。

1.2. 目标函数
#

目标函数的一般形式： $$ \mathcal{L}(\theta) = \sum_{i} l(y_i, \hat{y}i) + \sum{k} \Omega(f_k) $$
- 其中，$ \Omega(f) $ 是正则化项，$ l $ 是损失函数，$ \theta $ 是模型参数。
对于每一轮迭代，我们添加一个新的函数 $ f_t $ 来改进当前模型的预测。
- 目标函数可以表示为： $$ \mathcal{L}^{(t)} = \sum_{i} l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) $$
- 其中，$ \hat{y}_i^{(t-1)} $ 是第 $ t-1 $ 轮的预测值，$ f_t $ 是第 $ t $ 轮的新树。
二阶泰勒展开
- 为了方便优化，XGBoost 使用二阶泰勒展开对目标函数进行近似。对于每个数据点 $ i $，我们有： $$ l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) \approx l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) $$
- 其中，$ g_i $ 和 $ h_i $ 分别是一阶导数和二阶导数： $$ g_i = \frac{\partial l(y_i, \hat{y}_i)}{\partial \hat{y}_i} $$ $$ h_i = \frac{\partial^2 l(y_i, \hat{y}_i)}{\partial \hat{y}_i^2} $$
- 目标函数的二阶展开形式
- 将二阶泰勒展开式代入到目标函数，我们得到： $$ \mathcal{L}^{(t)} \approx \sum_{i} \left[ l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t) $$
- 去掉与 $ f_t $ 无关的常数项后，可以得到在每一轮的迭代中，XGBoost 优化目标函数的二阶泰勒展开式：
$$ \mathcal{L}^{(t)} \approx \sum_{i} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) $$

1.3. 叶子节点预测
#

对于每个叶子节点 $ j $，其局部目标函数为： $$ \mathcal{L_j} = \sum_{i \in \text{节点 } j} \left[ g_i w_j + \frac{1}{2} h_i w_j^2 \right] + \frac{1}{2} \lambda w_j^2 $$ 求解最优 $ w_j $

对 $ \mathcal{L_j} $ 进行求导，并令其等于零： $$ \frac{\partial \mathcal{L_j}}{\partial w_j} = \sum_{i \in \text{节点 } j} g_i + \left( \sum_{i \in \text{节点 } j} h_i + \lambda \right) w_j = 0 $$

解得： $$ w_j = -\frac{\sum_{i \in \text{节点 } j} g_i}{\sum_{i \in \text{节点 } j} h_i + \lambda} $$

1.4. 模拟计算
#

下面通过一个直观的例子，来了解具体的计算过程

假设我们有一个简单的数据集，目标是预测一个连续值。初始模型的预测值是常数 $ \hat{y}^{(0)} = 0 $。损失函数是平方损失，即： $$ l(y, \hat{y}) = \frac{1}{2} (y - \hat{y})^2 $$

数据集
- 假设我们有如下数据：
  
  样本 $ i $ 特征 $ x_i $ 实际值 $ y_i$ 初始预测值 $ \hat{y}_i^{(0)} $
  
  1 1.0 2.0 0
  
  2 2.0 3.0 0
  
  3 3.0 4.0 0
第一步：计算梯度和二阶导数
- 损失函数： $$ l(y, \hat{y}) = \frac{1}{2} (y - \hat{y})^2 $$
- 梯度 $ g_i $ 和二阶导数 $ h_i $ 计算如下： $$ g_i = \frac{\partial l(y_i, \hat{y}_i)}{\partial \hat{y}_i} = \hat{y}_i - y_i $$ $$ h_i = \frac{\partial^2 l(y_i, \hat{y}_i)}{\partial \hat{y}_i^2} = 1 $$
- 对于所有样本：
  
  样本 $ i $ 特征 $ x_i $ 实际值 $ y_i$ 初始预测值 $ \hat{y}_i^{(0)} $ 梯度 $ g_i$ 二阶导数 $ h_i$
  
  1 1.0 2.0 0 -2.0 1
  
  2 2.0 3.0 0 -3.0 1
  
  3 3.0 4.0 0 -4.0 1
第二步：构建树模型
- 假设我们构建了一棵简单的树，只有一个分裂：
```
      [根节点]
         |
    [分裂点: x < 2.5]
       /     \
[叶子节点1]  [叶子节点2]
```
- 每个叶子节点的预测值通过最小化局部目标函数来确定： $$ \text{叶子节点1的预测值} = -\frac{\sum_{i \in \text{节点1}} g_i}{\sum_{i \in \text{节点1}} h_i + \lambda} $$ $$ \text{叶子节点2的预测值} = -\frac{\sum_{i \in \text{节点2}} g_i}{\sum_{i \in \text{节点2}} h_i + \lambda} $$
- 假设分裂后：
  - 样本1和样本2在叶子节点1中。
  - 样本3在叶子节点2中。
- 则叶子节点的预测值为： $$ \text{叶子节点1的预测值} = -\frac{(-2.0) + (-3.0)}{1 + 1 + \lambda} = \frac{5.0}{2 + \lambda} $$ $$ \text{叶子节点2的预测值} = -\frac{(-4.0)}{1 + \lambda} = \frac{4.0}{1 + \lambda} $$
- 假设 $\lambda = 0$： $$ \text{叶子节点1的预测值} = 2.5 $$ $$ \text{叶子节点2的预测值} = 4.0 $$
第三步：更新预测

样本 $ i $ 特征 $ x_i $ 实际值 $ y_i$ 初始预测值 $ \hat{y}_i^{(0)} $ 新预测值

1 1.0 2.0 0 2.5

2 2.0 3.0 0 2.5

3 3.0 4.0 0 4.0
- 解释
  1. 计算梯度和二阶导数：
    - 对于每个样本，计算梯度和二阶导数，梯度 $ g_i $ 表示损失函数对当前预测值的负偏导数，二阶导数 $ h_i $ 是常数。
  2. 构建树模型：
    - 根据梯度和二阶导数，找到最佳分裂点（在本例中为 x < 2.5 ）。计算每个叶子节点的预测值，通过负梯度和二阶导数的比值来确定。
  3. 更新预测：
    - 将新树的预测值加入到当前预测值中，更新每个样本的预测结果。
通过这样的迭代过程，XGBoost 在每一轮迭代中不断优化模型，使其逐步逼近最优解。二阶优化使得模型能够更快、更稳定地收敛，减少过拟合风险。

样本 \( i \)	特征 \( x_i \)	实际值 \( y_i\)
1	1.0	2.0
2	2.0	3.0
3	3.0	4.0

样本 \( i \)	特征 \( x_i \)	实际值 \( y_i\)	梯度 \( g_i\)	二阶导数 \( h_i\)
1	1.0	2.0	-2.0	1
2	2.0	3.0	-3.0	1
3	3.0	4.0	-4.0	1

样本 \( i \)	特征 \( x_i \)	实际值 \( y_i\)	新预测值
1	1.0	2.0	2.5
2	2.0	3.0	2.5
3	3.0	4.0	4.0

1.5. 节点的分裂
#

在XGBoost中，节点分裂准则是用于确定如何在特定节点上选择最佳分裂点（即选择哪个特征和哪个阈值来分裂节点），以最大程度地减少损失函数。这个过程是通过计算每个可能的分裂点的增益来完成的。通过计算增益，选择能够最大化损失减少量的分裂点，从而构建出性能优良的决策树模型。

具体来说，增益计算的过程包括以下步骤：

基本公式： $$ \text{增益} = \mathcal{L_\text{分裂前}} - \mathcal{L}_{\text{分裂后}} $$
- 其中：
  - $\mathcal{L}_{\text{分裂前}}$ 是节点在分裂前的损失。
  - $\mathcal{L}_{\text{分裂后}}$ 是节点在分裂后的损失。
具体步骤：
1. 计算分裂前的损失：
  - 对于一个节点，其损失函数是通过其梯度和二阶导数来计算的。假设节点中所有样本的集合为 $ I $，则分裂前的损失计算公式为： $$ \mathcal{L}{\text{节点}} = -\frac{1}{2} \frac{\left( \sum_{i \in I} g_i \right)^2}{\sum_{i \in I} h_i + \lambda} $$
    - 其中，$ g_i $ 是样本的梯度，$ h_i $ 是样本的二阶导数，$\lambda$ 是正则化参数。
2. 计算分裂后的损失：
  - 分裂后的损失是左右两个子节点的损失之和。假设左子节点的样本集合为 $ I_L $，右子节点的样本集合为 $ I_R $，则分裂后的损失计算公式为： $$ \mathcal{L}{\text{分裂后}} = \mathcal{L_{\text{左子节点}}} + \mathcal{L}_{\text{右子节点}} $$
    - 其中，左右子节点的损失分别为： $$ \mathcal{L}{\text{左子节点}} = -\frac{1}{2} \frac{\left( \sum_{i \in I_L} g_i \right)^2}{\sum_{i \in I_L} h_i + \lambda} $$ $$ \mathcal{L}{\text{右子节点}} = -\frac{1}{2} \frac{\left( \sum_{i \in I_R} g_i \right)^2}{\sum_{i \in I_R} h_i + \lambda} $$
3. 计算增益：
  - 最终，增益的计算公式为： $$ \text{增益} = -\frac{1}{2} \frac{\left( \sum_{i \in I} g_i \right)^2}{\sum_{i \in I} h_i + \lambda} + \frac{1}{2} \left( \frac{\left( \sum_{i \in I_L} g_i \right)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{\left( \sum_{i \in I_R} g_i \right)^2}{\sum_{i \in I_R} h_i + \lambda} \right) $$

2. 过拟合问题
#

2.1. 正则化
#

正则化是通过在目标函数中引入惩罚项来控制模型复杂度，从而防止过拟合。

L1正则化（Lasso）：
- 通过参数 alpha 控制叶子节点权重的 L1 正则化。可以在参数设置中通过 alpha 来实现。
```
param = {'alpha': 0.1}
```
L2正则化（Ridge）：
- 通过参数 lambda 控制叶子节点权重的 L2 正则化。可以在参数设置中通过 lambda 来实现。
```
param = {'lambda': 1.0}
```

2.2. 子采样
#

子采样（Subsampling）是通过随机选择部分数据和特征来训练模型，以增加模型的多样性，从而防止过拟合。

行采样（Subsample）：
- 通过参数 subsample 控制训练每棵树时使用的样本比例。
```
param = {'subsample': 0.8}
```
列采样：
- 通过 colsample_bytree 控制训练每棵树时使用的特征比例；
- 通过 colsample_bylevel 控制树的每一层使用的特征比例；
- 通过 colsample_bynode 控制树的每一个节点使用的特征比例。
```
param = {'colsample_bytree': 0.8, 
         'colsample_bylevel': 0.8, 
         'colsample_bynode': 0.8}
```

2.3. 树的参数控制
#

通过控制决策树的结构来防止过拟合。

最大深度：
- 通过参数 max_depth 控制树的最大深度。较小的树深度可以防止模型过拟合。
```
param = {'max_depth': 5}
```
最小叶子节点样本数：
- 通过参数 min_child_weight 控制叶子节点所需的最小样本权重和。
- 较大的 min_child_weight 值可以防止过拟合。
```
param = {'min_child_weight': 10}
```
最小分裂损失：
- 通过参数 gamma 控制分裂的最小损失减少。较大的 gamma 值可以防止过拟合。
```
param = {'gamma': 0.1}
```

2.4. 学习率
#

通过降低每棵树对模型的贡献来防止过拟合。
- 学习率（Learning Rate）：
- 通过参数 eta 控制学习率。较小的学习率可以减缓模型的学习速度，从而减少过拟合的风险。
```
param = {'eta': 0.01}
```

2.5. 提前停止
#

通过在验证集上的性能不再提升时，使用提前停止（Early Stopping）来防止过拟合。

提前停止轮数（early_stopping_rounds）：

在验证集上，如果在指定轮数内性能不再提升，提前停止训练。

model.fit(X_train, 
          y_train, 
          early_stopping_rounds=10, 
          eval_set=[(X_valid, y_valid)], 
          verbose=True)

2.6. 树模型类型
#

通过选择适当的模型类型来防止过拟合。

模型类型（Booster Types）：
- 选择不同的提升器类型，例如 gbtree、gblinear 或 dart。
- 其中，dart 通过 dropout 技术可以进一步防止过拟合。
```
param = {'booster': 'dart'}
```

2.7. 自定义损失函数
#

通过定义适合特定问题的损失函数和评估指标，可以更好地控制模型的复杂度和泛化能力。

3. Python 代码
#

安装依赖包

pip install xgboost scikit-learn numpy pandas

代码示例：

import xgboost as xgb
import numpy as np
import pandas as pd
from sklearn.datasets import load_boston
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error

# 加载数据集
data = load_boston()
X = data.data
y = data.target

# 拆分数据集
X_train, X_valid, y_train, y_valid = train_test_split(X, 
                                                      y, 
                                                      test_size=0.2, 
                                                      random_state=42)

# 创建 DMatrix
dtrain = xgb.DMatrix(X_train, label=y_train)
dvalid = xgb.DMatrix(X_valid, label=y_valid)

# 设置参数
param = {
    'max_depth': 5,
    'eta': 0.01,
    'subsample': 0.8,
    'colsample_bytree': 0.8,
    'min_child_weight': 10,
    'gamma': 0.1,
    'lambda': 1.0,
    'alpha': 0.1,
    'objective': 'reg:squarederror',
    'eval_metric': 'rmse',
    'nthread': 4  # 使用4个线程进行并行计算
}

# 设置验证集
evals = [(dtrain, 'train'), (dvalid, 'eval')]

# 训练模型
bst = xgb.train(param, 
                dtrain, 
                num_boost_round=1000, 
                evals=evals, 
                early_stopping_rounds=10, 
                verbose_eval=True)

# 预测
y_pred = bst.predict(dvalid)

# 评估模型
rmse = mean_squared_error(y_valid, y_pred, squared=False)
print(f'RMSE: {rmse}')

# 保存模型
bst.save_model('xgboost_model.json')

# 加载模型
loaded_bst = xgb.Booster()
loaded_bst.load_model('xgboost_model.json')

# 使用加载的模型进行预测
y_pred_loaded = loaded_bst.predict(dvalid)

# 评估加载后的模型
rmse_loaded = mean_squared_error(y_valid, 
                                 y_pred_loaded, 
                                 squared=False)
print(f'RMSE (Loaded Model): {rmse_loaded}')

4. XGBoost vs. GBDT
#

XGBoost（eXtreme Gradient Boosting）和 GBDT（Gradient Boosting Decision Tree）都是基于梯度提升算法的集成学习方法，但 XGBoost 对传统的 GBDT 做了许多改进和优化。例如：使用正则化来控制模型复杂度，从而减少过拟合的风险；采用了二阶导数信息来优化损失函数，提高了优化过程的稳定性和速度。

以下是两者的主要区别：

正则化：
- 传统的 GBDT 并没有明确的正则化项，只是通过调节树的深度、叶子节点的最小样本数等参数来控制模型的复杂度。
- XGBoost 引入了正则化项（L1 和 L2 正则化）来控制树的复杂度，防止过拟合。
并行化和分布式计算：
- 传统的 GBDT 通常是顺序构建树的，不支持并行化和分布式计算。
- XGBoost 和 GBDT 一样都是基于前一个树预测后的残差进行继续学习，所以无法在树的维度上进行并行训练。
- 但是，XGBoost 支持特征粒度的并行化（Feature-wise Parallelism），可以在构建树的过程中并行计算每个特征的分裂点。
- XGBoost 还支持分布式计算，可以在大规模数据集上使用分布式环境（如 Hadoop、Spark）进行训练。
缺失值处理：
- 传统的 GBDT 需要对缺失值进行预处理，或者在训练过程中忽略含有缺失值的样本。
- XGBoost 自动处理缺失值，在训练过程中找到最优的分裂方向，无需额外的预处理步骤。
  - 在特征k上寻找最佳 split point 时，不会对该列特征缺失的样本进行遍历，而只对该列特征值为非缺失的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。
  - 在逻辑实现上，为了保证完备性，会将该特征值缺失的样本分别分配到左叶子结点和右叶子结点，两种情形都计算一遍后，选择分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向。
  - 如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。
加权分位数和近似算法：
- 传统的 GBDT 通常是通过精确算法计算每个分裂点，计算复杂度较高。
- XGBoost 使用加权分位数和近似算法来加快分裂点的计算。
  - 通过将特征值进行分桶（binning），减少需要计算的分裂点数量，从而提高训练速度。
二阶导数（泰勒展开）：
- 传统的 GBDT 仅使用一阶导数（梯度）来优化损失函数。
- XGBoost 使用二阶泰勒展开来优化损失函数，不仅考虑一阶导数（梯度），还考虑二阶导数（曲率），使得优化过程更加稳定和高效。
树的构建
- 传统的 GBDT 通常是按层次顺序构建树，即一层一层地添加节点。
- XGBoost 使用了预排序算法来加速树的构建。
  - 支持按节点顺序构建树，通过计算每个节点的增益来决定是否分裂节点，从而优化树的结构。
参数调优
- GBDT 的参数调优主要集中在树的深度、学习率和叶子节点的最小样本数等。
- XGBoost 的参数调优更加灵活，除了树的深度、学习率等，还包括正则化参数（$ \lambda $ 和 $ \alpha $）、子样本比例、列样本比例等，可以更好地控制模型复杂度和训练速度。