- 自助采样法 & Bagging算法 & 随机森林
- 自助采样法（Bootstrap sampling）
- 算法原理
- Bagging算法（Bootstrap aggregating，引导聚集算法）
- 简介
- 包外估计（out-of-bag estimate）
- bagging算法描述
- 随机森林（Random Forest， RF）
- 算法简介
- 算法原理
- 算法描述
- 随机森林的优缺点
给定包含 m m m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集中，使得下次采用时该样本扔有可能被选中，这样经过 m m m次随机采样操作，我们得到含有 m m m个样本的采样集，初始数据集中有的样本多次出现，有的则从未出现。
最终，我们会发现：
-
初始数据集中约有 36.8 36.8% 36.8的样本未出现在采样数据集中
-
初始数据集中约有 63.2 ％ 63.2％ 63.2％的样本出现在采样集中
计算过程如下：
我们做一个简单估计，样本在m次采样中始终不被采样到的概率为 ( 1 − 1 m ) m (1 - frac{1}{m})^m (1−m1)m，取极限得：
lim m → ∞ ( 1 − 1 m ) m → 1 e ≈ 0.368 lim_{m to infty } (1 - frac{1}{m})^m to frac{1}{e}approx 0.368 m→∞lim(1−m1)m→e1≈0.368
Bagging算法（Bootstrap aggregating，引导聚集算法） 简介
Bagging算法（Bootstrap aggregating，引导聚集算法），也被称为装袋算法，是机器学习领域的一种团体学习算法。
Bagging算法是直接基于自助采样法，采样出 T T T个含 m m m个样本的采样集，然后基于每个采样集分别训练出一个基学习期，再将这些基学习器进行结合，通过结合几个模型来降低泛化误差。主要想法是：分别训练几个不同的模型，然后让所有模型表决测试样例的输出。这是机器学习中常规策略的一个例子，被称为模型平均（model averaging）.
模型平均奏效的原因是：不同的模型通常不会再测试集上产生完全相同的误差。模型平均是一个减少泛化误差的方法。
包外估计（out-of-bag estimate）由于每个个体学习器都只使用了初始训练集中约 63.2 63.2% 63.2的样本，剩下的样本可用作验证集来对泛化性能进行包外估计。
对每个个体学习器 h t h_t ht而言，有 36.8 36.8% 36.8的样本没有用来训练，称为该学习器的包外估计样本。令 D t D_t Dt表示个体学习器 h t h_t ht所使用的训练样本集， H o o b ( x ) H^{oob}(x) Hoob(x)表示对样本 x x x的包外预测。
保外估计方法如下：
-
对数据集 D D D中的每个样本 x x x，计算它作为包外样本的个体学习器对该样本的分类情况
-
以简单多数表决方法，得到样本 x x x的包外预测结果：
H o o b ( x ) = arg max y ∈ k ∑ t = 1 T I ( h t ( x ) = y ) ⋅ I ( x ∉ D t ) H^{oob}(x)=argmax_{y in k}sum_{t=1}^{T}I(h_t(x)=y) cdot I(x notin D_t) Hoob(x)=argy∈kmaxt=1∑TI(ht(x)=y)⋅I(x∈/Dt)
-
最后用所有包外预测不等于真实标记的误分个数占样本总数的比例，作为包外估计，则Bagging的泛化误差包外估计为：
H o o b = 1 ∣ D ∣ ∑ ( x , y ) ∈ D I ( H o o b ( x ) ∉ y ) H^{oob}=frac{1}{|D|}sum_{(x,y) in D}I(H^{oob}(x) notin y) Hoob=∣D∣1(x,y)∈D∑I(Hoob(x)∈/y)
bagging算法描述**输入：**训练集 D D D，基学习算法$mathcal{L} ， 基 学 习 器 个 数 ，基学习器个数 ，基学习器个数T$。
过程：
f
o
r
t
=
1
,
2
,
⋯
,
T
d
o
for space t = 1, 2, cdots, T space do
for t=1,2,⋯,T do
1.采样自助得到含m个样本的采样集
D
t
D_t
Dt;
2.用采样集
D
t
D_t
Dt训练第
t
t
t个基学习器
h
t
=
L
(
D
t
)
h_t = mathcal{L}(D_t)
ht=L(Dt)。
输出：
H ( x ) = arg max y ∈ k ∑ t = 1 T I ( h t ( x ) = y ) ( 分 类 任 务 ) H(x)=argmax_{y in k}sum_{t=1}^{T}I(h_t(x)=y) space (分类任务) H(x)=argy∈kmaxt=1∑TI(ht(x)=y) (分类任务)
H = 1 T ∑ t = 1 T h t x ( 回 归 任 务 ) H = frac{1}{T}sum_{t=1}^{T}h_t{x} space (回归任务) H=T1t=1∑Thtx (回归任务)
随机森林（Random Forest， RF） 算法简介RF是以决策树为基学习器构建bagging的基础上，进一步在决策树的训练过程中引入随机属性。简而言之就是：bagging + 决策树。如果非必要的的话，没有必要从头到尾重新搭建基学习器，已有的包可以解决当前问题即可。
RF本质上将，属于集成学习的方法。
算法原理随机森林是Bagging的一个扩展变体，RF与Bagging的不同之处在于：
- Bagging的基学习器不一定是同质的，也不一定是决策树；但RF以CART为基学习器
- RF在训练过程中，引入了随机特征选择。RF在Bagging的数据样本扰动的基础上，增加了输入特征扰动，提高了模型的泛化能力。具体来说：传统决策树在划分特征时，在当前结点的特征集合中，选择一个最优划分特征；而在RF中，是对基决策树的每个结点，先从该结点的特征集合中随机选择一个含有 k k k个特征的子集，然后再从该子集中选择最优划分特征。 k k k越小，模型越健壮，同时对训练集的拟合程度会变差，也就是说** k k k越小，模型方差越大，偏差越大**。
输入： 训练集 D D D，决策树算法 L mathcal{L} L、基学习器个数 T T T。
过程：
$ for space t = 1, 2, cdots, T space do$
1.采样自主得到含 m m m个样本的采样集 D t D_t Dt；
2.用采样集 D t D_t Dt训练第 t t t个基学习器： h t = L ( D t ) h_t = mathcal{L}(D_t) ht=L(Dt)。并且在模型训练过程中，对决策树模型的每个结点，在结点的特征集合中选择 k k k个特征，再从这些特征中选择最优划分特征来划分子树 。
输出：
H ( x ) = arg max y ∈ k ∑ t = 1 T I ( h t ( x ) = y ) ( 分 类 任 务 ) H(x)=argmax_{y in k}sum_{t=1}^{T}I(h_t(x)=y) space (分类任务) H(x)=argy∈kmaxt=1∑TI(ht(x)=y) (分类任务)
H = 1 T ∑ t = 1 T h t x ( 回 归 任 务 ) H = frac{1}{T}sum_{t=1}^{T}h_t{x} space (回归任务) H=T1t=1∑Thtx (回归任务)
随机森林的优缺点随机森林的优点：
- 训练可以高度并行化，可以实现在大型数据集上高效运行；
- 由于可以随机选择决策树结点的划分特征，因此能够处理具有高维特征的输入样本，而不需要降维；
- 能够评估各个特征对预测的重要性；
- 由于采用了随机采样和随机特征选择，训练模型方差小，泛化能力强；
- 对缺失值不敏感，可以处理不平衡数据。
随机森林的缺点：
- 在某些噪音较大的数据集上，容易陷入过拟合。
