机器学习（四）：决策树之集成学习（Ensemble Learning）

集成学习概念

集成学习通过构建合并多个学习器来完成学习任务，有时候也被称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）等。通俗的来说，就是“三个臭皮匠，赛过诸葛亮”，集成学习应用某种逻辑，将单个学期器组合在一起，常常可以获得比单一学习器显著优越的泛化性能。

根据个体学习器的生成方式，目前的集成学习方法大致可以分为两类，即个体学习器之间存在强依赖关系、必须以串行生成的序列化方法，以及个体学习器之间不存在强依赖关系，可以同时生成的并行化方法；前者的代表是Boosting和GBDT，后者的代表是Bagging和随机森林。

Boosting

Boosting 是一种可将若学习器提升为强学习器的算法，这类算法的工作机制类似：先从初始训练数据集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多的关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先制定的值T，最终将这T个基学习器进行加权结合。Boosting最著名的代表就是AdaBoost，这里不赘述AdaBoost的具体算法。

从偏差 - 方差分解的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能当当若的许西器构造出很强的集成。

Bagging

Bagging是并行式集成学习最著名的代表，它基于自助采样法（boostrap sampling）。给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时，该样本仍有可能被选中，这样，经过m次随机采样操作，我们的到含有m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的从未出现。样本在m次采样中始终没被采集到的概率为$(1 - \frac{1}{m})^m$，m取极限之后等于1/e，这个值近似约0.368，也就是说，有36.8%的数据，可能未被采样集采样。这部分包外样本可以用作验证集来对泛化性能进行“包外估计，Bagging泛化误差的包外估计为：$e^{oob} = \frac{1}{|D|}\sum_{(x, y)\in{D}}I(H^{oob}(x\not=y))$ 。

当基学习器是决策树时，包外样本就可以用来辅助剪枝；当基学习器是神经网络时，包外样本可以辅助早期停止以减小过拟合风险。

照这样的策略，我们可以采样出T个包含m个训练样本的采样集，然后基于每个采样集训练出基学习器，再将这些学习器进行结合，这就是Bagging的基本流程。

输出结果的时候，Bagging通常对分类任务使用简单的投票法，对回归任务采用简单的平均法。若预测时出现两个类收到的基学习器票数相同，则随机选择一个类别，也可以进一步考察学习器投票的置信度来确定最终胜者。

从偏差 - 方差的分解角度看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

结合策略

对回归任务，可以采用简单平均法，和加权平均法。一般来说对于单个基学习器性能差距不大的情况，我们使用简单平均法；对于单个基学习器性能差距较大的情况，使用加权平均法。
对于分类任务，可以使用投票法。
- 绝对多数投票法：即若对于某样本，其某类别标记的基学习器得票数超过半数，则预测为该类别标记；否则拒绝该假设。
- 相对多数投票法：即预测为的票最多的标记，若同时有多个标记获得最高票，则从中随机选取一个。
- 加权投票法：与加权平均类似，给票数乘以一个权重之后，再用绝对多数投票法来决策。
学习法（Stacking）：

当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行基学习器预测结果的结合。Stacking是学习法的典型代表，这里我们把个体基学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器。

Stacking先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器，在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。

为避免过拟合，一般通过交叉验证或留一法的方式，用初级学习器为使用的样本来产生次级学习器。另外，次级学习器的输入属性表示和次级学习器算法，对Stacking集成的泛化性能有很大影响。有研究表明，将初级学习器的输出类概率作为次级学习器的输入，次级学习器算法使用多响应线性回归MLR（Multi-response Linear Reggerssion），这样的集成学习效果较好。

随机森林（Random Forest）

随机森林（Random Forest, RF）是Bagging的一种扩展变体，RF的基学习器都是CART决策树，并且在Bagging的基础上，引入了随机属性选择。具体来说，传统决策树在选择划分属性时，是在当前结点的属性集合（假设有d个属性）中选择一个最优划分属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择包含k个属性的属性子集，然后从这k个属性中选择一个最优划分属性用于划分该结点。这里的参数k实质上控制了随机性的引入程度：若令k=d，则基决策树的构建与传统决策树相同；若k=1，则意味着该结点随机选择了一个属性作为最优划分属性；一般情况下，推荐$k = log_2d$。这种来自属性的扰动保证了不同基决策树之间的多样性，相比Bagging的多样只来自于样本扰动，进步一提升了模型的泛化能力。

在合成策略中，随机森林通常采用投票法，少数服从多数。当数据较多的时候，也可以采用更强大的学习法。

随机森林有很多好处，例如算法简单、易于实现、计算开销小，更令人惊奇的是RF在很多任务中都表现出了强大的性能。所以RF也成为经常被人们首先拿来使用的模型。

随机森林在基学习器数量较少的时候性能较差，是因为基学习器有来自属性的扰动，相比原先的决策树更弱，但是当个体学习器的数量不断增加的时候，随机森林可以收敛到比Bagging更低的泛化误差。更值得一提的是，随机森林的训练效率常常优于普通的Bagging，因为RF在构建单棵决策树的时候，使用的是“随机型”决策树，只考察属性的子集，降低了计算开销。

随机森林在sklearn中的参数

参数		特点
n_estimators	基学习器数目（默认值 10）	基本趋势是值越大精度越高，直到达到一个上限
criterion	选择算法 gini 或者 entropy (默认 gini)	视具体情况定
max_features	2.2.3 节中子集的大小，即 k 值（默认 sqrt(n_features)）
max_depth	决策树深度	过小基学习器欠拟合，过大基学习器过拟合。粗调节
max_leaf_nodes	最大叶节点数（默认无限制）	粗调节
min_samples_split	分裂时最小样本数，默认 2	细调节, 越小模型越复杂
min_samples_leaf	叶节点最小样本数，默认 2	细调节，越小模型越复杂
bootstrap	是否采用自助法进行样本抽样（默认使用）	决定基学习器样本是否一致

示例：利用GridSearchCV调参

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from sklearn.model_selection import GridSearchCV
from sklearn.model_selection import learning_curve

def plot_learning_curve(estimator, title, X, y, cv=10,
                        train_sizes=np.linspace(.1, 1.0, 5)):
    plt.figure()
    plt.title(title) # 设置图的 title
    plt.xlabel('Training examples') # 横坐标
    plt.ylabel('Score') # 纵坐标
    train_sizes, train_scores, test_scores = learning_curve(estimator, X, y, cv=cv,
                                                            train_sizes=train_sizes) 
    train_scores_mean = np.mean(train_scores, axis=1) # 计算平均值
    train_scores_std = np.std(train_scores, axis=1) # 计算标准差
    test_scores_mean = np.mean(test_scores, axis=1)
    test_scores_std = np.std(test_scores, axis=1)
    plt.grid() # 设置背景的网格

    plt.fill_between(train_sizes, train_scores_mean - train_scores_std,
                     train_scores_mean + train_scores_std,
                     alpha=0.1, color='g') # 设置颜色
    plt.fill_between(train_sizes, test_scores_mean - test_scores_std,
                     test_scores_mean + test_scores_std,
                     alpha=0.1, color='r')
    plt.plot(train_sizes, train_scores_mean, 'o-', color='g',
             label='traning score') # 绘制训练精度曲线
    plt.plot(train_sizes, test_scores_mean, 'o-', color='r',
             label='testing score') # 绘制测试精度曲线
    plt.legend(loc='best')
    return plt

clf = RandomForestClassifier()
para_grid = {'max_depth': [10], 'n_estimators': [100], 'max_features': [1, 5, 10], 'criterion': ['gini', 'entropy'],
             'min_samples_split': [2, 5, 10], 'min_samples_leaf': [1, 5, 10]}#对以上参数进行网格搜索
gs = GridSearchCV(clf, param_grid=para_grid, cv=3, scoring='accuracy')
gs.fit(X, y)
gs_best = gs.best_estimator_ #选择出最优的学习器
gs.best_score_ #最优学习器的精度

g = plot_learning_curve(gs_best, 'RFC', X, y)# 绘制学习曲线

GBDT（Gradient Boosting Decison Tree）

回归决策树

基于梯度提升算法的学习器叫做GBM(Gradient Boosting Machine)。理论上，GBM可以选择各种不同的学习算法作为基学习器。现实中，用得最多的基学习器是回归决策树模型。回归树在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分裂时穷举每一个feature的每个阈值，找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，也就是说划分依据是使分裂后的均方误差最小。若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

用决策树作基学习器的优点

为什么梯度提升方法倾向于选择决策树（通常是CART树）作为基学习器呢？这与决策树算法自身的优点有很大的关系。

决策树可以认为是if-then规则的集合，易于理解，可解释性强，预测速度快。
决策树算法相比于其他的算法需要更少的特征工程，比如可以不用做特征标准化，可以很好的处理字段缺失的数据，也可以不用关心特征间是否相互依赖等。
决策树能够自动组合多个特征，它可以毫无压力地处理特征间的交互关系并且是非参数化的，因此你不必担心异常值或者数据是否线性可分。

不过，单独使用决策树算法时，有容易过拟合缺点。所幸的是，通过各种方法，抑制决策树的复杂性，降低单颗决策树的拟合能力，再通过梯度提升的方法集成多个决策树，最终能够很好的解决过拟合的问题。由此可见，梯度提升方法和决策树学习算法可以互相取长补短，是一对完美的搭档。至于抑制单颗决策树的复杂度的方法有很多，比如限制树的最大深度、限制叶子节点的最少样本数量、限制节点分裂时的最少样本数量、吸收bagging的思想对训练样本采样（subsample），在学习单颗决策树时只使用一部分训练样本、借鉴随机森林的思路在学习单颗决策树时只采样一部分特征、在目标函数中添加正则项惩罚复杂的树结构等。现在主流的GBDT算法实现中这些方法基本上都有实现，因此GBDT算法的超参数还是比较多的，应用过程中需要精心调参，并用交叉验证的方法选择最佳参数。

GBDT是Boosting家族中另一个非常重要的算法，现在很多大厂的面试都会问到GBDT，可见该算法的效果与在实际应用中的广泛程度。

基于残差的Gradient Boosting

GB的策略是迭代生成多棵回归树共同进行目标值的预测。GBDT的核心就在于，每一棵树学的是之前所有树和标签值的残差。

比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，如此继续学习下去，就能够越来越精确。

形式化一些，我们可以这样来表示，以上过程就是从对样本$(x_{1},y_{1}),(x_{2},y_{2}),…(x_{n},y_{n})$的拟合，转变成对$(x_{1},y_{1}-F(x_{1})),(x_{2},y_{2}-F(x_{2})),…(x_{n},y_{n}-F(x_{n}))$的拟合。

数学上来说，为什么这样能够使我们的模型变得更精确？假设我们前一轮迭代得到的强学习器是$f_{t-1}(x)$，损失函数是$L(y_i, f_{t-1}(x_i))$，我们本轮迭代的目标是找到一个CART决策树的弱学习器$f_t(x)$，让本轮的损失函数$L(y_i, f_t(x_i)) = L(y, y^{t-1}i + {f_t}(x_i))$最小，也就是说，本轮迭代找到的决策树，要让拟合样本的损失更小。如上述例子，我们会发现当此时的损失函数为均方误差，残差刚好就是该损失函数的负梯度（负一阶导），后续每一棵树的生成都是去拟合这个负梯度。因此，上一轮的损失$L(y_i, f{t-1}(x_i))$在往它的负梯度方向更新，也就是减小了损失，模型的精确度提高。换成其它损失函数，也是同样的道理，利用负梯度去拟合，降低损失。

sklearn - GBDT Boosting参数指南

n_estimators: 默认是100，最大的弱学习器的个数，或者弱学习器的最大迭代次数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，又容易过拟合，一般选择一个适中的数值。在实际调参的过程中，常常将n_estimators和下面介绍的参数learning_rate一起考虑。
learning_rate: 默认为0.1，即每个弱学习器的权重缩减系数ν，也称作步长。是为了过拟合，加上的正则化项系数，我们的强学习器的迭代公式为$f_k(x)=f_{k−1}(x)+νh_k(x)$。ν的取值范围为0<ν≤1。对于同样的训练集拟合效果，较小的ν意味着我们需要更多的弱学习器的迭代次数（需要更多的弱学习器）。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。所以这两个参数n_estimators和learning_rate要一起调参。一般来说，可以从一个小一点的ν开始调参。
subsample: 默认为1，正则化中的子采样，防止过拟合，取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5,0.8]之间，默认是1.0，即不使用子采样。
init: 即我们的初始化的时候的弱学习器，如果不输入，则用训练集样本来做样本集的初始化分类回归预测。否则用init参数提供的学习器做初始化分类回归预测。一般用在我们对数据有先验知识，或者之前做过一些拟合的时候，如果没有的话就不用管这个参数了。
loss: 即我们GBDT算法中的损失函数。分类模型和回归模型的损失函数是不一样的。对于分类模型，有对数似然损失函数”deviance”和指数损失函数”exponential”两者输入选择。默认是对数似然损失函数”deviance”。一般来说，推荐使用默认的”deviance”。它对二元分离和多元分类各自都有比较好的优化。而指数损失函数等于把我们带到了Adaboost算法。对于回归模型，有均方差”ls”, 绝对损失”lad”, Huber损失”huber”和分位数损失“quantile”。默认是均方差”ls”。一般来说，如果数据的噪音点不多，用默认的均方差”ls”比较好。如果是噪音点较多，则推荐用抗噪音的损失函数”huber”。而如果我们需要对训练集进行分段预测的时候，则采用“quantile”。
alpha: 这个参数只有GradientBoostingRegressor有，当我们使用Huber损失”huber”和分位数损失“quantile”时，需要指定分位数的值。默认是0.9，如果噪音点较多，可以适当降低这个分位数的值。

sklearn - GBDT 基学习器参数指南

这里我们再对GBDT的类库弱学习器的重要参数做一个总结。由于GBDT使用了CART回归决策树，因此它的参数基本来源于决策树类，也就是说，和DecisionTreeClassifier和DecisionTreeRegressor的参数基本类似。

max_features: RF划分时考虑的最大特征数。可以使用很多种类型的值，默认是”None”,意味着划分时考虑所有的特征数；如果是”log2”意味着划分时最多考虑log2N个特征；如果是”sqrt”或者”auto”意味着划分时最多考虑N−−√N个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数，其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的”None”就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。
max_depth: 决策树最大深度。默认为”None”，决策树在建立子树的时候不会限制子树的深度这样建树时，会使每一个叶节点只有一个类别，或是达到min_samples_split。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
min_samples_split: 内部节点再划分所需最小样本数，默认2。这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。
min_samples_leaf: 叶子节点最少样本数。这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。
min_weight_fraction_leaf: 叶子节点最小的样本权重和。这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
max_leaf_nodes: 最大叶子节点数。通过限制最大叶子节点数，可以防止过拟合，默认是”None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。
min_impurity_split: 节点划分最小不纯度。这个值限制了决策树的增长，如果某节点的不纯度(基于基尼系数，均方差)小于这个阈值，则该节点不再生成子节点，即为叶子节点。一般不推荐改动默认值1e-7。
presort: 是否对数据进行预分类，以加快拟合中最佳分裂点的发现。默认False，适用于大数据集。小数据集使用True,可以加快训练。是否预排序,预排序可以加速查找最佳分裂点，对于稀疏数据不管用，Bool，auto：非稀疏数据则预排序，若稀疏数据则不预排序

上面决策树参数中最重要的包括最大特征数max_features，最大深度max_depth，内部节点再划分所需最小样本数min_samples_split和叶子节点最少样本数min_samples_leaf。

扩展阅读

实际上GBDT的坑还有很多，知乎上的这篇《N问GBDT》非常好的总结了一些问题，另一位大佬给出了前12问的答案。
为什么xgboost/gbdt在调参时为什么树的深度很少就能达到很高的精度？第一个回答在偏差和方差的角度上解释了Bagging和Boosting的特点。

XGBoost

XGBoost在GBDT的基础上用目标函数代替损失函数，目标函数简单的来说就是损失函数+正则项。

目标函数

用平方损失（square loss）作为损失函数，正则项为$\Omega(f_t)$，那么目标函数为

$Obj^{(t)} = \sum_{i=1}^{n}(y_i - (y_i^{t-1} + f_t(x_i))^2 + \Omega(f_t)$

对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度，因此要求每个分类回归树的深度不会很深。最终的总分类器是将每轮训练得到的弱分类器加权求和得到的（也就是GBDT中的加法模型）。

在正则项中，我们可以加入单棵树叶子结点数量，已达到限制加入的树的复杂度的目的。当一棵决策树构建完成，每个叶子结点对应一个权值表示样本的获得的结果$w_q$，因此决策树可以定义为$f_t(x) = w_q(x)$。正则项就可以表示成

$\Omega(f_t) = \gamma{T} + \frac{1}{2}\lambda\sum_{y=1}^T\omega^2_j$，这里使用的是叶子结点值的L2范数。

对于不是非平方损失函数，目标函数可以由损失函数与正则项相加得到：

$Obj^{(t)} = \sum_{i=1}^{(n)}L(y, y^{t-1}_i + f_t(x)) + \Omega(f_t)$

为了化简目标函数，这里可以使用泰勒展开式，对损失函数部分展开。

泰勒公式二阶展开：$f(x + \Delta{x})\approx f(x) + f’(x)\Delta + \frac{1}{2}f”(x)\Delta^2$

则目标函数为：$Obj^t = \sum_{i=1}^n[l(y_i,y_i^{t-1}) + g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]+ \Omega(f_t)$

(以上均省略了常数项，因为常数项对优化目标函数没有影响)

此处$g_i$和$h_i$是损失函数对$y^{(t-1)}$的一阶偏微分和二阶偏微分，$f_t(x_i)$相当于$\Delta{x}$。

而第一项$l(y_i,y_i^{t-1})$对目标函数的优化并没有作用，因为$y^{t-1}$是上一轮中的预测值，这一项相当于一个常数。因此拿掉它之后的目标函数为：$Obj^t = \sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]+ \Omega(f_t)$

最小化目标函数

定义集合$I_j = {i|q(x_i) = j}$为所有被划分到叶子结点$j$的训练样本集合。用叶子结点数量重新组织上一节的目标函数：

$Obj^t = \sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]+ \Omega(f_t)$

$ = \sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]+\gamma{T} + \frac{1}{2}\lambda\sum_{y=1}^T\omega^2_j$

$ = \sum^T_{j = 1}[(\sum_{i\in{I_j}}g_i)w_i + \frac{1}{2}(\sum_{i\in{I_j}}h_i + \lambda)]+\gamma{T}$

定义$G_j = \sum_i\in{i_j}g_i$，$H_i = \sum_{i\in{I_j}}h_i$

以上目标函数就可以写成：

$Obj^{(t)} = \sum_{j=1}^T[G_iw_j + \frac{1}{2}(H_i + \lambda)w_j^w] + \gamma{T}$

使目标函数一阶导数为0，用此时的$w_j$值最小化目标函数，这也就是我们需要的叶子结点$j$对应的值。

$w_j = - \frac{G_j}{H_j+\lambda}……(1)$

目标函数值为：

$Obj = -\frac{1}{2}\sum_{j=1}^T\frac{G^2_j}{H_j + \lambda} + \gamma{T}…..(2)$

综上，我们在训练过程中需要枚举多有可能的树结构，用(2) 计算每个树结构对应的目标函数值，分数越小越好。利用(1) 可以求出相应树结构的叶子结点对应的值。

然而，树结构的数量可能是无穷的，所以实际中，我们不会枚举所有树的可能，往往采用贪心的策略生成决策树的每个结点。

从深度为0的树开始，枚举所有的可用特征
针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益）
选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集
回到第1步，递归执行到满足特定条件为止

如何计算每次分裂的收益呢？假设当前节点记为$C$,分裂之后左孩子节点记为$L$，右孩子节点记为$R$，则该分裂获得的收益定义为当前节点的目标函数值减去左右两个孩子节点的目标函数值之和：$Gain = Obj_C - Obj_L - Obj_R$，具体根据等式(2)可得：

$Gain = \frac{1}{2}[\frac{G^2_L}{H_L + \lambda}+\frac{G^2_R}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}] - \gamma$

其中，$-\gamma$表示树的复杂度的惩罚项。

XGBoost 参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
xlf = xgb.XGBRegressor(max_depth=10, 
                        learning_rate=0.1, 
                        n_estimators=10, 
                        silent=True, 
                        objective='reg:linear', 
                        nthread=-1, 
                        gamma=0,
                        min_child_weight=1, 
                        max_delta_step=0, 
                        subsample=0.85, 
                        colsample_bytree=0.7, 
                        colsample_bylevel=1, 
                        reg_alpha=0, 
                        reg_lambda=1, 
                        scale_pos_weight=1, 
                        seed=1440, 
                        missing=None)

xlf.fit(X_train, y_train, eval_metric='rmse', verbose = True, eval_set = [(X_test, y_test)],early_stopping_rounds=100)

总结

算法流程：

算法每次迭代生成一颗新的决策树
在每次迭代开始之前，计算损失函数在每个训练样本点的一阶导数和二阶导数
通过贪心策略生成新的决策树，通过等式(7)计算每个叶节点对应的预测值
把新生成的决策树添加到模型中

通常在第四步，我们把模型更新公式替换为：$y_t = y^{t - 1} + \eta{f_t(x_i)}$，其中$\eta$称之为步长或者学习率。增加因子的目的是为了避免模型过拟合。

XGBoost相较于GBDT优点如下：

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是ft−1(x)ft−1(x), 损失函数是L(y,ft−1(x))L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x)ht(x)，让本轮的损失损失L(y,ft(x)=L(y,ft−1(x)+ht(x))L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。

传统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还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

——转自知乎wepon

集成学习总结

Boosting、bagging和stacking是集成学习的三种主要方法。不同于bagging方法，boosting方法通过分步迭代（stage-wise）的方式来构建模型，在迭代的每一步构建的弱学习器都是为了弥补已有模型的不足。Boosting族算法的著名代表是AdaBoost，AdaBoost算法通过给已有模型预测错误的样本更高的权重，使得先前的学习器做错的训练样本在后续受到更多的关注的方式来弥补已有模型的不足。与AdaBoost算法不同，梯度提升方法在迭代的每一步构建一个能够沿着梯度最陡的方向降低损失（steepest-descent）的学习器来弥补已有模型的不足。

经典的AdaBoost算法只能处理采用指数损失函数的二分类学习任务)，而梯度提升方法通过设置不同的可微损失函数可以处理各类学习任务（多分类、回归、Ranking等），应用范围大大扩展。另一方面，AdaBoost算法对异常点（outlier）比较敏感，而梯度提升算法通过引入bagging思想、加入正则项等方法能够有效地抵御训练数据中的噪音，具有更好的健壮性。这也是为什么GBDT、XGBoost如此流行的原因。