xgboost二元分类和多元分类原理总结

1. Xgboost能够解决的问题：

Xgboost能够解决二元分类、多元分类、回归问题。

二元分类案例：

输入输出:

每个人是一个样本，样本数量n是5

每个人有m个特征，有age, male/female ......

输出y为0不喜欢打游戏，1喜欢打游戏

模型训练：通过训练集生成树和树叶的权重

每棵树初始时从m个属性中选取一个开始进行分裂，经几次分叉后，形成T个叶子，每个叶子根据属性的划分，是一定量样本的集合，共用叶子的权重wj。

一棵树分叉完成后，进行下一棵树的分叉。

模型应用:

将同样带有m个特征的样本，输入到生成的树，找到这个样本在每棵树所属的叶子，将所有权重wj相加，得到预测值yi, 二元分类yi经过sigmoid函数后和阈值比较输出0或1，多元分类yi经过softmax函数，得到属于某一类型的最大概率，输出某一类型的值。

xgboost可以处理的特征属性：

输入值可能有连续属性、二元属性、标称属性（类型比二元多）、序数属性（衣码小中大号等）

2. 模型训练1：树的分叉

刚读xgboost原理 https://arxiv.org/pdf/1603.02754.pdf 的时候会有困惑，为什么2.2小节能够同时得到树的结构和书的权值，实际上是先通过3节讲的树的分裂得到树结构，然后才有公式（4）的演进。

传统决策树举例：

CART选择Gini系数划分树杈，Gini系数代表不纯度，为0时称作0不纯度，用来将样本进行分类后度量不纯度，选取不纯度小的分杈方法，CART用二分法来规避分叉过多带来的零不纯度。

$Gini(t)=1-\sum_{0}^{c}{p(i)}^2$

Decision Tree: https://blog.csdn.net/bjjoy2009/article/details/80841657

xgboost 树模型：

将梯度算法引入到树模型优化中，分叉度量公式不再是GINI系数，而是用每个样本的gi, hi（是由上一棵树估值后与实际值比较得到的权重，来代入到当前树的生成中。gi和hi分别将在后面的第3小节进行介绍，是损失函数的一阶导数和二阶导数，仅与上一棵树生成后的预估值和实际值有关。

贪婪算法：遍历所有m个属性，遍历第m个属性可能的分叉方式，选取最大的Lsplit分叉方式。Score是分叉前的OBJ减去分叉后OBJ左和OBJ右，当Lsplit小于0，则不分叉，大于0则分叉, 因此 $\gamma$ 是在树模型建立的时候，较大则不容易分叉，较小则容易分叉。

近似算法：设置切分点，比如三分位数：排序后选取1/3点，2/3做为切分点。参考xgboost 权值3.2小节

Global:学习每棵树前就提出候选切分点，并在每次分列式都采用这种分割，需要更多的候选点

Local：每次分裂前将重新提出候选切分点，需要的计算步骤。

3. 模型训练2：梯度下降法求得样本权重和叶子权重

对于每个样本，将各个树的叶子节点的和作为预测值可以表示为：

对于损失函数:

损失函数 $l$ 并没有固定是哪种函数，所以可以处理回归和分类问题，后续进行归纳总结。

正则表达是是二项式，为防止过拟合，是所有叶节点权值的平方和。

经过泰勒展开：

需要注意到的是，这个公式的时候树是已经分好的，有多少个节点，对于样本i在哪个j节点，是已经固定好了，这个公式就是用来求叶子的权值

可以看到这个时候的损失函数只有 $G , H$ ，可以用于2模型训练1：树的分叉中。

4. 损失函数的选择：'objective'：

流程是：将样本i在每棵树上的wj权重求和，得到的y作为预测值，将y代入到Obj函数中，再代入到评价函数logloss中，即是损失函数 $l$ .

a. 二元分类器 binary:logistic:

目标函数sigmoid： $y_x$ $=\frac{1}{1+e^{-x}}$ ，一阶导数： $y_{x}^‘ =\frac{e^{-x}}{\left(1+e^{-x}\right)^2}=y_x(1-y_x)$

评价函数eval_metric： $Logloss=-(ylog(p)+(1-y)log(1-p))$ ，代入sigmoid函数如下：

$Logloss(y_i,\widehat{y_i})=(y_iln(1+e^{-\widehat{y_i}})+(1-y_i)log(1+e^{\widehat{y_i}}))$

一阶导数 $g_i=\partial_{y_i^{(t-1)}}l(y_i,{\hat{y}}_i^{(t-1)})=-y_i(1-\frac{1}{1+e^{-{\hat{y}}_i^{t-1}}})+(1-y_i)\frac{1}{1+e^{-{\hat{y}}_i^{t-1}}}=P_i^{t-1}-y_i$

二阶导数 $h_i=\partial_{y_i^{(t-1)}}^2l(y_i,{\hat{y}}_i^{(t-1)})=\ \frac{e^{-{\hat{y}}_i^{t-1}}}{\left(1+e^{-{\hat{y}}_i^{t-1}}\right)^2}=P_i^{t-1}(1-P_i^{t-1})$

分类器输出：https://blog.csdn.net/u014033218/article/details/90516849

binary:logistic和 'objective': 'reg:logistic'的输出是一样的,都是预测的概率

binary:logitraw是输出的得分，用sigmoid（）函数处理后就和上述两个概率值一致

XGBClassifier里就是把预测的概率值，取阈值0.5，小于这个值的为0，大于这个值的为1，

b. 多元分类器 multi:softmax:

目标函数softmax: $p_i=\frac{e^{{\hat{y}}_i}}{\sum_{j}e^{{\hat{y}}_j}}$

def softmax(x): e =np.exp(x) return e / np.sum(e)

求导： $\partial_{y_i}p(y_i)=p_i.(1-p_i)\$ $i=j$ ;

$\partial_{y_i}p(y_i)=-p_i.p_j\$ $i\neq j$

评价函数mlogloss: $logloss=-\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{M}{y_{ij}log(p_{i,j})}$

只针对第i个样本可以得到 $logloss=-\sum_{}{y_{j}log(p_{j})}$

N：样本数; M：类别数; $y_{ij}$ ：第i个样本属于分类j时为为1，否则为0;

$p_{ij}$ ：第i个样本被预测为第j类的概率 (平均为1/j), 即softmax输出的第j个layer

一阶导数： $\frac{\partial logloss}{\partial{\hat{y}}_i}=\sum_{j}\frac{\partial logloss}{\partial p_j}.\frac{\partial p_j}{\partial{\hat{y}}_i}=\frac{\partial logloss}{\partial p_i}.\frac{\partial p_i}{\partial{\hat{y}}_c}+\sum_{j\neq i}\frac{\partial logloss}{\partial p_j}.\frac{\partial p_j}{\partial{\hat{y}}_i}$

$=-{y_i.\frac{1}{p_i}.p}_i(1-p_i)+\sum_{j\neq i}{\frac{-y_j}{p_j}\left(-1\right).p_i.p_j=-}y_i+{y_ip}_i+\sum_{j\neq i}{y_j.p_i}=p_i-y_i$

二阶导数： $\frac{\partial^2logloss}{\partial^2{\hat{y}}_i}=p_i.(1-p_i)$

代码：https://github.com/dmlc/xgboost/blob/master/demo/guide-python/custom_softmax.py

多元分类输出: https://blog.csdn.net/phyllisyuell/article/details/81011660

我们这里以标签为0,1,2的三分类数据为例。

每个类别有独立的树，有对应的wjc, j是第几片叶子，c是第几个类别的树。

multi：softmax是使用softmax后产生的分类结果，输出为0，1，2。

multi:softprob是y通过softmax后输出的概率矩阵，输出的是n*3的概率矩阵（n为测试数据的条数）。

选取最大概率的赋予对应的类别eg[0.34,0.56，0.42],对应softmax类别1.

多元分类的泰勒展开：经过推导，改进这篇，多分类原理https://www.jianshu.com/p/2698db68f2e7

1

这个地方不同样本i 在不同的分类树上有不同的I集合，属于两个叶子节点，不能用一个j来合并。

而应该在后求导时，就选取对类别c求导，将iwn与 iwc分离后再进行I集合合并。

对类别1进行求导， $g_{i1}=\frac{e^{{yi1}^{t-1}}}{\sum e^{{\rm yin}^{t-1}}}-y_{i1}^{t-1}$ ； $h_{in}=\frac{e^{{yi1}^{t-1}}}{\sum e^{{\rm yin}^{t-1}}}*(1-\frac{e^{{yi1}^{t-1}}}{\sum e^{{\rm yin}^{t-1}}})=\frac{1}{\sum e^{{\rm yin}^{t-1}}}$

$\frac{d\ \sum_{j=1}^{Tn}\left\{\sum_{i\ inIj}{\left(g_{i1}+h*\sum_{n=0and\ n\neq1}^{N-1}w_{in}\right)*w_{j1}+\frac{1}{2}}\left(h+\lambda_1\right)*w_{j1}^2\right\}}{dw_{j1}}=0$

当多元分类， $\sum_{n=0and\ n\neq1}^{N-1}w_{in}$ 可以忽略？？即可以得到 $w_{j1}=-\frac{\sum_{i\ inI j}g_{i1}}{\sum_{i\ inIj}h_{i1}+\lambda_1}$

需要进一步查看到代码得到如何实现。

https://github.com/dmlc/xgboost/blob/master/python-package/xgboost/training.py

c. 线性回归 reg:linear 没有找到资料

损失函数RMSE均方根误差：

5. xgboost parameter https://xgboost.readthedocs.io/en/latest/parameter.html

gamma：用于控制是否后剪枝的参数,越大越保守，一般0.1、0.2这样子

max_depth：树的深度，对结果影响较大，越深越容易过拟合

alpha：L1正则，树的深度过大时，可以适大该参数

lambda：L2正则，控制模型复杂度的权重值的L2正则化项参数，参数越大，模型越不容易过拟合。

subsample：随机采样的比率，通俗理解就是选多少样本做为训练集，选择小于1的比例可以减少方差，即防止过拟合

colsample_bytree：这里是选择多少列作为训练集，具体的理解就是选择多少特征

min_child_weight：决定最小叶子节点样本权重和。当它的值较大时，可以避免模型学习到局部的特殊样本。但如果这个值过高，会导致欠拟合

eta：学习率

silent:是否打印训练过程中的信息，0表示打印，1反之

nthread：运行的线程数，-1所有线程，该值需要根据具体情况调整，线程对最终结果有一点影响，曾今测试，线程越多，结果会变差一丢丢

seed：这个随机指定一个常数，防止每次结果不一致

'nthread':7, cpu线程数

https://www.csdn.net/gather_2f/MtTacgwsOTY1NTItYmxvZwO0O0OO0O0O.html

6.工程演示在另一篇

7.并行计算：

当生成下一棵树时，所有样本的权重gi hi是可以通过当前树的预测值和实际值得到。因为要确定最佳分割点，需要提前对特征值进行排序，计算每个特征分裂后的增益，选择增益最大的特征取分类，xgboost可以在训练下一棵树前预先计算好每个特征在不同切分点的增益，并对数据进行排序，保存为block的结构，迭代中重复使用这个结构，因此各个特征的增益计算就可以多线程并行进行。

8. 遗留问题：

缺失值处理：对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向

第一棵树的生成 http://iphil.cc/?p=482

多元分类的w求导凸函数公式

回归损失函数的推导