模式识别 | 决策树与随机森林_综合

1. 信息增益

2. ID3

3. C4.5

4. CART

5. Random Forest

本章PPT

更多决策树和随机森林的内容：随机森林、CART

1. 信息增益

熵表示随机变量不确定性的度量。设X是一个取有限值的离散型随机变量，概率分布律为：

则随机变量X的熵定义为：

条件熵

设二维离散随机变量(X,Y)的联合概率分布律为：

随机变量X给定条件下随机变量Y的条件熵为H(Y|X),表示已知随机变量X的条件下随机变量Y的不确定性，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

信息增益(互信息)

特征A对训练集D的信息增益g(D,A),定义为训练集D的经验熵H(D)与特征A给定条件下D的条件经验熵之差：

信息增益算法

根据信息增益进行特征选择：对训练集D或其子集，依次计算每个特征的信息增益，选择信息增益最大的特征进行分裂。

信息增益计算示例

2. ID3

核心思想

从根结点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为该节点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有可选特征的信息增益都很小或没有特征可以选择时为止，最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。

算法流程

ID3算法举例

决策树基于训练集构建好后，对于新的样本，根据构建好的决策树，看他属于哪个叶子节点，返回该叶子节点的标签作为新样本的标签。

3. C4.5

ID3的缺点

ID3使用信息增益进行特征选择，会偏向于选择具有大量取值的特征。对于取值比较多的特征，尤其是一些连续型特征，如身高、学号、姓名等。比如学号这一个单独的特征就可以划分所有样本，最极端的情况是每个叶子节点只有一个样本，此时信息增益更大，会首先挑选该特征作为根结点，训练会得到一个庞大且非常浅的树,虽然对训练集拟合程度很高，但泛化能留很差，比如来了一个新生，有一个新学号，就没办法进行分类了。

C4.5

C4.5采用信息增益率进行特征选择：

信息增益率引入了分裂信息，取值数目多的特征分裂信息也会变大，将该特征的信息增益除以分裂信息，再加上一些额外操作，可以有效控制信息增益过大的问题。

C4.5 vs. ID3

1）用信息增益率来选择特征，克服了用信息增益选择特征时偏向选择取值多的特征的不足。

2）在树构造过程中进行剪枝。

3）能够完成对连续属性的离散化处理。

4）能够对不完整数据进行处理。

4. CART

CART由特征选择，树的生成以及剪枝组成，既可以用于分类也可以用于回归，CART决策树是二叉树。

回归树使用平方误差最小化准则，分类树使用基尼指数最小化准则，进行特征选择并且决定特征的最优2值切分点，生成二叉树。当标签Y是连续变量时，生成回归树，是离散变量时生成分类树。

由于ID3、C4.5分别使用信息增益和信息增益率进行特征选择，所以它们只能进行分类（因为对于回归问题，标签Y是连续变量，此时无法计算）。

回归树

输入：训练数据集D

输出：回归树f(x)

1）选择最优的切分特征和切分点。遍历所有的特征j（假设回归时所有特征都是连续特征，当出现离散特征时，此时每个离散特征取值可以做切分点），对于固定的切分特征j，再遍历特征j的所有的切分点s（对所有训练样本 $x_i$ 在特征j上的取值从小到大排序，相邻样本在特征j上的取值的平均数作为一个切分点，共N-1个切分点）。找到一对(j,s)使得下式最小：

其中， $c_1$ 可以是在当前(j,s)划分下，左子树 $R_1$ 中所有样本标签值 $y_i$ 的均值（ $R_1$ 中的样本满足 $x_{i}^{(j)} \leq s$ ）， $c_2$ 同理。

2）用选定的(j,s)划分区域并决定相应区域或节点的输出值：

3）继续对两个子区域/节点递归调用步骤1），2），直到满足停止条件。

4）最后将输入空间划分为M(叶子结点的数目)个区域 $R_1,...,R_M$ ,生成决策树：

对于新的输入样本x，通过构建好的决策树，找到它属于的区域 $R_m$ ,取该区域中所有样本标签值的均值，作为它的输出。

分类树

基尼指数：

基尼指数和熵类似，越大表示样本集合的不确定性越大，当样本集合中都是同一类时，基尼指数为0.

输入：训练数据集D

输出：分类树f(x)

1）选择最优的切分特征和切分点。遍历所有的特征A（假设分类时所有特征都是离散特征，当出现连续特征时，可以采用和之前回归树一样的方法，构造切分点），对于固定的切分特征A，再遍历特征A的所有的切分点a（切分点的数量是特征A的取值数,a是特征A的任意取值）。找到一对(A,a)使得下式最小：

2）用选定的(A,a)划分区域并决定相应区域或节点的输出值：

$D_1$ 区域中所有样本在特征A上的取值为a， $D_2$ 区域中所有样本在特征A上的取值为非a。每个区域的输出值为该区域的样本中出现次数最多的标签或类别。

3）继续对两个子区域/节点递归调用步骤1），2），直到满足停止条件。

4）最后将输入空间划分为M(叶子结点的数目)个区域 $R_1,...,R_M$ ,生成分类树。

对于新的输入样本x，通过构建好的决策树，找到它属于的区域 $R_m$ ,取该区域中所有样本出现次数最多的标签或类别，作为它的类别。

算法停止的条件：节点中样本个数小于预定的阈值，或样本集的基尼指数小于预定阈值(样本基本属于同一类)，或没有更多的特征。

连续值处理

C4.5和CART处理连续值的方法差不多，都是对当前所有训练样本 $x_i$ 在连续特征j上的取值从小到大排序，相邻样本在特征j上的取值的平均数作为一个切分点s，共N-1个切分点。对于C4.5来说，找到一对(j,s)使得切分后信息增益率最大；对于CART来说，解决回归问题时，找到一对(j,s)使得切分后的平方误差最小，解决分类问题时，找到一对(j,s)使得切分后的基尼指数最小。

注意：在C4.5中，离散特征只会参与一次节点的建立，因为C4.5可以是多叉树，分裂后每个子结点在该离散特征上的取值都是一样的，之后特征集会除去这个特征；而连续特征之后还可以参与节点的建立过程，因为对于分裂后每个子结点，该特征仍是连续的，所以可以继续构造切分点。

在CART中，连续特征或离散特征在后面还可以参与子节点的建立。（因为他是二叉树）。

缺失值处理和剪枝

详情查看：https://www.cnblogs.com/keye/p/10267473.html。

ID3，C4.5,CART的比较

5. Random Forest

Random Forest通过训练一群决策树（CART）来完成分类任务。RF用了两次随机抽取，一次是对训练样本的随机抽取;另一次是对特征的随机抽取。核心是由弱变强思想，每棵决策树由于只用了部分特征、部分样本训练而成，可能单个的分类准确率并不是很高。但是当一群这样的决策树组合起来分别对输入数据作出判断时，可以带来较高的准确率（多数投票）。两个重要参数：树节点预选的特征数，随机森林中树的个数。

构建随机森林

1. 从样本集中用bagging采样选出n个样本，预建立CART

2. 在树的每个节点上，从所有属性中随机选择k个属性，从k个属性中选择出一个最佳分割属性（A,a）作为节点(RI 和 RC)

3. 重复以上两步m次，i.e. 构建m棵CART(不剪枝)

4. 这m个CART形成Random Forest

与bagging方法不同，随机森林存在两次随机过程:

1）使用Bootstrap随机选择子样本;

2）每次分裂最佳分割属性不是从完全的属性集上挑选出来，而是从随机选出的部分属性集中挑选的。

对于样本采样使用的是0.632自助法（Bootstrap）。

对于特征的采样，Breiman设计了两种方法，分别是RI(随机输入选择)和 RC(随机线性组合)。

1）RI就是随机的从完全特征集中选择一定数量的特征形成候选特征集。

2）RC会先从所有特征里面随机选择L个特征，然后把这些特征通过线性组合形成一个新的组合特征，线性组合系数来自于[-1,1]上的随机数。重复上述过程F次，就可以得到F个组合特征形成候选分割特征集。

利用随机森林预测

基本步骤(分类)

1. 向建立好的随机森林中输入一个新样本

2. 随机森林中的每棵决策树都独立的做出判断

3. 将得到票数最多的分类结果作为该样本最终的类别

对于回归预测，最简单的做法就是将所有决策树的预测结果取平均值作为最终的结果。

影响随机森林分类性能的主要因素

1) 森林中单颗树的分类强度(Strength):每颗树的分类强度越大，则随机森林的分类性能越好。

2) 森林中树之间的相关度(Correlation):树之间的相关度越大，则随机森林的分类性能越差(最好每个树都是独立的)。

袋外估计

通过bootstrap得到新的样本集D'，再由D'训练不同的 $g_t$ 。我们知道D'中包含了原样本集D中的一些样本(可放回采样)，但也有些样本没有涵盖进去。如下表所示，不同的 $g_t$ (基于 $\hat{D_t}$ 训练得到)下，红色的表示在 $\hat{D_t}$ 中没有这些样本。例如对 $g_1$ 来说， $(x_2,y_2)$ 和 $(x_3,y_3)$ 没有包含进去，对 $g_2$ 来说， $(x_1,y_1)$ 和 $(x_2,y_2)$ 没有包含进去，等等。每个 $g_t$ 中，红色表示的样本被称为 out?-of-?bag(OOB) example。

首先，我们来计算OOB样本到底有多少。假设bootstrap的数量N'=N，那么某个样本 $(x_n,y_n)$ 是OOB的概率是:

其中，e是自然对数，N是原样本集(D)的样本数量。由上述推导可得，每个 $g_t$ 中( $\hat{D_t}$ )，OOB数目大约是 $N/e$ ，即大约有三分之一的样本没有在bootstrap中被抽到。

然后，我们将OOB与之前介绍的Validation进行对比:

在Validation表格中(每一列对应不同的模型或超参数配置，训练集和验证集是一样的，没有使用交叉验证)，蓝色的 $D_{train}$ 用来得到不同的 $g_{\bar{m}}$ ，而红色的 $D_{val}$ 用来验证各自的 $g_{\bar{m}}$ 。 $D_{train}$ 与 $D_{val}$ 没有交集，一般 $D_{train}$ 是 $D_{val}$ 的数倍关系。再看左边的OOB表格，之前我们也介绍过，蓝色的部分用来得到不同的 $g_t$ ，而红色的部分是OOB样本。而我们刚刚也推导过，红色部分大约占N的 $\frac{1}{e}$ 。通过两个表格的比较，我们发现OOB样本类似于 $D_{val}$ ，那么是否能使用OOB样本来验证 $g_t$ 的好坏呢?答案是肯定的。但是，通常我们并不需要对单个 $g_t$ 进行验证。因为我们更关心的是由许多 $g_t$ 组合成的 G，即使 $g_t$ 表现不太好，只要G表现足够好就行了。那么问题就转化成了如何使用 OOB来验证G的好坏。方法是先看每一个样本 $(x_n,y_n)$ n=1,...,N是哪些 $g_t$ 的OOB数据，然后计算其在这些 $g_t$ 上的表现，最后将所有样本的表现求平均即可。例如，样本 $(x_N,y_N)$ 是 $g_2,g_3,g_T$ 的OOB，则可以计算 $(x_N,y_N)$ 在 $G_{\bar{N}}(x)$ 上的表现为:

这种做法我们并不陌生，就像是我们之前介绍过的Leave-?One-?Out Cross Validation(每次取数据集中的一个样本做验证，剩余样本训练)，每次只对一个样本进行 $g_{\bar{m}}$ 的验证一样，只不过这里选择的是每个样本是哪些 $g_t$ 的 OOB，然后再分别进行 $G_{\bar{n}}(x)$ 的验证。每个样本都当成验证数据一次(与留一法相同)，最后计算所有样本的平均表现:

$E_{oob}(G)$ 估算的就是G的表现好坏。我们把 $E_{oob}(G)$ 称为bagging或者Random Forest的 self?-validation。

这种self?-validation相比于validation来说还有一个优点就是它不需要重复训练。如下图左边所示，在通过 $D_{val}$ 选择到表现最好的 $g_{\bar{m}^*}$ (在验证集上误差最小)之后，还需要在 $D_{train}$ 和 $D_{val}$ 组成的所有样本集D上重新对 $g_{\bar{m}^*}$ 对应的模型或超参数配置下训练一次，以得到最终的模型参数（对应一个最好的假设g）。但是self?-validation在调整随机森林算法相关系数（超参数）并得到最小的 $E_{oob}$ 之后，就完成了整个模型的建立，无需重新训练模型。随机森林算法中，self?-validation在衡量G的表现上通常相当准确。

优缺点

优点：

1）可以处理高维数据，可以不用进行特征筛选

2）非常容易进行分布式处理，实现起来非常高效

3）可以利用OOB(out of bag)数据评价算法的误差率，而不用像一般算法那样还需要选择validation set测误差

4）可以利用OOB和permutation test(把某个特征的值随机进行重排)计算每个feature的重要性，也可以作为其他非线性算法特征选择阶段的算法

5）因为最终结果通过voting by majority得到，相对光滑，像SVM 那样“large-margin like”的边界,受噪音干扰小，鲁棒性好

6）CART的优点:容易理解，处理非线性的问题，可以很好的处理数值型和序列型变量，处理缺失值。

缺点：

1）树越多，随机森林的表现才会越稳定。所以在实际使用随机森林的时候需要注意如果树不够多的时候，可能会导致不稳定的情况。

2）不平衡数据集。分类结果会倾向于样本多的类别，所以训练样本中各类别的数据必须相同或相近。

Breiman在实现该算法的时候考虑到了该问题，采取了根据样本类别比例对决策树的判断赋予不同权值的方法，比如类A:类 B的样本量比例=3:1,,则对新样本，判断为类A的决策结果乘以 25%，判断为类B的结果乘以75%，然后再比较两者大小，得到最终的结果。但是Breiman的实验结果也表明了该方法还是不能很好的解决由样本数量不平衡造成的结果不准确的问题。