基于树模型的集成算法---Random Forest

一、模型介绍

随机森林是一种由决策树构成的集成算法. 随机森林属于集成学习中的 Bagging. 用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。

二、模型原理

随机森林的构造过程：

• 1. 假如有 n 个样本，有放回的随机选择 n 个样本(每次随机选择一个样本，然后放回继续选择)。这样就选择好了 n 个样本，用来训练一个决策树，作为决策树根节点处的样本。
• 2. 当每个样本有 m 个属性是，在决策树的每个节点需要分裂时，随机从这 m个属性中选取初 k 个属性，满足条件 k<<m。然后从这 k 个属性种采用某种策略(ID3、C4.5、CART)来选择 1 个属性作为该节点的分裂属性。
• 3. 决策树形成过程中每个节点都要按照 2 来分裂(如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到叶子节点，无须继续分裂了)。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
• 4. 按照步骤 1～3 建立大量的决策树，这样就构成了随机森林。

三、模型细节

1. 在建立每一棵决策树的过程中，需要注意两点: 采样与完全分裂

• 采样：这里有两个随机采样的过程，对输入的数据要进行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的集合样本中，可能有重复的样本。假设输入样本为 n 个，那么采样的样本也为 n 个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，相对不容易出现过拟合。然后进行列采样，从 m 个属性中个选择 k 个，k<<m。
• 完全分裂：在对数据进行完采样之后，使用完全分裂的方式建立决策树，这样的决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本都是指向同一个类别。一般的决策树算法都会有一个剪枝的步骤，但这里不会做剪枝，由于之前的两个随机采样过程保证了随机性，很大程度上降低了过拟合的可能性。

2. 偏差和方差

相较于一般的决策树, RF 中存在了对特征的子采样,增强了模型的随机性,虽然这增加了偏差,但是是同时因为集成效果,降低了方差,因而这通常在整体上会获得一个更好的模型。

3. 极限随机树

除了普通版本的随机森林以外,我们还可以通过使用极限随机树来构建极限随机森林,极限随机树与普通随机森林的随机树的区别在于,前者在划分属性的时候并非选取最优属性,而是随机选取(sklearn中的实现方式是,对每个属性生成随机阈值,然后在随即阈值中选择最佳阈值)

4. 完全随机树嵌入

sklearn 中还实现了随机森林的一种特殊用法, 即完全随机树嵌入(RandomTreesEmbedding) 。RandomTreesEmbedding 实现了一个无监督的数据转换。 通过由完全随机树构成的森林，RandomTreesEmbedding 使用数据最终归属的叶子节点的索引值（编号）对数据进行编码。 该索引以 one-of-K 方式编码，最终形成一个高维的稀疏二进制编码。 这种编码可以被非常高效地计算出来，并且可以作为其他学习任务的基础。 编码的大小和稀疏度可以通过选择树的数量和每棵树的最大深度来确定。

5.为什么要随机抽样训练集?

如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；

6. 为什么要有放回地抽?

如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是"有偏的"，都是"片面的"，也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是"求同"，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是"盲人摸象"。

7. 袋外错误率（oob error）

随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。在构建每棵树时，我们对训练集使用了不同的 bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第 k 棵树的oob样本。

四、模型优缺点

优点:

• 1. 在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合。
• 2. 在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力。
• 3. 它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。
• 4. 可生成一个Proximities=（pij）矩阵，用于度量样本之间的相似性： pij=aij/N, aij表示样本i和j出现在随机森林中同一个叶子结点的次数，N随机森林中树的颗数。
• 5. 在创建随机森林的时候，对 generlization error 使用的是无偏估计。
• 6. 训练速度比较快，容易做成并行方法。
• 7. 可以得到变量重要性排序，可以判断出不同特征之间的相互影响。

缺点:

• 1. 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。
• 2. 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。

五、模型使用

sklearn 中的随机森林:

from sklearn.ensemble import RandomForestClassifier, RandomForestRegressor

重要参数:

• 1. n_estimators: 随机森林里面的树数目，默认10。
• 2. max_features: 分割节点时考虑的特征的随机子集的大小。
• 3. max_depth: 树的最大深度。
• 4. min_samples_leaf: 叶子节点所需要的最小样本数。
• 5. oob_score: 是否使用袋外样本来泛化精度。

n_estimators 是森林里树的数量，通常数量越大，效果越好，但是计算时间也会随之增加。 此外要注意，当树的数量超过一个临界值之后，算法的效果并不会很显著地变好。

max_features 是分割节点时考虑的特征的随机子集的大小。 这个值越低，方差减小得越多，但是偏差的增大也越多。 根据经验，回归问题中使用 max_features = n_features， 分类问题使用max_features = sqrt（n_features （其中 n_features 是特征的个数）是比较好的默认值。

max_depth = None 和 min_samples_split = 2 结合通常会有不错的效果（即生成完全的树）。 这些（默认）值通常不是最佳的，同时还可能消耗大量的内存，最佳参数值应由交叉验证获得。 另外，请注意，在随机森林中，默认使用自助采样法（bootstrap = True）， 当使用自助采样法方法抽样时，泛化精度是可以通过剩余的或者袋外的样本来估算的，设置 oob_score = True 即可实现。

oob_score 误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。

重要方法:

• 1. fit(x,y): 训练
• 2. predict(x)：预测
• 3. predict_proba(x)：预测概率

随机森林的应用方向:

• 1. 对离散值的分类。
• 2. 对连续值的回归。
• 3. 异常点检测 (孤立森林)。
• 4. 无监督学习聚类 (具体参考这问题下面的答案，http://sofasofa.io/forum_main_post.php?postid=1000365)。