自助采样法 & Bagging算法 & 随机森林

自助采样法（Bootstrap sampling）

算法原理

给定包含$m$个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集中，使得下次采用时该样本扔有可能被选中，这样经过$m$次随机采样操作，我们得到含有$m$个样本的采样集，初始数据集中有的样本多次出现，有的则从未出现。

最终，我们会发现：

• 初始数据集中约有$36.8$的样本未出现在采样数据集中

• 初始数据集中约有$63.2％$的样本出现在采样集中

计算过程如下：

我们做一个简单估计，样本在m次采样中始终不被采样到的概率为$(1-\frac{1}{m}{)}^m$，取极限得：

$$\underset{m\to \infty }{\lim }(1-\frac{1}{m}{)}^m\to \frac{1}{e}\approx 0.368$$

---

Bagging算法（Bootstrap aggregating，引导聚集算法）

简介

​ Bagging算法（Bootstrap aggregating，引导聚集算法），也被称为装袋算法，是机器学习领域的一种团体学习算法。

Bagging算法是直接基于自助采样法，采样出$T$个含$m$个样本的采样集，然后基于每个采样集分别训练出一个基学习期，再将这些基学习器进行结合，通过结合几个模型来降低泛化误差。主要想法是：分别训练几个不同的模型，然后让所有模型表决测试样例的输出。这是机器学习中常规策略的一个例子，被称为模型平均（model averaging）.

模型平均奏效的原因是：不同的模型通常不会再测试集上产生完全相同的误差。模型平均是一个减少泛化误差的方法。

包外估计（out-of-bag estimate）

由于每个个体学习器都只使用了初始训练集中约$63.2$的样本，剩下的样本可用作验证集来对泛化性能进行包外估计。

对每个个体学习器$h_t$而言，有$36.8$的样本没有用来训练，称为该学习器的包外估计样本。令$D_t$表示个体学习器$h_t$所使用的训练样本集，$H^{oob}(x)$表示对样本$x$的包外预测。

保外估计方法如下：

1. 对数据集$D$中的每个样本$x$，计算它作为包外样本的个体学习器对该样本的分类情况

2. 以简单多数表决方法，得到样本$x$的包外预测结果：

   $$H^{oob}(x)=\arg \underset{y\in k}{\max }\sum _{t=1}^{T}I(h_t(x)=y)\cdot I(x\notin D_t)$$

3. 最后用所有包外预测不等于真实标记的误分个数占样本总数的比例，作为包外估计，则Bagging的泛化误差包外估计为：

$$H^{oob}=\frac{1}{|D|}\sum _{(x,y)\in D}I(H^{oob}(x)\notin y)$$

bagging算法描述

---

**输入：**训练集$D$，基学习算法$\mathcal{L} $，基学习器个数$T$。

过程：

$fort=1,2,\cdots ,Tdo$
　　　　1.采样自助得到含m个样本的采样集$D_t$;
　　　　2.用采样集$D_t$训练第$t$个基学习器$h_t=\mathcal{L}(D_t)$。

输出：

$$H(x)=\arg \underset{y\in k}{\max }\sum _{t=1}^{T}I(h_t(x)=y)(分类任务)$$

$$H=\frac{1}{T}\sum _{t=1}^T{h}_{t}x(回归任务)$$

随机森林（Random Forest， RF）

算法简介

RF是以决策树为基学习器构建bagging的基础上，进一步在决策树的训练过程中引入随机属性。简而言之就是：bagging + 决策树。如果非必要的的话，没有必要从头到尾重新搭建基学习器，已有的包可以解决当前问题即可。

RF本质上将，属于集成学习的方法。

算法原理

随机森林是Bagging的一个扩展变体，RF与Bagging的不同之处在于：

• Bagging的基学习器不一定是同质的，也不一定是决策树；但RF以CART为基学习器
• RF在训练过程中，引入了随机特征选择。RF在Bagging的数据样本扰动的基础上，增加了输入特征扰动，提高了模型的泛化能力。具体来说：传统决策树在划分特征时，在当前结点的特征集合中，选择一个最优划分特征；而在RF中，是对基决策树的每个结点，先从该结点的特征集合中随机选择一个含有$k$个特征的子集，然后再从该子集中选择最优划分特征。$k$越小，模型越健壮，同时对训练集的拟合程度会变差，也就是说**$k$越小，模型方差越大，偏差越大**。

算法描述

输入： 训练集$D$，决策树算法$\mathcal{L}$、基学习器个数$T$。

过程：

$ for \space t = 1, 2, \cdots, T \space do$

        1.采样自主得到含$m$个样本的采样集$D_t$；

        2.用采样集$D_t$训练第$t$个基学习器：$h_t=\mathcal{L}(D_t)$。并且在模型训练过程中，对决策树模型的每个结点，在结点的特征集合中选择$k$个特征，再从这些特征中选择最优划分特征来划分子树 。

输出：

$$H(x)=\arg \underset{y\in k}{\max }\sum _{t=1}^{T}I(h_t(x)=y)(分类任务)$$

$$H=\frac{1}{T}\sum _{t=1}^T{h}_{t}x(回归任务)$$

随机森林的优缺点

随机森林的优点：

1. 训练可以高度并行化，可以实现在大型数据集上高效运行；
2. 由于可以随机选择决策树结点的划分特征，因此能够处理具有高维特征的输入样本，而不需要降维；
3. 能够评估各个特征对预测的重要性；
4. 由于采用了随机采样和随机特征选择，训练模型方差小，泛化能力强；
5. 对缺失值不敏感，可以处理不平衡数据。

随机森林的缺点：

• 在某些噪音较大的数据集上，容易陷入过拟合。