【干货】树算法对比:RF、GBDT、XGBoost

RF、GBDT和XGBoost都属于集成学习(Ensemble Learning),集成学习的目的是通过结合多个基学习器的预测结果来改善单个学习器的泛化能力和鲁棒性。

根据个体学习器的生成方式,目前的集成学习方法大致分为两大类

  • 个体学习器之间存在强依赖关系、必须串行生成的序列化方法;
  • 个体学习器间不存在强依赖关系、可同时生成的并行化方法;

前者的代表就是Boosting,后者的代表是Bagging和“随机森林”(Random Forest)。

1、RF

1.1 原理

提到随机森林,就不得不提Bagging,Bagging可以简单的理解为:放回抽样,多数表决(分类)或简单平均(回归),同时Bagging的基学习器之间属于并列生成,不存在强依赖关系。

Random Forest(随机森林)是Bagging的扩展变体,它在以决策树 为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中引入了随机特征选择,因此可以概括RF包括四个部分:1、随机选择样本(放回抽样);2、随机选择特征;3、构建决策树;4、随机森林投票(平均)。

随机选择样本和Bagging相同,随机选择特征是指在树的构建中,会从样本集的特征集合中随机选择部分特征,然后再从这个子集中选择最优的属 性用于划分,这种随机性导致随机森林的偏差会有稍微的增加(相比于单棵不随机树),但是由于随机森林的‘平均’特性,会使得它的方差减小,而且方差的减小补偿了偏差的增大,因此总体而言是更好的模型。

(As a result of this randomness, the bias of the forest usually slightly increases (with respect to the bias of a single non-random tree) but, due to averaging, its variance also decreases, usually more than compensating for the increase in bias, hence yielding an overall better model.)

在构建决策树的时候,RF的每棵决策树都最大可能的进行生长而不进行剪枝;在对预测输出进行结合时,RF通常对分类问题使用简单投票法,回归任务使用简单平均法。

RF的重要特性是不用对其进行交叉验证或者使用一个独立的测试集获得无偏估计,它可以在内部进行评估,也就是说在生成的过程中可以对误差进行无偏估计,由于每个基学习器只使用了训练集中约63.2%的样本,剩下约36.8%的样本可用做验证集来对其泛化性能进行“包外估计”。

RF和Bagging对比:RF的起始性能较差,特别当只有一个基学习器时,随着学习器数目增多,随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging,因为在单个决策树的构建中,Bagging使用的是‘确定性’决策树,在选择特征划分结点时,要对所有的特征进行考虑,而随机森林使用的是‘随机性’特征数,只需考虑特征的子集。

1.2 优缺点

随机森林的优点较多,简单总结:1、在数据集上表现良好,相对于其他算法有较大的优势(训练速度、预测准确度);2、能够处理很高维的数据,并且不用特征选择,而且在训练完后,给出特征的重要性;3、容易做成并行化方法。

RF的缺点:在噪声较大的分类或者回归问题上回过拟合。

2、GBDT

提GBDT之前,谈一下Boosting,Boosting是一种与Bagging很类似的技术。不论是Boosting还是Bagging,所使用的多个分类器类型都是一致的。但是在前者当中,不同的分类器是通过串行训练而获得的,每个新分类器都根据已训练的分类器的性能来进行训练。Boosting是通过关注被已有分类器错分的那些数据来获得新的分类器。

由于Boosting分类的结果是基于所有分类器的加权求和结果的,因此Boosting与Bagging不太一样,Bagging中的分类器权值是一样的,而Boosting中的分类器权重并不相等,每个权重代表对应的分类器在上一轮迭代中的成功度。

2.1 原理

GBDT与传统的Boosting区别较大,它的每一次计算都是为了减少上一次的残差,而为了消除残差,我们可以在残差减小的梯度方向上建立模型,所以说,在GradientBoost中,每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法,与传统的Boosting中关注正确错误的样本加权有着很大的区别。

在GradientBoosting算法中,关键就是利用损失函数的负梯度方向在当前模型的值作为残差的近似值,进而拟合一棵CART回归树。

GBDT的会累加所有树的结果,而这种累加是无法通过分类完成的,因此GBDT的树都是CART回归树,而不是分类树(尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树)。

2.2 优缺点

GBDT的性能在RF的基础上又有一步提升,因此其优点也很明显,1、它能灵活的处理各种类型的数据;2、在相对较少的调参时间下,预测的准确度较高。

当然由于它是Boosting,因此基学习器之前存在串行关系,难以并行训练数据。

3、XGBoost

3.1 原理

XGBoost的性能在GBDT上又有一步提升,而其性能也能通过各种比赛管窥一二。坊间对XGBoost最大的认知在于其能够自动地运用CPU的多线程进行并行计算,同时在算法精度上也进行了精度的提高。

由于GBDT在合理的参数设置下,往往要生成一定数量的树才能达到令人满意的准确率,在数据集较复杂时,模型可能需要几千次迭代运算。但是XGBoost利用并行的CPU更好的解决了这个问题。

其实XGBoost和GBDT的差别也较大,这一点也同样体现在其性能表现上,详见XGBoost与GBDT的区别。

4、区别

4.1 GBDT和XGBoost区别

传统的GBDT以CART树作为基学习器,XGBoost还支持线性分类器,这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归(分类)或者线性回归(回归);传统的GBDT在优化的时候只用到一阶导数信息,XGBoost则对代价函数进行了二阶泰勒展开,得到一阶和二阶导数;

XGBoost在代价函数中加入了正则项,用于控制模型的复杂度。从权衡方差偏差来看,它降低了模型的方差,使学习出来的模型更加简单,放置过拟合,这也是XGBoost优于传统GBDT的一个特性;shrinkage(缩减),相当于学习速率(XGBoost中的eta)。XGBoost在进行完一次迭代时,会将叶子节点的权值乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间。(GBDT也有学习速率);

列抽样。XGBoost借鉴了随机森林的做法,支持列抽样,不仅防止过 拟合,还能减少计算;

对缺失值的处理。对于特征的值有缺失的样本,XGBoost还可以自动 学习出它的分裂方向;

XGBoost工具支持并行。Boosting不是一种串行的结构吗?怎么并行的?注意XGBoost的并行不是tree粒度的并行,XGBoost也是一次迭代完才能进行下一次迭代的(第t次迭代的代价函数里包含了前面t-1次迭代的预测值)。XGBoost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),XGBoost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代 中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

原文发布于微信公众号 - Spark学习技巧(bigdatatip)

原文发表时间:2018-05-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏赵俊的Java专栏

从源码上分析 ArrayList

1161
来自专栏Phoenix的Android之旅

Java 集合 Vector

List有三种实现,ArrayList, LinkedList, Vector, 它们的区别在于, ArrayList是非线程安全的, Vector则是线程安全...

642
来自专栏xingoo, 一个梦想做发明家的程序员

AOE关键路径

这个算法来求关键路径,其实就是利用拓扑排序,首先求出,每个节点最晚开始时间,再倒退求每个最早开始的时间。 从而算出活动最早开始的时间和最晚开始的时间,如果这两个...

2507
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

1706
来自专栏MelonTeam专栏

ArrayList源码完全分析

导语: 这里分析的ArrayList是使用的JDK1.8里面的类,AndroidSDK里面的ArrayList基本和这个一样。 分析的方式是逐个API进行解析 ...

4469
来自专栏java闲聊

JDK1.8 ArrayList 源码解析

当运行 ArrayList<Integer> list = new ArrayList<>() ; ,因为它没有指定初始容量,所以它调用的是它的无参构造

1192
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1K4
来自专栏ml

朴素贝叶斯分类器(离散型)算法实现(一)

1. 贝叶斯定理:        (1)   P(A^B) = P(A|B)P(B) = P(B|A)P(A)   由(1)得    P(A|B) = P(B|...

3417
来自专栏计算机视觉与深度学习基础

Leetcode 114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given...

1928
来自专栏刘君君

JDK8的HashMap源码学习笔记

3008

扫码关注云+社区