决策树-GBDT-RF-Xgboost

决策树算法有很多良好的特性，比如可以直观的展示模型，适用于非线性分类等。但是单决策树容易过拟合，于是人们采用剪枝的办法来尽量减少这种情况。后来出现将模型组合（boosting，bagging）与决策树结合，使几百颗简单的决策树组合在一起，组合后的分类器很强大，不容易过拟合。常见的两种基本形式有GBDT和随机森林（RF）。而xgboost是eXtreme Gradient Boosting，xgboost最大的特点在于，它能够自动利用CPU的多线程进行并行，同时在算法上加以改进提高了精度。接下来一一介绍三种算法。

1.GBDT

GBDT(Gradient Boost Decision Tree)又叫MART(Multiple Additive Regression Tree)，GBRT(Gradient Boost Regression Tree)，Tree Net等。

先讲一下Gradient Boost与传统的Boost的不同，传统的Boost是给每个样本赋一个权值，然后每次分错的样本的权值会增大，分对的样本的权值就会减小，进行M此迭代后，将M个弱分类器组合在一起，组合为一个强分类器，其中分类正确率高的弱分类器的权值比较大，分类正确率低的分类器的权值小。而Gradient Boost每次迭代的目标是为了减少上一次的残差(residual)，在残差减少的梯度(Gradient)方向上建立一个新的模型。也就是说，在Gradient Boost中，每个新的模型的建立是使之前模型的残差往梯度方向减少，与传统Boost对正确、错误的样本进行加权有着很大的区别。

GBDT主要的思想是每一次建立模型是在之前建立模型损失函数的梯度下降方向。损失函数的梯度这样计算：

其中pk,m-1(xi)是Fm-1(x)对xi的分类结果，其计算公式为：

具体的算法流程为：

先给定一个初始值；然后建立M棵决策树（迭代M次）；对函数估计值F(x)进行Logistic变换；然后求残差减少的梯度方向；然后根据每一个样本点x，与其残差减少的梯度方向，得到一棵由J个叶子节点组成的决策树（这个决策树是一个叶子节点数J固定的，当生成了J个节点后，就不再生成新的节点了。）； 为当决策树建立完成后计算每一个叶子节点的增益；最后当前得到的决策树与之前的那些决策树合并起来，作为新的一个模型。

2.RF

随机森林是用随机的方式建立一个森林，森林里面有很多的决策树组成，每棵决策树之间是没有关联的。在建立好森林之后，当有新样本输入的时候，就让森林中的每一棵决策树分别进行一下判断，每颗决策树会给出新样本的一个分类，哪一类被选择最多，则新样本就属于那一类。

在建立每一棵决策树的过程中，有两点需要注意 - 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 - 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。

按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。

3. XGBOOST

GBDT中考虑的残差，以square loss为例：

如果将目标函数进行二阶泰勒展开，依然以square loss为例：square loss为例：

首先定义

则

而对于模型的复杂度，则定义：
第一部分为叶子数，第二部分是叶节点分数的L2范数，那么目标函数改写为：

定义，

，
则

如果树的结构确定了，那么最佳的权值和目标值则为：

，
所以，xgboost中树节点分裂时所采用的公式为：

这个公式形式上跟ID3算法（采用entropy计算增益） 、CART算法（采用gini指数计算增益） 是一致的，都是用分裂后的某种值 减去 分裂前的某种值，从而得到增益。为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂，上式中的gamma即阈值，它是正则项里叶子节点数T的系数，所以xgboost在优化目标函数的同时相当于做了预剪枝。另外，上式中还有一个系数lambda，是正则项里leaf score的L2模平方的系数，对leaf score做了平滑，也起到了防止过拟合的作用，这个是传统GBDT里不具备的特性。

参考其它资料，xgboost相对于普通gbm的实现，具有以下的一些优势：
1.显式地将树模型的复杂度作为正则项加在优化目标。
2.公式推导里用到了二阶导数信息，而普通的GBDT只用到一阶。
3.分裂公式不同。
4.事先将数据排好序，并以block的形式存储，利于并行计算。
5.支持分布式计算。