本文共 3506 字，大约阅读时间需要 11 分钟。

决策树，随机森林补充（二）

一. 如何评价一棵决策树

1. 思想

首先，我们先明确一些符号和概念。

假定样本的总类别有K个。对于决策树的某叶结点,假定该叶结点含有样本数目为n。其中，第k类的样本点数目为nk (k=1,2,…,K)。我们先拿出两个极端情况：

• 假如某类样为第j个样本本nj =n，而n1 ,…,n(j-1) ,n(j+1) ,…,nK =0，那么，我们称这个nj结点为纯结点;(说白了，只有一种类别)

• 若各类样本数目n1 =n2 =…=nk =n/K,称该样本为均结点。(即：所有类别)

纯结点与均结点有如下特点：

• 纯结点的熵Hp =0，最小
• 均结点的熵Hu =lnk, (满k叉树的高度)，最大

在这个情况下，我们对所有叶子结点的高度求和，在决策树中，就相当于我们对所有叶结点的熵求和，该值越小说明对样本的分类越精确。

2. 评价函数

这个评价函数就是：$$C(T)=\sum _{t\in leaves}Nt\times H(t)$$ 。该评价函数值越小越好，某些方面讲，也可以把他当做损失函数。

二.决策树过拟合的处理

1. 剪枝

我们之前已经知道，决策树有三种构造方式：ID3，C4.5，CART。无论你是哪种剪枝方式，剪枝的思路都一样。只有一个一点不一样：每剪一次，对当前树的评价标准不一样。如果这个决策树是ID3构造的，你就得按照信息增益值为标准；如果是C4.5，你就得按照信息增益率为标准；如果是CART，你就得按照基尼系数为标准。

那么，如何进行剪枝呢？思路如下：

• 首先，由完全树T0 开始，剪枝部分结点得到T1 ,再次剪枝部分结点得到T2 …直到仅剩树根的树T k ;
• 每剪一次，都会得到一次全新的树。剪枝k次，就会得到k个全新的树。在验证数据集上对这k个树分别评价,选择损失函数最小的树Tα为最后的决策树

关于剪枝，其实有预剪枝，即在训练之前就进行剪枝，还有后剪枝，即：过拟合之后再进行剪枝。

预剪枝比较容易，甚至在api里面就直接有，你只需指定定决策树的高度等等参数即可。如果不合适，再在api当中直接进行调参即可。

后剪枝比较麻烦，下面的内容都是后剪枝的内容。

2.剪枝系数

我们从评价函数入手：$$C(T)=\sum _{t\in leaves}Nt\times H(t)$$ 。我们在这个基础上引入一个系数$$\alpha$$，然后构造出另外一个式子：

我们对当前树进行剪枝，假设剪枝的对象是以结点r为根节点的树，剪枝之后，只保留这个r结点，和r连接的所有孩子和子孙都删掉。我们考察这个以r为结点的树：

• 剪枝之前，评价函数，即：损失函数为：$$C_{\alpha }(R)=C(R)+\alpha |R_{leaf}|$$
• 剪枝之后，评价函数，即：损失函数为：$$C_{\alpha }(r)=C(r)+\alpha$$
• 我们令上面这两个式子相等：求得：$$\alpha =\frac{C(r)-C(R)}{|R_{leaf}-1|}$$

这个$$\alpha$$，我们就称之为：剪枝系数

3.剪枝算法

引入剪枝系数之后，我们结合剪枝的思路，大致可以总结出一个剪枝算法：

对于给定的决策树T0：

• 计算所有内部节点的剪枝系数;
• 查找最小剪枝系数的结点,剪枝得决策树Tk ;
• 重复以上步骤,直到决策树Tk 只有1个结点，在这个过程中，我们会得到决策树序列[T0，T1， T2 …TK] ;
  使用验证样本集选择最优子树。

三.决策森林

1. Bagging

之前在介绍随机森林基本原理的时候，有简单介绍过这个采样方式。这个采样方式英文全称为：Bootstrap aggregation，因此在某些资料里面，也被简称为Bagging策略。它可以应用于决策树，也可以应用于SVM，逻辑回归等。这个策略的内容如下：

• 首先，从样本集中重采样(有重复的，有放回的)选出n个样本
• 在所有属性上,对这n个样本建立分类器
• 重复以上两步m次,即获得了m个分类器
• 将数据放在这m个分类器上,最后根据这m个分类器的投票结果,决定数据属于哪一类

在一些书籍或者资料里面，会提及一个事情：在进行bagging策略采样的时候，如果n足够大，当m=n的时候，那么大概会有（1-1/e）这么多比例（大约63.2%）的独立样本，剩下的样本是不会出现在样本集合里的（Bagging取样一定会取到重复的，毕竟是又放回的，有重复的。所以，就意味着一定有数据取不到）。(1-63.2%) = 36.8%，也就是说，Bootstrap每次约有36.8%的样本不会出现在Bootstrap所采集的样本集合中,这些数据很显然，我们将这些不参与训练的数据成为OOB（Out of Bag，中文名：袋外数据）。尽管OOB不参与训练数据，但可以用于取代测试集用于误差估计。科学家们进行多次实验，证明用OOB进行误差估计与同训练集一样大小的测试集精度相同，因此是可靠的。

2.随机森林与Bagging的联系

基于Bagging，随机森林做了一部分修改：

• 从样本集中用Bootstrap采样选出n个样本;
• 从所有属性中随机选择k个属性,选择最佳分割属性作为节点建立CART决策树;
• 重复以上两步m次，即建立了m棵CART决策树这m个CART形成随机森林,通过投票表决结果，决定数据属于哪一类

值得一提的是：随机森林不一定是基于决策树的。你也可以使用SVM、逻辑回归等其他分类器。习惯上，这些分类器组成的“总分类器”,仍然叫做随机森林。

四. 随机森林还能干什么？

1.计算样本间的相似度

这个可以用来作数据的预处理。它的原理不难：若两样本同时出现在相同叶结点的次数越多，那么这两个样本就越相似。算法过程如下:

• 我们假设有N个样本，我们初始化一个N×N的零矩阵S，其中S[i,j]表示样本i和样本j的相似度。那么这n个样本会分别进入一个随机森林，我们假设这个随机森林有m个决策树。
• 对于m颗决策树形成的随机森林，让这N个数据分别进入决策森林。这样，这些样本最终肯定会到达一个叶子结点。等所有样本都跑完了，就相当于遍历所有决策树的所有叶子结点，这样，每个叶子结点和其他叶子结点之间都会产生相似度。这个相似度，我们可以用欧氏距离，曼哈顿距离等等，都可以。
• 如果有i 和 j最后落入同一个叶子结点，说明他俩相似度比较高，S[i][j]加上1

2.计算特征重要程度

随机森林是常用的衡量特征重要性的方法。一个数据集当中有许多特征，让这些特征样本通过一个随机森林，那么肯定会落到一个叶子结点。我们计算这些特征经过的结点的一些情况，比如说：使用经过结点的数目、经过结点的gini系数和等指标。或者随机替换一列数据，重新建立决策树，计算新模型的正确率变化,从而考虑这一列特征的重要性。

3. 孤立森林

英文名：Isolation Forest. 简称：iForest。这个东西经常用于异常点的检测。

很多时候，我们并不需要一板一眼的建立决策树和随机森林，我们可以随机选择特征、随机选择分割点，最后生成一定深度的决策树iTree。然后，由这若干颗iTree组成iForest。

所谓异常点，就是离常规样本的距离通常非常大的那种点。这也就意味着，它不具有正常样本的那些特征，因此，在进入随机森林之后，它会更快的到达叶子节点，即：从跟到叶子结点的距离更短。因此，我们遵从如下算法：

• 计算iTree中样本x从根到叶子的长度f(x)。
• 计算iForest中f(x)的总和F(x)。若F(x)越小，那么这个点就大概率是异常点

转载地址：https://blog.csdn.net/johnny_love_1968/article/details/116405950 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！