梯度提升树（GBDT）算法-多分类

1.算法原理

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

2. GBDT多分类算法实例

（1）数据集

（2）模型训练阶段
首先，由于我们需要转化3个二分类的问题，所以需要先做一步one-hot：

参数设置：
学习率：learning_rate = 1
树的深度：max_depth = 2
迭代次数：n_trees = 5
首先对所有的样本，进行初始化 ，就是各类别在总样本集中的占比，结果如下表。

注意：在Friedman论文里全部初始化为0，但在sklearn里是初始化先验概率（就是各类别的占比），这里我们用sklearn中的方法进行初始化。
1）对第一个类别 拟合第一颗树 。

首先，利用公式 计算概率。
其次，计算负梯度值，以 为例 ：


同样地，计算其它样本可以有下表：接着，寻找回归树的最佳划分节点。在GBDT的建树中，可以采用如MSE、MAE等作为分裂准则来确定分裂点。本文采用的分裂准则是MSE，具体计算过程如下。遍历所有特征的取值，将每个特征值依次作为分裂点，然后计算左子结点与右子结点上的MSE，寻找两者加和最小的一个。
比如，选择 作为分裂点时 。
左子结点上的集合的MSE为：

右子节点上的集合的MSE为：

比如选择 作为分裂点时 。

对所有特征计算完后可以发现，当选择 做为分裂点时，可以得到最小的MSE， 。
下图展示以 为分裂点的 拟合一颗回归树的示意图：

然后，我们的树满足了设置，还需要做一件事情，给这棵树的每个叶子节点分别赋一个参数 （也就是我们文章提到的 ），来拟合残差。


最后，更新 可得下表：


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

首先，利用 计算概率。
其次，计算负梯度值，以 为例 ：

同样地，计算其它样本可以有下表：

然后，以 为分裂点的 拟合一颗回归树，可计算得到叶子节点：
，
最后，更新 可得下表：


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