随机森林

预备：决策树学习

决策树是各种机器学习任务的常用方法。 Hastie et al.说：“树学习是如今最能满足于数据挖掘的方法，因为它在特征值的缩放和其他各种转换下保持不变，对无关特征是鲁棒的，而且能生成可被检查的模型。然而，它通常并不准确。”
特别的，生长很深的树容易学习到高度不规则的模式，即过学习，在训练集上具有低偏差和高方差的特点。随机森林是平均多个深决策树以降低方差的一种方法，其中，决策树是在一个数据集上的不同部分进行训练的。这是以偏差的小幅增加和一些可解释性的丧失为代价的，但是在最终的模型中通常会大大提高性能。

从 bagging 到随机森林

上面的过程描述了树的原始的bagging 算法。随机森林与这个通用的方案只有一点不同:它使用一种改进的学习算法，在学习过程中的每次候选分裂中选择特征的随机子集。这个过程有时又被称为“特征 bagging”。这样做的原因是bootstrap 抽样导致的树的相关性：如果有一些特征预测目标值的能力很强，那么这些特征就会被许多树所选择，这样就会导致树的强相关性。Ho分析了不同条件下bagging 和随机子空间投影对精度提高的影响。
典型地，对于一个包含p 个特征的分类问题，可以在每次划分时使用 个特征。对于回归问题，作者推荐p/3 但不少于5 个特征。

极限树

再加上一个随机化步骤，就会得到极限随机树（extremely randomized trees），即极限树。与普通的随机森林相同，他们都是单个树的集成，但也有不同：首先，每棵树都使用整个学习样本进行了训练，其次，自上而下的划分是随机的。它并不计算每个特征的最优划分点（例如，基于信息熵或者基尼不纯度），而是随机选择划分点。该值是从特征经验范围内均匀随机选取的。在所有随机的划分点中，选择其中分数最高的作为结点的划分点。与普通的随机森林相似，可以指定每个节点要选择的特征的个数。该参数的默认值，对于分类问题，是，对于回归问题，是，其中 是模型的特征个数。

特征的重要性

随机森林天然可用来对回归或分类问题中变量的重要性进行排序。下面的技术来自Breiman的论文，R语言包randomForest包含它的实现。
度量数据集的特征重要性的第一步是，使用训练集训练一个随机森林模型。在训练过程中记录下每个数据点的out-of-bag误差，然后在整个森林上进行平均。
为了度量第个特征的重要性，第个特征的值在训练数据中被打乱，并重新计算打乱后的数据的out-of-bag误差。则第个特征的重要性分数可以通过计算打乱前后的out-of-bag误差的差值的平均来得到，这个分数通过计算这些差值的标准差进行标准化。
产生更大分数的特征比小分数的特征更重要。这种特征重要性的度量方法的统计定义由Zhu et al.给出。
这种度量方法也有一些缺陷。对于包含不同取值个数的类别特征，随机森林更偏向于那些取值个数较多的特征，partial permutations
、growing unbiased trees可以用来解决这个问题。如果数据包含一些相互关联的特征组，那么更小的组更容易被选择。

基于随机森林的非监督学习

作为构建的一部分，随机森林预测器自然会导致观测值之间的不相似性度量。还可以定义未标记数据之间的随机森林差异度量：其思想是构造一个随机森林预测器，将“观测”数据与适当生成的合成数据区分开来。 观察到的数据是原始的未标记数据，合成数据是从参考分布中提取的。随机森林的不相似性度量之所以吸引人，是因为它能很好地处理混合变量类型，对输入变量的单调变换是不敏感的，而且在存在异常值的情况下度量结果依然可靠。由于其固有变量的选择，随机森林不相似性很容易处理大量的半连续变量。