基本概念与原理

XGBoost （eXtreme Gradient Boosting）的概念

“Extreme”表示其极致的性能优化
“Gradient”指其使用梯度下降算法优化损失函数
“Boosting”表示其采用提升（Boosting）集成学习方法

XGBoost 是一种高效的机器学习算法，由华盛顿大学的Tianqi Chen开发。它是梯度提升决策树（GBDT）的一种改进实现，通过集成多个弱学习器（通常是决策树）来构建强大的预测模型。

XGBoost 相较GBDT的优势

XGBoost在传统GBDT的基础上引入了多项创新：

目标函数优化：XGBoost的目标函数由两部分组成：
• 损失函数（Loss）：衡量模型预测与实际值的差距
• 正则化项（Regularization）：控制模型复杂度，防止过拟合
目标函数可表示为：Obj = L + Ω
二阶泰勒展开
XGBoost使用损失函数的二阶泰勒展开进行近似，这使得优化过程更加高效。
树结构学习：XGBoost采用贪心算法来确定最佳的树结构，通过评估分裂增益来决定是否进行节点分裂。

XGBoost 的实现原理

XGBoost 的基本思想同 GBDT 一样，对于一个包含 $n$ 个样本和 $m$ 个特征的数据集 (\mathcal{D} = \left{\left(\mathbf{x}_i, y_i\right)\right})，其中 (\left|\mathcal{D}\right| = n, \mathbf{x}_i \in \mathbb{R}^m, y_i \in \mathbb{R})，一个集成树模型可以用 (K) 个加法函数(经过K轮迭代训练）预测输出：

$$ \hat{y}_i^K = \phi \left(\mathbf{x}i\right) = \sum{k=1}^{K}{f_k \left(\mathbf{x}_i\right)} =\hat{y}_i^{K-1} + f_K \left(\mathbf{x}_i\right) , f_k \in \mathcal{F} $$

其中，(\mathcal{F} = \left{f \left(\mathbf{x}\right) = w_{q}{\left(\mathbf{x}\right)}\right} \left(q: \mathbb{R}^m \to T, w \in \mathbb{R}^T\right)) 为回归树 (CART)，
(q) 表示每棵树的结构，其将一个样本映射到最终的叶子节点，(T) 为叶子节点的数量，每个 (f_w) 单独的对应一棵结构为 (q) 和权重为 (w) 的树。不同于决策树，每棵回归树的每个叶子节点上包含了一个连续的分值，我们用 (w_i) 表示第 (i) 个叶子节点上的分值。

XGBoost 首先对损失函数进行了改进，添加了 L2 正则项，同时进行了二阶泰勒展开。损失函数表示为：

$$ \begin{equation} \begin{split} \mathcal{L} \left(\phi\right) = \sum_{i}{l \left(\hat{y}_i, y_i\right)} + \sum_{k}{\Omega \left(f_k\right)} \ \text{where} \ \Omega \left(f\right) = \gamma T + \dfrac{1}{2} \lambda \left| w \right|^2 \end{split} \end{equation} $$

其中，(l) 为衡量预测值 (\hat{y}_i) 和真实值 (y_i) 之间差异的函数，(\Omega) 为惩罚项，(\gamma) 和 (\lambda) 为惩罚项系数。

我们用 (\hat{y}_i^{\left(t\right)}) 表示第 (t) 次迭代的第 (i) 个实例，我们需要增加 (f_t) 来最小化如下的损失函数：

$$ \mathcal{L}^{\left(t\right)} = \sum_{i=1}^{n}{l \left(y_i, \hat{y}_i^{\left(t-1\right)} + f_t \left(\mathbf{x}_i\right)\right)} + \Omega \left(f_t\right) $$

对上式进行二阶泰勒展开有：

$$ \mathcal{L}^{\left(t\right)} \simeq \sum_{i=1}^{n}{\left[l \left(y_i, \hat{y}_i^{\left(t-1\right)}\right) + g_i f_t \left(\mathbf{x}_i\right) + \dfrac{1}{2} h_i f_t^2 \left(\mathbf{x}_i\right)\right]} + \Omega \left(f_t\right) $$

其中，(g_i = \partial_{\hat{y}^{\left(t-1\right)}} l \left(y_i, \hat{y}^{\left(t-1\right)}\right), h_i = \partial_{\hat{y}^{\left(t-1\right)}}^{2} l \left(y_i, \hat{y}^{\left(t-1\right)}\right)) 分别为损失函数的一阶梯度和二阶梯度。去掉常数项，第 (t) 步的损失函数可以简化为：

$$ \tilde{\mathcal{L}}^{\left(t\right)} = \sum_{i=1}^{n}{\left[ g_i f_t \left(\mathbf{x}_i\right) + \dfrac{1}{2} h_i f_t^2 \left(\mathbf{x}_i\right)\right]} + \Omega \left(f_t\right) $$

令 (I_j = \left{i \ | \ q \left(\mathbf{x}_i\right) = j\right}) 表示叶子节点 (j) 的实例集合，上式可重写为：

$$ \begin{equation} \begin{split} \tilde{\mathcal{L}}^{\left(t\right)} &= \sum_{i=1}^{n}{\left[ g_i f_t \left(\mathbf{x}_i\right) + \dfrac{1}{2} h_i f_t^2 \left(\mathbf{x}i\right)\right]} + \gamma T + \dfrac{1}{2} \lambda \sum{j=1}^{T}{w_j^2} \ &= \sum_{j=1}^{T}{\left[\left(\sum_{i \in I_j}{g_i}\right) w_j + \dfrac{1}{2} \left(\sum_{i \in I_j}{h_i + \lambda}\right) w_j^2\right]} + \gamma T \end{split} \end{equation} $$

对于一个固定的结构 (q \left(\mathbf{x}\right))，可以通过下式计算叶子节点 (j) 的最优权重 (w_j^*)：

$$ w_j^* = - \dfrac{\sum_{i \in I_j}{g_i}}{\sum_{i \in I_j}{h_i} + \lambda} $$

进而计算对应的最优值：

$$ \tilde{\mathcal{L}}^{\left(t\right)} \left(q\right) = - \dfrac{1}{2} \sum_{j=1}^{T}{\dfrac{\left(\sum_{i \in I_j}{g_i}\right)^2}{\sum_{i \in I_j}{h_i} + \lambda}} + \gamma T $$

上式可以作为评价树的结构 (q) 的评分函数。通常情况下很难枚举所有可能的树结构，一个贪心的算法是从一个节点出发，逐层的选择最佳的分裂节点。令 (I_L) 和 (I_R) 分别表示分裂后左侧和右侧的节点集合，令 (I = I_L \cup I_R)，则分裂后损失的减少量为：

$$ \mathcal{L}{\text{split}} = \dfrac{1}{2} \left[\dfrac{\left(\sum{i \in I_L}{g_i}\right)^2}{\sum_{i \in I_L}{h_i} + \lambda} + \dfrac{\left(\sum_{i \in I_R}{g_i}\right)^2}{\sum_{i \in I_R}{h_i} + \lambda} - \dfrac{\left(\sum_{i \in I}{g_i}\right)^2}{\sum_{i \in I}{h_i} + \lambda}\right] - \gamma $$

XGBoost 也采用了 Shrinkage 的思想减少每棵树的影响，为后续树模型留下更多的改进空间。同时 XGBoost 也采用了随机森林中的特征下采样 (列采样) 方法用于避免过拟合，同时 XGBoost 也支持样本下采样 (行采样)。XGBoost 在分裂点的查找上也进行了优化，使之能够处理无法将全部数据读入内存的情况，同时能够更好的应对一些由于数据缺失，大量零值和 One-Hot 编码导致的特征稀疏问题。除此之外，XGBoost 在系统实现，包括：并行化，Cache-Aware 加速和数据的核外计算 (Out-of-Core Computation) 等方面也进行了大量优化，相关具体实现请参见论文和文档。

运行示例

简单示例代码如下，涵盖数据加载，模型训练，模型预测，性能评估。


# loadData
iris = load_iris()
X, Y = iris.data, iris.target
feature_names = iris.feature_names
target_names = iris.target_names
X_train, X_test, Y_train, Y_test = train_test_split(
        X, Y, test_size=0.2, random_state=30, stratify='y'
    )

# 将数据转换为DMatrix格式
dtrain = xgb.DMatrix(X_train, label=y_train, feature_names=feature_names)
dtest = xgb.DMatrix(X_test, label=y_test, feature_names=feature_names)

# 训练参数
params = {
        'objective': 'multi:softmax',  # 多分类问题
        'num_class': 3,                # 类别数量
        'max_depth': 3,                # 树的最大深度
        'learning_rate': 0.1,          # 学习率
        'eval_metric': 'mlogloss',     # 评估指标
        'seed': 42                     # 随机种子
    }


# 训练模型
num_rounds = 100  # 迭代次数
model = xgb.train(
    params, 
    dtrain, 
    num_rounds, 
    evals=[(dtrain, 'train'), (dtest, 'test')],
    early_stopping_rounds=10,
    verbose_eval=20
)

# 模型预测
y_pred = model.predict(dtest)

# 准确率评估
accuracy = accuracy_score(Y_test, y_pred)

# 混淆矩阵
cm = confusion_matrix(Y_test, y_pred)

reference

精通梯度提升算法