XGBoost算法原理详解与参数详解
数据科学与机器学习案例之客户的信用风险与预测
数据科学与机器学习之信用卡欺诈识别（严重类失衡数据建模)
数据科学与机器学习案例之汽车目标客户销售策略研究
数据科学与机器学习案例之WiFi定位系统的位置预测
数据科学与机器学习案例之Stacking集成方法对鸢尾花进行分类
XGBoost算法原理详解与实战
- 1. Paper下载
- 2. XGBoost原理详解
- 2.1.1 XGBoost原理
- 2.1.2 XGBoost目标函数的构造
- 2.1.3 目标函数的优化
- 2.1.4 树的定义
- 2.1.5最优切分点的寻找
- 2.1.5.1 贪心算法
- 2.1.5.2近似算法
- 2.1.5.3 加权分位数方法
1. Paper下载
XGBoost: A Scalable Tree Boosting System论文下载地址
2. XGBoost原理详解
XGBoost在数据科学方面深受数据科学家的喜爱，并且在Kaggle数据科学竞赛中有大量的学生、工作者使用；XGBoost在业界也备受推宠，其可以在Hadoop、SGE、Dask等各个分布式环境中使用，使得该算法可以更好地解决业界大规模数据的问题，本篇博客将完全从Paper中讲述XGBoost的数学原理以及实现。
2.1.1 XGBoost原理
XGBoost仍属于boosting集成方法中的一种，但是其统计思想是基于模型的残差进行训练，这是什么意思呢？
以最简单的方式把XGBoost原理讲明白！
对于我们预测数据中的响应变量
y,我们建立树模型对响应变量y进行预测，得到Model.1,此时残差为y − y ^ y-\hat{y} y−y^;接下来我们根据我们将Model.1预测得到的残差作为Model.2预测的响应变量，然后拟合进而得到Model.2的残差，以此类推，进而得到Model.K.
XGBoost是由
k
k
k个基模型组成的一个加法模型，其训练的思想是：第
k
k
k个模型根据第
k
−
1
k-1
k−1个模型的残差进行拟合。
M
o
d
e
l
f
i
n
a
l
=
M
o
d
e
l
.
1
+
M
o
d
e
l
.
2
+
.
.
.
+
M
o
d
e
l
.
k
Model_{final}=Model.1+Model.2+...+Model.k
Modelfinal=Model.1+Model.2+...+Model.k
2.1.2 XGBoost目标函数的构造
假设在XGBoost中有
K
K
K个基模型，对于第
i
i
i个样本，
K
K
K个模型对于其的预测分别为
f
1
(
x
i
)
,
f
2
(
x
i
)
,
.
.
.
,
f
K
(
x
i
)
f_{1}(x_{i}),f_{2}(x_{i}),...,f_{K}(x_{i})
f1(xi),f2(xi),...,fK(xi).XGBoost对第
i
i
i个样本的预测为：
y
i
^
=
∑
k
=
1
K
f
k
(
x
i
)
,
f
k
∈
F
\hat{y_{i}}=\sum_{k=1}^{K}f_{k}(x_{i}),f_{k}\in \mathcal{F}
yi^=k=1∑Kfk(xi),fk∈F我们对于目标函数的构造如下(假设前
K
−
1
K-1
K−1个模型已知)：
构建第 k k k个基模型：
对于给定的样本x i x_{i} xi:
第1个基模型： y i ^ ( 1 ) = f 1 ( x i ) \hat{y_{i}}^{(1)}=f_{1}(x_{i}) yi^(1)=f1(xi)
前2个基模型： y i ^ ( 2 ) = f 1 ( x i ) + f 2 ( x i ) = y i ^ ( 1 ) + f 2 ( x i ) \hat{y_{i}}^{(2)}=f_{1}(x_{i})+f_{2}(x_{i})=\hat{y_{i}}^{(1)}+f_{2}(x_{i}) yi^(2)=f1(xi)+f2(xi)=yi^(1)+f2(xi)
…
前K个基模型: y i ^ ( K ) = f 1 ( x i ) + f 2 ( x i ) + . . . + f K ( x i ) = y i ^ ( K − 1 ) + f K ( x i ) \hat{y_{i}}^{(K)}=f_{1}(x_{i})+f_{2}(x_{i})+...+f_{K}(x_{i})=\hat{y_{i}}^{(K-1)}+f_{K}(x_{i}) yi^(K)=f1(xi)+f2(xi)+...+fK(xi)=yi^(K−1)+fK(xi)
目标函数：
L
o
s
s
=
∑
i
=
1
n
L
(
y
i
,
y
i
^
(
K
)
)
+
∑
k
=
1
K
Ω
(
f
k
)
=
∑
i
=
1
n
L
(
y
i
,
y
i
^
(
K
−
1
)
+
f
K
(
x
i
)
)
+
∑
k
=
1
K
−
1
Ω
(
f
k
)
+
Ω
(
f
K
)
\begin{align} Loss&=\sum_{i=1}^{n}L(y_{i},\hat{y_{i}}^{(K)})+\sum_{k=1}^{K}\Omega(f_{k}) \tag 1 \\ & = \sum_{i=1}^{n}L(y_{i},\hat{y_{i}}^{(K-1)}+f_{K}(x_{i})) +\sum_{k=1}^{K-1}\Omega(f_{k})+\Omega(f_{K}) \tag 2 \\ \end{align}
Loss=i=1∑nL(yi,yi^(K))+k=1∑KΩ(fk)=i=1∑nL(yi,yi^(K−1)+fK(xi))+k=1∑K−1Ω(fk)+Ω(fK)(1)(2)
从公式
( 1 ) (1) (1)到公式(2)是由于前K-1个基模型已经确定，所以前K-1个模型的预测以及复杂度都是常量.
对第K个模型的训练：
m
i
n
i
s
i
z
e
∑
i
=
1
n
L
(
y
i
,
y
i
^
(
K
−
1
)
+
f
K
(
x
i
)
)
+
Ω
(
f
K
)
(3)
minisize\sum_{i=1}^{n}L(y_{i},\hat{y_{i}}^{(K-1)}+f_{K}(x_{i}))+\Omega(f_{K}) \tag{3}
minisizei=1∑nL(yi,yi^(K−1)+fK(xi))+Ω(fK)(3)
2.1.3 目标函数的优化
使用泰勒公式近似目标函数.
泰勒公式： f ( x + Δ x ) ≈ f ( x ) + f ′ ( x ) Δ x + 1 2 f ′ ′ ( x ) Δ x 2 f(x+\Delta x)\approx f(x)+f^{'}(x)\Delta x+\frac{1}{2}f^{''}(x)\Delta x^{2} f(x+Δx)≈f(x)+f′(x)Δx+21f′′(x)Δx2
令 f ( x ) = L ( y i , y i ^ ( K − 1 ) ) , f ( x + Δ x ) = L ( y i , y i ^ ( K − 1 ) + f K ( x i ) ) f(x)=L(y_{i},\hat{y_{i}}^{(K-1)}),f(x+\Delta x)=L(y_{i},\hat{y_{i}}^{(K-1)}+f_{K}(x_{i})) f(x)=L(yi,yi^(K−1)),f(x+Δx)=L(yi,yi^(K−1)+fK(xi))
因此使用泰勒公式对目标函数展开：
m
i
n
i
s
i
z
e
∑
i
=
1
n
L
(
y
i
,
y
i
^
(
K
−
1
)
+
f
K
(
x
i
)
)
+
Ω
(
f
K
)
=
∑
i
=
1
n
[
L
(
y
i
,
y
i
^
(
K
−
1
)
)
+
L
′
(
y
i
,
y
i
^
(
K
−
1
)
)
f
K
(
x
i
)
+
1
2
L
′
′
(
y
i
,
y
i
^
(
K
−
1
)
)
f
K
2
(
x
i
)
]
+
Ω
(
f
K
)
\begin{align} minisize \sum_{i=1}^{n}L(y_{i},\hat{y_{i}}^{(K-1)}+f_{K}(x_{i}))+\Omega(f_{K}) \tag 4 \\ = \sum_{i=1}^{n}[L(y_{i},\hat{y_{i}}^{(K-1)})+L^{'}(y_{i},\hat{y_{i}}^{(K-1)})f_{K}(x_{i})+\frac{1}{2}L^{''}(y_{i},\hat{y_{i}}^{(K-1)})f_{K}^{2}(x_{i})]+ \Omega(f_{K}) \tag 5 \\ \end{align}
minisizei=1∑nL(yi,yi^(K−1)+fK(xi))+Ω(fK)=i=1∑n[L(yi,yi^(K−1))+L′(yi,yi^(K−1))fK(xi)+21L′′(yi,yi^(K−1))fK2(xi)]+Ω(fK)(4)(5)
令 g i = L ′ ( y i , y i ^ ( K − 1 ) ) , h i = L ′ ′ ( y i , y i ^ ( K − 1 ) ) g_{i}=L^{'}(y_{i},\hat{y_{i}}^{(K-1)}),h_{i}=L^{''}(y_{i},\hat{y_{i}}^{(K-1)}) gi=L′(yi,yi^(K−1)),hi=L′′(yi,yi^(K−1)),
这里的一阶偏导与二阶偏导都是对 y i ^ ( K − 1 ) ) \hat{y_{i}}^{(K-1)}) yi^(K−1))求导.
最终我们的目标函数为：
m
i
n
i
s
i
z
e
∑
i
=
1
n
[
g
i
f
K
(
x
i
)
+
1
2
h
i
f
K
2
(
x
i
)
]
+
Ω
(
f
K
)
\begin{align} minisize \sum_{i=1}^{n}[g_{i}f_{K}(x_{i})+\frac{1}{2}h_{i}f_{K}^{2}(x_{i})]+\Omega(f_{K}) \tag 6 \\ \end{align}
minisizei=1∑n[gifK(xi)+21hifK2(xi)]+Ω(fK)(6)
2.1.4 树的定义
对于一棵树我需要定义树的叶节点的值、有多少样本落入选定的叶节点。
推出：
f
k
(
x
i
)
=
W
q
(
x
i
)
f_{k}(x_{i})=W_{q(x_{i})}
fk(xi)=Wq(xi).其中
W
=
[
w
1
,
w
2
,
w
3
,
.
.
.
,
w
T
]
∈
R
T
W=[w_{1},w_{2},w_{3},...,w_{T}]\in R^{T}
W=[w1,w2,w3,...,wT]∈RT,
q
(
x
)
=
[
1
,
2
,
3
,
.
.
.
,
T
]
q(x)=[1,2,3,...,T]
q(x)=[1,2,3,...,T].
定义树的复杂度：
Ω
(
f
k
)
=
γ
T
+
1
2
λ
∑
j
=
1
T
w
j
2
\begin{align} \Omega(f_{k})=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2} \tag 7 \\ \end{align}
Ω(fk)=γT+21λj=1∑Twj2(7)
T:代表叶节点个数，叶节点的个数越少模型就越简单，对于叶节点下的值进行L2惩罚进行预测值的压缩本质上也是在减少叶节点的个数
按照上述目标函数可写为：
L
o
s
s
=
∑
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
\begin{align} Loss=\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}\tag 8 \\ \end{align}
Loss=i=1∑n[giWq(xi)+21hiWq(xi)2]+γT+21λj=1∑Twj2(8)
下面更新目标函数的表示方法：目标函数按照叶节点的方式循环。将属于第
j
j
j个叶节点的所有样本
x
i
x_{i}
xi归于集合
I
j
=
{
i
:
q
(
x
j
)
=
j
}
I_{j}=\lbrace i:q(x_{j})=j\rbrace
Ij={i:q(xj)=j}.
更新的目标函数为：
L
o
s
s
=
∑
j
=
1
T
[
(
∑
i
∈
I
j
g
i
)
w
j
+
1
2
(
∑
i
∈
I
j
h
i
+
λ
)
w
j
2
]
+
γ
T
\begin{align} Loss=\sum_{j=1}^{T}[(\sum_{i\in I_{j}}g_{i})w_{j}+\frac{1}{2}(\sum_{i\in I_{j}}h_{i}+\lambda)w_{j}^{2}]+\gamma T \tag 9 \\ \end{align}
Loss=j=1∑T[(i∈Ij∑gi)wj+21(i∈Ij∑hi+λ)wj2]+γT(9)
令 G j = ∑ i ∈ I j g i , H j = ∑ i ∈ I j h i G_{j}=\sum_{i\in I_{j}}g_{i},H_{j}=\sum_{i\in I_{j}}h_{i} Gj=∑i∈Ijgi,Hj=∑i∈Ijhi.
G j G_{j} Gj:叶子节点 j j j所包含样本的一阶偏导数累加之和，是一个常量
H j H_{j} Hj:叶子节点 j j j所包含样本的二阶偏导数累加之和，是一个常量
L o s s = ∑ j = 1 T [ G j w j + 1 2 ( H j + λ ) w j 2 ] + γ T \begin{align} Loss=\sum_{j=1}^{T}[G_{j}w_{j}+\frac{1}{2}(H_{j}+\lambda)w_{j}^{2}]+\gamma T \tag {10} \\ \end{align} Loss=j=1∑T[Gjwj+21(Hj+λ)wj2]+γT(10)
二次函数：
最后化简出的目标函数是关于 w j w_{j} wj的二次函数，由二次函数的性质很容易求出极值。
当
w
j
∗
=
−
b
2
a
=
−
G
j
H
j
+
λ
w_{j}^{*}=\frac{-b}{2a}=\frac{-G_{j}}{H_{j}+\lambda}
wj∗=2a−b=Hj+λ−Gj时，
L
o
s
s
∗
=
−
1
2
∑
j
=
1
T
G
j
2
H
j
+
λ
+
γ
T
Loss^{*}=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T
Loss∗=−21∑j=1THj+λGj2+γT
也就是说当树的结构已知时，我们可以很快的确定最小值。
下面
XGBoost面临着如何确定树的形状？我们将介绍三种确定树形状的方法。
2.1.5最优切分点的寻找
2.1.5.1 贪心算法
贪心算法的描述：
从树的深度为
0
0
0开始：
1.对于每一个叶节点列举出其所有可用的特征.
2.对于每一个特征，把属于该节点的训练样本根据特征值进行升序排列，再选择出对于该特征的最佳分裂点，并记录该特征的损失函数减小的值.
3.遍历完所有的特征之后，选择损失函数减小最大的特征作为该节点的分类特征， 在该节点左右两侧出现新的叶节点，并且为新节点关联其所对应的样本集.
4.回到第1步，递归执行直到满足特定条件为止.
举例说明贪心算法：
公式：
L
o
s
s
o
l
d
=
−
1
2
[
(
g
7
+
g
8
)
2
h
7
+
h
8
+
λ
+
(
g
1
+
g
2
+
.
.
.
+
g
6
)
2
h
1
+
h
2
+
.
.
.
+
h
6
+
λ
]
+
2
γ
Loss_{old}=-\frac{1}{2}[\frac{(g_{7}+g_{8})^{2}}{h_{7}+h_{8}+\lambda}+\frac{(g_{1}+g_{2}+...+g_{6})^{2}}{h_{1}+h_{2}+...+h_{6}+\lambda}]+2\gamma
Lossold=−21[h7+h8+λ(g7+g8)2+h1+h2+...+h6+λ(g1+g2+...+g6)2]+2γ
L
o
s
s
n
e
w
=
−
1
2
[
(
g
7
+
g
8
)
2
h
7
+
h
8
+
λ
+
(
g
1
+
g
3
+
g
5
)
2
h
1
+
h
3
+
h
5
+
λ
+
(
g
2
+
g
4
+
g
6
)
2
h
2
+
h
4
+
h
6
+
λ
]
+
3
γ
Loss_{new}=-\frac{1}{2}[\frac{(g_{7}+g_{8})^{2}}{h_{7}+h_{8}+\lambda}+\frac{(g_{1}+g_{3}+g_{5})^{2}}{h_{1}+h_{3}+h_{5}+\lambda}+\frac{(g_{2}+g_{4}+g_{6})^{2}}{h_{2}+h_{4}+h_{6}+\lambda}]+3\gamma
Lossnew=−21[h7+h8+λ(g7+g8)2+h1+h3+h5+λ(g1+g3+g5)2+h2+h4+h6+λ(g2+g4+g6)2]+3γ
L
o
s
s
o
l
d
−
L
o
s
s
n
e
w
=
1
2
[
G
L
2
H
L
+
λ
+
G
R
2
H
R
+
λ
−
(
G
L
+
G
R
)
2
H
L
+
H
R
+
λ
]
−
γ
Loss_{old}-Loss_{new}=\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
Lossold−Lossnew=21[HL+λGL2+HR+λGR2−HL+HR+λ(GL+GR)2]−γ
找到使得上式达到最大的特征作为分割点
2.1.5.2近似算法
贪心算法太过暴力，当数据量过大且某些特征下是连续型变量时可能会导致计算速度过慢，所以近似算法的提出解决了这一缺点。对于大规模的数据量，近似算法只考虑了特征下的分位点。
对于近似算法我们只考虑某些特征下的排序数据的分位点作为切割位点。这样就加速了大规模的数据量切分位点的运算。
近似算法可以看作贪心算法的简化版，对于树的左右两个叶节点是根据某些特征下的排序数据的分位数进行样本的划分。下面图片给出了近似算法(全局与局部)与贪心算法的比较。
2.1.5.3 加权分位数方法
不同于简单的近似算法，加权分位数方法是对分位数进行加权(使用二阶梯度h).论文中对于特征
k
k
k定义集合：
D
k
=
{
(
x
1
k
,
h
1
)
,
(
x
2
k
,
h
2
)
,
.
.
.
,
(
x
n
k
,
h
n
)
}
D_{k}=\lbrace(x_{1k},h_{1}),(x_{2k},h_{2}),...,(x_{nk},h_{n})\rbrace
Dk={(x1k,h1),(x2k,h2),...,(xnk,hn)}
其中
x
i
k
x_{ik}
xik表示第
i
i
i个样本下特征
k
k
k的取值，
h
i
h_{i}
hi为对应的二阶梯度。
rank function:
r
k
(
z
)
=
1
∑
(
x
,
h
)
∈
D
k
h
∑
(
x
,
h
)
∈
D
k
,
x
<
z
h
r_{k}(z)=\frac{1}{\sum_{(x,h)\in D_{k}}h}\sum_{(x,h)\in D_{k},x<z}h
rk(z)=∑(x,h)∈Dkh1(x,h)∈Dk,x<z∑h
对于使用二阶梯度加权的解释
L
o
s
s
=
m
i
n
i
s
i
z
e
∑
i
=
1
n
[
g
i
f
K
(
x
i
)
+
1
2
h
i
f
K
2
(
x
i
)
]
+
Ω
(
f
K
)
=
∑
i
=
1
n
1
2
(
2
g
i
h
i
f
k
(
x
i
)
+
f
k
2
(
x
i
)
+
Ω
(
f
K
)
≈
∑
i
=
1
n
1
2
(
2
g
i
h
i
f
k
(
x
i
)
+
f
k
2
(
x
i
)
+
(
g
i
h
i
)
2
)
+
Ω
(
f
K
)
=
∑
i
=
1
n
1
2
h
i
[
f
k
(
x
i
)
−
(
−
g
i
h
i
)
]
2
+
Ω
(
f
K
)
\begin{align} Loss&=minisize \sum_{i=1}^{n}[g_{i}f_{K}(x_{i})+\frac{1}{2}h_{i}f_{K}^{2}(x_{i})]+\Omega(f_{K}) \tag 1 \\ & = \sum_{i=1}^{n}\frac{1}{2}(2\frac{g_{i}}{h_{i}}f_{k}(x_{i})+f_{k}^{2}(x_{i})+\Omega(f_{K}) \tag 2 \\ & \approx \sum_{i=1}^{n}\frac{1}{2}(2\frac{g_{i}}{h_{i}}f_{k}(x_{i})+f_{k}^{2}(x_{i})+(\frac{g_{i}}{h_{i}})^{2})+\Omega(f_{K}) \tag 3 \\ & = \sum_{i=1}^{n}\frac{1}{2}h_{i}[f_{k}(x_{i})-(\frac{-g_{i}}{h_{i}})]^{2}+\Omega(f_{K}) \tag 4 \\ \end{align}
Loss=minisizei=1∑n[gifK(xi)+21hifK2(xi)]+Ω(fK)=i=1∑n21(2higifk(xi)+fk2(xi)+Ω(fK)≈i=1∑n21(2higifk(xi)+fk2(xi)+(higi)2)+Ω(fK)=i=1∑n21hi[fk(xi)−(hi−gi)]2+Ω(fK)(1)(2)(3)(4)
加权分位数算法的理解：目标仍然是极小化目标函数，但是在极小化的过程中通过观察式子，以配方的形式添加了常数项 ( g i f i ) 2 (\frac{g_{i}}{f_{i}})^{2} (figi)2，添加完常数项之后对配方的式子进行改写。
[ f k ( x i ) − ( − g i h i ) ] 2 [f_{k}(x_{i})-(\frac{-g_{i}}{h_{i}})]^{2} [fk(xi)−(hi−gi)]2:式子的形式接近于回归分析中的( y i ^ − y i ) 2 (\hat{y_{i}}-y_{i})^{2} (yi^−yi)2.认为是对第 i i i个样本的预测值减去第 i i i个样本的真实值。h i h_{i} hi代表的是对第 i i i个样本的权重，这样对于二阶样本的梯度加权就解释完毕了。
加权分位数方法的计算方式：
| 特征 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1 |
|---|---|---|---|---|---|---|---|---|
| 二阶导 | 0.1 | 0.1 | 0.1 | 0.2 | 0.3 | 0.3 | 0.4 | 0.5 |
| r k ( z ) r_k(z) rk(z) | 0 | 0.05 | 0.1 | 0.15 | 0.25 | 0.4 | 0.55 | 0.75 |
特征与对应的排序函数的关系：
红色箭头表示以三分位点作为切分点。
关于XGBoost的原理就讲到这里，后面会根据实际案例进行XGBoost实战。博客更新路上需要各位的批评与指正，谢谢大家！