1 Bagging
1.1 Bagging
通过“自助采样”的方法来增加多样性。
Bagging是一种并行式的集成学习方法，即基学习器的训练之间没有前后顺序可以同时进行，Bagging使用“有放回”采样的方式选取训练集，对于包含m个样本的训练集，进行m次有放回的随机采样操作，从而得到m个样本的采样集，这样训练集中有接近36.8%的样本没有被采到。按照相同的方式重复进行，我们就可以采集到T个包含m个样本的数据集，从而训练出T个基学习器，最终对这T个基学习器的输出进行结合。
Bagging算法的流程如下所示：
可以看出Bagging主要通过样本的扰动来增加基学习器之间的多样性，因此Bagging的基学习器应为那些对训练集十分敏感的不稳定学习算法，例如：神经网络与决策树等。从偏差-方差分解来看，Bagging算法主要关注于降低方差，即通过多次重复训练提高稳定性。不同于AdaBoost的是，Bagging可以十分简单地移植到多分类、回归等问题。总的说起来则是：AdaBoost关注于降低偏差，而Bagging关注于降低方差。
1.2 随机森林
Bagging + 决策树 = 随机森林
随机森林（Random Forest）是Bagging的一个拓展体，它的基学习器固定为决策树，多棵树也就组成了森林，而“随机”则在于选择划分属性的随机，随机森林在训练基学习器时，也采用有放回采样的方式添加样本扰动，同时它还引入了一种属性扰动，即在基决策树的训练过程中，在选择划分属性时，RF先从候选属性集中随机挑选出一个包含K个属性的子集，再从这个子集中选择最优划分属性，一般推荐K=log2（d）。
多次随机取样，多次随机取属性，选取最优分割点，构建多个(CART)分类器，投票表决
这样随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，从而进一步提升了基学习器之间的差异度。相比决策树的Bagging集成，随机森林的起始性能较差（由于属性扰动，基决策树的准确度有所下降），但随着基学习器数目的增多，随机森林往往会收敛到更低的泛化误差。同时不同于Bagging中决策树从所有属性集中选择最优划分属性，随机森林只在属性集的一个子集中选择划分属性，因此训练效率更高。
算法流程：
输入为样本集
，弱分类器迭代次数
。
输出为最终的强分类器
-
对于
- 对训练集进行第
次随机采样，共采集
次，得到包含
- 用采样集
训练第
，在训练决策树模型的节点的时候，在节点上所有的样本特征中选择一部分样本特征，在这些随机选择的部分样本特征中选择一个最优的特征来做决策树的左右子树划分
- 对训练集进行第
如果是分类算法预测，则
随机森林有许多优点：
- 具有极高的准确率
- 随机性的引入，使得随机森林不容易过拟合
- 随机性的引入，使得随机森林有很好的抗噪声能力
- 能处理很高维度的数据，并且不用做特征选择
- 既能处理离散型数据，也能处理连续型数据，数据集无需规范化
- 训练速度快，可以得到变量重要性排序
- 容易实现并行化
随机森林的缺点：
- 当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大
- 随机森林模型还有许多不好解释的地方，有点算个黑盒模型
与上面介绍的Bagging过程相似，随机森林的构建过程大致如下：
从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
对于n_tree个训练集，我们分别训练n_tree个决策树模型
对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果
2 面试题
随机森林的随机性体现在哪里？
多次有放回的随机取样，多次随机选择特征随机森林为什么不容易过拟合？
- 随机森林中的每一颗树都是过拟合的，拟合到非常小的细节上
- 随机森林通过引入随机性，使每一颗树拟合的细节不同
- 所有树组合在一起，过拟合的部分就会自动被消除掉。
因此随机森林出现过拟合的概率相对低。
为什么不用全样本训练？
全样本训练忽视了局部样本的规律（各个决策树趋于相同），对于模型的泛化能力是有害的，使随机森林算法在样本层面失去了随机性。为什么要随机特征？
随机特征保证基分类器的多样性（差异性），最终集成的泛化性能可通过个体学习器之间的差异度而进一步提升，从而提高泛化能力和抗噪能力。RF与 GBDT 的区别？
- 随机森林将多棵决策树的结果进行投票后得到最终的结果，对不同的树的训练结果也没有做进一步的优化提升，将其称为Bagging算法。
- GBDT用到的是Boosting算法，在迭代的每一步构建弱学习器弥补原有模型的不足。GBDT中的Gradient Boost就是通过每次迭代的时候构建一个沿梯度下降最快的方向的学习器。
RF为什么比Bagging效率高？
因为在个体决策树的构建过程中，Bagging使用的是“确定型”决策树，bagging在选择划分属性时要对每棵树是对所有特征进行考察；而随机森林仅仅考虑一个特征子集。你已经建了一个有10000棵树的随机森林模型。在得到0.00的训练误差后，你非常高兴。但是，验证错误是34.23。到底是怎么回事？你还没有训练好你的模型吗？
- 模型过拟合十分严重
- 新的测试集与训练集的数据分布不一致
- 如何使用随机森林对特征重要性进行评估？
袋外数据(OOB)： 大约有1/3的训练实例没有参与第k棵树的生成，它们称为第棵树的袋外数据样本。
在随机森林中某个特征的重要性的计算方法如下：
- 对于随机森林中的每一颗决策树，使用相应的OOB(袋外数据)来计算它的袋外数据误差，记为
。
- 随机地对袋外数据OOB所有样本的特征
。
- 假设随机森林中有
棵树，那么对于特征
，之所以可以用这个表达式来作为相应特征的重要性的度量值是因为：若给某个特征随机加入噪声之后，袋外的准确率大幅度降低，则说明这个特征对于样本的分类结果影响很大，也就是说它的重要程度比较高。
- 随机森林算法训练时主要需要调整哪些参数？
-
n_estimators:随机森林建立子树的数量。
较多的子树一般可以让模型有更好的性能，但同时让你的代码变慢。需要选择最佳的随机森林子树数量 -
max_features：随机森林允许单个决策树使用特征的最大数量。
增加max_features一般能提高模型的性能，因为在每个节点上，我们有更多的选择可以考虑。然而，这未必完全是对的，因为它降低了单个树的多样性，而这正是随机森林独特的优点。但是，可以肯定，你通过增加max_features会降低算法的速度。因此，你需要适当的平衡和选择最佳max_features。 -
max_depth： 决策树最大深度
默认决策树在建立子树的时候不会限制子树的深度 -
min_samples_split：内部节点再划分所需最小样本数
内部节点再划分所需最小样本数，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 -
min_samples_leaf： 叶子节点最少样本
这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 -
max_leaf_nodes： 最大叶子节点数
通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。 -
min_impurity_split： 节点划分最小不纯度
这个值限制了决策树的增长，如果某节点的不纯度（基于基尼系数，均方差）小于这个阈值，则该节点不再生成子节点。即为叶子节点。一般不推荐改动默认值1e-7。
- 随机森林的优缺点
- 优点
- 训练可以高度并行化，对于大数据时代的大样本训练速度有优势。个人觉得这是的最主要的优点。
- 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。
- 在训练后，可以给出各个特征对于输出的重要性
- 由于采用了随机采样，训练出的模型的方差小，泛化能力强。
- 相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。
- 对部分特征缺失不敏感，如果有很大一部分的特征遗失，仍可以维持准确度。
- 缺点
- 在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
- 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。
- Adaboost和随机森林算法的异同点
随机森林和Adaboost算法都可以用来分类，它们都是优秀的基于决策树的组合算法。
- 相同之处
- 二者都是Bootstrap自助法选取样本。
- 二者都是要训练很多棵决策树。
- 不同之处
- Adaboost是基于Boosting的算法，随机森林是基于Bagging的算法。
- Adaboost后面树的训练，其在变量抽样选取的时候，对于上一棵树分错的样本，抽中的概率会加大。
- 随机森林在训练每一棵树的时候，随机挑选了部分特征作为拆分特征，而不是所有的特征都去作为拆分特征。
- 在预测新数据时，Adaboost中所有的树加权投票来决定因变量的预测值，每棵树的权重和错误率有关；随机森林按照所有树中少数服从多数树的分类值来决定因变量的预测值（或者求取树预测的平均值）。
- GBDT和RF如何计算特征重要性
- RF有两种方法：
- 通过计算Gini系数的减少量VIm=GI−(GIL+GIR)判断特征重要性，越大越重要。
- 对于一颗树，先使用袋外错误率(OOB)样本计算测试误差a，再随机打乱OOB样本中第i个特征（上下打乱特征矩阵第i列的顺序）后计算测试误差b，a与b差距越大特征i越重要。
-
GBDT计算方法：
- 所有回归树中通过特征i分裂后平方损失的减少值的和/回归树数量 得到特征重要性。 在sklearn中，GBDT和RF的特征重要性计算方法是相同的，都是基于单棵树计算每个特征的重要性，探究每个特征在每棵树上做了多少的贡献，再取个平均值。
-
Xgb主要有三种计算方法：
- importance_type=weight（默认值），特征重要性使用特征在所有树中作为划分属性的次数。
- mportance_type=gain，特征重要性使用特征在作为划分属性时loss平均的降低量。
- importance_type=cover，特征重要性使用特征在作为划分属性时对样本的覆盖度。
