随机森林算法梳理
1、集成学习
集成学习通过构建并结合多个学习器来完成学习任务。 一般先产生一组“个体学习器”，再用某种策略讲它们结合起来，结合起来的结果进行整合会获得比单个学习器更好的学习效果。
也就是说，集成学习有两个主要的问题需要解决，第一是如何得到若干个个体学习器，第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器。
对于如何得到若干个个体学习器。这里我们有两种选择。
第一种就是所有的个体学习器都是一个种类的，或者说是同质的。比如都是决策树个体学习器，或者都是神经网络个体学习器。第二种是所有的个体学习器不全是一个种类的，或者说是异质的。比如我们有一个分类问题，对训练集采用支持向量机个体学习器，逻辑回归个体学习器和朴素贝叶斯个体学习器来学习，再通过某种结合策略来确定最终的分类强学习器。
目前来说，同质个体学习器的应用是最广泛的，一般我们常说的集成学习的方法都是指的同质个体学习器。而同质个体学习器使用最多的模型是CART决策树和神经网络。同质个体学习器按照个体学习器之间是否存在依赖关系可以分为两类，第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成，代表算法是boosting系列算法，第二个是个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成，代表算法是bagging和随机森林（Random Forest）系列算法。
2、Boosting Bagging
用于减少偏差的Boosting：Boosting是一类可将弱学习器提升为强学习器的算法。
先从训练集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续得到更多的关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，知道基学习器数目达到预先设定的值T，最终将T个基学习器进行加权结合。
用于减少方差的Bagging：
Bagging的样本采样基于自助采样法（bootstrap sampling）。采样出T个含有m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。
自助采样法： 自助采样法给定包含m个样本的数据集，从中随机取出一个样本放入采样集中，再把样本放回初始数据集（又放回采样），使得下次采样时该样本仍有可能被选中，这样，经过m次随机采样操作，得到含有m个样本的采样集，初始训练集中有的样本出现多次，有的未出现。初始训练集中约63.2%的样本出现在采样集中。
OOB：在Bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。对于这部分没采集到的数据，我们常常称之为袋外数据(Out Of Bag，简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。
方差度量了同等大小的训练集变动导致学习性能的变化，刻画了数据扰动所导致的影响。
3. 结合策略(平均法，投票法，学习法)
1）平均法
简单平均法：
加权平均法：
其中是个体学习器的hi的权重，通常要求权重>=0,
.
2）投票法
绝对多数投票法：若某标记得票过半数，则预测为该标记；否则拒绝预测。
相对多数投票法：预测为得票最多的标记，若同时有多个标记获得高票，则从中随机选取一个。
加权投票法：与加权平均类似。
3）学习法
当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。
4、随机森林
随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。随机森林可以既可以处理属性为离散值的量，比如ID3算法，也可以处理属性为连续值的量，比如C4.5算法。另外，随机森林还可以用来进行无监督学习聚类和异常点检测。
构造过程：
1、假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。
2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。
在建立每一棵决策树的过程中，有两点需要注意采样与完全分裂。
首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个（m << M）。
之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤——剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。
5、随机森林的推广
1、extra trees
是RF的一个变种, 原理几乎和RF一模一样，仅有区别有：
1） 对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。
2） 在选定了划分特征后，RF的决策树会基于信息增益，基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是extra trees比较的激进，他会随机的选择一个特征值来划分决策树。
从第二点可以看出，由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说，模型的方差相对于RF进一步减少，但是偏倚相对于RF进一步增大。在某些时候，extra trees的泛化能力比RF更好。
2、Totally Random Trees Embedding(以下简称 TRTE)
是一种非监督学习的数据转化方法。它将低维的数据集映射到高维，从而让映射到高维的数据更好的运用于分类回归模型。我们知道，在支持向量机中运用了核方法来将低维的数据集映射到高维，此处TRTE提供了另外一种方法。
3、Isolation Forest（以下简称IForest）
是一种异常点检测的方法。它也使用了类似于RF的方法来检测异常点
6、优缺点
优点：
1） 在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合
2）在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力
3）能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化
4）生成一个Proximities=（pij）矩阵，用于度量样本之间的相似性： pij=aij/N, aij表示样本i和j出现在随机森林中同一个叶子结点的次数，N随机森林中树的颗数
5）创建随机森林的时候，对generlization error使用的是无偏估计
6）练速度快，可以得到变量重要性排序（两种：基于OOB误分率的增加量和基于分裂时的GINI下降量
7）训练过程中，能够检测到feature间的互相影响
8）易做成并行化方法
9）现比较简单
缺点：
1）在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
2) 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。
7、 sklearn参数
sklearn.ensemble模块中包含两种基于随机决策树的平均算法：随机森林算法和ExtraTrees的方法。
from sklearn.datasets import make_blobs
from sklearn.ensemble import RandomForestClassifier
from sklearn.ensemble import ExtraTreesClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score
#在这里我们先引入一些训练数据集
X, y = make_blobs(n_samples=10000, n_features=10, centers=100, random_state=0)
#定义一个决策树分类器
clf = DecisionTreeClassifier(max_depth=None, min_samples_split=2, random_state=0)
scores = cross_val_score(clf, X, y)
print(scores.mean())
#定义一个随机森林分类器
clf = RandomForestClassifier(n_estimators=10, max_depth=None, min_samples_split=2, random_state=0)
scores = cross_val_score(clf, X, y)
print(scores.mean())
#定义一个极端森林分类器
clf = ExtraTreesClassifier(n_estimators=10, max_depth=None, min_samples_split=2, random_state=0)
scores = cross_val_score(clf, X, y)
print(scores.mean())#这里是极端森林训练器的模型精确度得分，效果优于随机森林