随机森林算法理论详解

Posted by mudux on February 28, 2020

  前面总结了集成学习算法,在bagging中,各个基学习器见关联不大,同时使用的基学习器是强模型。随机森林(Random Forest, RF)就是Bagging算法的进阶版,它的思想仍然是bagging,但是进行了相关改进。

1. 随机森林算法

  随机森林算法的改进如下:
  首先,RF使用了CART树作为基学习器;第二,在适用决策树的基础上,RF对决策树的建立做了改进,对于普通的决策树,会在结点上的所有$n$个样本特征中选择一个最优的特征来做决策树的左右子树划分,但是RF通过随机选择结点上的一部分样本特征,这个数字小于$n$,假设为$n_{sub}$,然后在这些随机选择的$n_{sub}$个样本特征中,选个一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。
  如果$n_{sub}=n$,则此时RF的CART树和普通的CART决策树没有区别。$n_{sub}$越小,则模型的方差会减小,但是偏差会增大。

2. 随机森林的推广

  由于RF在实际应用中的良好特性,基于RF有很多变种,不光可以用于分类回归,还可以用于特征转换,异常点检测等。

2.1 extra trees

  extra trees是RF的一个变种,原理几乎和RF一模一样,仅有区别有:

  • 对于每个决策树的训练集,RF采用的是随机采样bootstrp来选择采样集作为基学习器的训练集,而extra trees一般不采用随机采样,即每个决策树采用原始训练集;
  • 在选定了划分特征后,RF的决策树会基于基尼系数,均方差之类的划分准则选择一个最优的特征值花粉店。但是extra trees比较激进,它会随机选择一个特征值来划分决策树。

  从第二点可以看出,由于随机选择了特征值的划分点,而不是最优点,会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说,模型的方差相对于RF进一步减少,但是偏差进一步增大。在某些时候,extra trees的泛化能力比RF更好。

2.2 Totally Random Trees Embedding

  Totally Random Trees Embedding(以下简称 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维的高维特征。这里特征维度之间加上空格是为了强调三颗决策树各自的子编码。
映射到高维特征后,可以继续使用监督学习的各种分类回归算法了。

2.3 Isolation Forest

  Isolation Forest(简称IForest)是一种异常点检测的方法。它也使用了类似于RF的方法来检测异常点。
  对于在$T$个决策树的样本集,IForest也会对训练集随机采样,但是采样个数不需要和RF一样,对于RF需要采样到和原始数据集相同个数。IForest不需要采样这么多。因为我们的目的是异常点检测,只需要部分的样本就可以将异常点区别出来。
  对于每一个决策树的建立, IForest采用随机选择一个划分特征,对划分特征随机选择一个划分阈值。这点也和RF不同。
  另外,IForest一般会选择一个比较小的最大决策树深度max_depth,原因同样本采集,用少量的异常点检测一般不需要这么大规模的决策树。
  对于异常点的判断,则是将测试样本点$x$拟合到$T$棵决策树。计算在每棵决策树上该样本对应的叶子结点的深度$h_t(x)$。从而可以计算出平均高度$h(x)$。此时用下面的公式计算样本点$x$的异常概率:

  其中,$m$为样本个数。

  其中,$\xi$为欧拉常数。
  $s(x,m)$的取值范围为[0,1],取值越接近1,则是异常点的概率也越大。

3. 随机森林总结

  RF的主要优点有:

  • 训练可以高度并行化,这时最主要的优点;
  • 由于可以随机选择决策树结点划分特征,在样本特征维度很高时,仍然能高效的训练模型;
  • 在训练后,可以给出各个特征对输出的重要性,这里是基于每个特征别被选作切分特征的次数,常用于特征选择;
  • 由于采用了样本和特征随机采样,训练出的模型方差小,泛化能力强;
  • 相比于Boosting系列的Adaboost和GBDT,RF实现比较简单;
  • 对部分特征缺失不敏感。

  RF的主要缺点有:

  • 在某些噪音比较大的样本集上,RF模型容易陷入过拟合;
  • 取值划分比较多的特征容易对RF的决策产生更大的影响,从而影响拟合的模型的效果。