探究算法细节，深入了解算法原理
XGBoost的参考资料
【作者PPT内容】
（1）XGBoost全称：eXtreme Gradient Boosting 极端梯度提升
（2）学习算法的目标函数
O
b
j
(
Θ
)
=
L
(
Θ
)
+
Ω
(
Θ
)
Obj(\Theta)=L(\Theta)+\Omega(\Theta)
Obj(Θ)=L(Θ)+Ω(Θ)
（3）集成CART回归树
例子：输入特征有年龄、性别、职业等，判断一个人是否喜欢电脑游戏。
假设有 K K K棵树，则预测分数为：
y i ^ = ∑ k = 1 K f k ( x i ) \hat{y_i}=\sum_{k=1}^{K}f_k(x_i) yi^=k=1∑Kfk(xi)
目标函数为：
O b j = ∑ i = 1 n l ( y i , y i ^ ) + ∑ k = 1 K Ω ( f k ) Obj=\sum_{i=1}^{n}l(y_i,\hat{y_i})+\sum_{k=1}^{K}\Omega(f_k) Obj=i=1∑nl(yi,yi^)+k=1∑KΩ(fk)
【作者PPT内容】
（1）第 t t t 轮的模型表达式为：
y i ^ ( t ) = ∑ k = 1 t f k ( x i ) = y i ^ ( t − 1 ) + f t ( x i ) \hat{y_i}^{(t)}=\sum_{k=1}^{t}f_k(x_i)=\hat{y_i}^{(t-1)}+f_t(x_i) yi^(t)=k=1∑tfk(xi)=yi^(t−1)+ft(xi)
其中 f t ( x ) f_t(x) ft(x) 是需要在第 t t t 轮学习的。找出 f t ( x ) f_t(x) ft(x) 最小化以下目标函数：
O b j ( t ) = ∑ i = 1 n l ( y i , y i ^ ( t − 1 ) + f t ( x i ) ) + Ω ( f t ) + c o n s t a n t Obj^{(t)}=\sum_{i=1}^{n}l\left(y_i,\hat{y_i}^{(t-1)}+f_t(x_i)\right)+\Omega(f_t)+constant Obj(t)=i=1∑nl(yi,yi^(t−1)+ft(xi))+Ω(ft)+constant
（2）如果是平方损失，去掉常数项，则目标函数变为：
O b j ( t ) = ∑ i = 1 n [ y i − ( y i ^ ( t − 1 ) + f t ( x i ) ) ] 2 + Ω ( f t ) + c o n s t a n t = ∑ i = 1 n [ 2 ( y i ^ ( t − 1 ) − y i ) f t ( x i ) + f t ( x i ) 2 ] + Ω ( f t ) \begin{aligned} Obj^{(t)} &= \sum_{i=1}^{n}\left[y_i-(\hat{y_i}^{(t-1)}+f_t(x_i))\right]^2+\Omega(f_t)+constant \\&= \sum_{i=1}^{n}\left[2(\hat{y_i}^{(t-1)}-y_i)f_t(x_i)+f_t(x_i)^2\right]+\Omega(f_t) \end{aligned} Obj(t)=i=1∑n[yi−(yi^(t−1)+ft(xi))]2+Ω(ft)+constant=i=1∑n[2(yi^(t−1)−yi)ft(xi)+ft(xi)2]+Ω(ft)
（1）二阶泰勒展开公式为：
f ( x + Δ x ) ≃ f ( x ) + f ′ ( x ) Δ x + 1 2 f ′ ′ ( x ) Δ x f(x+\Delta x)\simeq f(x)+f^{'}(x)\Delta x+\frac{1}{2}f^{''}(x)\Delta x f(x+Δx)≃f(x)+f′(x)Δx+21f′′(x)Δx
（2）如果不是平方损失，目标函数很复杂
O b j ( t ) = ∑ i = 1 n l ( y i , y i ^ ( t − 1 ) + f t ( x i ) ) + Ω ( f t ) + c o n s t a n t Obj^{(t)}=\sum_{i=1}^{n}l\left(y_i,\hat{y_i}^{(t-1)}+f_t(x_i)\right)+\Omega(f_t)+constant Obj(t)=i=1∑nl(yi,yi^(t−1)+ft(xi))+Ω(ft)+constant
（3）定义损失函数对第 t − 1 t-1 t−1 轮的强学习器 y i ^ ( t − 1 ) \hat{y_i}^{(t-1)} yi^(t−1) 的一阶偏导和二阶偏导
g i = ∂ y i ^ ( t − 1 ) l ( y i , y i ^ ( t − 1 ) ) g_i=\partial_{\hat{y_i}^{(t-1)}}l(y_i,\hat{y_i}^{(t-1)}) gi=∂yi^(t−1)l(yi,yi^(t−1))
h i = ∂ y i ^ ( t − 1 ) 2 l ( y i , y i ^ ( t − 1 ) ) h_i=\partial^2_{\hat{y_i}^{(t-1)}}l(y_i,\hat{y_i}^{(t-1)}) hi=∂yi^(t−1)2l(yi,yi^(t−1))
（4）目标函数的近似表达式为：
O b j ( t ) = ∑ i = 1 n [ l ( y i , y i ^ ( t − 1 ) ) + g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) + c o n s t a n t Obj^{(t)}=\sum_{i=1}^{n}\left[l(y_i,\hat{y_i}^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]+\Omega(f_t)+constant Obj(t)=i=1∑n[l(yi,yi^(t−1))+gift(xi)+21hift2(xi)]+Ω(ft)+constant
（5）去掉常数项，目标函数变为：
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}\left[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]+\Omega(f_t) Obj(t)=i=1∑n[gift(xi)+21hift2(xi)]+Ω(ft)
通过叶子节点中的分数向量和叶子索引映射函数来定义树，该函数将一个实例映射到一个叶子节点。
f t ( x ) = w q ( x ) , w ∈ R T , q : R d → { 1 , 2 , . . . , T } f_t(x)=w_{q(x)}, \quad w \in R^T, \quad q:R^d \rightarrow \{1,2,...,T\} ft(x)=wq(x),w∈RT,q:Rd→{1,2,...,T}
利用叶子节点数 T T T，和叶子节点分数的L2范数 w j 2 w_j^2 wj2 共同定义模型的复杂度
Ω ( f t ) = γ T + 1 2 λ ∑ j = 1 T w j 2 \Omega(f_t)=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_j^2 Ω(ft)=γT+21λj=1∑Twj2
将叶子节点 j j j 中的实例样本定义为：
I j = { i ∣ q ( x i ) = j } I_j=\{i|q(x_i)=j\} Ij={i∣q(xi)=j}
根据叶子节点将目标函数重写为：
O b j ( t ) ≃ ∑ i = 1 n [ g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) = ∑ i = 1 n [ g i w q ( x i ) + 1 2 h i w q 2 ( x i ) ] + γ T + 1 2 λ ∑ j = 1 T w j 2 = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T \begin{aligned} Obj^{(t)} & \simeq \sum_{i=1}^{n}\left[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]+\Omega(f_t) \\ & = \sum_{i=1}^{n}\left[g_iw_q(x_i)+\frac{1}{2}h_iw_q^2(x_i)\right]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_j^2 \\ &=\sum_{j=1}^{T}\left[(\sum_{i \in I_j}g_i)w_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w_j^2\right]+\gamma T \end{aligned} Obj(t)≃i=1∑n[gift(xi)+21hift2(xi)]+Ω(ft)=i=1∑n[giwq(xi)+21hiwq2(xi)]+γT+21λj=1∑Twj2=j=1∑T⎣⎡(i∈Ij∑gi)wj+21(i∈Ij∑hi+λ)wj2⎦⎤+γT
（1）对于单变量的平方函数，有如下结论：
arg min x G x + 1 2 H x 2 = − G H , H > 0 \arg \min_{x} Gx+\frac{1}{2}Hx^2=-\frac{G}{H}, \quad H>0 argxminGx+21Hx2=−HG,H>0
min x G x + 1 2 H x 2 = − 1 2 G 2 H \min_{x} Gx+\frac{1}{2}Hx^2=-\frac{1}{2}\frac{G^2}{H} xminGx+21Hx2=−21HG2
（2）替换目标函数中的系数
定义如下系数：
G j = ∑ i ∈ I j g i G_j=\sum_{i \in I_j}g_i Gj=i∈Ij∑gi
H j = ∑ i ∈ I j h i H_j=\sum_{i \in I_j}h_i Hj=i∈Ij∑hi
目标函数变为：
O b j ( t ) ≃ ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T = ∑ j = 1 T [ G j w j + 1 2 ( H j + λ ) w j 2 ] + γ T \begin{aligned} Obj^{(t)} & \simeq \sum_{j=1}^{T}\left[(\sum_{i \in I_j}g_i)w_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w_j^2\right]+\gamma T \\ & = \sum_{j=1}^{T}\left[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2\right]+\gamma T \end{aligned} Obj(t)≃j=1∑T⎣⎡(i∈Ij∑gi)wj+21(i∈Ij∑hi+λ)wj2⎦⎤+γT=j=1∑T[Gjwj+21(Hj+λ)wj2]+γT
（3）假设树的结构 q ( x ) q(x) q(x) 是固定的，求得叶子节点的最佳权重、最小目标值（结构得分）为：
w j ∗ = − G j H j + λ w_j^*=-\frac{G_j}{H_j+\lambda} wj∗=−Hj+λGj
O b j = − 1 2 ∑ j = 1 T G j 2 H j + λ + γ T Obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T Obj=−21j=1∑THj+λGj2+γT
（4）最小目标值计算：
（1）从深度为0的树开始。
（2）对树的每个叶子节点，试图去分裂。增加分裂后的目标变化是：
（3）寻找最佳分裂
从左到右线性扫描经过排序的实例，找出特征的最佳分割。
（1）xgboost与传统的GBDT相比，对代价函数进行了二阶泰勒展开，同时用到了一阶与二阶导数，而GBDT在优化时只用到了一阶导数的信息，个人认为类似牛顿法与梯度下降的区别。
（2）xgboost在损失函数里加入的正则项可用于控制模型的复杂度。
（3）传统GBDT以CART回归树作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑回归（分类问题）或线性回归（回归问题）。
（4）Shrinkage（缩减），相当于学习速率（xgboost中的eta）。
（5）列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统GBDT的一个特性。
（6）对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
（7）xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？
（8）可并行的近似直方图算法。
以上3节内容是PPT中的资料，本节主要看一下【论文原文】的一些细节部分。
【XGBoost： A Scalable Tree Boosting System】
主要创新点：
构建高度可扩展的端到端的提升树系统。 XGBoost成功的最重要因素是其在所有情况下的可扩展性
该系统在单台机器上的运行速度比现有流行解决方案快十倍以上，并可在分布式或内存有限的环境中扩展到数十亿的数据规模。
提出一个理论上合理的加权分位数略图。（分裂节点时可以不用遍历所有点，省时间）
引入新颖的稀疏感知算法用于并行树学习。（令缺失值有默认方向）
提出有效的用于核外树形学习的缓存感知块结构。（用缓存加速寻找排序后被打乱的索引的列数据）
O b j ( t ) ≃ ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T = ∑ j = 1 T [ G j w j + 1 2 ( H j + λ ) w j 2 ] + γ T \begin{aligned} Obj^{(t)} & \simeq \sum_{j=1}^{T}\left[(\sum_{i \in I_j}g_i)w_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w_j^2\right]+\gamma T \\ & = \sum_{j=1}^{T}\left[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2\right]+\gamma T \end{aligned} Obj(t)≃j=1∑T⎣⎡(i∈Ij∑gi)wj+21(i∈Ij∑hi+λ)wj2⎦⎤+γT=j=1∑T[Gjwj+21(Hj+λ)wj2]+γT
对每列的统计数据进行并行采集，给出了一种并行的分割查找算法。重要的是，列块结构还支持列子采样，因为很容易在块中选择列的子集。
【特征选择时，并行处理列数据，XGB就是在这实现的并行化，多线程实现加速】
column subsampling表现不太稳定，sub有时好有时不好，什么时候该用sub呢？当没有重要的特征要选，每个特征值的重要性都很平均的时候，对列的subsampling效果就比较差了。
分布式的实验：在Amazon的云服务平台上用了32台m3.2xlarge搭建了一个YARN集群，数据没有放在HDFS里，放在了Amazon的S3 storage上，xgb虐了spark MLLib。
三部分：通用参数，tree booster参数，学习目标参数
params = {
'booster': 'gbtree',
'objective': 'multi:softmax',
'num_class': 10,
'gamma': 0.1,
'max_depth': 6,
'lambda': 2,
'subsample': 0.7,
'colsample_bytree': 0.7,
'min_child_weight': 3,
'silent': 1,
'eta': 0.007,
'seed': 1000,
'nthread': 4,
}
xgboost.train(params,
dtrain,
num_boost_round=10,
evals=(),
obj=None,
feval=None,
maximize=False,
early_stopping_rounds=None,
evals_result=None,
verbose_eval=True,
learning_rates=None,
xgb_model=None)
model
from sklearn.datasets import load_iris
import xgboost as xgb
from xgboost import plot_importance
from matplotlib import pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# 加载样本数据集
iris = load_iris()
X,y = iris.data,iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=1)
# 算法参数
params = {
'booster': 'gbtree',
'objective': 'multi:softmax',
# 'objective': 'reg:gamma', # 回归问题目标函数
'num_class': 3,
'gamma': 0.1,
'max_depth': 6,
'lambda': 2,
'subsample': 0.7,
'colsample_bytree': 0.7,
'min_child_weight': 3,
'silent': 1,
'eta': 0.1,
'seed': 1000,
'nthread': 4,
}
plst = params.items()
# 生成数据集格式
dtrain = xgb.DMatrix(X_train, y_train)
dtest = xgb.DMatrix(X_test)
# xgboost模型训练
num_rounds = 500
model = xgb.train(plst, dtrain, num_rounds)
# 对测试集进行预测
y_pred = model.predict(dtest)
accuracy = accuracy_score(y_test,y_pred)
print("accuarcy: %.2f%%" % (accuracy*100.0))
# 显示重要特征
plot_importance(model)
plt.show()
特征值越大，说明该特征越重要
from sklearn.datasets import load_iris
import xgboost as xgb
from xgboost import plot_importance
from matplotlib import pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# 加载样本数据集
iris = load_iris()
X,y = iris.data,iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=1)
# 训练模型
model = xgb.XGBClassifier(max_depth=5, learning_rate=0.1, n_estimators=160, silent=True, objective='multi:softmax')
model.fit(X_train, y_train)
# 对测试集进行预测
y_pred = model.predict(X_test)
accuracy = accuracy_score(y_test,y_pred)
print("accuarcy: %.2f%%" % (accuracy*100.0))
# 显示重要特征
plot_importance(model)
plt.show()
（1）先给定以下参数初始值，CV调整决策树数量
（2）调优 max_depth，min_child_weight
（3）依次 gamma，subsample ，colsample_bytree 参数调优
（4）正则化参数调优
（5）降低学习率，使用更多的决策树
参考博客
1. python机器学习案例系列教程——GBDT算法、XGBOOST算法
2. Boosting学习笔记（Adboost、GBDT、Xgboost）
3. xgboost原理
4. XGBoost 论文翻译+个人注释