机器不学习：从一棵决策树到xgboost

文章《有监督模型的两个最重要算法点》中讲到主要在于特征学习与数值优化两个点，最早的决策树则集中在特征学习这个部分。

① 决策树

网上决策树的教程很多，以下再进行傻瓜式剖析一下：

第一步，计算每个特征的纯度（纯度可以理解成此变量能区分事件的程度，例如信用卡领域：具有集团业务的人，越是可信之人。集团业务这个特征的纯度就很高），不同树的计算纯度的方法很多（信息增益等），计算纯度基础理论都是good/bad，比值越大，特征纯度越大。

第二步，最大特征形成顶点，第二大特征形成第二部分的叶子节点，最终形成树状结构，可以理解成最终根据多个纯度高的特征组合，判断样本是good或者bad，如下所示。

第三步，剪枝理论：减掉纯度低（对结果不会有很大影响）的特征，目的在于尽量减少特征依赖的数量，防止过拟合。

决策树是单一的特征学习

缺点：可能会对纯度高的特征非常依赖。导致人的行为变化，模型就会不稳定。因此，随机森林出现解决这一问题。

② 随机森林

随机森林可以理解成N个决策树的集成。每棵树都是随机（特征，样本数在总体样本中随机抽取）的。预测最终结果取N棵树的平均。

随机森林的每棵树都不一样，也保证不会对某些特征的依赖。

缺点：依然只用了特征学习，没有用到数值优化，因此，GBDT出现。

③ GBDT

g boost原理就是所有弱分类器想加等于预测值，下一个弱分类器去拟合误差函数对预测值的梯度。

这个梯度在gbdt中就是预测值和真实值差。

GBDT加入了简单的数值优化思想（数学证明网上很多，这里通俗解释一下）。

不同于随机森林所有树的预测求均值，gbdt所有的树的预测值加起来是最终的预测值，可以不断接近真实值。

GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，

第一棵树，我们首先用20岁去拟合，发现损失有10岁，

第二颗，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，

第三颗，我们用3岁拟合剩下的差距，差距就只有一岁了。

三棵树加起来为29岁，距离30最近。

目标函数：

第m颗树的目标函数就是m颗相加。

下一颗树都是用之前的残差去拟合（例如上面岁数的例子）

以下截图在t-1时刻进行的求导，即梯度提升的变量则是目标函数中t时刻fx，即t时刻需要预测的值

引用梯度提升树(GBDT)原理小结 - 刘建平Pinard - 博客园

求导等于0的极值即c=c，即argmin等式为0，损失函数求偏导后在最后有公式。

L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小

由于每棵树拟合的值不同，因此算出的Gini节点排序不同，每棵树根结点，子节点会不同。

④ Xgboost

Xgboost更加有效应用了数值优化。相比于gbdt，最重要是对损失函数（预测值和真实值的误差）变得更复杂。

目标函数依然是所有树想加等于预测值。

损失函数如下，引入了一阶导数，二阶导数。：

为什么会效果优呢？原因在于变换：

单纯从算法角度，

一，加入正则项，防止过拟合。

二，xgboost引入二阶导，下次拟合的不为y-fx，充分利用信息。

导数等于0.，可以得到

下棵树去拟合，相当于除以二阶导，差别大的时候还要放大点需要拟合的值。为误差大的加大权重

Xgboost迭代与gbdt一样根据误差建立下一个弱分类器，都是g boost的迭代方法，即下一棵树拟合损失函数根据预测值求导的梯度。

----xgboost用以下分裂方法代替Gini

xgboost分裂采用先对某字段对所有样本排序

理解成分母，错分很少，分子，放大错分大。通过这个从左到右搜索，错分情况最少的点，最佳分裂点。

----

调参，遍历法:学习速率，树的颗树，树的深度，终节点可以有多少人，行抽样，列抽样比例

小结：决策树的前世今生不过是从只是应用特征学习，最终也加入了数值优化的部分。由于纯粹的分类算法，xgboost即包含有效的特征学习，又包含有效的数值优化，因此成为了结构化数据大杀器。