决策树与随机森林

雨点打透心脏的1/2处 2022-09-16 14:22 184阅读 0赞

**目录**

决策树的简介

信息增益

如何构建决策树

如何避免过拟合

剪枝

随机森林

Bagging算法(套袋发)

特征选择

决策树的生成

--------------------

[决策树和随机森林 - 知乎][-]

[Bagging和Boosting的概念与区别 - 多一点 - 博客园][Bagging_Boosting_ - _ -]

# 决策树的简介 #

决策树模型是一种树形结构，由一系列节点组成，每一个节点代表一个特征和相应的决策规则。是基于特征对实例进行分类或回归的过程，即根据某个特征把数据分划分到若干个子区域(子树)，再对子区域递归划分，直到满足某个条件则停止划分并作为叶子节点，不满足条件则继续递归划分。  
决策树是一种基本的分类与回归方法，学习通常包含三个步骤：**特征选择、决策树的生成和决策树的剪枝。**![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16][]

决策树学习本质是**从训练数据集中归纳出一组分类规则**；决策树学习的损失函数通常是**正则化的极大似然函数**，学习策略是由训练数据集估计条件概率模型。

决策树学习的算法通常是一个**递归地选择最优特征，并根据该特征进行分割。这一过程对应着决策树的构建，也对应着特征空间的划分**。使得划分之后的各个子集能够被基本分类，那么构建叶节点；否则继续递归划分。

决策树可能发生过拟合，因此需要剪枝，从下而上进行，减去过于细分的结点，使其会退到父结点。

*  根节点：最顶层的节点，也是最重要的节点。如图中“是否去健身房”
 *  叶子节点：代表标签类别。如图中“看”和“不看”
 *  中间节点：中间分类条件。如图中“健身完后去游泳”，“是否有好看的电影”
 *  分枝：代表每一个条件的输出
 *  二叉树：每一个节点上有两个分枝
 *  多叉树：每一个节点上至少有两个分枝

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_18_color_FFFFFF_t_70_g_se_x_16][]

上面图中我们为啥要用“是否去健身房”做根节点呢？可不可以用“是否有好看的电影”做根节点呢？这样做有什么原因吗？要回答这些问题，我们首先要理解决策树的思想是什么。决策树实际上就是寻找最纯净的划分方法，这个“最纯净”在数学上叫纯度，纯度通俗点理解就是决策结果要分得足够开（y=1的和y=0的混到一起就会不纯），尽可能让类别一样的数据在树的同一边，当树的叶子节点的数据都是同一类的时候，则停止分类。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

其中： ![e78068f4fd214362ba3ae936170a6893.png][] 为随机变量 ![\[公式\]][equation_tex_X] 取值为 ![\[公式\]][equation_tex_i] 的概率， ![\[公式\]][equation_tex_n] 代表种类，每一个类别中， ![\[公式\]][equation_tex_P] 代表某个种类的概率乘以当前种类的概率![\[公式\]][equation_tex_P]取![\[公式\]][equation_tex_log]，然后将各个类别计算结果累加。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_17_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_18_color_FFFFFF_t_70_g_se_x_16 1][]

#  信息增益  #

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_18_color_FFFFFF_t_70_g_se_x_16 2][]

## 如何构建决策树 ##

根节点以及树节点是从最重要到次重要依次排序的，**ID3算法用的是信息增益，C4.5算法用信息增益率；CART算法使用基尼系数。**决策树方法是会把每个特征都试一遍，然后选取那个能够使分类分的最好的特征，也就是说将A属性作为父节点，产生的纯度增益（GainA）要大于B属性作为父节点，则A作为优先选取的属性。

**三种方法对比：**

ID3算法：信息增益越大，则选取该分裂规则，多分叉树。信息增益可以理解为，有了x以后对于标签p的不确定性的减少，减少的越多越好，即信息增益越大越好。倾向于选择水平数量较多的变量，可能导致训练得到一个庞大且深度浅的树；另外输入变量必须是分类变量（连续变量必须离散化）；最后无法处理空值。

C4.5选择了信息增益率替代信息增益作为分裂准则。此方法避免了ID3算法中的归纳偏置问题，因为ID3算法会偏向于选择类别较多的属性（形成分支较多会导致信息增益大）。多分叉树。连续属性的分裂只能二分裂，离散属性的分裂可以多分裂，比较分裂前后信息增益率，选取信息增益率最大的。

CART以基尼系数替代熵；最小化不纯度而不是最大化信息增益。既可以用于分类也可以用于回归。CART用Gini系数最小化准则来进行特征选择，生成二叉树。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

先构建决策树（训练阶段），再使用决策树（分类阶段）

# 如何避免过拟合 #

如果决策树考虑了所有的训练数据集，得到的决策树将会过于庞大。虽然这个决策树对于训练数据集的拟合概率为100%，但是由于过分考虑所有的数据，将数据切得太碎太碎了，这样就会使得决策树学习到一些噪音点、错误点，出现过拟合的现象。

两种方法可以避免过拟合：剪枝和随机森林。

## **剪枝** ##

剪枝分为**预剪枝和后剪枝**。

*  预剪枝：在构建决策树的过程中，提前停止。如限制深度、限制当前集合的样本个数的最低阈值。对比未剪枝的决策树和经过预剪枝的决策树可以看出：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛化性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。
 *  后剪枝：先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。对比预剪枝和后剪枝，能够发现，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛化性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

## **随机森林** ##

随机森林就是通过**集成学习的思想将多棵决策树**集成的一种算法，它的基本单元是决策树，本质是一种**集成学习（Ensemble Learning）方**法。

从直观角度来解释，每棵决策树都是一个分类器，那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果，将投票次数最多的类别指定为最终的输出，这就是一种最简单的 Bagging （下面介绍）思想。

随机森林属于集成学习(ensemble learning)中的bagging算法，在集成算法中主要分为bagging算法与boosting算法，

随机森林体现了两方面的**随机**：

*  **样本随机** ：不使用全部数据集，而是随机有放回采样（有一定概率避免选到异常点，使得树的效果更好）
 *  **特征随机** ：不使用全部特征，而是随机选取一部分特征（有一定概率避开使用传统信息增益出问题的特征）

随机森林中的每棵树是怎么生成的呢？

1.  如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本，作为该树的训练集；

从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本（理解这点很重要）。

问题1：为什么要随机抽样训练集？

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

问题2：为什么要有放回地抽样？

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

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

3. 每棵树都尽最大程度的生长，并且没有剪枝过程。

一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，**使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。**

**随机森林分类效果（错误率）与两个因素有关：**

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

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

## Bagging算法(套袋发) ##

*  bagging的算法过程如下：
    
    1.  从原始样本集中使用Bootstraping 方法随机抽取n个训练样本，共进行k轮抽取，得到k个训练集（k个训练集之间相互独立，元素可以有重复）。
    2.  对于n个训练集，我们训练k个模型，（这个模型可根据具体的情况而定，可以是决策树，knn等）
    3.  对于分类问题：由投票表决产生的分类结果；对于回归问题，由k个模型预测结果的均值作为最后预测的结果（所有模型的重要性相同）。

Boosting（提升法）

*  boosting的算法过程如下：
    
    1.  对于训练集中的每个样本建立权值wi，表示对每个样本的权重， 其关键在与对于被错误分类的样本权重会在下一轮的分类中获得更大的权重（错误分类的样本的权重增加）。
    2.  同时加大分类 误差概率小的弱分类器的权值，使其在表决中起到更大的作用，减小分类误差率较大弱分类器的权值，使其在表决中起到较小的作用。每一次迭代都得到一个弱分类器，需要使用某种策略将其组合，最为最终模型，(adaboost给每个迭代之后的弱分类器一个权值，将其线性组合作为最终的分类器,误差小的分类器权值越大。)

Bagging和Boosting 的主要区别

*  样本选择上: Bagging采取Bootstraping的是随机有放回的取样，Boosting的每一轮训练的样本是固定的，改变的是买个样的权重。
 *  样本权重上：Bagging采取的是均匀取样，且每个样本的权重相同，Boosting根据错误率调整样本权重，错误率越大的样本权重会变大
 *  预测函数上：Bagging所以的预测函数权值相同，Boosting中误差越小的预测函数其权值越大。
 *  并行计算: Bagging 的各个预测函数可以并行生成;Boosting的各个预测函数必须按照顺序迭代生成.

将决策树与以上框架组合成新的算法

*  Bagging + 决策树 = 随机森林
 *  AdaBoost + 决策树 = 提升树
 *  gradient + 决策树 = GDBT

# 特征选择 #

特征选择的准则：信息增益或信息增益比。我们选择信息增益最大的那个分割。

A.熵（entropy）与基尼（Gini）系数

熵：物体内部的混乱程度或不确定性，熵值越大，则物体内部的混乱程度越大;反之，熵值越低，物体内部纯净度越高。

由熵的公式可知，当物体内部某个类的概率 较小时，则 （负数）的绝对值就越大由此可知，当物体或集合内部的类别非常多时（即物体内部混乱程度很高），每个类别的概率就会很小，就会导致物体的熵值很高。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

# 决策树的生成 #

目的：得到熵值降低速度最快的决策树

构造决策树的基本思想：

1.  **随着树深度的增加，节点的熵迅速地降低。**
2.  **熵降低的速度（引入信息增益和信息增益比的概念）越快越好，以便得到一棵高度最矮的决策树**

[-]: https://zhuanlan.zhihu.com/p/74345351
[Bagging_Boosting_ - _ -]: https://www.cnblogs.com/onemorepoint/p/9264782.html
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c506e66cccb642dd8fd193ff0b793d44.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3c4767f2cf84495d8a01f9f6ed2a2446.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/14bb81f579684cb2b2b0b300475c4603.png
[e78068f4fd214362ba3ae936170a6893.png]: https://img-blog.csdnimg.cn/e78068f4fd214362ba3ae936170a6893.png
[equation_tex_X]: https://www.zhihu.com/equation?tex=X
[equation_tex_i]: https://www.zhihu.com/equation?tex=i
[equation_tex_n]: https://www.zhihu.com/equation?tex=n
[equation_tex_P]: https://www.zhihu.com/equation?tex=P
[equation_tex_log]: https://www.zhihu.com/equation?tex=log
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fe9bfb7198694440be89be18eddd2253.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/f4ae0f70c0cb4b338df22b28837d7d0a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/23829784234d4119a1305db9f659430f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_18_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/36c72aa0e8314cc782a042bd62b11f39.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/1dd14413e2754e998f1bc3ea873e47e7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/584fdc88446f4788a127e04503dd1bd8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAWmhhbmdKaVF1bi4_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/35651df3b58f4645a1c73fa76a3debf4.png