DataWhale集成学习【中】：（三）Boosting

本文主要是介绍DataWhale集成学习【中】：（三）Boosting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这篇博文是 DataWhale集成学习【中】 的第二部分，主要是介绍Boosting的思想原理以及其衍生的各种算法
参考资料为DataWhale开源项目：机器学习集成学习与模型融合(基于python)和scikit-learn官网
学习交流欢迎联系 obito0401@163.com

文章目录

Boosting
- 原理
- 分类
- - AdaBoost
  - - 原理
    - 方法
    - 示例
  - 前向分步算法
  - 梯度提升决策树（GBDT）
  - XGBoost
  - - 原理
    - 方法
    - 示例

Boosting

原理

前面曾经提到过 Bagging 方法的实质是：通过 Bootstrap 的方式对全样本数据集进行抽样得到抽样子集，对不同的子集使用同一种基本模型进行拟合，然后均权投票得出最终的预测结果，也自然地知道 Bagging 是通过降低方差的方式减少预测误差的
与 Bagging 不同，Boosting方法是使用同一组数据进行反复学习，得到一系列简单模型，然后将这些模型组合起来加权投票构成一个预测性能强大的机器学习模型，也自然地知道 Boosting 是通过降低偏差的方式减少预测误差的

–	Bagging	Boosting
样本选择	训练集是从原始数据集有放回抽取的，训练集之间相互独立	训练集不发生变化，只是训练集中的每个样本的权重会根据上一轮的分类结果调整权重
样本权重	均匀抽样，每个样本权重相等	根据错误率不断调整样本的权值，错误率越高则权重越大
预测函数	所有分类器权重相等	分类器的权重会和其分类误差的大小呈反向关系
计算方式	并行计算	串行计算

分类

前文原理介绍部分提到，Boosting 算法有两个问题：（一）如何整样本的权值（二）如何调整分类器的权值，对这两个问题的不同解决方式，就形成了 Boosting 的各个算法分支。

AdaBoost

原理

AdaBoost（Adaptive Boosting，自适应提升）算法是经典的 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}=\{-1,+1\}$ ， $\mathcal{X}$ 是特征空间，
$\mathcal{Y}$ 是类别集合，输出最终分类器 $G (x)$ 。

Adaboost算法流程如下：

初始化训练数据的分布： $D_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right), \quad w_{1 i}=\frac{1}{N}, \quad i=1,2, \cdots, N$
对于m=1,2,…,M
- 使用具有权值分布 $D_m$ 的训练数据集进行学习，得到基本分类器： $G_{m}(x): \mathcal{X} \rightarrow\{-1,+1\}$
- 计算 $G_m(x)$ 在训练集上的分类误差率 $e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{m i} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)$
- 计算 $G_m(x)$ 的系数 $\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}$ ，这里的log是自然对数ln
- 更新训练数据集的权重分布
  $\begin{array}{c} D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right) \\ w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2, \cdots, N \end{array}$
  这里的 $Z_m$ 是规范化因子，使得 $D_{m+1}$ 称为概率分布， $Z_{m}=\sum_{i=1}^{N} w_{m i} \exp\left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right)$
构建基本分类器的线性组合 $f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)$ ，得到最终的分类器
$\begin{aligned} G(x) &=\operatorname{sign}(f(x)) \\ &=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right) \end{aligned}$

说明：

对于步骤1，即假设训练数据的权值分布是均匀分布，以使在第一次没有先验信息的条件下保证每个样本在基分类器的学习中作用一样
对于步骤2，引入分类错误率 $e_{m}$ 代表了基分类器 $G_{m}(x)$ 中分类错误的样本权重和，引入系数 $\alpha_{m}$ 代表了分类器 $G_{m}(x)$ 在最终分类器中的比重，最重要的引入样本权重更新公式：
$w_{m+1, i}=\left\{\begin{array}{ll} \frac{w_{m i}}{Z_{m}} \mathrm{e}^{-\alpha_{m}}, & G_{m}\left(x_{i}\right)=y_{i} \\ \frac{w_{m i}}{Z_{m}} \mathrm{e}^{\alpha_{m}}, & G_{m}\left(x_{i}\right) \neq y_{i} \end{array}\right.$
可以看出：被基本分类器 $G_m(x)$ 错误分类的样本的权重扩大，被正确分类的样本权重减少，二者相比相差 $\mathrm{e}^{2 \alpha_{m}}=\frac{1-e_{m}}{e_{m}}$ 倍
对于步骤3，线性组合 $f (x)$ 实现了将 $m$ 个基本分类器的加权表决，系数 $\alpha_{m}$ 代表了基本分类器 $G_{m}(x)$ 的重要性，注：所有的 $\alpha_{m}$ 之和不为1， $f (x)$ 的符号决定了样本 $x$ 属于哪一类

示例

以UCI的机器学习库里开源数据集：葡萄酒数据集作为示例数据集（https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data ）
该数据集包含178个样本和13个特征，从不同的角度对不同的化学特性进行描述
任务：根据这些数据预测红酒属于哪一个类别

# 引入函数库
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
plt.style.use("ggplot") # 用ggplot样式绘图
import seaborn as sns

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"# 加载数据集
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']
wine.shape # 数据集大小
wine["Class label"].value_counts() # 标签类别及数量
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	稀释酒OD280 OD350
Proline	脯氨酸

在这里插入图片描述

# 数据预处理
## 作为示例，仅考虑2,3类葡萄酒
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)## 按82法则划分训练集和测试集
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=911,stratify=y)
## stratify参数表示按照y的类别等比例抽样

附：Label Encoder vs. One Hot Encoder in Machine Learning

# 使用单一决策树建模
from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(criterion="gini",random_state=911,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))

在这里插入图片描述

# 使用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=911)
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的决策边界：
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=14)
plt.tight_layout()
plt.text(x=0,y=-0.2,s='OD280/OD315 of diluted wines',ha="center",va="center",fontsize=14,transform=axarr[1].transAxes)
plt.show()

在这里插入图片描述

可以看出，Adaboost模型的决策边界比单棵决策树复杂的多，也就是说，其是通过提升模型复杂度从而降低偏差的方式去减少总误差
但是，在这个过程中也会使得方差变大，可能会出现过拟合的情况，这也正是为什么adaboost模型在训练集和测试集上的表现差异较大的原因
因此，在实践中要谨慎考虑是否需要为预测性能的相对改善而增加计算成本，而且 boosting 的一个较大缺陷在于其使用的是迭代算法，因此无法做到并行计算

前向分步算法

Adaboost 算法是前向分步算法的特例：其是由基本分类器组成的加法模型，损失函数为指数损失函数

加法模型：
- 在Adaboost模型中，我们把每个基本分类器集成为一个复杂分类器的方法是每个分类器的加权和，即 $f(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)$ 。其中， $b\left(x ; \gamma_{m}\right)$ 为即基本分类器， $\gamma_{m}$ 为基本分类器的参数， $\beta_m$ 为基本分类器的权重
- 在给定训练数据以及损失函数 $L (y, f (x))$ 的条件下，学习加法模型 $f (x)$ 就是：
  $\min _{\beta_{m}, \gamma_{m}} \sum_{i=1}^{N} L\left(y_{i}, \sum_{m=1}^{M} \beta_{m} b\left(x_{i} ; \gamma_{m}\right)\right)$
- 通常这是一个复杂的优化问题，很难通过简单的凸优化的相关知识进行解决。而前向分步算法正是为解决这一问题产生的
前向分步算法：
- 基本思路：因为学习的是加法模型，那么则可以从前向后依次优化每个基函数及其系数，逐步逼近目标函数，就可以降低该优化问题求解的复杂度，即每一步只需优化：
  $\min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right)$
- 完整流程：给定数据集 $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}=\{+1,-1\}$ 。损失函数 $L (y, f (x))$ ，基函数集合 $\{b(x ; \gamma)\}$ ，我们需要输出加法模型 $f (x)$
  1. 初始化： $f_{0}(x)=0$
  2. 对m = 1,2,…,M:
    - 极小化损失函数
      $\left(\beta_{m}, \gamma_{m}\right)=\arg \min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right)$
      得到参数 $\beta_{m}$ 与 $\gamma_{m}$
    - 更新
      $f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right)$
  3. 得到加法模型：
    $f(x)=f_{M}(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)$

附：集成学习系列(四)-AdaBoost与前向分步算法

梯度提升决策树（GBDT）

因个人时间原因，这部分先挖个坑，等这周结束后填完

XGBoost

原理

XGBoost是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进，被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并且成绩不斐
XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致，所以叫X (Extreme) GBoosted
XGBoost是一个优化的分布式梯度增强库，旨在实现高效，灵活和便携。它在Gradient Boosting框架下实现机器学习算法。 XGBoost提供了并行树提升（也称为GBDT，GBM），可以快速准确地解决许多数据科学问题。相同的代码在主要的**分布式环境（Hadoop，SGE，MPI）**上运行，并且可以解决超过数十亿个样例的问题
XGBoost利用了核外计算并且能够让使用者在一个主机上处理数亿的样本数据。最终，将这些技术进行结合来做一个端到端的系统以最少的集群系统来扩展到更大的数据集上
XGBoost以CART决策树为子模型，通过Gradient Tree Boosting实现多棵CART树的集成学习，得到最终模型

方法

假设数据为 $\mathcal{D}=\left\{\left(\mathbf{x}_{i}, y_{i}\right)\right\}\left(|\mathcal{D}|=n, \mathbf{x}_{i} \in \mathbb{R}^{m}, y_{i} \in \mathbb{R}\right)$

构造目标函数
假设有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}$ ，其中， $\mathcal{F}=\left\{f(\mathbf{x})=w_{q(\mathbf{x})}\right\}\left(q: \mathbb{R}^{m} \rightarrow T, w \in \mathbb{R}^{T}\right)$
因此，目标函数的构建为：
$\mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right)$
其中， $\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)$ 为loss function， $\sum_{k} \Omega\left(f_{k}\right)$ 为正则化项。
叠加式的训练(Additive Training)：
给定样本 $x_i$ ， $\hat{y}_i^{(0)} = 0$ (初始预测)， $\hat{y}_i^{(1)} = \hat{y}_i^{(0)} + f_1(x_i)$ ， $\hat{y}_i^{(2)} = \hat{y}_i^{(0)} + f_1(x_i) + f_2(x_i) = \hat{y}_i^{(1)} + f_2(x_i)$ …以此类推，可以得到： $\hat{y}_i^{(K)} = \hat{y}_i^{(K-1)} + f_K(x_i)$ ，其中， $\hat{y}_i^{(K-1)}$ 为前K-1棵树的预测结果， $f_K(x_i)$ 为第K棵树的预测结果。
因此，目标函数可以分解为：
$\mathcal{L}^{(K)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(K-1)}+f_{K}\left(\mathrm{x}_{i}\right)\right)+\sum_{k} \Omega\left(f_{k}\right)$
由于正则化项也可以分解为前K-1棵树的复杂度加第K棵树的复杂度，因此： $\mathcal{L}^{(K)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(K-1)}+f_{K}\left(\mathrm{x}_{i}\right)\right)+\sum_{k=1} ^{K-1}\Omega\left(f_{k}\right)+\Omega\left(f_{K}\right)$ ，由于 $\sum_{k=1} ^{K-1}\Omega\left(f_{k}\right)$ 在模型构建到第K棵树的时候已经固定，无法改变，因此是一个已知的常数，可以在最优化的时候省去，故：
$\mathcal{L}^{(K)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(K-1)}+f_{K}\left(\mathrm{x}_{i}\right)\right)+\Omega\left(f_{K}\right)$
使用泰勒级数近似目标函数：
$\mathcal{L}^{(K)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(K-1)}\right)+g_{i} f_{K}\left(\mathrm{x}_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(\mathrm{x}_{i}\right)\right]+\Omega\left(f_{K}\right)$
其中， $g_{i}=\partial_{\hat{y}(t-1)} l\left(y_{i}, \hat{y}^{(t-1)}\right)$ 和 $h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right)$
如何定义一棵树：
为了说明如何定义一棵树的问题，我们需要定义几个概念：
- 概念是样本所在的节点位置 $q (x)$
- 概念是有哪些样本落在节点j上 $I_{j}=\left\{i \mid q\left(\mathbf{x}_{i}\right)=j\right\}$
- 每个结点的预测值 $w_{q(x)}$
- 模型复杂度 $\Omega\left(f_{K}\right)$ ，它可以由叶子节点的个数以及节点函数值来构建，则： $\Omega\left(f_{K}\right) = \gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}$
如下图所示：

$q(x_1) = 1,q(x_2) = 3,q(x_3) = 1,q(x_4) = 2,q(x_5) = 3$ ， $I_1 = \{1,3\},I_2 = \{4\},I_3 = \{2,5\}$ ， $w = (15, 12, 20)$
因此，目标函数用以上符号替代后：
$\begin{aligned} \tilde{\mathcal{L}}^{(K)} &=\sum_{i=1}^{n}\left[g_{i} f_{K}\left(\mathrm{x}_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(\mathrm{x}_{i}\right)\right]+\gamma T+\frac{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}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned}$
由于我们的目标就是最小化目标函数，现在的目标函数化简为一个关于w的二次函数： $\tilde{\mathcal{L}}^{(K)}=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T$ ，根据二次函数求极值的公式： $y=ax^2 bx c$ 求极值，对称轴在 $x=-\frac{b}{2 a}$ ，极值为 $y=\frac{4 a c-b^{2}}{4 a}$ ，因此：
$w_{j}^{*}=-\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda}$
以及
$\tilde{\mathcal{L}}^{(K)}(q)=-\frac{1}{2} \sum_{j=1}^{T} \frac{\left(\sum_{i \in I_{j}} g_{i}\right)^{2}}{\sum_{i \in I_{j}} h_{i}+\lambda}+\gamma T$
如何寻找树的形状：
不难发现，刚刚的讨论都是基于树的形状已经确定了计算 $w$ 和 $L$ ，但是实际上我们需要像学习决策树一样找到树的形状。因此，我们借助决策树学习的方式，使用目标函数的变化来作为分裂节点的标准。我们使用一个例子来说明：

例子中有8个样本，分裂方式如下，因此:
$\tilde{\mathcal{L}}^{(old)} = -\frac{1}{2}[\frac{(g_7 + g_8)^2}{H_7+H_8 + \lambda} + \frac{(g_1 +...+ g_6)^2}{H_1+...+H_6 + \lambda}] + 2\gamma \\ \tilde{\mathcal{L}}^{(new)} = -\frac{1}{2}[\frac{(g_7 + g_8)^2}{H_7+H_8 + \lambda} + \frac{(g_1 +...+ g_3)^2}{H_1+...+H_3 + \lambda} + \frac{(g_4 +...+ g_6)^2}{H_4+...+H_6 + \lambda}] + 3\gamma\\ \tilde{\mathcal{L}}^{(old)} - \tilde{\mathcal{L}}^{(new)} = \frac{1}{2}[ \frac{(g_1 +...+ g_3)^2}{H_1+...+H_3 + \lambda} + \frac{(g_4 +...+ g_6)^2}{H_4+...+H_6 + \lambda} - \frac{(g_1+...+g_6)^2}{h_1+...+h_6+\lambda}] - \gamma$
因此，从上面的例子看出：分割节点的标准为 $max\{\tilde{\mathcal{L}}^{(old)} - \tilde{\mathcal{L}}^{(new)} \}$ ，即：
$\mathcal{L}_{\text {split }}=\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}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma$
6. 选取最优特征和最优切分点
XGBoost在生成新树的过程中，最基本的操作是节点分裂。节点分裂中最重要的环节是找到最优特征及最优切分点, 然后将叶子节点按照最优特征和最优切分点进行分裂

方法一：精确贪心分裂算法
1. 首先找到所有的候选特征及所有的候选切分点, 一一求得其 $\mathcal{L}_{\text {split }}$
2. 然后选择 $\mathcal{L}_{\mathrm{split}}$ 最大的特征及对应切分点作为最优特征和最优切分点
在这里插入图片描述
方法二：基于直方图的近似算法

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

对于每个特征 $\cdots, m,$ 按分位数对特征 $k$ 分桶 $\Theta,$ 可得候选切分点, $S_{k}=\left\{S_{k 1}, S_{k 2}, \cdots, S_{k l}\right\}^{1}$
对于每个特征 $\cdots, m,$ 有：
$\begin{array}{l} G_{k v} \leftarrow=\sum_{j \in\left\{j \mid s_{k, v} \geq \mathbf{x}_{j k}>s_{k, v-1\;}\right\}} g_{j} \\ H_{k v} \leftarrow=\sum_{j \in\left\{j \mid s_{k, v} \geq \mathbf{x}_{j k}>s_{k, v-1\;}\right\}} h_{j} \end{array}$

方法三：类似精确贪心算法

主要思想：依据梯度统计找到最大增益的候选切分点
计算过程：
假设有一个年龄特征，其特征的取值为18、19、21、31、36、37、55、57，我们需要使用近似算法找到年龄这个特征的最佳分裂点：

小结：

近似算法实现了两种候选切分点的构建策略：全局策略和本地策略
- 全局策略是在树构建的初始阶段对每一个特征确定一个候选切分点的集合, 并在该树每一层的节点分裂中均采用此集合计算收益, 整个过程候选切分点集合不改变
- 本地策略则是在每一次节点分裂时均重新确定候选切分点
全局策略需要更细的分桶才能达到本地策略的精确度, 但全局策略在选取候选切分点集合时比本地策略更简单
在XGBoost系统中, 用户可以根据需求自由选择使用精确贪心算法、近似算法全局策略、近似算法本地策略, 算法均可通过参数进行配置