随机森林

Posted on

随机森林

1. 原理

随机森林（Random Forest，RF）是Bagging的一个扩展变体。RF在以决策树为基学习器（CART）构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。
具体来说，传统决策树在选择划分属性时是在当前节点的属性集合（假定有\(d\)个属性）中选择一个最优属性；而在RF中，对基决策树的每个节点，先从该节点的属性结合中随机选择一个包含\(k\)（\(k \leq d\)）个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数\(k\)控制了随机性的引入程度：若令\(k=d\)，则基决策树的构建与传统决策树相同；若令\(k=1\)，则是随机选择一个属性用于划分；一般情况下，推荐值\(k = \log_2 d\)。
随机森林对Bagging只做了小改动，但是与Bagging中基学习器的“多样性”仅通过样本扰动（通过对初始训练集采样）而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。

2. 算法流程

输入：训练样本集\(\{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2),\cdots,(\pmb{x}_n,y_n)\}\)，弱学习算法，迭代次数； 输出：强学习器\(f(\pmb{x})\)；

算法流程：

  1. 对于\(m=1,2,\cdots,T\)：
    1. 对训练集进行第\(m\)次随机采样，得到包含\(n\)个样本的数据集\(D_m\)；
    2. 用采样得到的\(D_m\)数据集训练第\(m\)个弱学习器\(G_m(\pmb{x})\)，在训练模型的时候，在当前节点的所有特征中随机选择\(k\)个特征，在\(k\)个随机选择的特征中选择最优的一个特征作为当前节点的切分点；
  2. 如果是分类算法，则用多数投票得到最后的强分类器；如果是回归问题，将\(T\)个弱学习器得到的回归结果进行算术平均得到最后的强学习器。

3. 随机森林的推广

3.1. 极端随机树

极端随机树（Extra Tree）是随机森林的一个变种，主要区别有：

  • 不进行随机采样，每个CART训练时采用原始数据集；
  • 在构建CART决策树时，随机选择\(k\)个特征，RF是根据基尼指数或均方差等选择最佳特征以及特征的划分进行节点的再分裂。而ET是在每个特征中随机决定一个划分值，然后计算每个特征上的基尼指数或者均方差，选择最佳的一个作为切分点。ET对于特征的划分有更加随机的选择，使得随机森林的随机性更强，泛化能力更好。

ET在sklearn中有实现：ExtraTreeClassifier和ExtraTreeRegrassor。

3.2. Totally Random Trees Embedding(TRTE)

TRTE是一种非监督学习的数据转化方法。它将低维度的数据集映射到高维，从而让映射到高维的数据更好的运用于分类回归模型。在支持向量机中运用核方法，而TRTE提供了另一种方法。
TRTE在数据转化的过程中也是用了类似RF的方法，建立\(T\)个决策树来拟合数据。当决策树建立完成以后，数据集里的每个数据在\(T\)个决策树中叶子节点的位置也定下来了。比如有3棵决策树，每个决策树有5个叶子节点，某个样例\(x\)划分到第一个决策树的第2个叶子节点，第二个决策树的第3个叶子节点，第三个决策树的第5个叶子节点，则\(x\)映射后的特征编码为\((0,1,0,0,0,0,0,1,0,0,0,0,0,0,1)\)，15维的高维特征。映射到高维特征以后，可继续用于各种分类回归算法。

3.3. 孤立森林

孤立森林(Isolation Forest)用于异常值的检测。使用了类似于RF的方法来检测异常值，与RF的主要区别有：

  • 在随机采样部分，IForest不需要采集和原始数据集个数相同的样本集，只需要很少的样本即可。因为我们的目的是异常值检测，只需要部分样本就可以将异常点区别出来；
  • 对于每一个决策树的建立，IForest随机选择一个特征，对特征随机选择一个划分阈值进行节点的再分裂；
  • IForest的决策树的最大深度一般比较小。

IForest算法：

训练完模型之后，我们得到了\(T\)棵决策树，对于测试样本\(\pmb{x}\)，计算其在每棵决策树上所属叶子节点的深度，从而可以计算出平均深度\(h(\pmb{x})\)，之后用一下公式计算\(\pmb{x}\)是异常点的概率： \[s(\pmb{x},n) = 2^{- \frac{E[h(\pmb{x})]}{c(n)}}\] 其中，\(c(n) = 2H(n-1)-(2(n-1)/n)\)，这里\(H(·)\)为调和级数，\(H(i) = \ln(i) + 0.5772156649\)，\(n\)为样本个数。
\(s(\pmb{x},n)\)有三种情况：

  1. 越接近于1，是异常点的可能性越大；
  2. 所有样本点都小于0.5，则可以基本断定数据集正常；
  3. 艘在0.5附近，那么数据集不包含明显异常点。

IForest在sklearn中有实现：IsolationForest方法。

4. RF的优缺点

RF的主要优点有：

  1. 训练可以高度并行化，对于大样本训练有速度优势；
  2. 由于可以随机选择决策树节点划分特征，在样本特征维度很高时，仍然可以高效地训练模型；
  3. 训练后，可以给出各个特征对于输出的重要性；
  4. 由于采用随机采样，训练得到的模型方差小，泛化能力强；
  5. 相比于AdaBoost和GBDT，RF实现较为简单；
  6. 对于部分特征值缺失不敏感。

RF的主要缺点：

  1. 在某些噪音比较大的样本集上，RF模型容易陷入过拟合；
  2. 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，随机森林在这种数据上产出的属性权值是不可信的。

5. sklearn使用

sklearn中包含RandomForestClassifier和RandomForestRegressor，分别是随机森林的分类与回归。

RandomForestClassifier：

1
class sklearn.ensemble.RandomForestClassifier(n_estimators=10, 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=1, random_state=None, verbose=0, warm_start=False, class_weight=None)

RandomForestRegressor：

1
class sklearn.ensemble.RandomForestRegressor(n_estimators=10, criterion=’mse’, 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=1, random_state=None, verbose=0, warm_start=False)

框架参数

弱分类器参数：即CART的参数

函数

属性