随机森林算法梳理

集成学习概念

集成学习通过构建并结合多个学习器（分类器）来完成分类任务。集成学习的一般结构：先产生一组“个体学习器”（individual learner)，再用某种策略将它们结合起来。集成学习有两个关键的东西，第一，就是一组个体学习器；第二，结合策略。

个体学习器概念

集成学习通过对多个学习器进行组合，通常可获得比单一学习器更优的泛化性能。这对“弱学习器”（weak learner）尤为明显，因此集成学习很多研究是针对弱学习器，而基学习器有时也被直接称为弱学习器。在不正式的说法下，基学习器、弱学习器、弱分类器、个体学习器说的都是一个东西。

个体学习器通常由一个现有的学习算法从训练数据产生，是为了集成学习而产生的个体，通常有以下几种：

只包含同种类型的个体学习器，这样的集成是“同质”的（homogeneous）。同质集成中的个体学习器亦称为”基学习器“（base learning）。
集成也可包含不同类型的个体学习器，这样集成是”异质“的（heterogeneous）。相应的个体学习器，常称为”组件学习器“（component learning）或直接称为个体学习器。

集成学习把多个学习器集合起来，获得比最好的单一学习器获得更好的性能，就要让个体学习器尽量的有差异。

根据个体学习器的生成方式，集成学习可分成两大类：

个体学习器之间存在强依赖关系、必须串行生成，例如：Boosting
个体学习器之间不存在强依赖关系，可同时生成的，例如：Bagging和随机森林（Random Forest）

Boosting Bagging

Boosting 和 Bagging 都是将弱分类器组装成强分类器的算法。

Boosting

Boosting算法的工作机制：

先从初始训练集训练出一个基学习器，在根据基学习器的表现对样本分布权重进行调整，使得先前基学习器做错的训练样本在后续收到更多的关注，然后基于调整后的样本分布来训练下一个基学习器，如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。

Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。

Boosting 主要关注降低偏差。

Bagging

Bagging 的个体弱学习器的训练集是通过随机采样得到的。通过T次的随机采样，我们就可以得到T个采样集，对于这T个采样集，我们可以分别独立的训练出T个弱学习器，再对这T个弱学习器通过集合策略来得到最终的强学习器。

Bagging 使用装袋采样来获取数据子集训练基础学习器。通常分类任务使用投票的方式集成，而回归任务通过平均的方式集成。

其算法过程如下：

从原始样本集中抽取训练集。每轮从原始样本集中使用 Bootstraping 的方法抽取 $n$ 个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行 $k$ 轮抽取，得到 $k$ 个训练集。（$k$ 个训练集相互独立）
每次使用一个训练集得到一个模型，$k$ 个训练集共得到 $k$ 个模型.
对分类问题：将上步得到的 $k$ 个模型采用投票的方式得到分类结果；
对回归问题：计算上述模型的均值作为最后的结果。

常用的集成算法模型是随机森林和随机树。

Bagging 主要关注降低方差。

两者的区别

样本选择上：

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
样例权重：
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
Bagging：使用均匀取样，每个样例的权重相等
预测函数：
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
Bagging：所有预测函数的权重相等。
并行计算：
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
Bagging：各个预测函数可以并行生成。

结合策略(平均法，投票法，学习法)

平均法

简单平均法（simple average）
$H(x) = \frac{1}{T}\sum_{i=1}{T}h_i(x)$
加权平均法（weighted average）
$H(x) = \sum_{i=1}{T}w_ih_i(x)$

投票法

绝对多数投票法：某标记超过半数；
相对多数投票法：预测为得票最多的标记，若同时有多个标记的票最高，则从中随机选取一个。
加权投票法：提供了预测结果，与加权平均法类似。

学习法

当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。Stacking是学习法的典型代表。我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器。Stacking算法本身是一种著名的集成学习方法，且有不少集成学习算法可视为其变体或特例，它也可以看做是一种结合策略。

Stacking描述：先从初始数据集中训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在新数据集中，初级学习器的输出被当做样例输入特征，初始样本的标记仍被当做样例标记。

随机森林思想

在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

传统决策树在选择划分属性时是在当前节点的属性集合（假设有 $d$ 个属性）中选择一个最优属性
在RF中，从该点属性集合中随机选择一个包含 $k$ 个属性的子集（若 $k=d$，则基决策树的构建与传统决策树相同）——推荐$k=logd$

随机选择样本

给定一个训练样本集，数量为N，我们使用有放回采样到N个样本，构成一个新的训练集。然后把这个样本集作为训练集，进入下面的一步。

随机选择特征

在随机森林中，不计算所有特征的增益，而是从总量为M的特征向量中，随机选择m个特征，然后计算m个特征的增益，选择最优特征（属性）。

随机森林投票分类

通过上面的三步走，我们可以得到一棵决策树，我们可以重复这样的过程H次，就得到了H棵决策树。然后来了一个测试样本，我们就可以用每一棵决策树都对它分类一遍，得到了H个分类结果。这时，我们可以使用简单的投票机制，或者该测试样本的最终分类结果。

优缺点

优点：

在当前的很多数据集上，相对其他算法有着很大的优势，表现良好
它能够处理很高维度（feature很多）的数据，并且不用做特征选择
在训练完后，它能够给出哪些feature比较重要
在创建随机森林的时候，对generlization error使用的是无偏估计，模型泛化能力强
训练时树与树之间是相互独立的，训练速度快，容易做成并行化方法
在训练过程中，能够检测到feature间的互相影响
实现比较简单
对于不平衡的数据集来说，它可以平衡误差。
对缺失值不敏感，如果有很大一部分的特征遗失，仍可以维持准确度。

缺点：

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

sklearn参数

sklearn.ensemble.RandomForestClassifier(n_estimators=’warn’, criterion=’gini’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=’auto’, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, bootstrap=True, oob_score=False, n_jobs=None, random_state=None, verbose=0, warm_start=False, class_weight=None)

具体参数查看：
3.2.4.3.1. sklearn.ensemble.RandomForestClassifier
sklearn随机森林分类类RandomForestClassifier

应用场景

数据维度相对低（几十维），同时对准确性有较高要求时。

因为不需要很多参数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。