XGboost加法模型
$$
\hat{y_i}^{(t)}=\sum_{j=1}^tf_j(\pmb{x_i})=\sum_{j=1}^{t-1}f_j(\pmb{x_i})+f_t(\pmb{x_i})=\hat{y_i}^{(t-1)}+f_t(\pmb{x_i})
$$
其中，每个$f_j(\cdot)$都是一个决策树，$f_j \in \mathcal{F}$。XGboost使用前向分布算法，采取贪心策略逐棵树进行优化。在优化第t棵树$f_t(\cdot)$时，前面的t-1棵树都已经是确定的函数。
构造目标函数
在XGboost模型中，目标函数由损失函数和正则项构成。损失函数$\mathcal{L}(y_i,\cdot)$是任意的可微函数，可根据实际需要选择合适的损失函数。而正则项量化了每一棵树的复杂程度，以便对树的复杂性加以限制防止过拟合。
$$
obj=\sum_{i=1}^n\mathcal{L}(y_i,\hat{y_i}^{(t)})+\sum_{j=1}^t\Omega(f_j)
$$
因为前t-1棵树已经是确定的函数，故将目标函数改写成如下形式：
$$
obj=\sum_{i=1}^n\mathcal{L}(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+[\sum_{j=1}^{t-1}\Omega(f_j)]+\Omega(f_t)
$$
损失函数的二阶泰勒展开
损失函数$\mathcal{L}(y_i,\cdot)$是任意的可微函数，则为了方便计算对其泰勒展开至二阶：
$$
\mathcal{L}(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))\approx\mathcal{L}(y_i,\hat{y_i}^{(t-1)})+\mathcal{L}^{'}(y_i,\hat{y_i}^{(t-1)})f_t(x_i)+\frac{1}{2}\mathcal{L}^{''}(y_i,\hat{y_i}^{(t-1)})[f_t(x_i)]^2
$$
正则项的公式
我们认为，一棵决策树的复杂程度与其叶节点的个数，以及每个节点的权重有关。节点越多，每个节点的权重越大，则复杂性越大。故我们构造一下的正则项：
$$
\Omega(f_t)=\gamma L^{(t)}+\frac{1}{2}\lambda \sum_{j=1}^{L^{(t)}}{\omega_j^2}
$$
其中$\gamma$和$\lambda$是两个超参数，用来调节惩罚力度
目标函数的变形
由此，我们可以对目标函数做如下变形：
1、将总的求和变为每个节点求和之后再求和
2、带入损失函数的二阶泰勒展开式和正则项
$$
obj=\sum_{j=1}^{L^{(t)}}\sum_{i \in I_j}{\{\mathcal{L}(y_i,\hat{y_i}^{(t-1)})+\mathcal{L}^{'}(y_i,\hat{y_i}^{(t-1)})f_t(x_i)+\frac{1}{2}\mathcal{L}^{''}(y_i,\hat{y_i}^{(t-1)})[f_t(x_i)]^2}\}+\gamma L^{(t)}+\frac{1}{2}\lambda \sum_{j=1}^{L^{(t)}}{\omega_j^2}
$$
又因为：
1、$\mathcal{L}(y_i,\hat{y_i}^{(t-1)})$是常数，在优化时不受影响，不妨删去
2、$\sum_{j=1}^{L^{(t)}}\sum_{i \in I_j}{f_t(x_i)}=\sum_{j=1}^{L^{(t)}}{\omega_j}$
3、令$\mathcal{L}^{'}(y_i,\hat{y_i}^{(t-1)})=g_i$，$\mathcal{L}^{''}(y_i,\hat{y_i}^{(t-1)})=h_i$
故目标函数可改写为：
$$
obj=\gamma L^{(t)}+\sum_{j=1}^{L^{(t)}}{\{\omega_j[\sum_{i \in I_j}g_i]+\frac{1}{2}\omega_j^2[\lambda+\sum_{i \in I_j}{h_i}]\}}
$$
再令$\sum_{i \in I_j}g_i=G_i$，$\sum_{i \in I_j}h_i=H_i$，则obj可简化为：
$$
obj=\gamma L^{(t)}+\sum_{j=1}^{L^{(t)}}{\{\omega_jG_i+\frac{1}{2}\omega_j^2[\lambda+H_i]\}}
$$
故：
$$
(\omega_1,\omega_2,...,\omega_{L^{(t)}})=arg \mathop{\min}\limits_{(\omega_1,\omega_2,...,\omega_{L^{(t)}})}\gamma L^{(t)}+\sum_{j=1}^{L^{(t)}}{\{\omega_j[\sum_{i \in I_j}g_i]+\frac{1}{2}\omega_j^2[\lambda+\sum_{i \in I_j}{h_i}]\}}
$$
令：
$$
\frac{\partial obj}{\partial\pmb{\omega}}=0
$$
可解得，对于每一个$j$，$\omega_j=-\frac{G_j}{H_j+\lambda}$时，目标函数最小，带入可得$obj_{min}=\gamma L^{(t)}+\sum_{j=1}^{L^{(t)}}{-\frac{1}{2}\frac{G_j}{H_j+\lambda}}$
结论
对于一棵形态已经固定的树，对每个节点$j$的权重$\omega_j$取$-\frac{G_j}{H_j+\lambda}$的时候目标函数最小，$obj_{min}=\gamma L^{(t)}+\sum_{j=1}^{L^{(t)}}{-\frac{1}{2}\frac{G_j}{H_j+\lambda}}$
树结构的调整
我们已经知道对于一个确定结构的决策树，我们可以算出每个叶子节点的权重使得目标函数值最小。但是在创建新的决策树的时候结构是未知的。故现在我们的目标变成确定树的结构。一种简单的想法是穷举出所有可能的树的结构，并且比较每棵树的$obj_{min}$，再找到其中的最小值$(obj_{min})_{min}$，该值对应的树即为我们想要的树。
然而这种方法计算量十分庞大，在数据量较大的情况下是不可行的。实际应用中我们采用的是“精确贪心算法”，对每个叶子节点进行分裂。如果分裂后的obj有所减小，则保留该次分裂。之后还可以对分裂后的叶子节点再进行分裂，依次类推。
精确贪心算法
对于分裂前的叶子节点，可以通过模型计算出该节点的$G$与$H$，且该节点的$\omega=-\frac{G}{H+\lambda}$，$obj=\lambda \times1-\frac{1}{2}\frac{G}{H+\lambda}$
则其分裂出左右两个叶节点后，$obj_{new}=\lambda \times2-\frac{1}{2}\frac{G_L}{H_L+\lambda}-\frac{1}{2}\frac{G_R}{H_R+\lambda}$
则：
$$
gain=obj-obj_{new}=\frac{1}{2}[\frac{G_L}{H_L+\lambda}+\frac{G_R}{H_R+\lambda}-\frac{G}{H+\lambda}]-\lambda
$$
则如果$gain>0$，就继续分裂，否则就不分裂。
选择分裂的介值
选择分裂的介值，即考虑该节点选择以哪个特征，以多少为介值将原节点分为两个新的叶子节点。常规方法就是使用两层循环，遍历每个特征的每个可能的取值，然后分别算出$gain$的值，取$gain_{min}$对应的分类方法即可。
为了简化计算的一些优化操作
列采样
即在众多的特征中随机挑选一个或多个特征进行计算，而不是对所有的特征都进行计算。列采样又可分为桉树随机与按层随机，其中按树随机是指在同一棵树种，采样的特征值都是相同的，而按层随机是指在同一棵树中，每层都会重新随机挑选分类使用的特征。
特征值分桶
即不再按每一个特征值进行划分，而是按照特征值的分位数进行划分，例如，按照10,20,…,90分位数进行划分。
加权分位法
对目标函数进行变形：
$$
obj=\sum_{i=1}^n\{\mathcal{L}(y_i,\hat{y_i}^{(t-1)})+\mathcal{L}^{'}(y_i,\hat{y_i}^{(t-1)})f_t(\pmb{x_i})+\frac{1}{2}\mathcal{L}^{''}(y_i,\hat{y_i}^{(t-1)})[f_t(\pmb{x_i})]^2\} +[\sum_{j=1}^{t-1}\Omega(f_j)]+\Omega(f_t)\\=\sum_{i=1}^n\{\mathcal{L}(y_i,\hat{y_i}^{(t-1)})+g_i\cdot f_t(\pmb{x_i})+\frac{1}{2}h_i\cdot [f_t(\pmb{x_i})]^2\} +[\sum_{j=1}^{t-1}\Omega(f_j)]+\Omega(f_t)
$$
因为最后看的是obj的变化量，故这里obj加上或减去常数项都无所谓，故：
$$
obj\Rightarrow\sum_{i=1}^n\{g_i\cdot f_t(\pmb{x_i})+\frac{1}{2}h_i\cdot [f_t(\pmb{x_i})]^2\}+\Omega(f_t)\\\Rightarrow\sum_{i=1}^n\{g_i\cdot f_t(\pmb{x_i})+\frac{1}{2}h_i\cdot [f_t(\pmb{x_i})]^2\}\\ \Rightarrow\sum_{i=1}^n\{\frac{1}{2}\frac{g_i^2}{h_i}+g_i\cdot f_t(\pmb{x_i})+\frac{1}{2}h_i\cdot [f_t(\pmb{x_i})]^2\}\\
\Rightarrow\sum_{i=1}^n{\frac{1}{2}h_i(f_t(\pmb{x_i})-(-\frac{g_i}{h_i}))^2}
$$
发现每个样本贡献对目标函数的贡献率是不同的，贡献率的大小由系数$h_i$来体现。故在进行介值的选择的时候可以按照加权的分位数进行划分，权重位$h_i$
学习率
XGboost中加入了步长$\eta$，即：
$$
\hat{y_i}^{(t)}=\hat{y_i}^{(t-1)}+\eta f_t(\pmb{x_i})
$$
$\eta$一般取0.1，这样有助于防止过拟合的问题。
XGboost的优缺点
优点：
- 简单易用。相对其他机器学习库，用户可以轻松使用XGBoost并获得相当不错的效果。
- 高效可扩展。在处理大规模数据集时速度快效果好，对内存等硬件资源要求不高。
- 鲁棒性强。相对于深度学习模型不需要精细调参便能取得接近的效果。
- XGBoost内部实现提升树模型，可以自动处理缺失值。
缺点：
- 相对于深度学习模型无法对时空位置建模，不能很好地捕获图像、语音、文本等高维数据。
- 在拥有海量训练数据，并能找到合适的深度学习模型时，深度学习的精度可以遥遥领先XGBoost。
XGboost实例
安装并载入所需的R包
1
2
3
4
5
6
7
8
9
10
|
if (!require(xgboost)){
install.packages("xgboost")
}
if (!require(caret)){
install.packages("caret")
}
library(xgboost)
library(caret)
library(Matrix)
|
选取数据集，并将数据集进行划分
1
2
3
4
5
6
7
8
|
# 选取鸢尾花数据集，这是R语言自带的一个多分类数据集
data(iris)
# 将数据集的80%分为训练集，剩下20%作为测试集
data(iris)
trainlist <- createDataPartition(iris$Species, p = 0.8, list = F)
trainset <- iris[trainlist,]
testset <- iris[-trainlist,]
|
从数据集构建xgb.DMatrix对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# 读取自变量矩阵
traindata1 <- data.matrix(trainset[,c(1:4)])
# 将自变量矩阵转化为系数矩阵的形式
traindata2 <- Matrix(traindata1,sparse=T)
# 将分类变量转为数字0,1,2...
train_y <- as.numeric(trainset[,5])-1
# 将自变量和因变脸拼接为list
traindata <- list(data=traindata2,label=train_y)
# 构造模型所需要的xgb.DMatrix对象
dtrain <- xgb.DMatrix(data = traindata$data,label=traindata$label)
# 对测试集也按相同步骤构建xgb.DMatrix对象
testdata1 <- data.matrix(testset[,c(1:4)])
testdata2 <- Matrix(testdata1,sparse=T)
test_y <- as.numeric(testset[,5])-1
testdata <- list(data=testdata2,label=test_y)
dtest <- xgb.DMatrix(data = testdata$data,label=testdata$label)
|
构建模型
1
2
3
4
5
6
7
8
9
10
|
# 构建模型。这里是多分类变量的预测，故损失函数选择softmax，分类数选择3。
model_xgb <- xgboost(
data = dtrain,
boost = 'gbtree',
max_depth = 4,
eta = 0.1,
objective = 'multi:softmax',
num_class = 3,
nround = 50
)
|
模型预测与效果评估
1
2
3
4
5
6
|
# 模型预测
pre <- predict(model_xgb, newdata = dtest)
# 模型评估
xgb.cf <- caret::confusionMatrix(as.factor(pre),as.factor(test_y))
xgb.cf
|
