GBDT原理与实践-多分类篇

摘要：

GBDT-分类
GBDT-回归
前面两篇文章已经详细介绍了在回归和分类下的GBDT算法。这一篇文章将最后介绍一个多分类任务的GBDT。其过程和二分类的GBDT类似，但是有一个地方有很大的不同，下文将详细的介绍。

正文：

下图是Friedman在论文中对GBDT多分类给出的伪代码：

---

从代码上看，大致和分类时候的过程一样。最大的不同点在于多了一层内部的循环For。

这里需要注意的是：
1.对于多分类任务，GDBT的做法是采用一对多的策略（详情见文章）。
也就是说，对每个类别训练M个分类器。假设有K个类别，那么训练完之后总共有M*K颗树。
2.两层循环的顺序不能改变。也就是说，K个类别都拟合完第一颗树之后才开始拟合第二颗树，不允许先把某一个类别的M颗树学习完，再学习另外一个类别。

---

算法6使用的是多分类常用的损失函数：
L({yk,Fk(x)}K1)=−∑Kk=1yklogpk(x)$L\left(\{y_k,F_k(x){\}}_1^K\right)=-\sum _{k=1}^K{y}_{k}log{p}_k(x)$
其中pk(x)=eFk(x)∑Kl=1eFl(x)$p_k(x)=\frac{e^{F_k(x)}}{\sum _{l=1}^K{e}^{F_l(x)}}$（softmax)
对损失函数求一阶导有：
ỹ ik=−[∂L({yil,Fl(x)}Kl=1)∂Fk(xi)]{Fl(x)=Fl,m−1(x)}K1=yik−pk,m−1(xi)${\tilde{y}}_{ik}=-{\left[\frac{\mathrm{\partial }L\left(\{y_{il},F_l(x){\}}_{l=1}^K\right)}{\mathrm{\partial }{F}_k(x_i)}\right]}_{\{F_l(x)=F_{l,m-1}(x){\}}_1^K}=y_{ik}-p_{k,m-1}(x_i)$。
叶子节点的更新值为：
γjkm=K−1K∑xi∈Rjkmỹ ik∑xi∈Rjkm|ỹ ik|(1−|ỹ ik|)${\gamma }_{jkm}=\frac{K-1}{K}\frac{\sum _{x_i\in R_{jkm}}{\tilde{y}}_{ik}}{\sum _{x_i\in R_{jkm}}|{\tilde{y}}_{ik}|(1-|{\tilde{y}}_{ik}|)}$

---

下面以一个简单的数据集说明整个GBDT的流程。

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
yi$y_i$	0	0	0	0	0	1	1	1	1	1	2	2	2	2

由于我们需要转化3个二分类的问题，所以需要先做一步one-hot：

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
yi$y_i$	0	0	0	0	0	1	1	1	1	1	2	2	2	2
yi,1$y_{i,1}$	1	1	1	1	1	0	0	0	0	0	0	0	0	0
yi,2$y_{i,2}$	0	0	0	0	0	1	1	1	1	1	0	0	0	0
yi,3$y_{i,3}$	0	0	0	0	0	0	0	0	0	0	1	1	1	1

为了方便说明，作以下设置：
1. 树的深度为1
2. 学习率1

首先进行初始化Fk0(xi)=0$F_{k0}(x_i)=0$，对所有的样本。
注意：在Friedman论文里全部初始化为0，但在sklearn里是初始化先验概率（就是各类别的占比）

---

对第一个类别（yi=0$y_i=0$)拟合第一颗树(m=1)$(m=1)$。

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
yi,1$y_{i,1}$	1	1	1	1	1	0	0	0	0	0	0	0	0	0

利用pk,m(x)=eFk,m(x)∑Kl=1eFl,m(x)$p_{k,m}(x)=\frac{e^{F_{k,m}(x)}}{\sum _{l=1}^K{e}^{F_{l,m}(x)}}$

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
p1,0$p_{1,0}$	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333

下面计算负梯度值，以x1$x_1$为例(k=1,i=1)$(k=1,i=1)$：
ỹ ik=yi,k−pk,m−1${\tilde{y}}_{ik}=y_{i,k}-p_{k,m-1}$
=>ỹ 11=y1,1−p1,0=1−0.3333=0.6667${\tilde{y}}_{11}=y_{1,1}-p_{1,0}=1-0.3333=0.6667$
同样地，计算其他样本可以有下表：

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
ỹ i1${\tilde{y}}_{i1}$	0.6667	0.6667	0.6667	0.6667	0.6667	-0.3333	-0.3333	-0.3333	-0.3333	-0.3333	-0.3333	-0.3333	-0.3333	-0.3333

以ỹ i1${\tilde{y}}_{i1}$拟合一颗回归树，（以31为分裂点）

---

这里简单补充一下，为什么选择31作为分裂点。
在GBDT的建树中，可以采用如MSE，MAE等作为分裂准则来确定分裂点（启发式）。而本文采用的分裂准则是MSE，具体计算过程如下。
遍历所有特征的取值，将每个特征值依次作为的分裂点，然后计算左子结点与右子结点上的MSE，寻找两者加和最小的一个。

比如，选择1作为分裂点时(x<1)。
左子结点上的集合的MSE为:MSEleft=(−0.3333−(−0.3333)2=0$MS{E}_{left}=(-0.3333-(-0.3333{)}^2=0$
右子节点上的集合的MSE为:
MSEright=(0.6667−0.02384)2+(0.6667−0.02384)2+.....+(−0.3333−0.02384)2=3.2142$MS{E}_{right}=(0.6667-0.02384{)}^2+(0.6667-0.02384{)}^2+.....+(-0.3333-0.02384{)}^2=3.2142$
故总的MSE为:MSE=MSEleft+MSEright=0+3.2142=3.2142$MSE=MS{E}_{left}+MS{E}_{right}=0+3.2142=3.2142$

比如选择2作为分裂点时(x<2)。
MSEleft=0,MSEright=3.07692,MSE=3.07692$MS{E}_{left}=0,MS{E}_{right}=3.07692,MSE=3.07692$

计算完后可以发现，当选择31做为分裂点时，可以得到最小的MSE，MSE=1.42857$MSE=1.42857$

---

和前面文章类似，分别计算γjkm${\gamma }_{jkm}$可得：
γ111=1.1428${\gamma }_{111}=1.1428$，γ211=−0.9999${\gamma }_{211}=-0.9999$

更新Fkm(xi)=Fk,m−1(xi)+η∗∑xi∈Rjkmγjkm∗I(xi∈Rjkm)$F_{km}(x_i)=F_{k,m-1}(x_i)+\eta \ast \sum _{x_i\in R_{jkm}}{\gamma }_{jkm}\ast I(x_i\in R_{jkm})$可得下表：

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
F1,1(xi)$F_{1,1}(x_i)$	1.1428	1.1428	1.1428	1.1428	1.1428	-0.999	-0.999	-0.999	1.1428	1.1428	-0.999	-0.999	-0.999	-0.999

至此第一个类别（类别0）的第一颗树拟合完毕，下面开始拟合第二个类别（类别1）的第一颗树：

---

对第二个类别（yi=1$y_i=1$)拟合第一颗树(m=1)$(m=1)$。

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
yi,2$y_{i,2}$	0	0	0	0	0	1	1	1	1	1	0	0	0	0

利用pk,m(x)=eFk,m(x)∑Kl=1eFl,m(x)$p_{k,m}(x)=\frac{e^{F_{k,m}(x)}}{\sum _{l=1}^K{e}^{F_{l,m}(x)}}$

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
p2,0$p_{2,0}$	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333	0.3333

下面计算负梯度值，以x1$x_1$为例(k=2,i=1)$(k=2,i=1)$：
ỹ ik=yi,k−pk,m−1${\tilde{y}}_{ik}=y_{i,k}-p_{k,m-1}$
=>ỹ 12=y1,2−p2,0=0−0.3333=−0.3333${\tilde{y}}_{12}=y_{1,2}-p_{2,0}=0-0.3333=-0.3333$
同样地，计算其他样本可以有下表：

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
ỹ i2${\tilde{y}}_{i2}$	-0.3333	-0.3333	-0.3333	-0.3333	-0.3333	0.6667	0.6667	0.6667	0.6667	0.6667	-0.3333	-0.3333	-0.3333	-0.3333

以ỹ i2${\tilde{y}}_{i2}$拟合一颗回归树，（以6为分裂点）,可计算得到叶子节点：
γ121=2${\gamma }_{121}=2$，γ221=−0.2499${\gamma }_{221}=-0.2499$
更新Fkm(xi)=Fk,m−1(xi)+η∗∑xi∈Rjkmγjkm∗I(xi∈Rjkm)$F_{km}(x_i)=F_{k,m-1}(x_i)+\eta \ast \sum _{x_i\in R_{jkm}}{\gamma }_{jkm}\ast I(x_i\in R_{jkm})$可得下表：

xi$x_i$	6	12	14	18	20	65	31	40	1	2	100	101	65	54
F2,1(xi)$F_{2,1}(x_i)$	-0.2499	-0.2499	-0.2499	-0.2499	-0.2499	-0.2499	-0.2499	-0.2499	2	2	-0.2499	-0.2499	-0.2499	-0.2499

然后再拟合第三个类别（类别2）的第一颗树，过程也是重复上述步骤，所以这里就不再重复了。在拟合完所有类别的第一颗树后就开始拟合第二颗树。反复进行，直到训练了M轮。

总结

至此，GBDT回归与分类就完整的说了一遍了。在多分类里面不打算分析Sklearn源码是因为其实现和Frieman论文里面步骤有一点不太一样。

————————
感谢网友们对本文的阅读以及宝贵的意见！特别感谢网友@guo15996278092提出的宝贵意见！