机器学习之随机森林

这里记录一下 AI 作品赛里接触到的随机森林算法。

决策树

随机森林由许多决策树（decision tree）组成，我们可以将决策树视为一系列关于数据的是/否问题，从而最终得出一个预测类别（或回归情况下的连续值）。 这是一个可解释的模型，因为它非常像我们人类进行分类的过程：在我们做出决定之前（在理想世界中），我们会对可用数据进行一系列的询问。
当我们训练决策树时到底发生了什么？可视化可以帮助我们更好地理解决策树，这可以通过 Scikit-Learn 的一个功能来实现（详细信息，请查看 notebook 或这篇文章）。

除叶子节点（彩色终端节点）外，所有节点都有 5 个部分：

• 基于某个特征的一个值对数据进行的提问，每个提问都有一个真或假的答案可以分裂节点。根据答案，数据点相应地向下移动。
• gini：节点的 Gini 不纯度。当我们沿着树向下移动时，平均加权基尼不纯度会减少。
• samples：节点中的观测数据数量。
• value：每个类中的样本数。例如，根节点中有 2 个样本属于类 0，有 4 个样本属于类 1。
• class：该节点中大多数点的分类。在叶节点中，即是对节点中所有样本的预测。

决策树的特征选择一般有 3 种量化方法：信息增益、信息增益率、基尼指数。

信息增益

在信息论中，熵表示随机变量不确定性的度量。假设随机变量 X 有有限个取值，取值 对应的概率为 ，则 X 的熵定义为：

如果某件事一定发生（太阳东升西落）或一定不发生（钓鱼岛是日本的），则概率为 1 或 0，对应的熵均为 0。
如果某件事可能发生可能不发生（天要下雨，娘要嫁人），概率介于 0 到 1 之间，熵大于 0。
由此可见，熵越大，随机性越大，结果越不确定。
我们再来看一看条件熵 ，表示引入随机变量 Y 对于消除 X 不确定性的程度。假如 X、Y 相互独立，则 X 的条件熵和熵有相同的值；否则条件熵一定小于熵。
明确了这两个概念，理解信息增益就比较方便了。现在我们有一份数据集 D（例如贷款信息登记表）和特征 A（例如年龄），则A 的信息增益就是 D 本身的熵与特征 A 给定条件下 D 的条件熵之差，即：

数据集 D 的熵是一个常量。信息增益越大，表示条件熵 越小，A 消除 D 的不确定性的功劳越大。
所以要优先选择信息增益大的特征，它们具有更强的分类能力。由此生成决策树，称为ID3 算法。

信息增益率

当某个特征具有多种候选值时，信息增益容易偏大，造成误差。引入信息增益率可以校正这一问题。
信息增益率 为信息增益与数据集 D 的熵之比：

同样，我们优先选择信息增益率最大的特征，由此生成决策树，称为C4.5 算法。

基尼不纯度（Gini Impurity）

节点的基尼不纯度是指，根据节点中样本的分布对样本分类时，从节点中随机选择的样本被分错的概率。
如，在根节点中，根据节点中的样本标签有 44.4％的可能性错误地对某个随机选择的数据点进行分类。可以      使用以下等式得出这个值：

节点 n 的基尼不纯度是1 减去每个类（二元分类任务中是 2）的样本比例的平方和。

例如根节点的基尼不纯度：

在每个节点，决策树要在所有特征中搜索用于拆分的值，从而可以最大限度地减少基尼不纯度。（拆分节点的另一个替代方法是使用信息增益）。
然后，它以贪婪递归的过程重复这种拆分，直到达到最大深度，或者每个节点仅包含同类的样本。
树每层的加权总基尼不纯度（每个节点的基尼不纯度按照该节点中来自父节点的点的比例进行加权）一定是减少的。在树的第二层，总加权基尼不纯度值为 0.333：

最终，最后一层的加权总基尼不纯度变为 0，也意味着每个节点都是完全纯粹的，从节点中随机选择的点不会被错误分类。虽然这一切看起来挺好的，但这意味着模型可能过拟合，因为所有节点都是仅仅使用训练数据构建的。

决策树剪枝

决策树生成算法递归产生一棵决策树，直到结束划分。什么时候结束呢？

• 样本属于同一种类型
• 没有特征可以分割

这样得到的决策树往往对训练数据分类非常精准，但是对于未知数据表现比较差。
原因在于基于训练集构造的决策树过于复杂，产生过拟合。所以需要对决策树简化，砍掉多余的分支，提高泛化能力。
决策树剪枝一般有两种方法：

• 预剪枝：在树的生成过程中剪枝。基于贪心策略，可能造成局部最优
• 后剪枝：等树全部生成后剪枝。运算量较大，但是比较精准

决策树剪枝往往通过极小化决策树整体的损失函数实现。

假设树 T 有|T|个叶子节点，某一个叶子节点 t 上有 个样本，其中 k 类的样本有 个， 为叶子节点 t 的熵， 是参数，则决策树的损失函数定义为：

其中熵为：

损失函数第一项为训练误差，第二项为模型复杂度，用参数 来衡量二者的比重。

CART 算法

CART 表示分类回归决策树，同样由特征选择、树的生成及剪枝组成，可以处理分类和回归任务。
相比之下，ID3 和 C4.5 算法只能处理分类任务。
CART 假设决策树是二叉树，内部结点特征的取值为“是”和“否”，依次递归地二分每个特征。
CART 对回归树采用平方误差最小化准则，对分类树用基尼指数最小化准则。

过拟合–为什么森林比一棵树更好

因为这棵树是在训练数据上没有犯错，我们没有限制最大深度（树的层数），因此泛化能力差。
过拟合发生在当我们有一个非常灵活的模型（模型具有高能力）时，其本质上是通过紧密拟合来记住训练数据。这样的问题是模型不仅学到了训练数据中的实际关系，还学习了存在的噪声。灵活的模型具有高方差（variance），因为学到的参数（例如决策树的结构）将随着训练数据的不同而变化很大。

当我们不限制最大深度时决策树容易过拟合的原因是它具有无限的灵活性，这意味着它可以持续生长，直到它为每个单独的观察点都生成一个叶节点，达到完美地分类。
如果返回到之前决策树的图像并将最大深度限制为 2（仅进行一次拆分），则分类不再 100％正确。我们减少了决策树的方差，但代价是增加了偏差。
限制树的深度可以减少方差（好）并且增加偏差（坏），一种替代方案是，我们可以将许多决策树组合成一个称为随机森林的集成模型（ensemble model）。

随机森林

我们将使用CART 决策树作为弱学习器的 bagging 方法称为随机森林。
bagging 是一种在原始数据集上，通过有放回抽样分别选出 k 个新数据集，来训练分类器的集成算法。分类器之间没有依赖关系。

随机森林是由许多决策树组成的模型。这个模型不是简单地平均所有树（我们可以称之为“森林”）的预测，而是使用了两个关键概念，名字中的随机二字也是由此而来：

• 在构建树时对训练数据点进行随机抽样
• 分割节点时考虑特征的随机子集

随机抽样训练观测数据

在训练时，随机森林中的每棵树都会从数据点的随机样本中学习。样本被有放回的抽样，称为自助抽样法（bootstrapping），这意味着一些样本将在一棵树中被多次使用。背后的想法是在不同样本上训练每棵树，尽管每棵树相对于特定训练数据集可能具有高方差，但总体而言，整个森林将具有较低的方差，同时不以增加偏差为代价。
在测试时，通过平均每个决策树的预测来进行预测。这种在不同的自助抽样数据子集上训练单个学习器，然后对预测进行平均的过程称为 bagging，是 bootstrap aggregating 的缩写。

用于拆分节点的随机特征子集

随机森林中的另一个主要概念是，只考虑所有特征的一个子集来拆分每个决策树中的每个节点。通常将其设置为 sqrt（n_features）以进行分类，这意味着如果有 16 个特征，则在每个树中的每个节点处，只考虑 4 个随机特征来拆分节点。（随机森林也可以在每个节点处考虑所有的特征，如回归中常见的那样。这些选项可以在 Scikit-Learn Random Forest 的实现中控制）。
如果你能理解一棵单独的决策树，bagging 的理念，以及随机的特征子集，那么你对随机森林的工作方式也就有了很好的理解：

随机森林将成百上千棵决策树组合在一起，在略微不同的观察集上训练每个决策树，在每棵树中仅考虑有限数量的特征来拆分节点。随机森林的最终预测是通过平均每棵树的预测来得到的。

想理解为什么随机森林优于单一的决策树，请想象以下场景：你要判断特斯拉的股票是否上涨，现在你身边有十几位对该公司都没有先验知识的分析师。每个分析师都有较低的偏见，因为他们没有任何假设，并且可以从新闻报道的数据集中学习。
这似乎是一个理想的情况，但问题是报道中除了真实的信号外也可能包含噪音。 因为分析师们完全根据数据做出预测，即他们具有很高的灵活性，也就意味着他们可能会被无关的信息所左右。分析师们可能会从同一数据集中得出不同的预测。此外，如果提供不同的报道训练集，每个分析师都有高方差，并得出截然不同的预测。
解决方案是不依赖于任何一个人，而是汇集每个分析师的投票。此外，与随机森林一样，允许每个分析师仅使用一部分报道，并希望通过采样来消除噪声信息的影响。在现实生活中，我们也依赖于多种信息来源（从不信任亚马逊的单独评论），因此，不仅决策树的思想很直观，而且将它们组合在一起成为随机森林的想法同样如此。

算法特点

由于随机性，随机森林对于降低模型方差效果显著。故随机森林一般不需要额外剪枝，就能取得较好的泛化性能。

相对而言，模型对于训练集的拟合程度就会差一些，相比于基于 boosting 的 GBDT 模型，偏差会大一些。

另外，随机森林中的树一般会比较深，以尽可能地降低偏差；而 GBDT 树的深度会比较浅，通过减少模型复杂度来降低方差。

最后，我们总结一下随机森林都有哪些优点：

• 采用了集成算法，精度优于大多数单模型算法
• 在测试集上表现良好，两个随机性的引入降低了过拟合风险
• 树的组合可以让随机森林处理非线性数据
• 训练过程中能检测特征重要性，是常见的特征筛选方法
• 每棵树可以同时生成，并行效率高，训练速度快
• 可以自动处理缺省值

模型评价

AUC(area under the curve)是 ROC 曲线下的面积。所以，在理解 AUC 之前，要先了解 ROC 是什么。而 ROC 的计算又需要借助混淆矩阵。

AUC 是一个从 0（最差）到 1（最佳）的度量值，

我们还可以绘制单个决策树（顶部）和随机森林（底部）的 ROC 曲线。靠近左上角的曲线代表着更好的模型：

问答

为什么要随机抽样训练集？

如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有 bagging 的必要；

为什么要有放回地抽样？

如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是”有偏的”，都是绝对”片面的”（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是”求同”，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是”盲人摸象”。

随机森林的随机体现在哪里？

1）如果训练集大小为 N，对于每棵树而言，随机且有放回地从训练集中的抽取 N 个训练样本（这种采样方式称为 bootstrap sample 方法），作为该树的训练集；

从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本

2）如果每个样本的特征维度为 M，指定一个常数 m<<M，随机地从 M 个特征中选取 m 个特征子集，每次树进行分裂时，从这 m 个特征中选择最优的；

这两种随机有什么好处？

两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。

随机森林分类的错误率和什么有关？

• 森林中任意两棵树的相关性：相关性越大，错误率越大；
• 森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。

减小特征选择个数 m，树的相关性和分类能力也会相应的降低；增大 m，两者也会随之增大。所以关键问题是如何选择最优的 m（或者是范围），这也是随机森林唯一的一个参数。