采样方法与集成策略

1 BootStrapping 采样

Bootstrapping 名字来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法，是非参数统计中一种重要的估计统计量方差进而进行区间估计的统计方法。其核心思想和基本步骤如下：
(1) 采用重抽样技术从原始样本中抽取一定数量的样本，此过程允许重复抽样。
(2) 根据抽出的样本计算给定的统计量 T。
(3) 重复上述 N 次（一般大于1000），得到 N 个统计量 T。
(4) 计算上述 N 个统计量 T 的样本方差，得到统计量的方差。

应该说Bootstrap是现代统计学较为流行的一种统计方法，在小样本时效果很好。通过方差的估计可以构造置信区间等，其运用范围得到进一步延伸。

2 集成策略

2.1 Bagging

Bootstrap aggregating的缩写。让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练样本组成，某个初始训练样本在某轮训练集中可以出现多次或根本不出现，训练之后可得到一个预测函数序列 $h_{1},\cdots,h_{n}$​ ，最终的预测函数H对分类问题采用投票方式，对回归问题采用简单平均方法对新示例进行判别。(训练R个分类器$f_{i}$​，分类器之间只有参数不同。其中$f_{i}$​是通过从N个训练样本中有放回地随机取N个样本构成的训练集上训练得到的。对于样本d，用这R个分类器去预测，得到最多的那个结果类别作为d的最终类别)

2.2 Boosting

其中主要的是AdaBoost (Adaptive Boosting)。初始化时对每一个训练样例赋相等的权重$\frac{1}{n}$，然后用该学习算法对训练集训练t轮，每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在后续的学习中集中对比较难的训练例进行学习，从而得到一个预测函数序列$h_{1},\cdots,h_{m}$，其中$h_{i}$​也有一定的权重，预测效果好的预测函数权重较大，反之权重较小。最终的预测函数H对分类问题采用有权重的投票方式，对回归问题采用加权平均的方法对新样例进行判别。(类似Bagging方法，但是训练是串行进行的(Bagging的训练是并行的)，第k个分类器训练时关注前k-1个分类器中错分的样例，即不是随机取，而是加大取这些样例的概率)

2.3 Bagging与Boosting的区别

二者的主要区别是取样方式不同。
(1) Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分类精度要优于Bagging。
(2) Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boosting的各轮训练集的选择与前面各轮的学习结果有关。
(3) Bagging的各个预测函数没有权重，而Boosting是有权重的。
(4) Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于像神经网络这样极为耗时的学习方法，Bagging可通过并行训练节省大量时间开销。
(5) Bagging和Boosting都可以有效地提高分类的准确性。在大多数数据集中，Boosting的准确性比Bagging高。但在有些数据集中，Boosting会引起退化导致过拟合。
(6) Boosting思想的一种改进型AdaBoost方法在邮件过滤、文本分类方面都有很好的性能。
(7) Bagging方法使得方差减小，Boosting方法使得偏差减小。

3 集成算法

3.1 Random Forest(RF)

随机森林是用随机的方式建立一个森林，森林由很多的决策树组成，随机森林的每一棵决策树之间没有关联。在得到森林之后，当有一个新的输入样本进入时，森林中的每一棵决策树都会进行判断，预测这个样本所属的类别(对于分类算法)，将样本归为预测最多的类别。

3.1.1 Random Forest 生成步骤

step1从始训练数据集中，应用bootstrap方法有放回地随机抽取k个新的自助样本集，并由此构建k棵分类回归树，每次未被抽到的样本组成了Ｋ个袋外数据(out-of-bag)。
step2：设有n 个特征，则在每一棵树的每个节点处随机抽取m个特征，通过计算每个特征蕴含的信息量，从m个特征中选择一个最具有分类能力的特征进行节点分裂。
step3：每棵树最大限度地生长， 不做任何剪裁。
step4：将生成的多棵树组成随机森林， 用随机森林对新的数据进行分类， 分类结果按树分类器投票多少而定。

3.1.2 Random Forest 的优点

(1) 不必担心过度拟合；
(2) 适用于数据集中存在大量未知特征；
(3) 能够估计哪个特征在分类中更重要，可以将特征按重要性进行排序；
(4) 具有很好的抗噪声能力；
(5) 算法容易理解；
(6) 可以并行处理。

3.1.3 Random Forest 的缺点

(1) 对小量数据集和低维数据集的分类不一定可以得到很好的效果。
(2) 执行速度虽然比Boosting等快，但是比单个的决策树慢很多。
(3) 可能会出现一些差异度非常小的树，淹没了一些正确的决策。
(4) 由于树是随机生成的，结果不稳定(kpi值比较大)。

3.1.4 为什么 Random Forest 不会发生过拟合？

在建立每一棵决策树的过程中，有两点需要注意：采样与完全分裂。

首先是两个随机采样的过程，Random Forest对输入的数据要实施行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般的决策树算法都一个重要的步骤 – 剪枝，但是Random Forest不同，因为之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。

3.1.5 Random Forest 与SVM 比较

(1) 不需要调节过多的参数，因为随机森林只需要调节树的数量，而且树的数量一般是越多越好，而其他机器学习算法，比如SVM，有非常多超参数需要调整，如选择最合适的核函数，正则惩罚等。
(2)分类较为简单、直接。随机森林和支持向量机都是非参数模型（复杂度随着训练模型样本的增加而增大）。相较于一般线性模型，就计算消耗来看，训练非参数模型更为耗时耗力。分类树越多，需要消耗更多时间来构建随机森林模型。同样，我们训练出来的支持向量机有很多支持向量，最坏情况为，我们训练集有多少实例，就有多少支持向量。虽然，我们可以使用多类支持向量机，但传统多类分类问题的执行一般是one-vs-all（所谓one-vs-all 就是将binary分类的方法应用到多类分类中。比如我想分成K类，那么就将其中一类作为positive），因此我们还是需要为每个类训练一个支持向量机。相反，决策树与随机森林则可以毫无压力解决多类问题。
(3) 随机森林比较容易入手实践。随机森林在训练模型上要更为简单。很容易可以得到一个又好且具鲁棒性的模型。随机森林模型的复杂度与训练样本和树成正比。支持向量机则需要我们在调参方面做些工作，除此之外，计算成本会随着类增加呈线性增长。
(4) 小数据上，SVM优异，而随机森林对数据需求较大。就经验来说，我们更愿意认为支持向量机在存在较少极值的小数据集上具有优势。随机森林则需要更多数据但一般可以得到非常好的且具有鲁棒性的模型。

3.1.6 Random Forest与Bagging的区别

(1) Random Forest是选与输入样本的数目相同多(bootstraps)的次数(可能一个样本会被选取多次，同时也会造成一些样本不会被选取到)，而Bagging一般选取比输入样本的数目少的样本；
(2) Bagging是用全部特征来得到分类器，而Random forest是需要从全部特征中选取其中的一部分来训练得到分类器；
(3) 一般Random Forest的效果比Bagging效果好！

3.1.7 Random Forest与Gradient Boosting Decision Tree(GBDT)区别

决策树+bagging=随机森林;
决策树+Boosting=GBDT。

3.2 GBDT 及其改进

3.2.1 Gradient Boosting Decision Tree (GBDT)

Boosting是一种思想，Gradient Boosting是一种实现Boosting的方法，它主要的思想是，每一次建立模型是在之前建立模型损失函数的梯度下降方向。损失函数(loss function)描述的是模型的不靠谱程度，损失函数越大，则说明模型越容易出错。如果我们的模型能够让损失函数持续的下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度（Gradient)的方向上下降。

3.2.2 GBDT 为什么使用负梯度来代替残差

(1) 残差是使用平方损失函数时的特殊情况，倘若使用其他损失函数，那么再沿着残差的方向进行训练，模型的效果就不会再逐次提升了，而负梯度可以很好的拓展到任何一阶可导的损失函数中。
(2) 负梯度是损失函数下降最快的方向。
(3) 一般来说，损失函数中不光有残差这类基本损失项(例如残差平方和)，还包含正则化项，有时候虽然基本损失项在下降，而正则化项却在上升，从而导致整体损失在上升。负梯度是整体损失的共同导数，它可以保证整体损失保持下降。

3.2.3 XGBoost 为什么使用二阶梯度展开

(1) 二阶梯度能够使得梯度收敛的更快更准确；
(2) 可以支持自定义损失函数

3.2.4 LightGBM相较于XGBoost做了哪些改进？

(1) 为了使得XGB能够支持并行运算，XGB对数据进行了预排序，而这个过程是极其耗时的，LGB通过使用直方图算法加速了这一处理过程。
(2) 通过二阶梯度进行单边梯度采样。
(3) 互斥特征合并。
(4) XGB不支持处理分类特征，LGB支持处理分类特征。

3.2.5 LightGBM 是怎么输出概率值的？

(1)对于二分类问题：假设LightGBM模型公训练K轮，每一轮的输出结果都是一个权值$W_{k}$(实数域取值)，记$W=\sum\limits_{k=1}^{K}W_{k}$，则通过对$W$进行sigmoid变换即可得到预测概率值$P\{Y=1\}=\frac{1}{1+e^{W}}$。
(2)对于多分类问题：$LightGBM$会将其拆分为多个二分类问题，然后通过(1)中的方式计算实例属于每个类别的概率值，然后再通过$softmax$输出实例所属类别的概率值。

3.2.6 CatBoost 做了哪些工作？

参考：https://zhuanlan.zhihu.com/p/102540344

3.2.7 Boosting树模型中有哪些可调节的参数？

树的深度$depth$，叶子节点数$num_leaf$，列抽样比例，$L_1$正则化系数，$L_2$正则化系数，训练轮次。

3.2.8 XGBoost，Lightgbm，CATBoost的生长策略

XGB：level-wise;
LGB：leaf-wise;
CAT：SymmetricTree。