目录
模型公式
XGBoost 在集成学习中占有重要的地位,其具有理论的完备性和在比赛中的实用性:
- XGBoost 的本质属于加法模型,其基函数为回归决策树;
- XGBoost 的目标函数为损失函数+正则化项,且损失函数使用了二阶泰勒展开;
- XGBoost 使用前向分步算法,通过最小化目标函数来进行模型的优化与学习。
XGBoost 的模型预测值是由
M
M
M 个基函数的预测值累加得到的:
y
^
i
=
∑
t
=
1
M
f
t
(
x
i
)
\widehat{y}_{i}=\sum_{t=1}^{M}f_{t}(x_{i})
y
i=t=1∑Mft(xi)
这里的基函数
f
(
x
)
f(x)
f(x) 为 CART 算法(回顾第二十课)中的回归树:
f
(
x
i
)
=
w
q
(
x
i
)
=
w
j
f(x_{i})=w_{q(x_{i})}=w_{j}
f(xi)=wq(xi)=wj
其中,
w
w
w 为叶子结点向量,
j
j
j 为叶子结点索引,如下所示:
w
=
[
w
1
,
w
2
,
.
.
.
,
w
j
,
.
.
.
,
w
T
]
w=[w_{1},w_{2},...,w_{j},...,w_{T}]
w=[w1,w2,...,wj,...,wT]
函数
q
(
x
)
q(x)
q(x) 是由回归决策树的结构所决定的,通过
q
(
x
)
q(x)
q(x) 可以得到输入特征向量
x
i
x_{i}
xi 所属的叶子结点索引
j
j
j;根据叶子结点索引
j
j
j 可以得到回归树的预测值
w
j
w_{j}
wj ,如图所示:
图中的回归树有 4 个叶子结点,样本
x
i
x_{i}
xi 被划分到了 3 号叶子结点,对应的预测值为 0.8
优化算法
XGBoost 属于加法模型,使用前向分步算法进行迭代优化的过程如下:
输入:训练集 T T T、目标函数 o b j obj obj
输出: XGBoost 模型
- 1.初始化 XGBoost 模型:
y ^ i ( 0 ) = 0 \widehat{y}_{i}^{(0)}=0 y i(0)=0 - 2.使用前向分步算法迭代 XGBoost (
M
M
M轮),每一轮迭代:先最小化目标函数得到新的回归树,然后累加到上一轮的 XGBoost 上:
- 3.得到 XGBoost 模型:
y ^ i = y ^ i ( M ) = ∑ t = 1 M f t ( x i ) \widehat{y}_{i}=\widehat{y}_{i}^{(M)}=\sum_{t=1}^{M}f_{t}(x_{i}) y i=y i(M)=t=1∑Mft(xi)
目标函数
XGBoost 最小化的目标函数(objective function)定义为损失函数+正则化项:
o
b
j
=
∑
i
=
1
N
L
(
y
i
,
y
^
i
)
+
∑
t
=
1
M
Ω
(
f
t
)
obj=\sum_{i=1}^{N}L(y_{i},\widehat{y}_{i})+\sum_{t=1}^{M}\Omega (f_{t})
obj=i=1∑NL(yi,y
i)+t=1∑MΩ(ft)
正则化项对每棵回归树的复杂度进行了惩罚,最小化上述目标函数意味着:既要最小化训练集的损失,又要保证回归树的结构不能太复杂;
在进行第
t
t
t 次迭代时,前
t
−
1
t-1
t−1 棵回归树的结构是已知的,对应的正则化项为常数。常数不影响最优化模型参数的求解,因此可以直接去掉,此时目标函数的表达式如下:
o
b
j
(
t
)
=
∑
i
=
1
N
L
(
y
i
,
y
^
i
(
t
)
)
+
Ω
(
f
t
)
obj^{(t)}=\sum_{i=1}^{N}L(y_{i},\widehat{y}_{i}^{(t)})+\Omega (f_{t})
obj(t)=i=1∑NL(yi,y
i(t))+Ω(ft)
公式中的正则化项只保留了第
t
t
t 棵树的部分,样本预测值变成了第
t
t
t 次迭代后的模型预测值;
下面,对损失函数的部分进行二阶泰勒展开。因此,先认识一下泰勒公式:
第二行公式中,自变量为
x
x
x ,因变量为
f
(
x
)
f(x)
f(x),二阶泰勒展开是使用
f
(
x
)
f(x)
f(x) 在
x
t
−
1
x^{t-1}
xt−1 处的各阶导数信息来表示它在
x
t
x^{t}
xt 处的取值,
Δ
x
\Delta x
Δx 是一个很小的未知增量;
由于损失函数是一个二元函数,而泰勒公式描述的是一元函数,为了方便理解,将损失函数看作关于模型预测值的一元函数,由此得到新的目标函数:
o
b
j
(
t
)
=
∑
i
=
1
N
L
(
y
^
i
(
t
)
)
+
Ω
(
f
t
)
obj^{(t)}=\sum_{i=1}^{N}L(\widehat{y}_{i}^{(t)})+\Omega (f_{t})
obj(t)=i=1∑NL(y
i(t))+Ω(ft)
根据二阶泰勒展开公式,我们可以得到损失函数部分的二阶泰勒展开形式:
y
^
i
(
t
)
=
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
\widehat{y}_{i}^{(t)}=\widehat{y}_{i}^{(t-1)}+f_{t}(x_{i})
y
i(t)=y
i(t−1)+ft(xi)
L
(
y
^
i
(
t
)
)
≈
L
(
y
^
i
(
t
−
1
)
)
+
L
′
(
y
^
i
(
t
−
1
)
)
f
t
(
x
i
)
+
1
2
L
′
′
(
y
^
i
(
t
−
1
)
)
f
t
2
(
x
i
)
L(\widehat{y}_{i}^{(t)})\approx L(\widehat{y}_{i}^{(t-1)})+L^{'}(\widehat{y}_{i}^{(t-1)})f_{t}(x_{i})+\frac{1}{2}L^{''}(\widehat{y}_{i}^{(t-1)})f_{t}^{2}(x_{i})
L(y
i(t))≈L(y
i(t−1))+L′(y
i(t−1))ft(xi)+21L′′(y
i(t−1))ft2(xi)
将第二行公式中的一阶导数和二阶导数分别表示为
g
i
g_{i}
gi 和
h
i
h_{i}
hi ,则损失函数变为:
L
(
y
^
i
(
t
)
)
≈
L
(
y
^
i
(
t
−
1
)
)
+
g
i
f
t
(
x
i
)
+
1
2
h
i
f
t
2
(
x
i
)
L(\widehat{y}_{i}^{(t)})\approx L(\widehat{y}_{i}^{(t-1)})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})
L(y
i(t))≈L(y
i(t−1))+gift(xi)+21hift2(xi)
t
−
1
t-1
t−1 时 XGBoost 的模型预测值是已知的,因此公式中的第一项为常数。将损失函数的常数项去掉后再带入目标函数,得到:
o
b
j
(
t
)
=
∑
i
=
1
N
[
g
i
f
t
(
x
i
)
+
1
2
h
i
f
t
2
(
x
i
)
]
+
Ω
(
f
t
)
obj^{(t)}=\sum_{i=1}^{N}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega (f_{t})
obj(t)=i=1∑N[gift(xi)+21hift2(xi)]+Ω(ft)
给定训练数据之后,一阶导
g
i
g_{i}
gi 和二阶导
h
i
h_{i}
hi 都可以计算出来,唯一的未知变量只有
f
(
x
)
f(x)
f(x),由上文可知,回归决策树
f
(
x
)
f(x)
f(x) 可以用叶子结点的取值来表示:
f
(
x
i
)
=
w
q
(
x
i
)
=
w
j
f(x_{i})=w_{q(x_{i})}=w_{j}
f(xi)=wq(xi)=wj
而回归决策树
f
f
f 的正则化项表示模型复杂度,可以将其定义为如下形式:
Ω
(
f
)
=
γ
T
+
1
2
λ
∣
∣
w
∣
∣
2
2
=
γ
T
+
1
2
λ
∑
j
=
1
T
w
j
2
\Omega(f)=\gamma T+\frac{1}{2}\lambda||w||_{2}^{2}=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}
Ω(f)=γT+21λ∣∣w∣∣22=γT+21λj=1∑Twj2
其中,
T
T
T为叶子节点个数,
w
w
w为叶子节点向量,
γ
,
λ
\gamma,\lambda
γ,λ为正则化系数;
将回归树
f
(
x
)
f(x)
f(x) 的表达式和对应的正则化项代入目标函数,得到:
o
b
j
(
t
)
=
∑
i
=
1
N
[
g
i
w
q
(
x
i
)
+
1
2
h
i
w
q
(
x
i
)
2
]
+
γ
T
+
1
2
λ
∑
j
=
1
T
w
j
2
obj^{(t)}=\sum_{i=1}^{N}[g_{i}w_{q(x_{i})}+\frac{1}{2}h_{i}w_{q(x_{i})}^{2}]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}
obj(t)=i=1∑N[giwq(xi)+21hiwq(xi)2]+γT+21λj=1∑Twj2
第一个累加项是对
N
N
N 个训练样本进行遍历计算,而第二个累加项是对
T
T
T 个叶子结点进行遍历计算;
具体地,若定义每个叶节点
j
j
j 上的样本集合为:
I
j
=
{
i
∣
q
(
x
i
)
=
j
}
I_{j}=\left\{i|q(x_{i})=j\right\}
Ij={i∣q(xi)=j}
则第
t
t
t 轮目标函数的化简过程如下:
至此,推导出了 XGBoost 在第
t
t
t 轮迭代时的目标函数表达式:
o
b
j
(
t
)
=
∑
j
=
1
T
[
G
j
w
j
+
1
2
(
H
j
+
λ
)
w
j
2
]
+
γ
T
obj^{(t)}=\sum_{j=1}^{T}[G_{j}w_{j}+\frac{1}{2}(H_{j}+\lambda)w_{j}^{2}]+\gamma T
obj(t)=j=1∑T[Gjwj+21(Hj+λ)wj2]+γT
其中,
G
j
G_{j}
Gj 和
H
j
H_{j}
Hj 的表达式如下:
G
j
=
∑
i
∈
I
j
g
i
=
∑
i
∈
I
j
L
′
(
y
^
i
(
t
−
1
)
)
G_{j}=\sum_{i\in I_{j}}g_{i}=\sum_{i\in I_{j}}L^{'}(\widehat{y}_{i}^{(t-1)})
Gj=i∈Ij∑gi=i∈Ij∑L′(y
i(t−1))
H
j
=
∑
i
∈
I
j
h
i
=
∑
i
∈
I
j
L
′
′
(
y
^
i
(
t
−
1
)
)
H_{j}=\sum_{i\in I_{j}}h_{i}=\sum_{i\in I_{j}}L^{''}(\widehat{y}_{i}^{(t-1)})
Hj=i∈Ij∑hi=i∈Ij∑L′′(y
i(t−1))
其中,
G
j
G_{j}
Gj 表示叶子结点
j
j
j 中所有样本的一阶梯度和;
H
j
H_{j}
Hj 表示叶子结点
j
j
j 中所有样本的二阶梯度和,最后,回顾一下 XGBoost 的迭代过程:
第二行的目标函数最优化实际上对应着回归树
f
t
f_{t}
ft 的生成过程。在第二十课CART中,讲到了回归树生成的两个重要步骤:特征空间的划分和预测值的确定。在 XGBoost 中,回归树的生成有什么不同之处?
树的生成
首先回顾 CART 回归树的生成过程:在训练数据集所在的特征空间里,通过最小化平方损失递归地将每个区域划分为两个子区域,并确定每个子区域的输出值,构建二叉决策树。
其中特征空间的划分以及预测值的确定都是通过最小化平方损失得到的。具体地,使用分裂后训练样本平方损失最小的切分变量和切分点进行树的分裂,通过损失函数的导数为零得到最优的预测值。XGBoost 中的回归树生成需要根据目标函数(损失函数+正则化项)来确定。
预测值的确定
假设第
t
t
t 棵回归树的结构
q
(
x
)
q(x)
q(x) 已确定,则各叶子结点最优预测值的求解过程如下:
由于目标函数中的损失函数是通过二阶泰勒展开近似的,故上述过程得到的最优预测值也是近似的,但是没有关系,XGBoost 可以继续迭代,同时正则化项的存在可以缓解模型的过拟合现象
特征空间的划分
特征空间的划分,即叶子结点的分裂。将叶子节点的最优预测值代入目标函数,即可得到 第
t
t
t轮 目标函数的最小值:
−
1
2
∑
j
=
1
T
G
j
2
H
j
+
λ
+
γ
T
-\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T
−21j=1∑THj+λGj2+γT
得到这个式子的前提是回归树的结构
q
(
x
)
q(x)
q(x) 已知,但目前来说还是未知的,故上面的式子是关于回归树
q
(
x
)
q(x)
q(x) 的函数,我们需要找到最优的
q
(
x
)
q(x)
q(x) 使得该函数值最小,所以目标函数值可以作为回归树叶子结点分裂的标准。
如图所示,
T
A
T_{A}
TA 是以根结点为叶子节点的单结点树,
T
B
T_{B}
TB 是根据训练样本某个特征的取值从
T
A
T_{A}
TA 分裂而来的回归树;
T
B
T_{B}
TB 有两个叶子结点,左叶子结点标记为 L,右叶子结点标记为 R。
T
A
T_{A}
TA 分裂前后的目标函数值分别为:
G
L
G_{L}
GL 表示叶子结点
L
L
L 中所有样本的一阶梯度和;
H
L
H_{L}
HL 表示叶子结点
L
L
L 中所有样本的二阶梯度和;
一般来说,
T
A
T_{A}
TA 的目标函数值是大于
T
B
T_{B}
TB 的,两式上下相减得到分裂增益的表达式:
G
a
i
n
=
1
2
(
G
L
2
H
L
+
λ
+
G
R
2
H
R
+
λ
−
(
G
L
+
G
R
)
2
H
L
+
H
R
+
λ
)
−
γ
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
Gain=21(HL+λGL2+HR+λGR2−HL+HR+λ(GL+GR)2)−γ
Gain 为分裂后目标函数值的减少量,选择不同的特征和分裂点时,训练样本就会被划分到不同的叶子结点中,从而得到的 Gain 也会不同,因此我们可以选择 Gain 最大的特征和分裂点进行回归树的生成。
实际计算时,使用下面的分裂增益公式来进行特征选择:
G
a
i
n
=
G
L
2
H
L
+
λ
+
G
R
2
H
R
+
λ
−
(
G
L
+
G
R
)
2
H
L
+
H
R
+
λ
−
γ
Gain=\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
Gain=HL+λGL2+HR+λGR2−HL+HR+λ(GL+GR)2−γ
由于是比较 Gain 的大小,故去掉常数
1
2
\frac{1}{2}
21 不会对特征选择的结果产生影响;
总结一下 XGBoost 中回归树的生成算法:从根结点开始递归地进行结点分裂,计算所有候选(feature,value)
对应的 Gain,选取 Gain 最大的候选进行分裂,并计算叶子结点的预测值,直到满足停止条件,如下图所示:
其中,
G
j
G_{j}
Gj 和
H
j
H_{j}
Hj 的表达式如下:
G
j
=
∑
i
∈
I
j
g
i
=
∑
i
∈
I
j
L
′
(
y
^
i
(
t
−
1
)
)
G_{j}=\sum_{i\in I_{j}}g_{i}=\sum_{i\in I_{j}}L^{'}(\widehat{y}_{i}^{(t-1)})
Gj=i∈Ij∑gi=i∈Ij∑L′(y
i(t−1))
H
j
=
∑
i
∈
I
j
h
i
=
∑
i
∈
I
j
L
′
′
(
y
^
i
(
t
−
1
)
)
H_{j}=\sum_{i\in I_{j}}h_{i}=\sum_{i\in I_{j}}L^{''}(\widehat{y}_{i}^{(t-1)})
Hj=i∈Ij∑hi=i∈Ij∑L′′(y
i(t−1))
由于XGBoost 的目标函数中包含了正则化项,迭代完成后,不需要对每棵回归树进行剪枝
使用 XGBoost 实现波士顿房价预测
XGBoost的应用可以借助xgboost
包,其中已经封装了XGBoost的各种功能,方便个人实验;
导入相关包:
# 导入 XGBoost 包
import xgboost as xgb
# 使用波士顿房价数据
from sklearn.datasets import load_boston
# 划分训练集和测试集
from sklearn.model_selection import train_test_split
# 回归问题的评价指标:MSE,R2
from sklearn.metrics import mean_squared_error,r2_score
数据加载与划分:
# 加载波士顿房价数据
boston = load_boston()
# 获取样本特征矩阵,shape = 样本数 x 特征数
x = boston.data
# 获取样本标记值数组,shape = 样本数
y = boston.target
# 划分训练集和测试集,测试集占20%
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.2, random_state=2021)
模型训练与预测:
# 实例化 XGBoost 回归模型:基学习器个数为 100,学习率为 0.1
model = xgb.XGBRegressor(n_estimators=100,learning_rate=0.1)
# 在训练集上训练
model = model.fit(x_train,y_train)
# 在测试集上预测(房价)
y_hat = model.predict(x_test)
回顾GBDT中的梯度提升算法与上文的表达式:
y
^
i
(
t
)
=
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
\widehat{y}_{i}^{(t)}=\widehat{y}_{i}^{(t-1)}+f_{t}(x_{i})
y
i(t)=y
i(t−1)+ft(xi)
每次迭代的增量
f
t
(
x
i
)
f_{t}(x_{i})
ft(xi)实际上是在拟合负梯度,前向分步迭代次数即为基学习器个数,上面式子相当于将学习率设置为 1,如果引入固定的学习率
l
r
lr
lr ,迭代
M
M
M 轮,则XGBoost模型为:
y
^
i
=
y
^
i
(
M
)
=
∑
t
=
1
M
l
r
⋅
f
t
(
x
i
)
\widehat{y}_{i}=\widehat{y}_{i}^{(M)}=\sum_{t=1}^{M}lr\cdot f_{t}(x_{i})
y
i=y
i(M)=t=1∑Mlr⋅ft(xi)
模型评估:
# 计算均方根误差
rmse = mean_squared_error(y_hat,y_test)**0.5
# 计算 R2 值
r2 = r2_score(y_hat,y_test)
# 打印评估指标
print('RMSE = {}, R2 = {}'.format(rmse,r2))
MAE、RMSE在课程中都有提到, R 2 R^{2} R2 是回归问题中另一个用于衡量模型预测能力好坏的一个指标,预测数据和真实数据越接近, R 2 R^{2} R2 越大;
结果为:RMSE = 3.675741832705175, R2 = 0.7779981200087587
使用 XGBoost 完成乳腺癌诊断的二分类问题
前面说过, XGBoost 的本质属于加法模型,其基函数为回归决策树。如果将回归的输出作为得分,再输入分类器(可以是sigmoid,softmax等,以下式子为感知机的sign)即能实现分类:
G
(
x
i
)
=
s
i
g
n
(
y
^
i
)
=
s
i
g
n
(
∑
t
=
1
M
f
t
(
x
i
)
)
G(x_{i})=sign(\widehat{y}_{i})=sign(\sum_{t=1}^{M}f_{t}(x_{i}))
G(xi)=sign(y
i)=sign(t=1∑Mft(xi))
损失函数可以使用对数函数(也可以选择用于衡量分类的各种其他损失函数),目标函数的形式依然为 损失函数+正则化项,后续的泰勒展开也没有影响;
因此,使用 XGBoost 也可以解决分类问题:
### 1. 导入相关包
# 导入 XGBoost 包
import xgboost as xgb
# 使用乳腺癌诊断数据集
from sklearn.datasets import load_breast_cancer
# 划分训练集和测试集
from sklearn.model_selection import train_test_split
# 分类问题的评价指标:AUC,F1 score
from sklearn.metrics import roc_auc_score,f1_score
### 2. 数据加载与划分
# 加载乳腺癌诊断数据集
cancer = load_breast_cancer()
# 获取样本特征矩阵,shape = 样本数 x 特征数
x = cancer.data
# 获取样本标记值数组,shape = 样本数
y = cancer.target
# 正样本(取值为1)表示肿瘤为良性,负样本(取值为0)表示肿瘤为恶性
print('正样本数量为:{}, 负样本数量为:{}'.format(sum(y==1),sum(y==0)))
# 划分训练集和测试集,测试集占20%
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.2, random_state=2021)
### 3. 模型训练与预测
# 实例化 XGBoost 分类模型:基学习器个数为 100,学习率为 0.1
model = xgb.XGBClassifier(n_estimators=100,learning_rate=0.1)
# 在训练集上训练
model = model.fit(x_train,y_train)
# 在测试集上预测(良性肿瘤的概率值)
y_hat = model.predict_proba(x_test)[:,1]
### 4. 模型评估
# 计算 AUC 的值
auc = roc_auc_score(y_test,y_hat)
# 计算 F1 分值(肿瘤为良性的概率大于0.8时,对应的预测值为 1)
f1 = f1_score(y_test,y_hat>0.8)
# 打印评估指标
print('AUC = {}, F1 = {}'.format(auc,f1))
结果为:
正样本数量为:357, 负样本数量为:212
AUC = 0.9960317460317462, F1 = 0.9861111111111112