随机森林，GBDT，XGBoost的对比

随机森林 RF RandomForest

　　随机森林的集成学习方法是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) 忽略属性之间的相关性

RF的调参

通用的调参方法：

1. grid search 网格搜索。 sklearn 提供了相应的方GridSearchCV。即使用cross validation，对模型迭代的选用候选参数进行交叉验证，取结果最好的参数，优点：效果好，相当于穷举的思想，调参得到了候选参数里全局最优化结果。 缺点：计算复杂。 一般做竞赛的小项目选这个啦。
2. 基于贪心的坐标下降搜索。即固定其他参数，把某个参数取得最好。这样迭代一遍得到最终结果。优点：计算量少，缺点：可能不是全局最优值、陷入局部最优解。
3. 随机网格搜索：防止 网格搜索间隔过大而跳过最优值，而随机可以相对单个参数取到更多的值。

•  n_estimators越多结果更稳定（方差越小），所以只要允许内，数目越大越好, 但计算量会大增。只有这个参数对结果的影响是越大越好，其他参数都是中间取得最优值。
• “分裂条件”（criterion）对模型的准确度的影响也不一样，该参数需要在实际运用时灵活调整，可取gini或者信息增益比？。
• 每棵树最大特征数（max_features） 一般用sqrt(总特征数)。
• 调整“最大叶节点数”（max_leaf_nodes）以及“最大树深度”（max_depth）之一，可以粗粒度地调整树的结构：叶节点越多或者树越深，意味着子模型的偏差越低，方差越高；同时，调整“分裂所需最小样本数”（min_samples_split）、“叶节点最小样本数”（min_samples_leaf）及“叶节点最小权重总值”（min_weight_fraction_leaf），可以更细粒度地调整树的结构：分裂所需样本数越少或者叶节点所需样本越少，也意味着子模型越复杂。

随机森林的推广(Extra Trees)

extra trees是RF的一个变种, 原理几乎和RF一模一样，仅有区别有：

1） 对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。

2） 在选定了划分特征后，RF的决策树会基于信息增益，基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是extra trees比较的激进，他会随机的选择一个特征值来划分决策树。

从第二点可以看出，由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说，模型的方差相对于RF进一步减少，但是bias相对于RF进一步增大。在某些时候，extra trees的泛化能力比RF更好

GBDT (Gradient Boosting Decision Tree)

gbdt的基本原理是boost 里面的 boosting tree（提升树），并使用 gradient boost。

GBDT中的树都是回归树，不是分类树 ，因为gradient boost 需要按照损失函数的梯度近似的拟合残差，这样拟合的是连续数值，因此只有回归树。

梯度提升 gradient boosting:

Gradient Boosting是一种Boosting的方法，其与传统的Boosting的区别是，每一次的计算是为了减少上一次的残差(residual)，而为了消除残差，可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说，在Gradient Boosting中，每个新的模型的建立是为了使得之前模型的残差往梯度方向减少，与传统Boosting对正确、错误样本进行加权有着很大的区别。这个梯度代表上一轮学习器损失函数对预测值求导。

与Boosting Tree的区别：Boosting Tree的适合于损失函数为平方损失或者指数损失。而Gradient Boosting适合各类损失函数（损失函数为：平方损失则相当于Boosting Tree拟合残差、损失函数为：使用指数损失则可以近似于Adaboost，但树是回归树）

对于梯度提升树其学习流程与提升树类似只是不再使用残差作为新的训练数据而是使用损失函数的梯度作为新的新的训练数据的y值，具体的来说就是使用损失函数对f（x）求梯度然后带入fm-1（x）计算：

GDBT与提升树之间的关系：

提升树模型每一次的提升都是靠上次的预测结果与训练数据的label值差值作为新的训练数据进行重新训练，GDBT则是将残差计算替换成了损失函数的梯度方向，将上一次的预测结果带入梯度中求出本轮的训练数据，这两种模型就是在生成新的训练数据时采用了不同的方法，那么在这个背后有啥区别？使用残差有啥不好？

李航老师《统计学习方法》中提到了在使用平方误差损失函数和指数损失函数时，提升树的残差求解比较简单，但是在使用一般的损失误差函数时，残差求解起来不是那么容易，所以就是用损失函数的负梯度在当前模型的值作为回归问题中残差（均方误差）或者残差的近似值。 

（来自MLAPP）

XGBoost

XGBoost比GBDT好的地方：

二阶泰勒展开

节点分数惩罚正则

增益计算不同，gbdt是gini，xgb是优化推导公式

以下来自 一步一步理解GB、GBDT、xgboost

Xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）。下面所有的内容来自原始paper，包括公式。

(1). xgboost在目标函数中显示的加上了正则化项，基学习为CART时，正则化项与树的叶子节点的数量T和叶子节点的值有关。

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

第t次的loss：

对上式做二阶泰勒展开：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 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

以下内容来自wepon 作者：wepon

链接：https://www.zhihu.com/question/41354392/answer/98658997

• 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
• 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
• xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
• Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
• 列抽样（column subsampling）即特征抽样。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

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

• 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
• 多种语言封装支持。

XGBoost 调参

参考资料：

chentq的slides  http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf

chentq的paper  http://arxiv.org/abs/1603.02754

chentq在52cs上的中文博文  http://www.52cs.org/?p=429

微博上分享的 xgboost导读和实战.pdf XGBoost all in one

转自 http://www.cnblogs.com/sarahp/p/6900572.html