CART回归树
GBDT算法无论处理回归问题还是分类问题使用的决策树都是CART回归树，原因是GBDT每次迭代要拟合的是梯度值，是一个连续值，所以要用回归树。
假设将输入空间划分为M个区域R1，R2，…，RM，并且每个区域有一个固定的输出值cm，那么回归树模型就可以写成:
$$
f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right)
$$
我们用平方误差来表示回归树的单元取值与真实值的误差，用平方误差最小准则求解每个单元上的最优输出值。
$$
\mathcal{L}=\sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}
$$
根据最小二乘法，可以很容易知道单元Rm上的cm的最优值是Rm的所有样本的输出yi的均值:
$$
\hat c_{m}=\operatorname{ave}\left(y_{i} | x_{i} \in R_{m}\right)
$$
下面的问题就是如何对输入空间作划分。这里使用启发式方法，选择第j个特征xj和它取的值s，作为切分特征和切分点，并定义两个区域:
$$
R_{1}(j, s)=[ x | x^{(j)} \leqslant s]和 R_{2}(j, s)=[x | x^{(j)}>s]
$$
然后选择所有特征中的最优切分特征j和切分点s。即求解:
$$
\min_{j, s}\left[\min_{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min_{c_{2}} \sum_{x_{i} \in R_{2}(J, s)}\left(y_{i}-c_{2}\right)^{2}\right]
$$
对某个特征j可以找到最佳切分点s:
$$
\hat c_{1}=\operatorname{ave}\left(y_{i} | x_{i} \in R_{1}(j, s)\right) 和 \hat c_{2}=\operatorname{ave}\left(y_{i} | x_{i} \in R_{2}(j, s)\right)
$$
遍历所有特征，找到所有特征中的最优切分变量j，构成一个（j,s）对，将输入空间划分成两个区域。对每个区域重复上述过程，直到满足条件为止，这样的回归树称为最小二乘回归树。
CART回归树生成算法:
- 选择最优切分变量j和切分点s，求解下式。其实这步就和CART分类树对连续值的处理类似，即先对每一个特征找到一个最佳的切分点，这个切分点把该特征切分成两个区域，且最佳切分点是这个特征的所有切分点中平方误差最小的切分点。然后我们找出所有特征的切分点中平方误差最小的切分点以及对应的特征，构成一个（j,s）对，j是特征，s是切分点；
$$
\min_{j, s}\left[\min_{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min_{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]
$$ - 用选定的（j,s）对将数据集划分成两个子区域；
$$
R_{1}(j, s)=[x | x^{(j)} \leqslant s], \quad R_{2}(j, s)=[x | x^{(j)}>s]
$$
$$
\hat c_{m}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{n}(j, s)} y_{i}, \quad x \in R_{m}, \quad m=1,2
$$ - 继续对子区域递归调用上面两个步骤，直到满足停止条件（如平方误差小于阈值/树已达到最大高度）；
- 最后得到M个区域R1，R2，…，RM，生成决策树:
$$
f(x)=\sum_{m=1}^{M} \hat c_{m} I\left(x \in R_{m}\right)
$$Gradient Boosting梯度提升树
该算法流程如下: - 初始化f0（x）=0；
- 对m=1,2,…,M，每个样本i=1,2,…,N，计算残差:
$$
r_{m i}=y_{i}-f_{m-1}(x), i=1,2, \ldots, N
$$ - 拟合残差rmi，学习一个回归树hm（x），更新:
$$
f_{m}(x)=f_{m-1}+h_{m}(x)
$$ - 循环重复上面两步算法，直到损失函数值小于阈值时停止，得到梯度提升树:
$$
f_{M}(x)=\sum_{m=1}^{M} h_{m}(x)
$$GBDT算法
GBDT树介绍
GBDT算法将梯度提升树（Gradient Boosting）和CART回归树结合起来，其主要思想是每一轮迭代使用一个新的CART回归树来拟合上一轮模型预测值与真实值的残差，具体来说，是用损失函数的负梯度作为残差近似值，每轮的CART回归树拟合这个残差近似值。GBDT算法推导
在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是ft−1（x），损失函数是L（y,ft−1（x）），我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht（x），让本轮的损失:
$$
L\left(y, f_{t}(x)=L\left(y, f_{t-1}(x)+h_{t}(x)\right)\right.
$$
达到最小。也就是说，本轮迭代找到一个CART回归树，使本轮损失变得更小。由于GBDT选择了平方损失，则损失函数可化简为:
$$
\begin{array}{c}{L\left(y, f_{t-1}(x)+h_{t}(x)\right)} \\ {=\left(y-f_{t-1}(x)-h_{t}(x)\right)^{2}} \\ {=\left(r-h_{t}(x)\right)^{2}}\end{array}
$$
其中
$$
r=y-f_{t-1}(x)
$$
是当前模型拟合数据的残差。而GDBT算法每轮生成的CART回归树就是要拟合这个残差。
上面就是GBDT的基本思路，但是没有解决损失函数拟合方法的问题。当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。
第t轮的第i个样本的损失函数的负梯度为:
$$
-\frac{\partial L(y, f(x_{i}))}{\partial (f(x_{i}))}
$$
其中:
$$
f(x)=f_{t-1}(x)
$$
此时不同的损失函数将会得到不同的负梯度，如果选择平方损失，则
$$
L(y, f(x_{i}))=\frac{1}{2}[\left(y-f(x_{i})\right)^{2}]
$$
那么负梯度就为:
$$
-\frac{\partial L(y, f(x_{i}))}{\partial (f(x_{i}))}=y-f(x_{i})
$$
其中:
$$
f(x)=f_{t-1}(x)
$$
此时我们发现GBDT的负梯度就是残差，所以说对于GBDT回归算法，我们要拟合的就是残差。GBDT回归算法
- 初始化弱学习器:
$$
f_{0}(x)=\arg \min_{c} \sum_{i=1}^{N} L\left(y_{i}, c\right)
$$ - 对m=1,2,…,M，每个样本i=1,2,…,N，计算负梯度，即残差:
$$
r_{im}=-\frac{\partial L(y, f(x_{i}))}{\partial (f(x_{i}))}
$$
其中:
$$
f(x)=f_{t-1}(x)
$$ - 将上步得到的残差作为样本新的真实值，并将数据（xi,rim），i=1,2,..N作为下棵树的训练数据，得到一颗新的回归树fm（x），其对应的叶子节点区域为Rjm,j=1,2,…,J，其中J为回归树t的叶子节点的个数；
- 对叶子区域j=1,2,..J计算最佳拟合值
$$
\Upsilon_{j m}=argmin_{\Upsilon} \sum_{x_{i} \in R_{jm}} L(y_{i}, f_{m-1}(x_{i})+\Upsilon)
$$ - 更新强学习器:
$$
f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J} \Upsilon_{j m} I\left(x \in R_{j m}\right)
$$ 重复上述生成回归树的过程，直到损失函数值小于阈值为止，得到最终的GBDT树:
$$
f(x)=f_{M}(x)=f_{0}(x)+\sum_{m=1}^{M} \sum_{j=1}^{J} \Upsilon_{j m} I\left(x \in R_{j m}\right)
$$GBDT回归算法实例
有一组数据，特征为年龄、体重，身高为标签值。共有5条数据，前四条为训练样本，最后一条为要预测的样本。 数据如下:
编号 年龄(岁) 体重(kg) 身高(m,要预测的值) 1 5 20 1.1 2 7 30 1.3 3 21 70 1.7 4 30 60 1.8 5 25 65 ?现在我们要构建GBDT树，每棵树的最大深度设为1。
初始化弱学习器:
$$
f_{0}(x)=argmin_{\gamma} \sum_{i=1}^{N} L(y_{i}, \gamma)
$$
此时只有根节点，样本1,2,3,4都在根节点，要找到使得平方损失函数最小的参数Υ，直接对L求γ的导数，令导数等于零，求得γ。
$$
\frac{\partial L(y_{i}, \gamma)}{\partial \gamma}=\frac{\partial((\frac{1}{2})|y-\gamma|^{2})}{\partial \gamma}=\gamma-y=0
$$
所以γ=y，即γ为所有训练样本标签值的均值。
$$
\gamma=\frac{1.1+1.3+1.7+1.8}{4}=1.475
$$
$$
f_{0}(x)=\gamma=1.475
$$
迭代轮数m=1时:
负梯度为:
$$
r_{i1}=-\frac{\partial L(y, f(x_{i}))}{\partial (f(x_{i}))}
$$
其中
$$
f(x)=f_{0}(x)
$$编号 身高(真实值) f0(x) 残差 1 1.1 1.475 -0.375 2 1.3 1.475 -0.175 3 1.7 1.475 0.225 4 1.8 1.475 0.325将残差作为样本的真实值训练f1（x）:
编号 年龄(岁) 体重(kg) 身高(m,要预测的值) 1 5 20 -0.375 2 7 30 -0.175 3 21 70 0.225 4 30 60 0.325寻找回归树的最佳划分点，遍历每个特征的每个可能取值。从年龄特征的5开始，到体重特征的70结束，分别计算方差，找到使方差最小的那个划分点即为最佳划分点。
划分点 小于划分点的样本 大于等于划分点的样本 总方差 年龄5 / 1，2，3，4 0.082 年龄7 1 2，3，4 0.047 年龄21 1，2 3，4 0.0125 年龄30 1，2，3 4 0.062 体重20 / 1，2，3，4 0.082 体重30 1 2，3，4 0.047 体重60 1，2 3，4 0.0125 体重70 1，2，4 3 0.0867总方差最小为0.0125有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选年龄21，划分成两个叶子节点。 我们还要给这两个叶子节点分别赋一个参数，来拟合残差。
$$
\gamma_{j 1}=\operatorname{argmin} \sum_{x_{i} \in R_{j 1}} L\left(y_{i}, f_{0}\left(x_{i}\right)+\gamma\right)
$$
类似于求f0（x），对L求γ的导数，令导数等于零，化简之后得到每个叶子节点的参数γ，其实就是标签值的均值。
样本1，2为左叶子节点，样本3，4为右叶子节点，则有:
$$
\gamma_{11}=(-0.375-0.175) / 2=-0.275
$$
$$
\gamma_{21}=(0.225+0.325) / 2=0.275
$$
此时可更新强学习器:
$$
f_{1}(x)=f_{0}(x)+\sum_{j=1}^{2} \gamma_{j 1} I\left(x \in R_{j 1}\right)
$$
对迭代轮数m=2,3,4,5,…,M，循环迭代M次，迭代结束生成M棵树，得到最后的强学习器:
$$
\begin{aligned} f(x) &=f_{M}(x)=f_{0}(x)+\sum_{m=1}^{M} \sum_{j=1}^{J} \gamma_{j m} I\left(x \in R_{j m}\right) \\ &=f_{0}(x)+\sum_{j=1}^{2} \gamma_{j 1} I\left(x \in R_{j 1}\right) \end{aligned}
$$
假如我们就如上面只迭代一次，则得到只有两颗树的GBDT树:第一棵树f0(x): 1,2,3,4 γ0=1.475 第二棵树f1(x): 1,2,3,4 γ0=1.475 / \ 1,2 3,4 γ11=-0.275 γ21=0.275预测样本5:
样本5在f0(x)中被预测为1.475；样本5年龄为25，大于划分节点21岁，在f1(x)中被分到右边叶子节点，预测为0.275。此时便得到样本5的最终预测值为1.475+0.275=1.75。GBDT分类算法
如果是GBDT分类算法，由于样本输出不是连续的值而是离散的类别，我们无法直接从输出类别去拟合类别输出的误差。我们可以用指数损失函数（此时GBDT退化为Adaboost算法）或使用对数似然损失函数。
二元GBDT分类算法
二元GBDT树如果使用对数似然函数作为损失函数，则损失函数为:
$$
L(y, f(x))=\log (1+\exp (-y f(x)))
$$
其中
$$
y \in [-1,+1]
$$
此时负梯度为
$$
r_{ti}=-\frac{\partial L(y, f(x_{i}))}{\partial (f(x_{i}))} \\ =\frac{y_{i}}{1+\exp(y_{i} f\left(x_{i}\right))}
$$
其中
$$
f(x)=f_{t-1}(x)
$$
对于每轮生成的决策树，各个叶子节点的最佳负梯度拟合值为
$$
c_{t j}=argmin_{c} \sum_{x_{i} \in R_{t j}} \log (1+\exp \left(-y_{i}\left(f_{t-1}\left(x_{i}\right)+c\right)\right))
$$
上式比较难优化，因此我们使用下式作为近似值代替
$$
c_{t j}=\frac{\sum_{x_{i} \in R_{t j}} r_{t i}}{\sum_{x_{i} \in R_{t j}}|r_{t i}|(1-\left|r_{t i}\right|)}
$$
除了上面的过程之外，二元GBDT分类算法与GBDT回归算法的过程基本相同。多元GBDT分类算法
多元GBDT算法的对数似然损失函数为:
$$
L(y, f(x))=-\sum_{k=1}^{K} y_{k} \log p_{k}(x)
$$
其中如果样本输出类别为k，则yk=1，其余的yk=0。第k类的概率pk（x）的表达式为softmax函数:
$$
p_{k}(x)=\frac{\exp \left(f_{k}(x)\right)}{\sum_{l=1}^{K} \exp \left(f_{l}(x)\right)}
$$
第t轮的第i个样本对应类别l的负梯度为
$$
r_{t i l}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right) )}{\partial f\left(x_{i}\right)}\right]_{f_{k}(x)=f_{l, t-1}(x)} \\ =y_{i l}-p_{l, t-1}\left(x_{i}\right)
$$
我们可以发现这里的负梯度就是样本i对应类别l的真实概率和t−1轮预测概率的差值。
对于生成的决策树，各个叶子节点的最佳负梯度拟合值为
$$
c_{t j l}=\underbrace{\arg \min}_{c_{j l}} \sum_{i=0}^{m} \sum_{k=1}^{K} L\left(y_{k}, f_{t-1, l}(x)+\sum_{j=0}^{J} c_{j l} I\left(x_{i} \in R_{t j l}\right)\right)
$$
上式比较难优化，因此我们使用下式作为近似值代替
$$
c_{t j l}=\frac{K-1}{K} \frac{\sum_{x_{i} \in R_{t j}} r_{t i l}}{\sum_{x_{i} \in R_{t i l}}\left|r_{t i l}\right|\left(1-\left|r_{t i l}\right|\right)}
$$GBDT的正则化
GBDT的正则化主要有三种方式:
第一种是增加学习率，即:
$$
f_{k}(x)=f_{k-1}(x)+\eta h_{k}(x)
$$
η的取值范围为0<η≤1。学习率如果过大（取1）很容易一步学到位导致过拟合。- 第二种是设置子采样比例，取值为(0,1]。这里的子采样和随机森林不一样，这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间；
- 第三种是对于弱学习器即CART回归树进行正则化剪枝。
GBDT的优缺点
优点：
- 可以做回归，也可以做分类；
- 相对与SVM，调参时间较少，预测的准确率也比较高；
- 对异常值的鲁棒性较好。
缺点：
- 由于弱学习器之间存在依赖关系，难以并行训练数据。
XGBoost算法
XGBoost算法介绍
xgboost算法的步骤和GBDT算法基本相同，不同于GBDT算法的是，GBDT算法只利用了一阶导数信息（负梯度ri，也可以说是对损失函数只做了一阶的泰勒展开），而xgboost同时利用了一阶导数gi和二阶导数hi（也可以说是对损失函数做二阶泰勒展开），迭代M轮生成M轮CART回归树，并在目标函数之外加入正则项整体求最优解，用以权衡目标函数的下降和模型复杂程度，避免过拟合。
XGBoost目标函数的推导
同GBDT算法类似，XGBoost算法也可以看成是由K棵树组成的加法模型：
$$
\hat y_{i}=\sum_{k=1}^{K} f_{k}(x_{i}), f_{k} \in F
$$
其中F是指所有基模型组成的函数空间（即深度学习中的假设空间）。
损失函数可写为：
$$
L=\sum_{i=1}^{n} l\left(y_{i}, \hat y_{i}\right)
$$
最小化损失函数就相当于最小化模型的偏差，但同时我们也需要兼顾模型的方差，所以目标函数还包括抑制模型复杂度的正则项。
目标函数可以写成：
$$
O b j=\sum_{i=1}^{n} l\left(y_{i}, \hat y_{i}\right)+\sum_{k=1}^{K} \Omega\left(f_{k}\right)
$$
其中Ω代表了基模型的复杂度，若基模型是树模型，则树的深度、叶子节点数等指标可以反应树的复杂程度。
模型的学习过程:
同GBDT算法的学习过程类似，每一轮迭代生成一棵新的CART回归树，用来拟合残差近似值，只是XGBoost的残差近似值是损失函数的二阶泰勒展开。过程如下:
$$
\begin{aligned} \hat y_{i}^{0} &=0 \\ \hat y_{i}^{1} &=f_{1}\left(x_{i}\right)=\hat y_{i}^{0}+f_{1}\left(x_{i}\right) \\ \hat y_{i}^{2} &=f_{1}\left(x_{i}\right)+f_{2}\left(x_{i}\right)=\hat y_{i}^{1}+f_{2}\left(x_{i}\right) \\ & \cdots \\ \hat y_{i}^{t} &=\sum_{k=1}^{t} f_{k}\left(x_{i}\right)=\hat y_{i}^{t-1}+f_{t}\left(x_{i}\right) \end{aligned}
$$
在每一步中如何决定加入哪一个函数f呢？指导原则还是最小化目标函数。
在第t步，模型对xi的预测为:
$$
\hat y_{i}^{t}=\hat y_{i}^{t-1}+f_{t}\left(x_{i}\right)
$$
其中第一项是保留的前面t-1轮的模型预测结果，第二项ft（xi）为这一轮我们要学习的函数。则目标函数可写为:
$$
\begin{aligned} O b j^{(t)} &=\sum_{i=1}^{n} l\left(y_{i}, \hat y_{i}^{t}\right)+\sum_{i=i}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n} l\left(y_{i}, \hat y_{i}^{t-1}+f_{t}\left(x_{i}\right)\right)+\Omega\left(f_{t}\right)+\text {constant } \end{aligned}
$$
我们的目标是找到ft函数。假如损失函数为平方损失，则目标函数为:
$$
\begin{aligned} O b j^{(t)} &=\sum_{i=1}^{n}\left(y_{i}-\left(\hat y_{i}^{t-1}+f_{t}\left(x_{i}\right)\right)\right)^{2}+\Omega\left(f_{t}\right)+\text { constant } \\ &=\sum_{i=1}^{n}\left[2\left(\hat y_{i}^{t-1}-y_{i}\right) f_{t}\left(x_{i}\right)+f_{t}\left(x_{i}\right)^{2}\right]+\Omega\left(f_{t}\right)+\text {constant } \end{aligned}
$$
其中:
$$
\left(\hat y_{i}^{t-1}-y_{i}\right)
$$
称之为残差。
使用平方损失函数时，XGBoost算法的每一步在生成决策树时只需要拟合前面的模型的残差。
如果损失函数不是平方损失时，采用二阶泰勒展开来近似表示残差。
二阶泰勒公式:
$$
f(x+\Delta x) \approx f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^{2}
$$
目标函数是关于变量:
$$
\hat y_{i}^{t-1}+f_{t}\left(x_{i}\right)
$$
的函数，若把变量:
$$
\hat y_{i}^{t-1}
$$
看成是泰勒公式中的x，把变量ft（xi）看成是泰勒公式中的Δx，那么上面的目标函数可以展开为:
$$
O b j^{(t)}=\sum_{i=1}^{n}\left[l\left(y_{i}, \hat y_{i}^{t-1}\right)+g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right)+\text{constant}
$$
其中
$$
g_{i}=\partial_{\hat y^{t-1}} l\left(y_{i}, \hat y^{t-1}\right)
$$
$$
h_{i}=\partial_{\hat y^{t-1}}^{2} l\left(y_{i}, \hat y^{t-1}\right)
$$
分别是损失函数的一阶导数和二阶导数。
移除常数项（真实值与上一轮的预测值之差），则目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数:
$$
O b j^{(t)} \approx \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right)
$$
XGBoost正则化项与回归树分裂规则推导
XGBoost的每一棵树都是CART回归树，但是回归树的分裂规则与一般回归树不同。
定义CART回归树表示如下:
$$
f_{t}(x)=w_{q(x)}, w \in R^{T}, q : R^{d} \rightarrow{1,2, \cdots, T}
$$
树拆分成结构函数q（输入x输出叶子节点索引）和叶子权重部分w（输入叶子节点索引输出叶子节点分数），结构函数q把输入映射到叶子的索引号上面去，而w给定了每个索引号对应的叶子分数是什么。 wq（x）即这棵树对样本x的预测值。
正则化项:
$$
\Omega(f)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}
$$
T是一棵树里面叶子节点的个数，以及每个叶子节点上面预测值的L2模平方。 γ和λ，这是xgboost自己定义的，在使用xgboost时，你可以设定它们的值，γ越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大。λ越大也是越希望获得结构简单的树。
带有正则化项的目标函数可以化简为:
$$
\begin{aligned} O b j^{(t)} \simeq \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\ =\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \\ =\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned}
$$
其中Ij被定义为每个叶子上面样本集合。即:
$$
I_{j}={i | q\left(x_{i}\right)=j}
$$
定义Gj（每个叶子节点里面一阶梯度的和）Hj（每个叶子节点里面二阶梯度的和）:
$$
G_{j}=\sum_{i \in I_{j}} g_{i} \quad H_{j}=\sum_{i \in I_{j}} h_{i}
$$
则目标函数可写为:
$$
\mathrm{obj}^{(t)}=\sum_{j=1}^{T}\left[G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2}\right]+\gamma T
$$
对于第t棵CART树的某一个确定的结构（可用q(x)表示），所有的Gj和Hj都是确定的。而且上式中各个叶子节点的值wj之间是互相独立的。上式其实就是一个简单的二次式，我们很容易求出各个叶子节点的最佳值以及此时目标函数的值。
令上面目标函数的一阶导数为0（对wj求导），则叶子节点j对应的值为：
$$
w_{j}=-\frac{G_{j}}{H_{j}+\lambda}
$$
则目标函数的值为:
$$
obj=-\frac{1}{2} \sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T
$$
Obj代表了当我们指定一个树是某个结构时，我们在目标函数值上最多减少多少，看上面公式就知道obj只和Gj和Hj和T有关，而它们又只和树的结构q（x）有关，与叶子节点的值无关。
总结一下单棵决策树的生成过程:
- 枚举所有可能的树结构q；
- 用上面最后的目标函数表达式为每个q计算其对应的目标函数分数，分数越小说明对应的树结构越好；
- 根据上一步的结果，找到最佳的树结构，用上面的wj表达式为树的每个叶子节点计算预测值。
然而，可能的树结构数量是无穷的，实际上我们不可能枚举所有可能的树结构。通常情况下，我们采用贪心策略来生成决策树的每个节点:
- 从深度为0的树开始，对每个叶节点枚举所有的可用特征；
- 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益），其实这个就是决策树中遇到连续值特征时找到最佳划分点的做法。每个特征的特征值排序的时间复杂度为O（nlogn），假设共用K个特征，那么生成一颗深度为K的树的时间复杂度为O（Knlogn）。
- 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集；
- 回到第1步，递归执行到满足特定条件为止。
上面的步骤就是一个CART回归树的生成过程，只是寻找特征切分点的准则不同。假设当前节点记为C，分裂之后左孩子节点记为L，右孩子节点记为R，则以C点位切分点的的分裂收益定义为当前节点的目标函数值减去左右两个孩子节点的目标函数值:
$$
G a i n=O b j_{C}-O b j_{L}-O b j_{R}
$$
即:
$$
\operatorname{Gain}=\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]-\gamma
$$
其中，-γ项表示因为增加了树的复杂性（该分裂增加了一个叶子节点）带来的惩罚。
收益如果是正的，并且值越大，表示切分后obj值小于单节点的obj，所以收益值越大，就越值得切分。同时，收益的左半部分如果小于右侧的γ，则Gain就是负的，表明切分后obj反而变大了。γ在这里实际上是一个临界值，它的值越大，表示我们对切分后obj下降幅度要求越严。这个值也是可以在xgboost中设定的。
XGBoost算法过程
总结GBDT的学习算法过程:
- 算法每次迭代生成一颗新的决策树；
- 每次迭代开始之前，计算损失函数在每个训练样本点的一阶导数和二阶导数；
- 通过贪心策略生成新的决策树，通过wj表达式计算每个叶节点对应的预测值；
- 把新生成的决策树添加到模型中：
$$
\hat y_{i}^{t}=\hat y_{i}^{t-1}+f_{t}\left(x_{i}\right)
$$
通常在最后一步，我们把模型更新公式替换为:
$$
\hat y_{i}^{t}=\hat y_{i}^{t-1}+\eta f_{t}\left(x_{i}\right)
$$
其中η称之为步长或者学习率。增加因子的目的是为了避免模型过拟合。
XGBoost算法优点
与GBDT相比，XGBoost有以下改进:
- GBDT以传统CART作为基分类器，而XGBoost支持线性分类器；
- GBDT在优化时只用到一阶导数，XGBoost对代价函数做了二阶泰勒展开，同时使用了一阶导数和二阶导数；
- 当样本存在缺失值时，XGBoost能自动学习分裂方向；
- XGBoost借鉴了随机森林的做法，随机抽取一部分特征来拟合回归树，这样不仅能防止过拟合，还能降低计算；
- XGBoost的代价函数引入正则化项，控制了模型的复杂度，正则化项包含全部叶子节点的个数，每个叶子节点输出的score的L2模的平方和。从贝叶斯方差的角度考虑，正则项降低了模型的方差，防止模型过拟合；
- XGBoost在每次迭代之后，为叶子结点分配学习速率，降低每棵树的权重，减少每棵树的影响，为后面的模型提供更好的学习空间；
- XGBoost工具支持并行,但并不是树的生成上并行，而是在特征的值排序上并行。XGBoost在迭代之前，先对特征进行预排序，存为block结构，每次迭代，重复使用该结构，降低了模型的计算。block结构也为模型提供了并行可能，在进行结点的分裂时，计算每个特征的增益，选增益最大的特征进行下一步分裂，那么各个特征的增益可以开多线程进行；
- 可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，使用近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂。
