Random Forest.

随机森林(Random Forest)是一种把bagging和决策树结合起来的方法。在以决策树(如CART)为基学习器构建bagging集成模型的基础上，随机森林在决策树的训练过程中引入了随机子空间(random subspace)算法。

随机森林方法的优点：

  1. 每一个基学习器(CART决策树)训练是独立的，该算法可以并行实现；
  2. 继承了CART的优点(可解释性好,易于实现,能够处理特征缺失)；
  3. 使用bagging集成多个树，避免了过拟合问题，提高了模型的泛化能力。

1. 为决策树引入随机性 random-combination CART

标准的CART决策树在训练时，每一次选择分支(branching)是在当前结点的特征集合(假设有$d$个特征)中选择一个最优特征。在随机森林中， 在训练每一个CART基学习器时，为增加模型的能力，每一次选择分支时，可以随机的选择样本的一部分特征，比如选择其中的$k$个特征，再在这$k$个特征$(x_{i_1},x_{i_2},…,x_{i_{k}})$中选择一个最优特征构建分支。若$k=d$，则等价于标准的CART；若$k=1$，则随机选择一个特征用于划分；一般情况下推荐选$k=\log_2d$。

将随机子空间算法引入随机森林，在选择分支时可以引入特征映射(Feature Projection)，即：

\[φ(x) = Px\]

其中$P$是从高维映射到低维的映射矩阵，相当于对原特征进行随机的线性组合，映射到新的特征空间。这样做使得在选择分支时不是使用决策树桩(针对某个特征的决策树)针对某一特征，而是使用感知机同时处理多个特征。

上述方法为子树增加了更多的随机性。值得一提的是，随机森林的起始性能(基学习器较少时)往往相对较差，这是因为引入随机性使得单个基学习器的性能下降。随着基学习器的数目增加，随机森林通常会收敛到更低的泛化误差。

2. 包外估计 Out-Of-Bag Estimate

使用bagging随机生成子数据集也会为算法引入随机性。

假设使用bootstrap在$N$个样本中进行$T$轮有放回的抽样过程，生成$T$个子样本集：

在某一轮中，总样本集中未被选中的的样本称为out-of-bag(OOB) example.

假设在$N$个样本中有放回的抽样，每轮抽取$N$个样本组成子样本集，则其中某一样本$(x_n,y_n)$未被抽中(成为OOB样本)的概率为：

\[(1-\frac{1}{N})^N = \frac{1}{(\frac{N}{N-1})^N} = \frac{1}{(1+\frac{1}{N-1})^N} ≈ \frac{1}{e}\]

使用OOB样本可以进行自验证(self-validation)。对于每个样本(以上图$(x_N,y_N)$为例)，将所有未使用该样本训练的模型集成起来作为一个子模型：

\[G_N^-(x) = \text{avg}(g_2,g_3,...,g_T)\]

可以计算该样本在这个模型上的误差；进一步计算所有样本在其对应模型上的平均表现：

\[E_{OOB} = \frac{1}{N} \sum_{n=1}^{N} {\text{error}(y_n,g_n^-(x_n))}\]

随机森林算法不需要单独的验证集，而是用$E_{OOB}$代替验证集误差。

3. 特征选择 Feature Selection

随机森林可以用来进行特征选择(Feature Selection)，实现方法是通过随机排序测试(permutation test)。

首先对于给定样本集训练随机森林$G$，并进一步计算自验证误差$E_{OOB}$；

对于样本的第i个特征，将其在样本集中的值随机打乱后，计算打乱后的自验证误差$E_{OOB}^p$；

则第i个特征的重要性定义为将该特征随机排序打乱后引入的自验证误差值：

\[\text{importance}(i) = E_{OOB}^p(G)-E_{OOB}(G)\]