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

1. GBDT分类算法简介

GBDT无论用于分类还是回归，一直使用的是CART回归树。GBDT不会因为我们所选择的任务是分类任务就选用分类树，这里的核心原因是GBDT每轮的训练是在上一轮训练模型的负梯度值基础之上训练的。这就要求每轮迭代的时候，真实标签减去弱分类器的输出结果是有意义的，即残差是有意义的。如果选用的弱分类器是分类树，类别相减是没有意义的。对于这样的问题，可以采用两种方法来解决：

• 一是采用指数损失函数，这样GBDT就退化成了Adaboost，能够解决分类的问题；
• 二是使用类似于逻辑回归的对数似然损失函数，如此可以通过结果的概率值与真实概率值的差距当做残差来拟合；

下面我们就通过二分类问题，去看看GBDT究竟是如何做分类的。

2. GBDT二分类算法

2.1 逻辑回归的对数损失函数

逻辑回归的预测函数为：

函数 的值有特殊的含义，它表示结果取 的概率，因此对于输入 分类结果为类别 和类别 的概率分别为：


下面我们根据上式，推导出逻辑回归的对数损失函数 。上式综合起来可以写成：

然后取似然函数为：

因为 和 在同一 处取得极值，因此我们接着取对数似然函数为：

最大似然估计就是求使 取最大值时的 。这里对 取相反数，可以使用梯度下降法求解，求得的 就是要求的最佳参数：

2.2 GBDT二分类原理

逻辑回归单个样本 的损失函数可以表达为：

其中， 是逻辑回归预测的结果。假设GBDT第 步迭代之后当前学习器为 ，将 替换为 带入上式之后，可将损失函数写为：

其中，第 棵树对应的响应值为（损失函数的负梯度，即伪残差）：

对于生成的决策树，计算各个叶子节点的最佳残差拟合值为：

由于上式没有闭式解（closed form solution），我们一般使用近似值代替：

补充近似值代替过程：
假设仅有一个样本：
令 ，则
求一阶导：

求二阶导：

对于 的泰勒二阶展开式：

取极值时，上述二阶表达式中的c为：

GBDT二分类算法完整的算法过程如下：
（1）初始化第一个弱学习器 ：

其中， 是训练样本中 的比例，利用先验信息来初始化学习器。
（2）对于建立棵分类回归树 :
a）对 ，计算第 棵树对应的响应值（损失函数的负梯度，即伪残差）：

b）对于 ，利用CART回归树拟合数据 ，得到第 棵回归树，其对应的叶子节点区域为 ，其中 ，且 为第棵回归树叶子节点的个数。
c）对于 个叶子节点区域 ，计算出最佳拟合值：

d）更新强学习器 ：

（3）得到最终的强学习器 的表达式：

从以上过程中可知，除了由损失函数引起的负梯度计算和叶子节点的最佳残差拟合值的计算不同，二元GBDT分类和GBDT回归算法过程基本相似。那二元GBDT是如何做分类呢？
将逻辑回归的公式进行整理，我们可以得到 ，其中，也就是将给定输入 预测为正样本的概率。逻辑回归用一个线性模型去拟合 这个事件的对数几率（odds）。二元GBDT分类算法和逻辑回归思想一样，用一系列的梯度提升树去拟合这个对数几率，其分类模型可以表达为：

3. GBDT二分类算法实例

（1）数据集介绍

训练集如下表所示，一组数据的特征有年龄和体重，把身高大于1.5米作为分类边界，身高大于1.5米的令标签为1，身高小于等于1.5米的令标签为0，共有4组数据。

测试数据如下表所示，只有一组数据，年龄为25、体重为65，我们用在训练集上训练好的GBDT模型预测该组数据的身高是否大于1.5米？

（2）模型训练阶段

参数设置：

• 学习率：learning_rate = 0.1
• 迭代次数：n_trees = 5
• 树的深度：max_depth = 3

1）初始化弱学习器：

2）对于建立M棵分类回归树：
由于我们设置了迭代次数：n_trees=5，这就是设置了M=5。
首先计算负梯度，根据上文损失函数为对数损失时，负梯度（即伪残差、近似残差）为：

我们知道梯度提升类算法，其关键是利用损失函数的负梯度的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。这里，为了称呼方便，我们把负梯度叫做残差。
现将残差的计算结果列表如下：

此时将残差作为样本的标签来训练弱学习器 ，即下表数据：

接着寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。从年龄特征值为5开始，到体重特征为70结束，分别计算分裂后两组数据的平方损失（Square Error）， 为左节点的平方损失， 为右节点的平方损失，找到使平方损失和 最小的那个划分节点，即为最佳划分节点。
例如：以年龄7为划分节点，将小于7的样本划分为到左节点，大于等于7的样本划分为右节点。左节点包括 ，右节点包括样本 ， ， ， ，所有可能的划分情况如下表所示：

以上划分点的总平方损失最小为0.000，有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选年龄21。现在我们的第一棵树长这个样子：

我们设置的参数中树的深度max_depth=3，现在树的深度只有2，需要再进行一次划分，这次划分要对左右两个节点分别进行划分，但是我们在生成树的时候，设置了三个树继续生长的条件：

• 深度没有到达最大。树的深度设置为3，意思是需要生长成3层。
• 点样本数 >= min_samples_split
• 此节点上的样本的标签值不一样（如果值一样说明已经划分得很好了，不需要再分）（本程序满足这个条件，因此树只有2层）

最终我们的第一棵回归树长下面这个样子：

此时我们的树满足了设置，还需要做一件事情，给这棵树的每个叶子节点分别赋一个参数，来拟合残差。

根据上述划分结果，为了方便表示，规定从左到右为第1,2个叶子结点，其计算值过程如下：


此时的第一棵树长下面这个样子：

接着更新强学习器，需要用到学习率：learning_rate=0.1，用表示。更新公式为：

为什么要用学习率呢？这是Shrinkage的思想，如果每次都全部加上拟合值 ，即学习率为1，很容易一步学到位导致GBDT过拟合。
重复此步骤，直到结束，最后生成5棵树。


第一棵树：

第二棵树：

第三棵树：

第四棵树：

第五棵树：

3）得到最后的强学习器：

（3）模型预测阶段

• 
• 在 中，测试样本的年龄为25，大于划分节点21岁，所以被预测为2.0000。
• 在 中，测试样本的年龄为25，大于划分节点21岁，所以被预测为1.8187。
• 在 中，测试样本的年龄为25，大于划分节点21岁，所以被预测为1.6826。
• 在 中，测试样本的年龄为25，大于划分节点21岁，所以被预测为1.5769。
• 在 中，测试样本的年龄为25，大于划分节点21岁，所以被预测为1.4927。

最终预测结果为：