决策树之 GBDT 算法 - 分类部分

上一次我们一起学习了 GBDT 算法的回归部分，今天我们继续学习该算法的分类部分。使用 GBDT 来解决分类问题和解决回归问题的本质是一样的，都是通过不断构建决策树的方式，使预测结果一步步的接近目标值。

因为是分类问题，所以分类 GBDT 和回归 GBDT 的 Loss 函数是不同的，具体原因我们在《深入理解逻辑回归》 一文中有分析过，下面我们来看下分类 GBDT 的 Loss 函数。

Loss 函数

和逻辑回归一样，分类 GBDT 的 Loss 函数采用的也是 Log Likelihood：
L = arg ⁡ min ⁡ [ ∑ i n − ( y i log ⁡ ( p i ) + ( 1 − y i ) log ⁡ ( 1 − p i ) ) ] L = \arg\min\left[\sum_i^n-( y_i\log(p_i)+(1-y_i)\log(1-p_i) )\right] L=argmin[i∑n​−(yi​log(pi​)+(1−yi​)log(1−pi​))]
其中，n 表示有 n 条样本， y i y_i yi​ 为第 i 条样本的观察值（或目标值），该值要么是 0，要么是 1； p i p_i pi​ 为模型对第 i 个样本的预测值，它是一个取值范围为 [0,1] 之间的概率，现在我们来看下该 Loss 是否可导，只用看"求和符号 $\sum$" 里面的部分是否可导即可，如下：
l = − y i log ⁡ ( p i ) − ( 1 − y i ) log ⁡ ( 1 − p i ) = − y i log ⁡ ( p i ) − log ⁡ ( 1 − p i ) − y i log ⁡ ( 1 − p i ) = − y i ( log ⁡ ( p i 1 − p i ) ) − log ⁡ ( 1 − p i ) \begin{aligned} l&=-y_i\log(p_i) - (1-y_i)\log(1-p_i)\\ &=-y_i\log(p_i)-\log(1-p_i)-y_i\log(1-p_i)\\ &=-y_i(\log(\frac{p_i}{1-p_i}))-\log(1-p_i) \end{aligned} l​=−yi​log(pi​)−(1−yi​)log(1−pi​)=−yi​log(pi​)−log(1−pi​)−yi​log(1−pi​)=−yi​(log(1−pi​pi​​))−log(1−pi​)​
把上面式子中的 p 用 log(odds) 来表示，即用 log ⁡ ( o d d s i ) \log(odds_i) log(oddsi​) 来替换 log ⁡ ( p i / ( 1 − p i ) ) \log(p_i/(1-p_i)) log(pi​/(1−pi​))，用 e log ⁡ ( o d d s i ) / ( 1 + e log ⁡ ( o d d s i ) ) e^{\log(odds_i)}/(1+e^{\log(odds_i)}) elog(oddsi​)/(1+elog(oddsi​)) 来替换 p i p_i pi​（对 log(odds) 不熟悉的同学，可以先阅读深入理解逻辑回归一文），如下：
l = − y i log ⁡ ( o d d s i ) − log ⁡ ( 1 − e log ⁡ ( o d d s i ) 1 + e log ⁡ ( o d d s i ) ) = − y i log ⁡ ( o d d s i ) − log ⁡ ( 1 1 + e log ⁡ ( o d d s i ) ) = − y i log ⁡ ( o d d s i ) + log ⁡ ( 1 + e log ⁡ ( o d d s i ) ) \begin{aligned} l&= -y_i\log(odds_i) - \log(1-\frac{e^{\log(odds_i)}}{1+e^{\log(odds_i)}}) \\&=- y_i\log(odds_i) - \log(\frac{1}{1+e^{\log(odds_i)}}) \\&=-y_i\log(odds_i)+\log(1+e^{\log(odds_i)}) \end{aligned} l​=−yi​log(oddsi​)−log(1−1+elog(oddsi​)elog(oddsi​)​)=−yi​log(oddsi​)−log(1+elog(oddsi​)1​)=−yi​log(oddsi​)+log(1+elog(oddsi​))​
我们再对其求导：
d l d log ⁡ ( o d d s ) = − y i + e log ⁡ ( o d d s i ) 1 + e log ⁡ ( o d d s i ) \frac{dl}{d\log(odds)} = -y_i + \frac{e^{\log(odds_i)}}{1+e^{\log(odds_i)}} dlog(odds)dl​=−yi​+1+elog(oddsi​)elog(oddsi​)​
右边的 e l o g ( o d d s i ) / ( 1 + e l o g ( o d d s i ) ) e^{log(odds_i)}/(1+e^{log(odds_i)}) elog(oddsi​)/(1+elog(oddsi​)) 正好又是 p i p_i pi​，所以 l ′ ( log ⁡ ( o d d s ) ) l'(\log(odds)) l′(log(odds)) 又等于 − y i + p i -y_i+p_i −yi​+pi​，注意，这两种形式后面都会用到。可见，这个 loss 函数是可导的，该分类算法可以用梯度下降来求解。

构建分类 GBDT 的步骤依然是下面两个：

1. 初始化 GBDT
2. 循环生成决策树

下面我们来一一说明：

初始化 GBDT

和回归问题一样，分类 GBDT 的初始状态也只有一个叶子节点，该节点为所有样本的初始预测值，如下：
F 0 ( x ) = arg ⁡ min ⁡ γ ∑ i = 1 n L ( y , γ ) F_0(x) = \arg\min_{\gamma}\sum_{i=1}^n L(y,\gamma) F0​(x)=argγmin​i=1∑n​L(y,γ)
上式中，F 代表 GBDT 模型， F 0 F_0 F0​ 为模型的初始状态，该式子意为：找到一个 $\gamma$，使所有样本的 Loss 最小，在这里及下文中，$\gamma$ 都表示节点的输出，且它是一个 log(odds) 形式的值，在初始状态，$\gamma$ 又是 F 0 F_0 F0​。

我们还是用一个最简单的例子来说明该步骤，假设我们有以下 3 条样本：

我们希望构建 GBDT 分类树，它能通过「喜欢爆米花」、「年龄」和「颜色偏好」这 3 个特征来预测某一个样本是否喜欢看电影，因为是只有 3 个样本的极简数据集，所以我们的决策树都是只有 1 个根节点、2 个叶子节点的树桩（Stump），但在实际应用中，决策树的叶子节点一般为 8-32 个。

我们把数据代入上面的公式中求 Loss：
$$Loss=L(1,\gamma )+L(1,\gamma )+L(0,\gamma )$$
为了使其最小，我们对它求导，并令结果等于 0：
$$(-1+p)+(-1+p)+(0+p)=0$$
于是初始值 $p=2/3=0.67$，$\gamma =\log (2)=0.69$，模型的初始状态 F 0 ( x ) F_0(x) F0​(x) 为 0.69。

说了一大堆，实际上你却可以很容易的算出该模型的初始值，它就是正样本数比上负样本数的 log 值，例子中，正样本数为 2 个，负样本为 1 个，那么：
F 0 ( x ) = log ⁡ ( p o s i t i v e _ c o u n t n e g a t i v e _ c o u n t ) = log ⁡ ( 2 1 ) = 0.69 F_0(x)=\log(\frac{positive\_count}{negative\_count}) = \log(\frac{2}{1}) = 0.69 F0​(x)=log(negative_countpositive_count​)=log(12​)=0.69

循环生成决策树

和回归 GBDT 一样，分类 GBDT 第二步也可以分成四个子步骤：(A)、(B)、©、(D)，我们把它写成伪代码：

for m = 1 to M:(A)(B)(C)(D)

其中 m 表示第 m 棵树，M 为树的个数上限，我们先来看 (A)：

(A)：计算
r i m = − [ ∂ L ( y i , F ( x i ) ) ∂ F ( x i ) ] F ( x ) = F m − 1 ( x ) r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F(x)=F_{m-1}(x)} rim​=−[∂F(xi​)∂L(yi​,F(xi​))​]F(x)=Fm−1​(x)​
此处为使用 m-1 棵树的模型，计算每个样本的残差 r i m r_{im} rim​，这里的偏微分实际上就是求每个样本的梯度，因为梯度我们已经计算过了，即 − y i + p i -y_i+p_i −yi​+pi​，那么 r i m = y i − p i r_{im}=y_i-p_i rim​=yi​−pi​，于是我们的例子中，每个样本的残差如下：

这样，第 (A) 小步就完成了。

(B)：使用回归树来拟合 r i m r_{im} rim​，回归树的构建过程可以参照《CART 回归决策树》一文。我们产生的第 2 棵决策树（此时 m=1）如下：

©：对每个叶子节点 j，计算
γ j m = arg ⁡ min ⁡ γ ∑ x ∈ R i j L ( y i , F m − 1 ( x i ) + γ ) \gamma_{jm} = \arg\min_{\gamma}\sum_{x\in R_{ij}} L(y_i, F_{m-1}(x_i) + \gamma) γjm​=argγmin​x∈Rij​∑​L(yi​,Fm−1​(xi​)+γ)
意思是，在刚构建的树 m 中，找到每个节点 j 的输出 γ j m \gamma_{jm} γjm​，能使该节点的 Loss 最小。

左边节点对应第 1 个样本，我们把它带入到上式得：
L ( y 1 , F m − 1 ( x 1 ) + γ ) = − y 1 ( F m − 1 ( x 1 ) + γ ) + log ⁡ ( 1 + e F m − 1 ( x 1 ) + γ ) L(y_1,F_{m-1}(x_1)+\gamma)=-y_1(F_{m-1}(x_1)+\gamma) + \log(1+e^{F_{m-1}(x_1)+\gamma}) L(y1​,Fm−1​(x1​)+γ)=−y1​(Fm−1​(x1​)+γ)+log(1+eFm−1​(x1​)+γ)
对上式直接求导较为复杂，这里的技巧是先使用二阶泰勒公式来近似表示该式，再求导：把 $\gamma$ 作为变量，其余项作为常量的二阶泰勒展开式如下：
L ( y 1 , F m − 1 ( x 1 ) + γ ) ≈ L ( y 1 , F m − 1 ( x 1 ) ) + L ′ ( y 1 , F m − 1 ( x 1 ) ) γ + 1 2 L ′ ′ ( y 1 , F m − 1 ( x 1 ) ) γ 2 L(y_1,F_{m-1}(x_1)+\gamma)\approx L(y_1,F_{m-1}(x_1)) + L'(y_1,F_{m-1}(x_1))\gamma + \frac{1}{2}L''(y_1,F_{m-1}(x_1))\gamma^2 L(y1​,Fm−1​(x1​)+γ)≈L(y1​,Fm−1​(x1​))+L′(y1​,Fm−1​(x1​))γ+21​L′′(y1​,Fm−1​(x1​))γ2
这时再求导就简单了：
d L d γ = L ′ ( y 1 , F m − 1 ( x 1 ) ) + L ′ ′ ( y 1 , F m − 1 ( x 1 ) ) γ \frac{dL}{d\gamma} = L'(y_1,F_{m-1}(x_1)) + L''(y_1,F_{m-1}(x_1))\gamma dγdL​=L′(y1​,Fm−1​(x1​))+L′′(y1​,Fm−1​(x1​))γ
Loss 最小时，上式等于 0，于是我们可以求出 $\gamma$
γ 11 = − L ′ ( y 1 , F m − 1 ( x 1 ) ) L ′ ′ ( y 1 , F m − 1 ( x 1 ) ) \gamma_{11} = \frac{-L'(y_1,F_{m-1}(x_1))}{L''(y_1,F_{m-1}(x_1))} γ11​=L′′(y1​,Fm−1​(x1​))−L′(y1​,Fm−1​(x1​))​
可以看出，上式的分子就是残差 r，下面我们算一下分母，即 Loss 函数的二阶微分：
L ′ ′ ( y 1 , F ( x ) ) = d L ′ d log ⁡ ( o d d s ) = d d log ⁡ ( o d d s ) [ − y i + e log ⁡ ( o d d s ) 1 + e log ⁡ ( o d d s ) ] = d d log ⁡ ( o d d s ) [ e log ⁡ ( o d d s ) ( 1 + e log ⁡ ( o d d s ) ) − 1 ] = e log ⁡ ( o d d s ) ( 1 + e log ⁡ ( o d d s ) ) − 1 − e 2 log ⁡ ( o d d s ) ( 1 + e log ⁡ ( o d d s ) ) − 2 = e log ⁡ ( o d d s ) ( 1 + e log ⁡ ( o d d s ) ) 2 \begin{aligned} L''(y_1,F(x)) &= \frac{dL'}{d\log(odds)}\\ &=\frac{d}{d\log(odds)}\left[-y_i + \frac{e^{\log(odds)}}{1+e^{\log(odds)}}\right]\\ &=\frac{d}{d\log(odds)}\left[e^{\log(odds)}(1+e^{\log(odds)})^{-1}\right]\\ &=e^{\log(odds)}(1+e^{\log(odds)})^{-1} - e^{2\log(odds)}(1+e^{\log(odds)})^{-2}\\ &=\frac{e^{\log(odds)}}{(1+e^{\log(odds)})^2} \end{aligned} L′′(y1​,F(x))​=dlog(odds)dL′​=dlog(odds)d​[−yi​+1+elog(odds)elog(odds)​]=dlog(odds)d​[elog(odds)(1+elog(odds))−1]=elog(odds)(1+elog(odds))−1−e2log(odds)(1+elog(odds))−2=(1+elog(odds))2elog(odds)​​
我们知道， e log ⁡ ( o d d s ) / ( 1 + e log ⁡ ( o d d s ) ) e^{\log(odds)}/(1+e^{\log(odds)}) elog(odds)/(1+elog(odds)) 就是 p，而 1 / ( 1 + e log ⁡ ( o d d s ) ) 1/(1+e^{\log(odds)}) 1/(1+elog(odds)) 是 1-p，所以 L ′ ′ = p ( 1 − p ) L''=p(1-p) L′′=p(1−p)，那么该节点的输出就是
γ 11 = r 11 p 10 ( 1 − p 10 ) = 0.33 0.67 × 0.33 = 1.49 \gamma_{11} = \frac{r_{11}}{p_{10}(1-p_{10})}=\frac{0.33}{0.67\times0.33} = 1.49 γ11​=p10​(1−p10​)r11​​=0.67×0.330.33​=1.49
接着我们来计算右边节点的输出，它包含样本 2 和样本 3，同样使用二阶泰勒公式展开：
L ( y 2 , F m − 1 ( x 2 ) + γ ) + L ( y 3 , F m − 1 ( x 3 ) + γ ) ≈ L ( y 2 , F m − 1 ( x 2 ) ) + L ′ ( y 2 , F m − 1 ( x 2 ) ) γ + 1 2 L ′ ′ ( y 2 , F m − 1 ( x 2 ) ) γ 2 + L ( y 3 , F m − 1 ( x 3 ) ) + L ′ ( y 3 , F m − 1 ( x 3 ) ) γ + 1 2 L ′ ′ ( y 3 , F m − 1 ( x 3 ) ) γ 2 \begin{aligned} &L(y_2,F_{m-1}(x_2)+\gamma) + L(y_3,F_{m-1}(x_3)+\gamma)\\ &\approx L(y_2,F_{m-1}(x_2)) +L'(y_2,F_{m-1}(x_2))\gamma + \frac{1}{2}L''(y_2,F_{m-1}(x_2))\gamma^2\\ &+L(y_3,F_{m-1}(x_3)) +L'(y_3,F_{m-1}(x_3))\gamma + \frac{1}{2}L''(y_3,F_{m-1}(x_3))\gamma^2 \end{aligned} ​L(y2​,Fm−1​(x2​)+γ)+L(y3​,Fm−1​(x3​)+γ)≈L(y2​,Fm−1​(x2​))+L′(y2​,Fm−1​(x2​))γ+21​L′′(y2​,Fm−1​(x2​))γ2+L(y3​,Fm−1​(x3​))+L′(y3​,Fm−1​(x3​))γ+21​L′′(y3​,Fm−1​(x3​))γ2​
对上式求导，令其结果为 0，可以计算 $\gamma$ 为
γ 21 = − L ′ ( y 2 , F m − 1 ( x 2 ) ) − L ′ ( y 3 , F m − 1 ( x 3 ) ) L ′ ′ ( y 2 , F m − 1 ( x 2 ) ) + L ′ ′ ( y 3 , F m − 1 ( x 3 ) ) = r 21 + r 31 p 20 ( 1 − p 20 ) + p 30 ( 1 − p 30 ) = 0.33 − 0.67 0.67 × 0.33 + 0.67 × 0.33 = − 0.77 \begin{aligned} \gamma_{21} &= \frac{-L'(y_2,F_{m-1}(x_2))-L'(y_3,F_{m-1}(x_3))}{L''(y_2,F_{m-1}(x_2))+L''(y_3,F_{m-1}(x_3))}\\ &=\frac{r_{21}+r_{31}}{p_{20}(1-p_{20}) + p_{30}(1-p_{30})}\\ &=\frac{0.33-0.67}{0.67\times 0.33 + 0.67\times 0.33}\\ &= -0.77 \end{aligned} γ21​​=L′′(y2​,Fm−1​(x2​))+L′′(y3​,Fm−1​(x3​))−L′(y2​,Fm−1​(x2​))−L′(y3​,Fm−1​(x3​))​=p20​(1−p20​)+p30​(1−p30​)r21​+r31​​=0.67×0.33+0.67×0.330.33−0.67​=−0.77​
这样，© 步骤即完成了。可以看出，对任意叶子节点，我们可以直接计算其输出值：
γ j m = ∑ i = 1 R i j r i m ∑ i = 1 R i j p i , m − 1 ( 1 − p i , m − 1 ) \gamma_{jm} = \frac{\sum_{i=1}^{R_{ij}} r_{im}}{\sum_{i=1}^{R_{ij}} p_{i,m-1}(1-p_{i,m-1})} γjm​=∑i=1Rij​​pi,m−1​(1−pi,m−1​)∑i=1Rij​​rim​​
(D)：更新模型 F m ( x ) F_m(x) Fm​(x)
F m ( x ) = F m − 1 ( x ) + ν ∑ j = 1 J m γ m F_m(x) = F_{m-1}(x) + \nu \sum_{j=1}^{J_m} \gamma_m Fm​(x)=Fm−1​(x)+νj=1∑Jm​​γm​
仔细观察该式，实际上它就是梯度下降——「加上残差」和「减去梯度」这两个操作是等价的，这里设学习率 $\nu$ 为 0.1，则 3 个样本更新如下：

可见，样本 1 和样本 3 都离正确的方向更进了一步，虽然样本 2 更远了，但我们可以造更多的树来弥补该差距。

最终，循环 M 次后，或总残差低于预设的阈值时，我们的分类 GBDT 建模便完成了。

总结

本文主要介绍了分类 GBDT 的原理，具体有以下 2 个方面：

1. 分类 GBDT 的 Loss 函数
2. 构建分类 GBDT 的详细步骤

本文的公式比较多，但稍加耐心，你会发现它其实并不复杂。

参考：

• Gradient Boost Part 4: Classification Details
• 泰勒公式

相关文章：

• 决策树之 GBDT 算法 - 回归部分
• 深入理解逻辑回归算法（Logistic Regression）
• 决策树算法之分类回归树 CART（Classification and Regression Trees）【1】
• 决策树算法之分类回归树 CART（Classification and Regression Trees）【2】

联系博主：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！