随机森林算法是一种典型的集成学习算法，他是使用Bagging和Decision Tree的结合
Random Forest Algorithm
在前文中，我们已经介绍了bagging的方法，即通过bootstrap方法从原始数据集D中得到新的$\hat{D}$。然后再使用一些base algorithm对每个$\hat{D}$得到对应的$g_t$;最后将所有的$g_t$通过投票uniform的形式形成一个G。
而Decision Tree通过递归方法，利用分支条件，将原始数据集D分为一个个子树结构，最后长成一个完整的树形结构。
之所以将bagging和Decision Tree联合，这是因为bagging具有减小不同$g_t$的方差variance的作用。这是因为bagging采用投票的形式，将所有$g_t$uniform结合起来，起到了求平均的作用，从而降低了variance。而决策树因为每次切割的方式不同，而且分支包含的样本数逐渐减少，所以它对不同的资料D比较敏感，从而会得到较大的variance。所以如果将两者结合，我们也许会得到一个更加健壮的算法。
所以简单的随机森林算法就是使用Bootstrap得到不同的数据，然后基于不同的数据获得不同的决策树$g_t$，然后进行投票结合。
但是为了决策树保证多样性，我们有添加了额外的步骤，
就是在生成决策树的时候，我们随机抽取一部分特征，而不是使用全部的特征。例如，如果原本有100个特征，我们可以随机从里面抽取10个。这其实就是一种特殊的特征转换，从高维特征转换到低维特征。所以，我们的随机森林的最终算法就是:
For t = 1, 2, …., T:
-
从数据D中使用bootstrap方法获得尺寸为$N^{‘}$的的数据$\hat{D_t}$，
-
从M个特征中随机选择m个特征，满足m«M。
-
使用m个特征的数据$\hat{D_t}$基于决策树算法$\text{DTree}(\hat{D_t})$求解决策树$g_t$。
Return G = Uniform({$g_t$})
OOB
随机森林有一个非常好的优点，就是不需要使用交叉验证或者使用一个独立的测试集来获得误差的无偏估计。他完全可以在内部就进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。
之所以这样，是因为我们使用了bootstrap随机抽取了数据，所以在每一轮bootstrap存在有未被选中的数据。
假设对于N个样本，我们每次采样的样本个数也是N，那么对于一个样本未被选中的可能性为:$(1-\frac{1}{N})^N$.
假设我们的N是无限大的，那么我们就会得到一个极小替换:
\[\lim_{N\rightarrow\infty}(1-\frac{1}{N})^N = \frac{1}{e}\]所以，我们大概有$\frac{N}{e}$个样本没有被选中，大概$\frac{1}{3}$。这些资料就被成为OOB(out of bag)资料。
那么该如何使用OOB资料进行验证，我们假设有一下数据。
对于$(x_N, y_N)$，我们在训练$g_2, g_3, g_T$时没有使用到$(x_N, y_N)$, 因此，我们就可以使用这个样本来验证$g_2, g_3, g_T$。
我们将$g_2, g_3, g_T$组成一个局部随机森林$G_N^{-}(x) = vote(g_2, g_3, g_T)$。然后我们使用$(x_N, y_N)$来验证$G_N^-(x)$，即$err(y_N, G_N^{-}(x))$。
然后对于整个随机森林的误差就是所有样本的求平均:
\[E_{oob}(G) = \frac{1}{N}\sum_{n=1}^N \text{err}(y_n, G_n^{-}(x))\]其中$G_n^{-}(x)$就是没有使用样本$(x_n, y_n)$训练出来的决策树$g_t$的聚合。
特征选择
随机森林有一个较为重要的方法就是特征选择，一般而言，如果样本的特征数较多，我们就需要从样本中挑选一部分，而舍弃其他样本。这主要是因为样本中可能存在冗余特征，比如年龄和生日。或者存在不相关信息，比如预测疾病时的“保险状况”。
选择适当的特征有有优点也有缺点:
优点:1. 更高效 2. 去噪声 3. 去除无关特征
缺点: 1. 计算复杂 2. 易过拟合 3. 容易选到无关特征，导致解释性差
一般做特征选择就是依据特征的重要性，我们为特征计算一个重要性importance(i)，然后依次排序，选择重要性较前的特征。而计算重要性有两种思路。
- 线性模型， 在做线性拟合时，我们为每一个特征分配了一个权重$s = w^Tx$，因此，我们可以令$ \text{importance}(i) = \vert w_i\vert$， 也就是说特征对应的权重越大，说明，特征在分数中占比越大，也就越重要
- 非线性模型random forest， 对于非线性模型，其实主要的方法就是为特征添加噪声从而影响最终结果，如果影响较大，显然，我们的特征就比较重要。添加随机值的方法有两种，一种是使用高斯分布等生成随机数，一种就是将原本N个样本中的第i个特征值打乱。一般都是使用第二种
随机森林做特征选择
如果使用随机森林求解特征重要性，我们需要每一次打乱都要重新构建一个随机森林，这个计算量无疑是巨大的，所以，一种方法就是将重要性评估放在OOB validation上。
就是说我们的随机森林仍然使用样本D来构建，但是在使用OOB验证时，我们将第i个特征值打乱，然后计算$E_{oob}^{(p)}$验证G的表现。如果结果变化较大，说明比较重要。即，我们的importance(i)定义为:
\[\text{importance(i)} = E_{oob}(G) - E_{oob}^{(p)}(G)\]其中$E_{oob}^{(p)}$是从打乱第i个特征的OOB样本中得到的。这种方法大大简化了计算复杂度，因为应用广泛。