10 集成学习
10.1 Boosting（提升法）
梯度提升算法首先给定一个目标损失函数，它的定义域是所有可行的弱函数集合；提升算法通过迭代的选择一个负梯度方向上的基函数来逐渐逼近局部最小值。
提升的理论意义：如果一个问题存在弱分类器，则可以通过提升的办法得到强分类器。
基本思想：一个接一个的(串行)训练基学习器，每一个基学习器主要用来修正前面学习器的偏差。
10.1.1 梯度提升(GBDT)
DT表示使用决策树作为基学习器，使用的CART树。GBDT是迭代，但GBDT每一次的计算是都为了减少上一次的残差，进而在残差减少（负梯度）的方向上建立一个新的模型，其弱学习器限定了只能使用CART回归树模型。 残差=（实际值-预测值）
10.1.1.1 GBDT是训练过程如何选择特征？
GBDT使用基学习器是CART树，CART树是二叉树，每次使用yes or no进行特征选择，数值连续特征使用的最小均方误差，离散值使用的gini指数。在每次划分特征的时候会遍历所有可能的划分点找到最有的特征分裂点，这是用为什么gbdt会比rf慢的主要原因之一。
10.1.1.2 GBDT如何防止过拟合？
一般使用缩减因子对每棵树进行降权，可以使用带有dropout的GBDT算法，dart树，随机丢弃生成的决策树，然后再从剩下的决策树集中迭代优化提升树。
GBDT与Boosting区别较大，它的每一次计算都是为了减少上一次的残差，而为了消除残差，可以在残差减小的梯度方向上建立模型;
在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法。
10.1.1.3 梯度提升的如何调参？
1. 首先我们从步长(learning rate)和迭代次数(n_estimators)入手。
开始选择一个较小的步长来网格搜索最好的迭代次数。将步长初始值设置为0.1；
2. 找到了一个合适的迭代次数，对决策树进行调参。首先对决策树最大深度max_depth和内部节点再划分所需最小样本数(min_samples_split)进行网格搜索。
再对min_samples_split和叶子节点最少样本数(min_samples_leaf)一起调参。
得出： {'min_samples_leaf': 60, 'min_samples_split': 1200},
3.对比最开始完全不调参的拟合效果，可见精确度稍有下降，主要原理是我们使用了0.8的子采样，20%的数据没有参与拟合。
需要再对最大特征数(max_features)进行网格搜索。
10.1.1.4 GBDT对标量特征要不要one-hot编码？
从效果的角度来讲，使用category特征和one-hot是等价的，所不同的是category特征的feature空间更小。微软在lightGBM的文档里也说了，category特征可以直接输入，不需要one-hot编码，准确度差不多，速度快8倍。而sklearn的tree方法在接口上不支持category输入，所以只能用one-hot编码。
10.1.1.5 为什么GBDT用负梯度当做残差？
1. 负梯度的方向可证，模型优化下去一定会收敛
2. 对于一些损失函数来说最大的残差方向，并不是梯度下降最好的方向，倒是损失函数最小与残差最小两者目标不统一
10.1.2 自适应提升(AdaBoost)
定义: 是一种提升方法，将多个弱分类器，组合成强分类器。
Adaboost既可以用作分类，也可以用作回归。
算法实现：
1.提高上一轮被错误分类的样本的权值，降低被正确分类的样本的权值；
2.线性加权求和。误差率小的基学习器拥有较大的权值，误差率大的基学习器拥有较小的权值。
10.1.2.1 为什么Adaboost方式能够提高整体模型的学习精度？
根据前向分布加法模型，Adaboost算法每一次都会降低整体的误差，虽然单个模型误差会有波动，但是整体的误差却在降低，整体模型复杂度在提高。
10.1.2.2 使用m个基学习器和加权平均使用m个学习器之间有什么不同？
Adaboost的m个基学习器是有顺序关系的，第k个基学习器根据前k-1个学习器得到的误差更新数据分布，再进行学习，每一次的数据分布都不同，是使用同一个学习器在不同的数据分布上进行学习。
加权平均的m个学习器是可以并行处理的，在同一个数据分布上，学习得到m个不同的学习器进行加权。
10.1.2.3 Adaboost的迭代次数(基学习器的个数)如何控制？
一般使用earlystopping进行控制迭代次数。
10.1.2.4 adaboost算法中基学习器是否很重要，应该怎么选择基学习器？
sklearn中的adaboost接口给出的是使用决策树作为基分类器，一般认为决策树表现良好，其实可以根据数据的分布选择对应的分类器，比如选择简单的LR，或者对于回归问题选择线性回归。
10.1.3 极端梯度提升(XGBoost)
基于boosting增强策略的加法模型，训练的时候采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差。
XGBoost对GBDT进行了一系列优化，比如损失函数进行了二阶泰勒展开、目标函数加入正则项、支持并行和默认缺失值处理等，在可扩展性和训练速度上有了巨大的提升，但其核心思想没有大的变化。
XGBoost的学习分为3步：
① 集成思想 ② 损失函数分析 ③ 求解
10.1.3.1 XGBoost使用泰勒二阶展开的原因？
精准性：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数
可扩展性：损失函数支持自定义，只需要新的损失函数二阶可导。
10.1.3.2 XGBoost可以并行训练的原因？
XGBoost的并行，并不是说每棵树可以并行训练，XGB本质上仍然采用boosting思想，每棵树训练前需要等前面的树训练完成才能开始训练。
XGBoost的并行，指的是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。
10.1.3.3 XGBoost为什么快？
10.1.3.4 XGBoost防止过拟合的方法？
10.1.3.5 XGBoost如何处理缺失值？
在特征k上寻找最佳 split point 时，不会对该列特征 missing 的样本进行遍历，而只对该列特征值为 non-missing 的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。
在逻辑实现上，为了保证完备性，会将该特征值missing的样本分别分配到左叶子结点和右叶子结点，两种情形都计算一遍后，选择分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向。
如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。
10.1.3.6 为什么XGBoost相比某些模型对缺失值不敏感？
对存在缺失值的特征，一般的解决方法是：
离散型变量：用出现次数最多的特征值填充；
连续型变量：用中位数或均值填充；
一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，
也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。
对于有缺失值的数据在经过缺失处理后：
当数据量很小时，优先用朴素贝叶斯；
数据量适中或者较大，用树模型，优先XGBoost；
数据量较大，也可以用神经网络；
避免使用距离度量相关的模型，如KNN和SVM。
10.1.3.7 XGBoost如何处理不平衡数据？
对于不平衡的数据集，例如用户的购买行为，肯定是极其不平衡的，这对XGBoost的训练有很大的影响，XGBoost有两种自带的方法来解决：
第一种，如果你在意AUC，采用AUC来评估模型的性能，那你可以通过设置scale_pos_weight来平衡正样本和负样本的权重。例如，当正负样本比例为1:10时，scale_pos_weight可以取10；
第二种，如果你在意概率(预测得分的合理性)，你不能重新平衡数据集(会破坏数据的真实分布)，应该设置max_delta_step为一个有限数字来帮助收敛（基模型为LR时有效）。
10.1.3.8 XGBoost中叶子结点的权重如何计算出来？
XGBoost目标函数最终推导形式如下：
利用一元二次函数求最值的知识，当目标函数达到最小值Obj*时，每个叶子结点的权重为wj*。
具体公式如下：
10.1.3.9 XGBoost中的一棵树的停止生长条件？
- 当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程。
- 当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。
- 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细。
10.1.3.10 比较LR和GBDT，说说什么情景下GBDT不如LR？
LR是线性模型，可解释性强，很容易并行化，但学习能力有限，需要大量的人工特征工程;
GBDT是非线性模型，具有天然的特征组合优势，特征表达能力强，但是树与树之间无法并行训练，而且树模型很容易过拟合；
当在高维稀疏特征的场景下，LR的效果一般会比GBDT好。原因如下：
先看一个例子：
假设一个二分类问题，label为0和1，特征有100维，如果有1w个样本，但其中只要10个正样本1，而这些样本的特征 f1的值为全为1，而其余9990条样本的f1特征都为0(在高维稀疏的情况下这种情况很常见)。
树模型很容易优化出一个使用f1特征作为重要分裂节点的树，因为这个结点直接能够将训练数据划分的很好，但是当测试的时候，却会发现效果很差，因为这个特征f1只是刚好偶然间跟y拟合到了这个规律，这也是我们常说的过拟合。
那么这种情况下，如果采用LR的话，应该也会出现类似过拟合的情况呀：y = W1*f1 + Wi*fi+….，其中 W1特别大以拟合这10个样本。
为什么此时树模型就过拟合的更严重呢？
因为现在的模型普遍都会带着正则项，而 LR 等线性模型的正则项是对权重的惩罚，也就是 W1一旦过大，惩罚就会很大，进一步压缩 W1的值，使他不至于过大。但是，树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种 case，树只需要一个节点就可以完美分割9990和10个样本，一个结点，最终产生的惩罚项极其之小。
这也就是为什么在高维稀疏特征的时候，线性模型会比非线性模型好的原因了：带正则化的线性模型比较不容易对稀疏特征过拟合。
10.1.3.11 XGBoost在什么地方做的剪枝? 如何进行剪枝？
（1）目标函数时，使用叶子的数目和l2模的平方，控制模型的复杂度
（2）在分裂节点的计算增益中，定义了一个阈值，当增益大于阈值才分裂
先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。
10.1.3.12 XGBoost如何选择最佳分裂点？
XGBoost在训练前预先将特征按照特征值进行了排序，并存储为block结构，以后在结点分裂时可以重复使用该结构。
因此，可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点，根据每次分裂后产生的增益，最终选择增益最大的那个特征的特征值作为最佳分裂点。如果在计算每个特征的最佳分割点时，对每个样本都进行遍历，计算复杂度会很大，这种全局扫描的方法并不适用大数据的场景。XGBoost还提供了一种直方图近似算法，对特征排序后仅选择常数个候选分裂位置作为候选分裂点，极大提升了结点分裂时的计算效率。
10.1.3.13 XGBoost的Scalable性如何体现？
基分类器的scalability： 弱分类器可以支持CART决策树，也可以支持LR和Linear。
目标函数的scalability：支持自定义loss function，只需要其一阶、二阶可导。有这个特性是因为泰勒二阶展开，得到通用的目标函数形式。
学习方法的scalability：Block结构支持并行化，支持 Out-of-core计算。
10.1.3.14 XGBooost参数调优的一般步骤？
首先需要初始化一些基本变量，例如：
max_depth = 5
min_child_weight = 1
gamma = 0
subsample, colsample_bytree = 0.8
scale_pos_weight = 1
(1) 确定learning rate和estimator的数量learning rate可以先用0.1，用cv来寻找最优的estimators(2) max_depth和 min_child_weight
我们调整这两个参数是因为，这两个参数对输出结果的影响很大。我们首先将这两个参数设置为较大的数，然后通过迭代的方式不断修正，缩小范围。
max_depth，每棵子树的最大深度，check from range(3,10,2)。
min_child_weight，子节点的权重阈值，check from range(1,6,2)。
如果一个结点分裂后，它的所有子节点的权重之和都大于该阈值，该叶子节点才可以划分。
(3) gamma也称作最小划分损失min_split_loss，check from 0.1 to 0.5，指的是，对于一个叶子节点，当对它采取划分之后，损失函数的降低值的阈值。
如果大于该阈值，则该叶子节点值得继续划分；
如果小于该阈值，则该叶子节点不值得继续划分。
(4) subsample, colsample_bytree
subsample是对训练的采样比例
colsample_bytree是对特征的采样比例
both check from 0.6 to 0.9
(5) 正则化参数
alpha 是L1正则化系数，try 1e-5, 1e-2, 0.1, 1, 100
lambda 是L2正则化系数
(6) 降低学习率降低学习率的同时增加树的数量，通常最后设置学习率为0.01~0.1
10.1.3.15 XGBoost模型如果过拟合了怎么解决？
当出现过拟合时，有两类参数可以缓解：
第一类参数：用于直接控制模型的复杂度。
包括max_depth,min_child_weight,gamma 等参数
第二类参数：用于增加随机性，从而使得模型在训练时对于噪音不敏感。
包括subsample,colsample_bytree还有就是直接减小learning rate，
但需要同时增加estimator 参数。
10.1.3.16 XGBoost如何寻找最优特征？是有放回还是无放回？
XGBoost利用梯度优化模型算法, 样本是不放回的。但XGBoost支持子采样, 也就是每轮计算可以不使用全部样本。
10.1.3.17 XGBoost如何分布式？特征分布式和数据分布式？ 各有什么问题？
XGBoost在训练之前，预先对数据按列进行排序，然后保存block结构。
- 特征分布式(特征间并行)：由于将数据按列存储，可以同时访问所有列，那么可以对所有属性同时执行切分点寻找算法，从而并行化切分点寻找；
（2）数据分布式(特征内并行)：可以用多个block分别存储不同的样本集，多个block可以并行计算。
问题：（1）不能从本质上减少计算量；（2）通讯代价高。
10.1.3.18 为什么XGBoost的近似算法比lightgbm慢很多呢？
xgboost在每一层都动态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。
10.1.4 LightGBM
基本思想: 先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点；
基于决策树算法的分布式梯度提升框架；是对GBDT的高效实现，原理上它和GBDT及XGBoost类似，都采用损失函数的负梯度作为当前决策树的残差近似值，去拟合新的决策树。
10.1.5 CatBoost
原理：One-hot编码可以在预处理阶段或在训练期间完成; 处理类别型特征棒。
具体实现方法如下：
1.将输入样本集随机排序，并生成多组随机排列的情况;
2.将浮点型或属性值标记转化为整数;
3.将所有的分类特征值结果都根据以下公式，转化为数值结果。
10.2 Bagging(套袋法)
算法过程如下：
从原始样本集中使Bootsraping方法随机抽取n个训练样本,共进行轮抽取, 得到k个训练集。 (k个训练集之间相互独立, 元素可以有重复)
对于k个训练集， 我们训练k个模型(这k个模型可以根据具体问题而定,比如决策树, knn等)
对于分类问题:由投票表决产生分类结果;
对于回归问题: 由k个模型预测结果的均值作为最后预测结果。
Bagging + 决策树 = 随机森林
AdaBoost + 决策树 = 提升树
Gradient Boosting + 决策树 = GBDT
10.2.1 随机森林
定义: 随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于集成学习方法。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。
算法思想:
1.随机选择样本（放回抽样）--> 2.随机选择特征 --> 3.构建决策树 --> 4.随机森林投票（平均）
10.2.1.1随机森林的随机性指的是？
1.决策树训练样本是有放回随机采样的；
2.决策树节点分裂特征集是有放回随机采样的；
10.2.1.2 为什么随机抽样？
保证基分类器的多样性，若每棵树的样本集都一样，训练的每棵决策树都是一样
10.2.1.3 为什么要有放回的抽样？
保证样本集间有重叠，若不放回，每个训练样本集及其分布都不一样，可能导致训练的各决策树差异性很大，最终多数表决无法 “求同”，即最终多数表决相当于“求同”过程。
10.2.1.4 为什么不用全样本训练？
全样本忽视了局部样本的规律，不利于模型泛化能力
10.2.1.5 为什么要随机特征？
随机特征保证基分类器的多样性（差异性），最终集成的泛化性能可通过个体学习器之间的差异度而进一步提升，从而提高泛化能力和抗噪能力
10.2.1.6 需要剪枝吗？
不需要，后剪枝是为了避免过拟合，随机森林随机选择变量与树的数量，已经避免了过拟合，没必要去剪枝了。一般rf要控制的是树的规模，而不是树的置信度，剩下的每棵树需要做的就是尽可能的在自己所对应的数据(特征)集情况下尽可能的做到最好的预测结果。剪枝的作用其实被集成方法消解了，所以用处不大
10.2.1.7 随机森林如何处理缺失值？
1.对于训练集,同一个类下的数据：如果是分类变量缺失，用众数补上；如果是连续型变量缺失，用中位数补。
2.先用方法1补上缺失值，然后构建森林并计算相似矩阵，再回头看缺失值，如果是分类变量，则用没有阵进行加权平均的方法补缺失值。然后迭代4-6次。
10.2.1.8 随机森林如何评估特征重要性？
1.Decrease GINI：对于回归问题，直接使用argmax作为评判标准，即当前节点训练集的方差(Var)减去左节点的方差(VarLeft)和右节点的方差(VarRight)。
2.Decrease Accuracy：对于一棵树，我们用OOB样本可以得到测试误差1；然后随机改变OOB样本的第j列：保持其他列不变，对第j列进行随机的上下置换，得到误差2。可以用(误差1-误差2)来刻画变量j的重要性。
基本思想: 如果一个变量j足够重要，那么改变它会极大的增加测试误差；反之，如果改变它测试误差没有增大，则说明该变量不是那么的重要。
10.2.1.9 RF与决策树的区别？
（1）RF是决策树的集成；
（2）RF中是“随机属性型”决策树
10.2.1.10 RF为什么比bagging效率高？
因为在个体决策树的构建过程中，Bagging使用的是“确定型”决策树，bagging在选择划分属性时要对每棵树是对所有特征进行考察；而随机森林仅仅考虑一个特征子集。
10.2.1.11 RF为什么能够更鲁棒？
由于RF使用了使用了行采样和列采样技术，是的每棵树不容易过拟合；并且是基于树的集成算法，由于使用了采用数据是的每棵树的差别较大，在进行embedding的时候可以更好的降低模型的方差，整体而言是的RF是一个鲁棒的模型。
10.2.1.12 RF分类和回归问题如何预测y值？
RF是一个加权平均的模型，是进行分类问题的时候，使用的个k个树的投票策略，多数服从少数。在回归的使用是使用的k个树的平均。可以看出来rf的训练和预测过程都可以进行并行处理。
10.2.1.13 为什么RF的树比GBDT的要深一点？
RF是通过投票的方式来降低方差，但是本质上需要每棵树有较强的表达能力，所以单颗树深点没关系，通过投票的方式降低过拟合。而GBDT是通过加强前一棵树的表达能力，所以每颗树不必有太强的表达能力。可以通过boosting的方式来提高，也能提高训练速度（gbdt害怕过拟合，rf不怕，通过投票的方式杜绝）
