随机森林算法梳理

集成学习的概念

集成学习(ensemble learning)指的是,我们采用多个弱学习进行学习,来替代用一个单一的精密的高效能的学习器对数据进行学习,并且通过一定的手段将这些弱学习器的结果进行整合来完成学习任务的方法,有时也被称为多分类系统(multi-classifier system)、基于委员会的学习(committee-based learning)等。

集成学习通过将多个弱学习器进行结合,常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”尤为明显,因此集成学习的很多理论研究都是针对弱学习器进行的。

个体学习器的概念

个体学习器(individual learner)通常是用一个现有的学习算法从训练数据产生,例如C4.5决策树算法、BP神经网络算法等。此时集成中只包含同种类型的个体学习器,例如“决策树集成”中的个体学习器全是决策树,“神经网络集成”中就全是神经网络,这样的集成是“同质”(homogeneous)的,同质集成中的个体学习器也称为“基学习器”(baselearner),相应的学习算法称为“基学习算法”(baselearning algorithm)。有同质就有异质(heterogeneous),若集成包含不同类型的个体学习器,例如同时包含决策树和神经网络,那么这时个体学习器一般不称为基学习器,而称作“组件学习器”(componentleaner)或直接称为个体学习器。

boosting bagging的概念、异同点

根据个体学习器生成方式的不同,目前的集成学习方法大致可以分为两大类,即个体学习器间存在强依赖关系、必须串行生成的序列化方法,以及个体学习器间不存在强依赖关系、可同时生成的并行化方法;前者的代表是Boosting,后者的代表是Bagging和“随机森林”(Random Forest)。

boosting

首先需要明确一个概念,在概率近似正确(PAC)学习框架中,一个概念(一个类),如果存在一个多项式的学习算法能够学习它,并且正确率很高,那么就称这个概念是强可学习的;一个概念,如果存在一个多项式的学习算法能够学习它,学习的正确率仅比随机猜测略好,那么就称这个概念是弱可学习的。并且可以从理论上面证明,强可学习和弱可学习是等价的。那么问题来了,在学习当中,如何将比较容易发现的“弱学习算法”提升(boosting)为“强学习算法”呢?这便是boosting需要解决的问题。

boosting这族算法的工作机制为:先从初识训练集训练出一个基学习器,再根据基学习器的表现对训练样本分布进行调整,使得先前基学习器做错的训练样本在后续受到更多的关注,然后基于调整后的样本分布训练下一个基学习器;如此重复进行,直到基学习器数据达到事先指定的值$T$,最终将这$T$个基学习器进行加权结合。

Boosting族算法最著名的代表是AdaBoost,其描述如下图所示,其中$y_i\in${-1,+1},$f$是真实函数。

AdaBoost算法

bagging

为了得到泛化性能强的集成,集成中的个体学习器应尽可能相互独立;虽然“独立”在现实任务中无法做到,但可以设法 使基学习器尽可能具有较大的差异。给定一个训练数据集,一种可能的做法是对训练样本进行采样,产生出若干个不同的子集,再从每个数据子集中训练出一个基学习器。这样,由于训练数据不同,我们获得的基学习器可望具有比较大的差距。

bagging正是借鉴这样的思想,直接基于自助采样法(bootstrap sampling),是并行式集成学习方法最著名的代表。给定包含$m$个样本的数据集,我们先随机去除一个样本放入采样集当中,再把该样本放回初始数据集,使得下次采样时该样本仍有可能被选中,这样经过$m$次随机采样操作,我们得到含$m$个样本的采样集,初始训练集中有的样本在采样集里多次出现,有的从未出现。约63.2%的样本出现在采样集中,而未出现的约36.8%的样本可用作验证集来对后续的泛化性能进行“包外估计”。

根据基学习器的不同,包外估计还有其他用途。当基学习器是决策树时,可以使用包外样本来辅助剪枝,或者用于估计决策树中各个结点的后验概率以辅助对零训练样本结点的处理;当基学习器是神经网络时,可使用包外样本来辅助早期停止来减小过拟合风险。

这样类推,我们可以采用出$T$个含$m$个训练样本的采样集,然后基于每个采样集训练出一个基学习器。再将这些基学习器进行结合,针对预测输出任务的不同,分类任务通常使用简单投票法,回归任务通常使用简单平均法,这就是Bagging的基本流程。算法描述如下图所示。

Bagging算法

对比

  • Bagging的个体学习器不存在强依赖关系,可以同时生成,比较便于并行化计算;Boosting的个体学习器存在强依赖关系,只能串行生成,后续的一些开源算法,比如XGBoost以及LightGBM的并行化都只是建树过程的分布式,学习本身还是串行的;
  • 从偏差-方差分解的角度看,Bagging主要关注降低方差,因此它在不剪枝的决策树、神经网络等易受到样本扰动的学习器上效用更明显;Boosting主要关注降低偏差,因此Boosting基于泛化性能相当弱的学习器构建出很强的集成。
  • 说说相同的,这两个算法如果采用相同的基学习器,那么算法的时间复杂度是基本相同的。

结合策略

学习器结合策略的好处有以下三个方面:

  • 从统计的方面来看,结合多个学习器可以减小因学习任务的假设空间太大导致仅仅使用单学习器可能因误选而导致泛化性能不佳的风险;
  • 从计算的方面来看,通过多次运行不同的学习算法之后进行结合可降低陷入糟糕局部极小点的风险;
  • 从表示的方面来看,通过结合多个学习器,扩大了相应的假设空间,有可能学得到更好的近视。

    平均法

对于数值型输出$h_i(x)\in R$,最常见的结合策略是使用平均法。

  • 简单平均法

$$H(x)=\frac{1}{T}\sum_{i=1}^Th_i(x)$$

  • 加权平均法

$$H(x)=\frac{1}{T}\sum_{i=1}^T\omega_ih_i(x)$$

其中$\omega_i$是个体学习器$h_i$的权重,通常要求$\omega_i\geqslant0,\sum_{i=1}^T\omega_i=1$。

显然,简单平均法是加权平均法的特例,加权平均法的权重一般是从训练数据中学习而得。一般而言,在个体学习器性能相差较大时宜使用加权平均法,而在个体学习器性能相近时使用简单平均法。

投票法

对于分类任务来说,学习器从类别标记集合中预测出一个标记,最常见的组合策略时使用投票法。

  • 绝对多数投票法

即若某标记得票过半数,则预测为该标记;否则拒绝预测。

  • 相对多数投票法

$$H(x)=c_\underset{j}{\mathrm{argmax}}\sum_{i=1}^Th_i^j(x)$$

即预测为得票最多的标记,若同时有多个标记获最高票,则从中随机选取一个。

  • 加权投票法

$$H(x)=c_\underset{j}{\mathrm{argmax}}\sum_{i=1}^T\omega_ih_i^j(x)$$

与加权平均法类似,其中$\omega_i$是个体学习器$h_i$的权重,通常要求$\omega_i\geqslant0,\sum_{i=1}^T\omega_i=1$。

需要补充的是,在现实任务中,不同类型个体学习器可能产生不同类型的$h_i^j(x)$值,比如:

  • 类标记:$h_i^j(x)\in${0,1},所谓“硬投票”
  • 类概率:$h_i^j(x)\in$[0,1],所谓“软投票”

必须注意,不同类型的$h_i^j(x)$值不能混用,必要的时候需要适当转化。

学习法

在训练数据很多时,一种更为强大的结合策略是使用“学习法”,即通过另外一个学习器来进行结合,大名鼎鼎的Stacking就是学习法的典型代表。我们不妨把个体学习器称为初级学习器,用于结合的学习器称为次级学习器或者元学习器(meta-learner)。

Stacking先从初始数据集训练出初级学习器,然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中,初级学习器的输出被当作样例输入特征,而初始样本的标记仍被当作样例标记。Stacking的算法描述如下所示,我们假定初级学习器使用了不同的学习算法产生。

Stacking

随机森林

随机森林是Bagging的一个扩展变体,在理解了Bagging方法后,随机森林学习起来就容易多了。RF在以决策树作为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中加入了随机属性的选择。

具体来说,传统决策树在选择划分属性时是在当前结点的所有候选属性(假定有$d$个)中选择一个最优属性;而在RF中,对基决策树的每个结点,先从该结点的候选属性集合中随机选择一个包含$k$个属性的子集,然后再从这个子集中选择一个最优属性用于划分。这里的参数$k$控制了随机性的引入程度:若令$k=d$,则基决策树的构建与传统决策树相同;若令$k=1$,则是随机选择一个属性用于划分;显然,抽取的属性数$k$的选择比较重要,一般推荐 $k=log_2d$ 。由此,随机森林的基学习器的“多样性”不仅来自样本的扰动,还来自属性的扰动,使得最终集成的泛化能力进一步提升。

随机森林的思想

除了作为一个bagging类的集成算法本身的构思,比如通过弱学习器的集成来提供精度和泛化能力,随机森林本身的主要思想在于随机性,通过随机性,提高模型的泛化能力,主要体现在以下三个方面:

  • 对训练样本的随机采样
  • 对属性的随机采样
  • 基于随机采样的属性的决策树构造

随机森林

随机森林的推广

由于RF在实际应用中的良好特性,基于RF,有很多变种算法,应用也很广泛,不光可以用于分类回归,还可以用于特征转换,异常点检测等。下面对于这些RF家族的算法中有代表性的做一个总结。

  • extra trees

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

对于每个决策树的训练集,RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集,而extra trees一般不采用随机采样,即每个决策树采用原始训练集。

在选定了划分特征后,RF的决策树会基于基尼系数,均方差之类的原则,选择一个最优的特征值划分点,这和传统的决策树相同。但是extra trees比较的激进,他会随机的选择一个特征值来划分决策树。

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

  • 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维的高维特征。这里特征维度之间加上空格是为了强调三颗决策树各自的子编码。

映射到高维特征后,可以继续使用监督学习的各种分类回归算法了。

  • Isolation Forest

Isolation Forest(以下简称IForest)是一种异常点检测的方法。它也使用了类似于RF的方法来检测异常点。

对于在T个决策树的样本集,IForest也会对训练集进行随机采样,但是采样个数不需要和RF一样,对于RF,需要采样到采样集样本个数等于训练集个数。但是IForest不需要采样这么多,一般来说,采样个数要远远小于训练集个数?为什么呢?因为我们的目的是异常点检测,只需要部分的样本我们一般就可以将异常点区别出来了。

对于每一个决策树的建立, IForest采用随机选择一个划分特征,对划分特征随机选择一个划分阈值。这点也和RF不同。

另外,IForest一般会选择一个比较小的最大决策树深度max_depth,原因同样本采集,用少量的异常点检测一般不需要这么大规模的决策树。

对于异常点的判断,则是将测试样本点x拟合到T颗决策树。计算在每颗决策树上该样本的叶子节点的深度$h_t(x)$。从而可以计算出平均高度$h(x)$。此时我们用下面的公式计算样本点x的异常概率:

$$s(x,m)=2^{-\frac{h(x)}{c(m)}}$$

其中,$m$为样本个数。$c(m)$的表达式为:

$$c(m)=2ln(m-1)+\xi-2\frac{m-1}{m}$$

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

随机森林的优缺点

优点

  • RF能够解决分类与回归两种类型的问题,并且在这两方面都有较好的表现
  • RF实现简单,并且是bagging族算法,可以高度并行化,训练速度快,在大数据时代的大样本训练有天然优势
  • 子数据集的构造采用有放回式抽样,使得抽样数据集有大约1/3的数据没有被抽中去参加决策树的构造,可以做“包外估计”,减小过拟合风险
  • 随机选择基学习器决策树节点划分特征,这样便于避免“维度灾难”,在高维时,仍然能高效的训练模型
  • 对部分特征缺失不敏感
  • 在训练后,可以给出各个特征对于输出的重要性

缺点

  • 虽然对于缺失值不敏感,但是对于噪音比较敏感,随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合
  • 对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响,所以随机森林在这种数据上产出的属性权值是不可信的

随机森林在sklearn中的参数解释

在sklearn当中按学习任务的不同一共有两个与随机森林相关的类:RandomForestClassifier应用于分类学习任务,RandomForestRegressor应用于回归学习任务。

RandomForestClassifier

参数(parameters)

  • n_estimators : integer, optional (default=10)

    • 随机森林中树的数量,整型,可选项,默认是10
  • criterion : string, optional (default=”gini”)

    • 衡量特征分裂质量的函数,这是一个与基学习器决策树相关的参数,通常对于Gini不纯度采用“gini”,对于信息增益用“entropy”。字符串类型,可选项,默认是”gini”
  • max_depth : integer or None, optional (default=None)

    • 树的最大深度。如果是None,那么结点会延伸直到所有的叶子都只含相同的样本或者所有的叶子结点包含比min_samples_splits少的样本。整型或者None,可选项,默认是None
  • min_samples_split : int, float, optional (default=2)

    • 用于分裂一个内部结点的最小所需的样本数,整型或者浮点型,可选项,默认是2
  • min_samples_leaf : int, float, optional (default=1)

    • 一个叶子结点所要求的最小样本个数,这个参数有平滑模型的作用,特别是回归的学习任务里面。整型或者浮点型,可选项,默认是1
  • min_weight_fraction_leaf : float, optional (default=0.)

    • 一个叶子结点所有输入样本权重总和的最小权重分数,浮点型,可选项,默认为0.
  • max_features : int, float, string or None, optional (default=”auto”)

    • 寻找最优分裂时所考虑的特征个数,整型、浮点型、字符串或者None,可选项,默认是“auto”

      • int, then consider max_features features at each split.
      • float, then max_features is a fraction and int(max_features * n_features) features are considered at each split.
      • “auto”, then max_features=sqrt(n_features).
      • “sqrt”, then max_features=sqrt(n_features) (same as “auto”).
      • “log2”, then max_features=log2(n_features).
      • None, then max_features=n_features.
  • max_leaf_nodes : int or None, optional (default=None)

    • 以最好的方式用max_leaf_nodes来建树,如果是Nonde的话则对叶子结点的个数不限制,整型或者Node,可选项,默认是Node
  • min_impurity_decrease : float, optional (default=0.)

    • 最小不纯度减少值,结点将会继续分裂,如果这个分裂对于不纯度的减少能够大于或者等于该值。浮点型,可选项,默认为0.
  • min_impurity_split : float, (default=1e-7)

    • 建树过程中早起停止的阈值。如果节点的不纯度大于该值将会继续分裂,否则停止,成为叶子结点。浮点型,默认为1e-7
    • 后续将会被min_impurity_decrease参数替代
  • bootstrap : boolean, optional (default=True)

    • 建树时将采用有放回自采样(bootstrap sample),如果是False,那么将用全量数据建树。布尔型,可选项,默认为True
  • oob_score : bool (default=False)

    • 是否采用包外样本来估计泛化准确性,布尔型,默认为False
  • n_jobs : int or None, optional (default=None)

    • 在学习和预测过程当中并行计算的任务数量。None意味着1,-1意味着使用所有的处理器。整型或者None,可选项,默认为None
  • random_state : int, RandomState instance or None, optional (default=None)

    • 随机状态,有以下三种方式
      • int, random_state is the seed used by the random number generator;
      • RandomState instance, random_state is the random number generator;
      • None, the random number generator is the RandomState instance used by np.random.
  • verbose : int, optional (default=0)

    • 控制在学习和预测时是否输出中间结果,整型,可选项,默认是0
  • warm_start : bool, optional (default=False)

    • 布尔型,可选项,默认为False,如果设置为True,将重复使用上一次调用的解来学习并加入更多的学习器到集成算法当中
  • class_weight : dict, list of dicts, “balanced”, “balanced_subsample” or None, optional (default=None)

    • 类别权重,字典,或者字典列表,可选项,默认为None

属性(attributes)

  • estimators_ : list of DecisionTreeClassifier

    • 拟合后的基学习器集合
  • classes_ : array of shape = [n_classes] or a list of such arrays

    • 类别标签(二分类),或者类别标签数组列表(多分类)
  • n_classes_ : int or list

    • 类别数量或者对于每一个输出类别的数量列表
  • n_features_ : int

    • 特征数量
  • n_outputs_ : int

    • 输出数量
  • feature_importances_ : array of shape = [n_features]

    • 特征重要性系数
  • oob_score_ : float

    • 包外样本估计效果,浮点型
  • oob_decision_function_ : array of shape = [n_samples, n_classes]

    • 包外样本预测结果

方法(methods)

方法名称 方法解释
apply(self, X) Apply trees in the forest to X, return leaf indices.
decision_path(self, X) Return the decision path in the forest
fit(self, X, y[, sample_weight]) Build a forest of trees from the training set (X, y).
get_params(self[, deep]) Get parameters for this estimator.
predict(self, X) Predict class for X.
predict_log_proba(self, X) Predict class log-probabilities for X.
predict_proba(self, X) Predict class probabilities for X.
score(self, X, y[, sample_weight]) Returns the mean accuracy on the given test data and labels.
set_params(self, **params) Set the parameters of this estimator.

RandomForestRegressor

参数(parameters)

  • n_estimators : integer, optional (default=10)

    • 随机森林中树的数量,整型,可选项,默认是10
  • criterion : string, optional (default=”mse”)

    • 衡量特征分裂质量的函数,字符串类型,可选项,默认是”mse”
  • max_depth : integer or None, optional (default=None)

    • 树的最大深度。如果是None,那么结点会延伸直到所有的叶子都只含相同的样本或者所有的叶子结点包含比min_samples_splits少的样本。整型或者None,可选项,默认是None
  • min_samples_split : int, float, optional (default=2)

    • 用于分裂一个内部结点的最小所需的样本数,整型或者浮点型,可选项,默认是2
  • min_samples_leaf : int, float, optional (default=1)

    • 一个叶子结点所要求的最小样本个数,这个参数有平滑模型的作用,特别是回归的学习任务里面。整型或者浮点型,可选项,默认是1
  • min_weight_fraction_leaf : float, optional (default=0.)

    • 一个叶子结点所有输入样本权重总和的最小权重分数,浮点型,可选项,默认为0.
  • max_features : int, float, string or None, optional (default=”auto”)

    • 寻找最优分裂时所考虑的特征个数,整型、浮点型、字符串或者None,可选项,默认是“auto”

      • int, then consider max_features features at each split.
      • float, then max_features is a fraction and int(max_features * n_features) features are considered at each split.
      • “auto”, then max_features=sqrt(n_features).
      • “sqrt”, then max_features=sqrt(n_features) (same as “auto”).
      • “log2”, then max_features=log2(n_features).
      • None, then max_features=n_features.
  • max_leaf_nodes : int or None, optional (default=None)

    • 以最好的方式用max_leaf_nodes来建树,如果是Nonde的话则对叶子结点的个数不限制,整型或者Node,可选项,默认是Node
  • min_impurity_decrease : float, optional (default=0.)

    • 最小不纯度减少值,结点将会继续分裂,如果这个分裂对于不纯度的减少能够大于或者等于该值。浮点型,可选项,默认为0.
  • min_impurity_split : float, (default=1e-7)

- 建树过程中早起停止的阈值。如果节点的不纯度大于该值将会继续分裂,否则停止,成为叶子结点。浮点型,默认为1e-7
- 后续将会被`min_impurity_decrease`参数替代
  • bootstrap : boolean, optional (default=True)
- 建树时将采用有放回自采样(bootstrap sample),如果是False,那么将用全量数据建树。布尔型,可选项,默认为True
  • oob_score : bool (default=False)

    • 是否采用包外样本来估计为建模数据的$R^2$,布尔型,默认为False
  • n_jobs : int or None, optional (default=None)

    • 在学习和预测过程当中并行计算的任务数量。None意味着1,-1意味着使用所有的处理器。整型或者None,可选项,默认为None
  • random_state : int, RandomState instance or None, optional (default=None)

    • 随机状态,有以下三种方式
      • int, random_state is the seed used by the random number generator;
      • RandomState instance, random_state is the random number generator;
      • None, the random number generator is the RandomState instance used by np.random.
  • verbose : int, optional (default=0)

    • 控制在学习和预测时是否输出中间结果,整型,可选项,默认是0
  • warm_start : bool, optional (default=False)

    • 布尔型,可选项,默认为False,如果设置为True,将重复使用上一次调用的解来学习并加入更多的学习器到集成算法当中
  • class_weight : dict, list of dicts, “balanced”, “balanced_subsample” or None, optional (default=None)

    • 类别权重,字典,或者字典列表,可选项,默认为None

属性(attributes)

  • estimators_ : list of DecisionTreeClassifier

    • 拟合后的基学习器集合
  • n_features_ : int

    • 特征数量
  • n_outputs_ : int

    • 输出数量
  • feature_importances_ : array of shape = [n_features]

    • 特征重要性系数
  • oob_score_ : float

    • 包外样本估计效果,浮点型
  • oob_prediction_ : array of shape = [n_samples, n_classes]

    • 包外估计在训练集上的预测结果

方法(methods)

方法名称 方法解释
apply(self, X) Apply trees in the forest to X, return leaf indices.
decision_path(self, X) Return the decision path in the forest
fit(self, X, y[, sample_weight]) Build a forest of trees from the training set (X, y).
get_params(self[, deep]) Get parameters for this estimator.
predict(self, X) Predict class for X.
score(self, X, y[, sample_weight]) Returns the mean accuracy on the given test data and labels.
set_params(self, **params) Set the parameters of this estimator.

随机森林的应用场景

因为随机森林可以学习分类和回归两种类型的任务,因此有着比较多的应用前景。结合自己的实践主要在以下两个方面使用了随机森林:

  • 样本维度不高,对精度要求高的分类任务,具体可以参考下面文章

随机森林——二元分类的利器之Kaggle初体验Titanic: Machine Learning from Disaster

  • 因为随机森林可以给出各个特征的重要性,也不失作为一个特征筛选的中间算法过程,具体可以参考下面文章,在信用评分卡的构建当中就用到了随机森林来筛选特征

随机森林在评分卡构建上的应用

参考