随机森林与xgboost算法有什么关系？

GY123456

谢邀。
一、随机森林
随机森林是一种类似于bagging的集成学习方法 ，但是和bagging不同的是：bagging只使用bootstrap有放回的采样样本，但随机森林即随机采样样本，也随机选择特征，因此防止过拟合能力更强，降低方差。

使用的融合方法：bagging
一种集成学习算法，基于bootstrap sampling 自助采样法，重复性有放回的随机采用部分样本进行训练最后再将结果 voting 或者 averaging 。它是并行式算法，因为不同基学习器是独立训练一个bagging集成学习器时间复杂度与基学习器同阶（n倍，n为基学习器个数）。bagging可以用于二分类／多分类／回归每个基学习器的未用作训练样本可用来做包外估计，评价泛化性能。bagging主要关注降低 方差。
两个步骤 1. 抽样训练（采样样本，采样特征） 2 融合
随机森林进一步在决策树训练时加入随机属性选择：
  如果有M个输入变量，每个节点都将随机选择m(m<M)个特定的变量，然后运用这m个变量来确定最佳的分裂点。在决策树的生成过程中，m的值是保持不变的。m一般取M均方根
  因此随机森林即有样本随机性（来自bagging的boostrap sampling）又有特征随机性。
随机森林的优缺点
优点：
a）随机森林算法能解决分类与回归两种类型的问题，表现良好，由于是集成学习，方差和偏差都比较低，泛化性能优越；
b）随机森林对于高维数据集的处理能力很好，它可以处理成千上万的输入变量，并确定最重要的变量，因此被认为是一个不错的降维方法。此外，该模型能够输出特征的重要性程度，这是一个非常实用的功能。
c) 可以应对缺失数据；
d）当存在分类不平衡的情况时，随机森林能够提供平衡数据集误差的有效方法；
e ) 高度并行化，易于分布式实现
f) 由于是树模型 ，不需要归一化即可之间使用

缺点：

a）随机森林在解决回归问题时并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续型的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在对某些还有特定噪声的数据进行建模时出现过度拟合。
b）对于许多统计建模者来说，随机森林给人的感觉像是一个黑盒子——你几乎无法控制模型内部的运行，只能在不同的参数和随机种子之间进行尝试。
c) 忽略属性之间的相关性

二、xgboost
    xgboost是在GBDT的基础上改进的，因此了解xgboost之前需要了解GBDT.XGBoost比GBDT好的地方：
(1)二阶泰勒展开
(2)节点分数惩罚正则
(3)增益计算不同，gbdt是gini，xgb是优化推导公式
1) xgboost在目标函数中显示的加上了正则化项，基学习为CART时，正则化项与树的叶子节点的数量T和叶子节点的值有关。

2)GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x)，xgboost不仅使用到了一阶导数，还使用二阶导数。


g为一阶导数，h为二阶导数
3）上面提到CART回归树中寻找最佳分割点的衡量标准是最小化均方差，xgboost寻找分割点的标准是最大化，lamda，gama与正则化项相关：


xgboost算法的步骤和GB基本相同，都是首先初始化为一个常数，gb是根据一阶导数ri，xgboost是根据一阶导数gi和二阶导数hi，迭代生成基学习器，相加更新学习器。

xgboost与gdbt除了上述三点的不同，xgboost在实现时还做了许多优化：

在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍。
特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。
按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。
xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。
最后：
一般情况xgboost常与GBDT相比较。和随机森林比较的少。

ROSoft YaHei, Source Han Sans SC, Noto Sans CJK SC, WenQuanYi Micro Hei, sans-serif">了解更多干货问题，关注小程序八斗问答