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

unkownwind 2018-08-28

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

① 决策树

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

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

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

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

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

决策树是单一的特征学习

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

② 随机森林

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

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

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

③ GBDT

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

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

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

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

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

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

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

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

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

目标函数:

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

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

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

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

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

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

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

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

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

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

④ Xgboost

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

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

损失函数如下,引入了一阶导数,二阶导数。:

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

为什么会效果优呢?原因在于变换:

单纯从算法角度,

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

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

导数等于0.,可以得到

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

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

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

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

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

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

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

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

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

----

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

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

相关推荐