机器学习之梯度提升树

目录

1. 简介
2. 数学基础
3. 算法原理
4. 算法流程
5. 损失函数
6. 正则化策略
7. 主流实现
8. 优缺点分析
9. 应用场景
10. 超参数调优
11. 实践建议

---

简介

梯度提升树（Gradient Boosting Decision Tree，GBDT）是一种基于集成学习的机器学习算法，属于Boosting算法家族。该算法通过迭代地训练一系列弱学习器（通常是决策树），每个新学习器都致力于修正前一个学习器的预测误差，最终将所有弱学习器组合成一个强学习器。

发展历史

• 1999年：Friedman提出了Gradient Boosting Machine（GBM）框架
• 2001年：Friedman在论文"Greedy Function Approximation: A Gradient Boosting Machine"中系统阐述了梯度提升算法
• 2014年：Tianqi Chen开发了XGBoost，大幅提升了GBDT的性能
• 2017年：微软推出了LightGBM，进一步优化了训练速度和内存使用
• 2018年：Yandex发布了CatBoost，专注于处理类别特征

核心思想

梯度提升树的核心思想是：将最速下降法（梯度下降）应用于函数空间。在每次迭代中，算法通过拟合负梯度来逐步逼近目标函数，从而最小化损失函数。

---

数学基础

1. 前向分步算法

给定训练数据集 $D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)\}$，其中 $x_i\in \mathcal{X}\subseteq {\mathbb{R}}^d$，$y_i\in \mathcal{Y}$。

我们的目标是学习一个函数 $F(x)$ 来最小化损失函数 $L(y,F(x))$：

$$F^{\ast }(x)=\arg \underset{F}{\min }{\mathbb{E}}_{y|x}[L(y,F(x))]$$

在梯度提升中，我们将模型表示为基学习器的加法模型：

$$F(x)=\sum _{m=1}^M{f}_m(x)$$

其中 $f_m(x)$ 是第 $m$ 个基学习器（决策树）。

2. 梯度下降在函数空间

传统梯度下降在参数空间中更新参数：

$${\theta }_{t+1}={\theta }_t-\eta {\nabla }_{\theta }L(\theta )$$

而梯度提升在函数空间中更新函数：

$$F_m(x)=F_{m-1}(x)+\eta \cdot f_m(x)$$

其中 $f_m(x)$ 是沿着损失函数负梯度方向的学习器：

$$f_m(x)\approx -{\nabla }_{F_{m-1}}L(y,F_{m-1}(x))$$

3. 拟合负梯度

对于第 $m$ 次迭代，我们需要找到一个新的基学习器 $f_m(x)$ 来拟合负梯度：

$$r_{im}=-{\left[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}\right]}_{F(x)=F_{m-1}(x)}$$

其中 $r_{im}$ 称为伪残差（pseudo-residual）。

---

算法原理

梯度提升树的核心机制

1. 初始化：用一个常数预测值初始化模型
2. 迭代训练：在每轮迭代中
   • 计算当前模型的负梯度（伪残差）
   • 用决策树拟合伪残差
   • 通过线搜索确定学习率
   • 更新模型
3. 输出：最终模型是所有基学习器的加权和

为什么有效？

• 贪心优化：每一步都朝着损失函数下降最快的方向前进
• 误差修正：每个新树专门学习前一个模型的残差
• 组合效应：多个弱学习器组合形成强学习器

---

算法流程

标准梯度提升算法

输入：训练数据 $D=\{(x_i,y_i){\}}_{i=1}^n$，损失函数 $L(y,F(x))$，迭代次数 $M$

输出：梯度提升模型 $F(x)$

算法：梯度提升算法

1. 初始化：

   $$F_0(x)=\arg \underset{\gamma }{\min }\sum _{i=1}^{n}L(y_i,\gamma )$$

2. 对于 $m=1,2,\dots ,M$ ：

   a) 计算负梯度（伪残差）：

   $$r_{im}=-{\left[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}\right]}_{F(x)=F_{m-1}(x)},\text{对于 }i=1,2,\dots ,n$$

   b) 用决策树拟合伪残差，得到叶节点区域 $R_{jm}$，$j=1,2,\dots ,J_m$

   c) 对于每个叶节点 $j$，计算最优输出值：

   $${\gamma }_{jm}=\arg \underset{\gamma }{\min }\sum _{x_i\in R_{jm}}L(y_i,F_{m-1}(x_i)+\gamma )$$

   d) 更新模型：

   $$F_m(x)=F_{m-1}(x)+\nu \sum _{j=1}^{J_m}{\gamma }_{jm}\mathbb{I}(x\in R_{jm})$$

   其中 $\nu$ 是学习率

3. 输出最终模型：

   $$\hat{F}(x)=F_M(x)=\sum _{m=1}^M\nu f_m(x)$$

关键步骤说明

步骤1：初始化

对于平方损失函数 $L(y,F(x))=\frac{1}{2}(y-F(x){)}^2$：

$$F_0(x)=\frac{1}{n}\sum _{i=1}^n{y}_i=\bar{y}$$

对于对数损失函数（分类问题）：

$$F_0(x)=\log \left(\frac{{\sum }_{i=1}^n{y}_i}{{\sum }_{i=1}^n(1-y_i)}\right)=\log \left(\frac{\sum y_i}{n-\sum y_i}\right)$$

步骤2a：计算伪残差

对于平方损失：

$$r_{im}=y_i-F_{m-1}(x_i)$$

对于对数损失（二分类）：

$$r_{im}=y_i-\sigma (F_{m-1}(x_i))$$

其中 $\sigma (z)=\frac{1}{1+e^{-z}}$ 是sigmoid函数。

步骤2c：计算叶节点值

对于平方损失，叶节点的最优值是该区域伪残差的平均值：

$${\gamma }_{jm}=\frac{{\sum }_{x_i\in R_{jm}}{r}_{im}}{|R_{jm}|}$$

---

损失函数

1. 回归问题

平方损失（MSE）

$$L(y,F(x))=\frac{1}{2}(y-F(x){)}^2$$

负梯度：
$$-\frac{\partial L}{\partial F(x)}=y-F(x)$$

绝对损失（MAE）

$$L(y,F(x))=|y-F(x)|$$

负梯度：
$$-\frac{\partial L}{\partial F(x)}=\text{sign}(y-F(x))$$

Huber损失

结合了MSE和MAE的优点，对异常值更鲁棒：

$$L_{\delta }(y,F(x))=\{\begin{array}{ll}\frac{1}{2}(y-F(x){)}^2& \text{if }|y-F(x)|\le \delta \\ \delta (|y-F(x)|-\frac{1}{2}\delta )& \text{otherwise}\end{array}$$

2. 分类问题

二分类：对数损失

$$L(y,F(x))=-[y\log (p(x))+(1-y)\log (1-p(x))]$$

其中 $p(x)=\frac{1}{1+e^{-F(x)}}$

负梯度：
$$-\frac{\partial L}{\partial F(x)}=y-p(x)$$

多分类：对数损失

对于 $K$ 类分类问题，模型输出 $K$ 个函数 $F_k(x)$：

$$L(y,F(x))=-\sum _{k=1}^{K}I(y=k)\log \left(\frac{e^{F_k(x)}}{{\sum }_{j=1}^K{e}^{F_j(x)}}\right)$$

负梯度：
$$-\frac{\partial L}{\partial F_k(x)}=I(y=k)-p_k(x)$$

其中 $p_k(x)=\frac{e^{F_k(x)}}{{\sum }_{j=1}^K{e}^{F_j(x)}}$

---

正则化策略

1. 学习率（Shrinkage）

学习率 $\nu \in (0,1]$ 控制每个基学习器的贡献：

$$F_m(x)=F_{m-1}(x)+\nu \cdot f_m(x)$$

较小的学习率需要更多的迭代次数，但通常能获得更好的泛化性能。

经验法则：$\nu =0.01$ 到 $0.1$ 之间，同时增加迭代次数 $M$。

2. 子采样（Stochastic Gradient Boosting）

在每轮迭代中，随机抽取一部分样本（如50%-80%）来训练基学习器：

• 减少过拟合
• 提高训练速度
• 增加模型多样性

3. 树的深度限制

限制决策树的最大深度 $d$：

• 较浅的树（如3-6层）作为弱学习器
• 防止过拟合
• 提高泛化能力

4. 叶节点最小样本数

限制每个叶节点所需的最小样本数，防止过细的划分。

5. L1和L2正则化

在损失函数中添加正则项：

$$L_{\text{reg}}=L(y,F(x))+\Omega (F)$$

其中：

• L1正则：$\Omega (F)=\lambda \sum |w_j|$
• L2正则：$\Omega (F)=\frac{1}{2}\lambda \sum w_j^2$

---

主流实现

1. XGBoost

特点：

• 二阶泰勒展开近似损失函数
• 正则化项控制模型复杂度
• 列块并行处理
• 稀疏感知算法
• 缓存优化

目标函数：

$$\mathcal{L}(\varphi )=\sum _{i}l(y_i,{\hat{y}}_i)+\sum _k\Omega (f_k)$$

其中 $\Omega (f)=\gamma T+\frac{1}{2}\lambda \Vert w{\Vert }^2$

分裂准则：

$${\mathcal{L}}_{\text{split}}=\frac{1}{2}\left[\frac{({\sum }_{I_L}{g}_i{)}^2}{{\sum }_{I_L}{h}_i+\lambda }+\frac{({\sum }_{I_R}{g}_i{)}^2}{{\sum }_{I_R}{h}_i+\lambda }-\frac{({\sum }_I{g}_i{)}^2}{{\sum }_I{h}_i+\lambda }\right]-\gamma$$

其中 $g_i={\partial }_{{\hat{y}}^{(t-1)}}l(y_i,{\hat{y}}^{(t-1)})$，$h_i={\partial }_{{\hat{y}}^{(t-1)}}^{2}l(y_i,{\hat{y}}^{(t-1)})$

2. LightGBM

特点：

• 基于直方图的算法
• GOSS（Gradient-based One-Side Sampling）：保留大梯度样本，随机采样小梯度样本
• EFB（Exclusive Feature Bundling）：将互斥特征捆绑
• Leaf-wise生长策略：优先选择增益最大的叶节点分裂
• 支持类别特征

GOSS算法：

1. 根据梯度的绝对值对样本排序
2. 保留前 $a\times 100\%$ 的大梯度样本
3. 从剩余样本中随机采样 $b\times 100\%$ 的样本
4. 对小梯度样本乘以常数 $(1-a)/b$ 进行补偿

3. CatBoost

特点：

• 处理类别特征的创新方法（Ordered Target Statistics）
• Ordered Boosting：减少预测偏移
• 对称树结构
• 自动处理缺失值
• GPU加速

Ordered Target Statistics：

对于类别特征 $x^j$ 的值 $x_k^j$，计算：

$${\hat{x}}_k^j=\frac{{\sum }_{i=1}^{p-1}1(x_i^j=x_k^j)\cdot Y_i+a\cdot \text{prior}}{{\sum }_{i=1}^{p-1}1(x_i^j=x_k^j)+a}$$

其中 $p$ 是样本的随机排列顺序。

4. 实现对比

特性	XGBoost	LightGBM	CatBoost
训练速度	快	最快	中等
内存使用	中等	低	较高
类别特征	需编码	需编码	原生支持
缺失值	自动处理	自动处理	自动处理
GPU支持	支持	支持	支持
解释性	好	好	好

---

优缺点分析

优点

1. 高预测精度：在结构化数据上表现优异
2. 灵活性：支持多种损失函数（回归、分类、排序）
3. 特征重要性：天然提供特征重要性评估
4. 鲁棒性：对异常值和噪声有较好的容忍度
5. 可解释性：相比深度学习更易解释
6. 无需特征缩放：对特征尺度不敏感
7. 处理混合数据：可同时处理数值和类别特征（尤其是CatBoost）

缺点

1. 训练时间长：相比单模型，需要更多计算资源
2. 调参复杂：超参数较多，需要经验调优
3. 对噪声敏感：标签噪声可能影响性能
4. 难以并行：串行训练特性限制了并行化程度
5. 过拟合风险：在数据量小或迭代次数过多时容易过拟合
6. 内存消耗：需要存储所有基学习器

---

应用场景

1. 推荐系统

• 点击率预测（CTR）
• 转化率预测
• 个性化推荐排序

2. 金融风控

• 信用评分
• 欺诈检测
• 违约预测

3. 搜索引擎

• 学习排序（Learning to Rank）
• 查询相关性预测
• 广告排序

4. 工业应用

• 质量检测
• 预测性维护
• 异常检测

5. 医疗健康

• 疾病诊断
• 风险评估
• 药物反应预测

---

超参数调优

核心超参数

1. 树相关参数

参数	说明	典型范围
max_depth	树的最大深度	3-10
min_child_weight	叶节点最小权重和	1-10
min_samples_leaf	叶节点最小样本数	1-50
max_leaves	最大叶节点数	0-256

2. Boosting参数

参数	说明	典型范围
learning_rate	学习率	0.01-0.3
n_estimators	基学习器数量	100-10000
subsample	样本采样比例	0.5-1.0
colsample_bytree	特征采样比例	0.5-1.0

3. 正则化参数

参数	说明	典型范围
reg_alpha	L1正则系数	0-10
reg_lambda	L2正则系数	0-10
gamma	最小分裂增益	0-10

调参策略

策略1：逐步调参法

1. 固定学习率：设置较大的学习率（如0.1）和足够的迭代次数
2. 调优树参数：先调max_depth，再调min_child_weight
3. 调优采样参数：调整subsample和colsample_bytree
4. 调优正则化：添加reg_alpha和reg_lambda
5. 降低学习率：减小学习率，增加迭代次数

策略2：网格搜索

from sklearn.model_selection import GridSearchCV

param_grid = {
    'max_depth': [3, 5, 7],
    'learning_rate': [0.01, 0.1, 0.2],
    'n_estimators': [100, 500, 1000],
    'subsample': [0.8, 1.0]
}

grid_search = GridSearchCV(xgb_model, param_grid, cv=5)
grid_search.fit(X_train, y_train)

策略3：随机搜索

from sklearn.model_selection import RandomizedSearchCV
from scipy.stats import uniform, randint

param_dist = {
    'max_depth': randint(3, 10),
    'learning_rate': uniform(0.01, 0.3),
    'n_estimators': randint(100, 2000),
    'subsample': uniform(0.6, 0.4)
}

random_search = RandomizedSearchCV(xgb_model, param_dist, n_iter=50, cv=5)
random_search.fit(X_train, y_train)

策略4：贝叶斯优化

使用optuna、hyperopt等库进行更高效的超参数搜索。

---

实践建议

1. 数据预处理

特征工程

• 数值特征：标准化/归一化（虽然GBDT对尺度不敏感，但有助于正则化）
• 类别特征：
  • Label Encoding（树模型友好）
  • Target Encoding（需注意目标泄露）
  • One-Hot Encoding（基数低时使用）
• 缺失值处理：GBDT可自动处理，但也可填充为均值/中位数/众数

特征选择

• 基于特征重要性筛选
• 去除高相关性特征
• 移除常数特征

2. 防止过拟合

• 使用验证集监控性能
• 早停法（Early Stopping）
• 交叉验证
• 增加正则化强度
• 减小树深度
• 增加学习率并增加迭代次数

3. 评估指标

回归问题

• MSE、RMSE
• MAE、MAPE
• R²

分类问题

• Accuracy、Precision、Recall、F1
• AUC-ROC、AUC-PR
• LogLoss

4. 代码示例

XGBoost示例

import xgboost as xgb
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 数据准备
X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.2, random_state=42)

# 创建DMatrix
dtrain = xgb.DMatrix(X_train, label=y_train)
dval = xgb.DMatrix(X_val, label=y_val)

# 参数设置
params = {
    'objective': 'binary:logistic',
    'max_depth': 6,
    'learning_rate': 0.1,
    'subsample': 0.8,
    'colsample_bytree': 0.8,
    'eval_metric': 'logloss',
    'seed': 42
}

# 训练模型
evals_result = {}
model = xgb.train(
    params,
    dtrain,
    num_boost_round=1000,
    evals=[(dtrain, 'train'), (dval, 'val')],
    early_stopping_rounds=50,
    evals_result=evals_result,
    verbose_eval=100
)

# 预测
dtest = xgb.DMatrix(X_test)
y_pred = model.predict(dtest)
y_pred_class = (y_pred > 0.5).astype(int)

# 评估
accuracy = accuracy_score(y_test, y_pred_class)
print(f'Accuracy: {accuracy:.4f}')

# 特征重要性
xgb.plot_importance(model)

LightGBM示例

import lightgbm as lgb
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error

# 数据准备
X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.2, random_state=42)

# 创建Dataset
train_data = lgb.Dataset(X_train, label=y_train)
val_data = lgb.Dataset(X_val, label=y_val, reference=train_data)

# 参数设置
params = {
    'objective': 'regression',
    'metric': 'rmse',
    'max_depth': -1,
    'num_leaves': 31,
    'learning_rate': 0.05,
    'feature_fraction': 0.8,
    'bagging_fraction': 0.8,
    'bagging_freq': 5,
    'verbose': -1
}

# 训练模型
model = lgb.train(
    params,
    train_data,
    num_boost_round=10000,
    valid_sets=[train_data, val_data],
    callbacks=[
        lgb.early_stopping(stopping_rounds=100),
        lgb.log_evaluation(100)
    ]
)

# 预测
y_pred = model.predict(X_test, num_iteration=model.best_iteration)
rmse = mean_squared_error(y_test, y_pred, squared=False)
print(f'RMSE: {rmse:.4f}')

# 特征重要性
lgb.plot_importance(model)

CatBoost示例

from catboost import CatBoostClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import roc_auc_score

# 数据准备
X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.2, random_state=42)

# 指定类别特征索引
cat_features = [0, 2, 5]  # 示例

# 创建模型
model = CatBoostClassifier(
    iterations=1000,
    learning_rate=0.1,
    depth=6,
    loss_function='Logloss',
    eval_metric='AUC',
    random_seed=42,
    od_type='Iter',
    od_wait=50,
    verbose=100
)

# 训练模型
model.fit(
    X_train, y_train,
    cat_features=cat_features,
    eval_set=(X_val, y_val),
    use_best_model=True,
    plot=True
)

# 预测
y_pred = model.predict_proba(X_test)[:, 1]
auc = roc_auc_score(y_test, y_pred)
print(f'AUC: {auc:.4f}')

# 特征重要性
model.get_feature_importance()

5. 模型解释

SHAP值

import shap

# 创建解释器
explainer = shap.TreeExplainer(model)
shap_values = explainer.shap_values(X_test)

# 可视化
shap.summary_plot(shap_values, X_test)
shap.dependence_plot('feature_name', shap_values, X_test)

特征重要性

• Gain：特征带来的分裂增益总和
• Cover：特征被用于分裂的样本数
• Frequency：特征被用于分裂的次数

---

总结

梯度提升树是机器学习中最强大的算法之一，特别适用于结构化数据。通过理解其数学原理、掌握调参技巧、合理使用各种实现框架，可以在实际项目中获得优异的性能。

关键要点

1. 理解原理：梯度提升是梯度下降在函数空间的应用
2. 合理调参：学习率、树深度、迭代次数是核心参数
3. 防止过拟合：使用早停、交叉验证、正则化
4. 选择框架：XGBoost通用性强，LightGBM速度快，CatBoost擅长类别特征
5. 模型解释：使用SHAP等工具增强可解释性