随机森林算法详解

机器学习算法--集成方法
集成方法的目标是把多个使用给定学习算法构建的基估计器的预测结果结合起来，从而获得比单个估计器更好的泛化能力

一、背景

集成方法通常分为两种:

1.平均方法

该方法的原理是构建多个独立的估计器，然后取它们的预测结果的平均。一般来说组合之后的估计器是会比单个估计器要好的，因为它的方差减小了。
示例: Bagging 方法 , 随机森林

2.boosting 方法

基估计器是依次构建的，并且每一个基估计器都尝试去减少组合估计器的偏差。这种方法主要目的是为了结合多个弱模型，使集成的模型更加强大。

二、森林的构建-重采样(自采样算法)

1.每棵树生成算法

给定一个包含 m 个样本的数据集 D , 我们对它进行采样产生数据集 D′ : 每次随机从 D 中挑选出一个样本，将其拷贝放入 D′ ，然后再将该样本放回初始数据集 D 中，使得该样本在下次采样中仍有可能被采到；

2.构建n颗树

这个过程重复执行 n 次以后，我们就得到了包含 n 个样本的数据集 D′，这就得到n颗树。
显然， D 中有一部分样本会在 D′ 中多次出现，而另一部分样本 不出现。可以做一个简单的估计，样本在 m 次采样中始终不被采到的概率是：

该式取极限得到 1/e=0.368
即通过自助采样，初始数据集 D 中约有 36.8% 的样本未出现在数据集D′ 中， 于是我们可以将 D′ 作为训练集，而剩下的作为测试集。

三、每个节点特征选择（随机选K，然后决策树算法）

特征的随机选择：
假设共有M个属性，制定一个属性数量F<=M，从M个属性中随机抽取F个属性作为待选择属性，使用CART决策树特征选择的方法从F个属性中选取最好的特征。
注意：因为每个节点每次选择最佳属性的时候都会从所有属性中选择，所有会有特征重复情况发生。

三、每个特征分割点的选择（决策树算法）

选好最好的特征后，从剩余数据中，在利用CART决策树找到最好的分割点。

四、特征重要性排序（ out of bag，OOB算法）

计算每个特征的重要性程度
$importance=\frac{1}{N}\sum_{i=1}^{N}|errOOB_{2}-errOOB_{1}|$

A. 对每一颗决策树，选择相应的袋外数据（out of bag，OOB）​计算袋外数据误差，记为$errOOB_{1}$
B. 随机对袋外数据OOB所有样本的特征X加入噪声干扰（可以随机改变样本在特征X处的值），再次计算袋外数据误差，记为$errOOB_{2}$。
假设森林中有N棵树，则特征X的重要性为
$importance=\frac{1}{N}\sum_{i=1}^{N}|errOOB_{2}-errOOB_{1}|$

这个数值之所以能够说明特征的重要性是因为，如果加入随机噪声后，袋外数据准确率大幅度下降（即errOOB_{2}上升），说明这个特征对于样本的预测结果有很大影响，进而说明重要程度比较高。

五、数据预测-多棵树投票（投票或均值算法）

多棵树求平均

五、随机体现在什么地方

1.样本的随机：“行”抽样随机
每次抽样样本的size和原始输入样本的大小相同，因为是放回抽样，所以有可能抽到重复的；这可以保证有重复样本被不同决策树分类，这样就可以对不同决策树的分类能力做个评价。
2.特征的随机：“列”抽样随机
特征的随机抽样是指，在建每棵树进行每个节点分裂的时候，都随机抽一部分特征，然后在这随机抽的部分特征里面，用决策树的特征选择的方法（比如信息增益，或信息增益率）来决定使用最优的特征来作为分裂节点的；

参考资料：
1.https://blog.csdn.net/liangjun_feng/article/details/80152796