[原]【机器学习基础】随机森林算法

在Bagging算法中，通过bootstrap在原来的数据中进行抽样，来得到不同的数据集，从而产生不同的g。

在随机森林的算法中，除了在数据集中做抽取之外，还可以在特征这一角度进行抽取。举个例子，如果事先我们有100个特征，现在我们可以抽取10个特征来训练一棵树，这样的方式我们也可以得到很不一样的树，其对于分类的标准显然也很不一样。

这种特征抽取的方式相当于在原来特征的100个维度中，随机选取10个维度，这等效于一个特征转换，这个过程中，从100维度到10个维度的转换中，相当于作了低维度的投影(Projection)。

得到的特征实际上是原始特征的随机子集，这使得生成模型过程中的效率也大大提高了。

上面介绍的特征投影等效于对原来的特征向量左乘一个投影矩阵Φ(x) = P·x，得到的特征抽样是随机选取的原始特征。现在我们可以尝试更加复杂、有能力的投影方式。

更加有能力的特征投影就是不再单一选取单一维度的特征，而是将多个维度的特征进行组合，得到新的一维的特征，这称为特征扩展。

在bootstrapping的过程中，有些数据可能没有被选择，这些数据称为out-of-bag(OOB) examples，对于训练每一个gt，其中用“*”标注的数据即是gt的OOB examples。

下面的公式是经过N’次选择之后没有被选择的数据，大约有(1/e)*N多的数据没有被选择到，即大约有三分之一的数据没有被选择，这些数据由于没有用来训练模型，故可以用于模型的验证。

在随机森林的算法中，我们不太需要使用OOB数据来验证每个g的性能，因为即使g的能力很差，最终进行平均得到的G的性能也可能会很好。但这些OOB数据可以用来验证G的性能。

上图中，(xN,yN)这一个数据由于没有用于g2，g3，gT的训练数据，故可以用来作为它们的验证数据。所以(xN,yN)可以作为G-的验证数据，其中G-(x)=average(g2, g3, gT)。

下面给出了OOB Error（Eoob）的公式，G的OOB Error的估算是通过不同的G-来平均得到的，所以，在bootstrap的过程就可以自己去验证模型的性能好坏，不需要单独划分一块数据作为专门的验证数据。

下面是随机森林算法中使用OOB Error进行验证的方法：

接下来要介绍的特征选择，其目的主要是使用程序来自动选择需要的特征，而将冗余的、不相关的特征忽略掉。

优点：特征选择由于舍去了不必要的特征，使得模型复杂度大大降低，可以简化假设，缩短预测时间；同时，舍去了特征的噪声，可以提高模型的泛化能力，使得模型不容易对噪声过拟合；最后，由于选择出来的特征具有很好的物理意义，其结果可以作很好的解释。

缺点：特征的选择计算量大；如果选出来的特征是噪声的话，可能会导致过拟合；如果选择了噪声特征，得到的解释可能只是数据之中的关联性，而非因果性。

Permutation Test的方法是通过将第i个维度特征的所有数据重新的随机调整位置，然后比较一下原始数据和调整之后的数据表现的差距，来评价这个维度的特征是有多么重要。

在随机森林中可以用OOB代替验证的过程，为了简化Permutation Test带来的重新进行训练的代价，我们在使用OOB Example（bootstrap过程中没有选取的数据）进行验证的过程中做一些修改，即在验证的时候去进行Permutation Test，而非训练时进行。

在求Eoob(G)时，我们通过G-(xn)来计算，我们在这里将x(n)修改成x(n,i)，就可以不用对G进行修改了。

在实际应用中，面对非线性的问题时，可以通过随机森林的方法来进行初步的特征选择。