随机森林
随机森林是一种集成算法(Ensemble Learning)，它属于Bagging类型，通过组合多个弱分类器，最终结果通过投票或取均值，使得整体模型的结果具有较高的精确度和泛化性能。其可以取得不错成绩，主要归功于 "随机"和“森林” ，一个使它具有抗过拟合能力，一个使它更加精准。
Bagging 是一种在原始数据集上通过有放回抽样重新选出k个新数据集来训练分类器的集成技术。它使用训练出来的分类器的集合来对新样本进行分类，然后用多数投票或者对输出求均值的方法统计所有分类器的分类结果，结果最高的类别即为最终标签。此类算法可以有效降低bias，并能够降低variance。
自助法 它通过自助法（bootstrap）重采样技术，从训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。
OOB 在Bagging的每轮随机采样中，训练集中大约有36.5%的数据没有被采样集采集中。 对于这部分没有采集到的数据，我们常常称之为袋外数据(Out of Bag, 简称OOB) 。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。
随机性 对于我们的Bagging算法，一般会对样本使用boostrap进行随机采集，每棵树采集相同的样本数量，一般小于原始样本量。这样得到的采样集每次的内容都不同 ，通过这样的自助法生成K个分类树组成随机森林，做到样本随机性 。
输出 Bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到的最终的模型输出。
弱分类器 首先，RF使用了CART决策树作为弱学习器。换句话说，其实我们只是将实验CART决策树作为弱学习器的Bagging方法称为随机森林。
随机性 同时，在生成每棵树的时候， 每个树选取的特征都不仅仅是随机选出的少数特征，一般默认取特征总数m的开方。 而一般的CART树则会选取全部的特征进行建模。因此 ，不但特征是随机的，也保证了特征随机性 。
样本量 相对于一般的Bagging算法，RF会选择采集和训练集样本数N一样个数的样本。、
特点 由于随机性，对于降低模型的方差很有作用，故随机森林一般不需要额外剪枝，即可以取得较好的泛化能力和抗拟合能力(Low Variance)。当然对于训练集的拟合程度就会差一点，也就是模型的偏倚会大一些(High Bias)，仅仅是相对的。
在关于随机森林的原始论文中，显示随机森林错误率取决于两件事：
?森林中任何两棵树之间的相关性。增加相关性会增加森林错误率。
?森林中每棵树的力量(具有低错误率的树是强分类器)。增加单棵数据的强度(分类更精确)会降低森林错误率。
随机森林的弱分类器使用的是CART树，CART决策树又称为分类回归树。当数据集的因变量为连续型数值时，该树算法就是一个回归树，可以用叶节点观察的均值作为预测值；当数据集的因变量为离散型数值时，该树算算法就是一个分类树，可以很好地解决分类问题。但是需要注意的是，该算法是一个二叉树，即每一个叶节点只能引申出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。同时，若某个非叶节点是连续变量时，决策树也将把他当做离散变量来处理(即在有限的可能值中做划分)。
特征选择目前比较流行的方法是信息增益、增益率、基尼系数和卡方检验。这里主要介绍基于基尼系数(Gini)的特征选择，因为随机森林采用的CART决策树就是基于基尼系数选择特征的。
基尼系数的选择的标准就是每个子节点达到最高的纯度，即落在子节点中的所有观察都属于同一分类，此时基尼系数最小，纯度最高，不确定度最小。对于一般的决策树，加入总***有K类，样本属于第K类的概率：pk,则该概率分布的基尼指数为：
基尼指数越大，说明不确定性就越大；基尼系数越小，不确定性越小，数据分割越彻底，越干净。
对于CART树而言，由于是二叉树，可以通过下面的表示：
在我们遍历每个特征的每个分割点时，当使用特征A=a，将D划分为两部分，即D1（满足A=a的样本集合），D2（不满足A=a的样本集合）。则在特征A=a的条件下D的基尼指数为：
Gini(D)：表示集合D的不确定性。
Gini(A,D)：表示经过A=a分割后的集合D的不确定性。
随机森林中的每棵CART决策树都是通过不断遍历这棵树的特征子集的所有可能的分割点，寻找Gini系数最小的特征的分割点，将数据集分成两个子集，直至满足停止条件为止。
首先，正如Bagging介绍中提到的，每个树选择使用的特征时，都是从全部m个特征值随机产生的，本身就已经降低了过拟合的风险和趋势。模型不会被特定的特征值或特征组合所决定，随机性的增加，将控制模型的拟合能力不会无限提高。
第二，与决策树不同，RF对决策树的简历做了改进。对于普通的决策树，我们会在节点上所有的m个样本特征中选择一个最优的特征来做决策树的左右子树划分。但是RF的每个树，其实选用的特征是一部分，在这些少量特征中，选择一个最优的特征来做决策树的左右子树划分，将随机性的效果扩大，进一步增强了模型的泛化能力。
假设每棵树选取msub个特征，msub越小，此时模型对于训练集的拟合程度会变差，偏倚增加，但是会泛化能力更强，模型方差减小。msub越大则相反。在实际使用中，一般会将msub的取值作为一个参数，通过开启OOB验证或使用交叉验证，不断调整参数以获取一个合适的msub的值。
优点：
（1）由于采用了集成算法，本身精度比大多数单个算法要好。
（2）在测试集上表现良好，由于两个随机性的引入，使得随机森林不容易陷入过拟合( 样本随机，特征随机 )
（3）在工业上，由于两个随机性的引入，使得随机森林具有一定的抗噪声能力，对比其他算法具有一定优势。
（4）由于树的组合，使得随机森林可以处理非线性数据，本身属于非线性分类(拟合)模型。
（5） 它能够处理很高维度(feature很多)的数据 ，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。
（6）训练速度快，可以运用在大规模数据集上。
（7）由于袋外数据(OOB)，可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量。
（8）在训练过程中，能够检测到feature间的互相影响， 且可以得出feature的重要性 ，具有一定参考意义。
（9）由于每棵树可以独立、同时生成，容易做成并行化方法。
（10）由于实现简单、 精度高、抗过拟合能力强 ，当面对非线性数据时，适于作为基准模型。
缺点：
（1）随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过拟合。（PS:随机森林已经被证明在某些噪音较大的分类或者回归问题上会过拟合）
（2）对于许多统计建模者来说，随机森林给人感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。
（3）可能有很多相似的决策树，掩盖了真实的结果。
（4）对于小数据或者低维数据(特征较少的数据)，可能不能产生很好的分类。( 处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处 )。
（5）执行数据虽然比boosting等快，但是比单棵决策树慢多了。
（1） 不要求是线性特征，比如逻辑回归很难处理类别型特征 ，而树模型，是一些决策树的集合，可以很容易的处理这些情况。
（2） 由于算法构建的过程，这些算法很容易处理高维的数据，大量的训练数据的场景 。
极端随机树是随机森林的一个变种，原理几乎和RF一模一样，仅有区别有：
（1）对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。
（2）在选定了划分特征后，RF的决策树会基于基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是极端随机树比较的激进，他会随机的选择一个特征值来划分决策树。