上一节我们提到决策树的一个主要缺点在于经常对训练数据过拟合。随机森林是解决这个问题的一种方法。随机森林是属于集成学习，其核心思想就是集成多个弱分类器以达到一个强分类器的效果。

1 bagging的原理

        随机森林采用Bagging的思想，所谓的Bagging可以用下面这张图表示：

        从上图可以看出，Bagging的弱学习器之间的确没有boosting那样的联系。它的特点在“随机采样”。那么什么是随机采样？

        随机采样(bootsrap)就是从我们的训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。对于我们的Bagging算法，一般会随机采集和训练集样本数m一样个数的样本。这样得到的采样集和训练集样本的个数相同，但是样本内容不同。如果我们对有m个样本训练集做T次的随机采样，，则由于随机性，T个采样集各不相同。

温馨提示：这和GBDT的子采样是不同的。GBDT的子采样是无放回采样，而Bagging的子采样是放回采样。

        对于一个样本，它在某一次含$m$个样本的训练集的随机采样中，每次被采集到的概率是$\frac{1}{m}$。不被采集到的概率为$1-\frac{1}{m}$。如果$m$次采样都没有被采集中的概率是$(1-\frac{1}{m}{)}^m$。当$m\to \infty$时，$(1-\frac{1}{m}{)}^m\to \frac{1}{e}\approx 0.368$。也就是说，在bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。

        对于这部分大约36.8%的没有被采样到的数据，我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。

        bagging对于弱学习器没有限制，这和Adaboost一样。但是最常用的一般也是决策树和神经网络。

        bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到最终的模型输出。

        由于Bagging算法每次都进行采样来训练模型，因此泛化能力很强，对于降低模型的方差很有作用。当然对于训练集的拟合程度就会差一些，也就是模型的偏倚会大一些。

        Bagging 的算法描述如下图所示：

---

2 随机森林算法

        随机森林(Random Forest,以下简称RF)是Bagging算法的进化版，也就是说，它的思想仍然是bagging，但是进行了独有的改进。我们现在就来看看RF算法改进了什么。

        首先，RF使用了CART决策树作为弱学习器。第二，在使用决策树的基础上，RF对决策树的建立做了改进，对于普通的决策树，我们会在节点上所有的$n$个样本特征中选择一个最优的特征来做决策树的左右子树划分，但是RF通过随机选择节点上的一部分样本特征，这个数字小于$n$，假设为$n_{sub}$，然后在这些随机选择的$n_{sub}$个样本特征中，选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。

        如果$n_{sub}=n$，则此时RF的CART决策树和普通的CART决策树没有区别。$n_{sub}$越小，则模型约健壮，当然此时对于训练集的拟合程度会变差。也就是说$n_{sub}$越小，模型的方差会减小，但是偏倚会增大。在实际案例中，一般会通过交叉验证调参获取一个合适的$n_{sub}$的值。

        随机森林本质上是许多决策树的集合，其中每棵树都和其他树略有不同。随机森林背后的思想是，每棵树的预测可能都相对较好，但可能对部分数据过拟合。如果构造很多树，并且每棵树的预测都很好，但都以不同的方式过拟合，那么我们可以对这些树的结果取平均值来降低过拟合。既能减少过拟合又能保持树的预测能力，这可以在数学上严格证明。

        为了实现这一策略，我们需要构造许多决策树。每棵树都应该对目标值做出可以接受的预测，还应该与其他树不同。随机森林的名字来自于将随机性添加到树的构造过程中，以确保每棵树都各不相同。随机森林中树的随机化方法有两种：一种是通过选择用于构造树的数据点，另一种是通过选择每次划分测试的特征。我们来更深入地研究这一过程。

        构造随机森林。想要构造一个随机森林模型，你需要确定用于构造的树的个数（RandomForestRegressor或RandomForestClassifier的n_estimators参数）。比如我们想要构造10棵树。这些树在构造时彼此完全独立，算法对每棵树进行不同的随机选择，以确保树和树之间是有区别的。

        接下来，基于这个新创建的数据集来构造决策树。但是，要对我们在介绍决策树时描述的算法稍作修改。在每个结点处，算法随机选择特征的一个子集，并对其中一个特征寻找最佳测试，而不是对每个结点都寻找最佳测试。选择的特征个数由max_features参数来控制。每个结点中特征子集的选择是相互独立的，这样树的每个结点可以使用特征的不同子集来做出决策。

        由于使用了自助采样，随机森林中构造每棵决策树的数据集都是略有不同的。由于每个结点的特征选择，每棵树中的每次划分都是基于特征的不同子集。这两种方法共同保证随机森林中所有树都不相同。

        在这个过程中的一个关键参数是max_features。如果我们设置max_features等于n_features，那么每次划分都要考虑数据集的所有特征，在特征选择的过程中没有添加随机性（不过自助采样依然存在随机性）。如果设置max_features等于1，那么在划分时将无法选择对哪个特征进行测试，只能对随机选择的某个特征搜索不同的阈值。因此，如果max_features较大，那么随机森林中的树将会十分相似，利用最独特的特征可以轻松拟合数据。如果max_features 较小，那么随机森林中的树将会差异很大，为了很好地拟合数据，每棵树的深度都要很大。

---

3 sklearn实现

3.1 模型介绍

        在scikit-learn中，RF的分类器是RandomForestClassifier，回归器是RandomForestRegressor。RF的参数也包括两部分，第一部分是Bagging框架的参数，第二部分是一棵CART决策树的参数。具体的参数参考随机森林分类器的函数原型：

class sklearn.ensemble.RandomForestClassifier(
											  n_estimators=100, *, criterion='gini', 
											  max_depth=None, min_samples_split=2, 
											  min_samples_leaf=1, min_weight_fraction_leaf=0.0, 
											  max_features='sqrt', max_leaf_nodes=None, 
											  min_impurity_decrease=0.0, bootstrap=True, 
											  oob_score=False, n_jobs=None, 
											  random_state=None, verbose=0, 
											  warm_start=False, class_weight=None, 
											  ccp_alpha=0.0, max_samples=None)

1. Bagging框架参数

        下面来看看RF重要的Bagging框架的参数，由于RandomForestClassifier和RandomForestRegressor参数绝大部分相同，这里会将它们一起讲，不同点会指出。

• n_estimators: 弱学习器（决策树）的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，计算量会太大，并且n_estimators到一定的数量后，再增大n_estimators获得的模型提升会很小，所以一般选择一个适中的数值。默认是100。
• oob_score：即是否采用袋外样本来评估模型的好坏。默认False。推荐设置为True，因为袋外分数反应了一个模型拟合后的泛化能力。
• criterion: 即CART树做划分时对特征的评价标准。分类模型和回归模型的损失函数是不一样的。分类RF对应的CART分类树默认是基尼系数gini,另一个可选择的标准是信息增益(information gain)。回归RF对应的CART回归树默认是均方差mse，另一个可以选择的标准是绝对值差mae。一般来说选择默认的标准就已经很好的。

        从上面可以看出, RF重要的框架参数比较少，主要需要关注的是n_estimators，即森林中决策树的个数。

2. 决策树参数
        下面我们再来看RF的决策树参数:

• RF划分时考虑的最大特征数 max_features: 就是之前提到的“在每个节点处，从M中随机选择m个特征维度”中的那个m。默认是"auto",意味着每个节点在划分时随机考虑$\sqrt{(}n)$个特征；如果是"log2"意味着划分时随机考虑$lo{g}_{2}N$个特征；如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑百分比*总特征维度数取整后的特征数。一般用默认的"auto"就可以了；如果特征数非常多，可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。
• 决策树最大深度max_depth: 默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
• 内部节点再划分所需最小样本数min_samples_split: 这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再划分。默认是2。如果样本量数量级非常大，则推荐增大这个值。
• 叶子节点最少样本数min_samples_leaf: 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝，只保留原来的父节点。默认是1。如果样本量数量级非常大，则推荐增大这个值。
• 叶子节点最小的样本权重和min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝，只保留原来的父节点。 默认是0，就是不考虑权重问题。如果我们有较多样本有缺失值，或者分类树样本的分布类别非常不平衡，就会引入样本权重，这时我们就要注意这个值了。
• 最大叶子节点数max_leaf_nodes: 通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征非常多的话，可以加以限制，具体的值可以通过交叉验证得到。
• 节点划分最小不纯度min_impurity_decrease: 这个值限制了决策树的增长，如果某节点的不纯度(基于基尼系数，均方差)小于这个阈值，则该节点不再生成子节点。即为叶子节点 。一般不推荐改动，默认值1e-7。
• 用于最小成本-复杂度修剪的复杂度参数ccp_alpha。将选择成本复杂度最大且小于ccp_alpha的子树。默认情况下，不进行修剪。详情请看最小成本复杂度修剪。
• max_samples，如果bootstrap为True，则从X中抽取的样本数量，以训练每个基础估计器。

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

3.2 案例分析

        导入常用的库：

import mglearn
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

        下面将由5棵树组成的随机森林应用到前面研究过的two_moons数据集上：

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split


X, y = make_moons(n_samples=100, noise=0.25, random_state=3)
X_train, X_test, y_train, y_test = train_test_split(X, y, stratify=y, random_state=42)

forest = RandomForestClassifier(n_estimators=5, random_state=2)
forest.fit(X_train, y_train)

        作为随机森林的一部分，树被保存在estimator_属性中。我们将每棵树学到的决策边界可视化，也将它们的总预测（即整个森林做出的预测）可视化。

fig, axes = plt.subplots(2, 3, figsize=(20, 10))
for i, (ax, tree) in enumerate(zip(axes.ravel(), forest.estimators_)):
    ax.set_title("tree {}".format(i))
    mglearn.plots.plot_tree_partition(X_train, y_train, tree, ax=ax)

mglearn.plots.plot_2d_separator(forest, X_train, fill=True, ax=axes[-1, -1], alpha=.4)
axes[-1, -1].set_title("Random Forest")
mglearn.discrete_scatter(X_train[:, 0], X_train[:, 1], y_train)

        可以清楚地看到，这5棵树学到的决策边界大不相同。每棵树都犯了一些错误，因为这里画出的一些训练点实际上并没有包含在这些树的训练集中，原因在于自助采样。

        随机森林比单独每一棵树的过拟合都要小，给出的决策边界也更符合直觉。在任何实际应用中，我们会用到更多棵树（通常是几百或上千），从而得到更平滑的边界。

        我们将包含100棵树的随机森林应用在乳腺癌数据集上：

from sklearn.datasets import load_breast_cancer

cancer = load_breast_cancer()

X_train, X_test, y_train, y_test = train_test_split(cancer.data, cancer.target, random_state=0)
forest = RandomForestClassifier(n_estimators=100, random_state=0)
forest.fit(X_train, y_train)

print("Accuracy on training set: {:.3f}".format(forest.score(X_train, y_train)))         
print("Accuracy on test set: {:.3f}".format(forest.score(X_test, y_test)))              

Accuracy on training set: 1.000
Accuracy on test set: 0.972

        在没有调节任何参数的情况下，随机森林的精度为97%，比线性模型或单棵决策树都要好。我们可以调节max_features 参数，或者像单棵决策树那样进行预剪枝。但是，随机森林的默认参数通常就已经可以给出很好的结果。

        与决策树类似，随机森林也可以给出特征重要性，计算方法是将森林中所有树的特征重要性求和并取平均。一般来说，随机森林给出的特征重要性要比单棵树给出的更为可靠。

def plot_feature_importances_cancer(model):
    n_features = cancer.data.shape[1]
    plt.barh(range(n_features), model.feature_importances_, align='center')
    plt.yticks(np.arange(n_features), cancer.feature_names)
    plt.xlabel("Feature importance")
    plt.ylabel("Feature")

plot_feature_importances_cancer(forest)

        与单棵树相比，随机森林中有更多特征的重要性不为零。与单棵决策树类似，随机森林也给了“worst radius”（最大半径）特征很大的重要性，但从总体来看，它实际上却选择“worst perimeter”（最大周长）作为信息量最大的特征。由于构造随机森林过程中的随机性，算法需要考虑多种可能的解释，结果就是随机森林比单棵树更能从总体把握数据的特征。

---

小结

RF的主要优点有：

• 训练可以高度并行化，对于大数据时代的大样本训练速度有优势。个人觉得这是的最主要的优点。
• 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。
• 在训练后，可以给出各个特征对于输出的重要性
• 由于采用了随机采样，训练出的模型的方差小，泛化能力强。
• 相对于Boosting系列的Adaboost和GBDT，RF实现比较简单。
• 对部分特征缺失不敏感。

RF的主要缺点有：

• 在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
• 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。

---

参考

• Bagging与随机森林算法原理：https://www.cnblogs.com/pinard/p/6156009.html
• 随机森林（Random Forest）：https://blog.csdn.net/qq_34106574/article/details/82016442
• 随机森林：https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#inter