决策树学习笔记（ID3、C4.5、CART）

小灰灰 2023-03-03 08:59 1阅读 0赞

# 决策树的基本流程 #

参考[决策树（上）——ID3、C4.5、CART（非常详细）][ID3_C4.5_CART]  
决策树（亦称判定树）是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。

其基本流程遵循简单的“分而治之”（divide-and-conquer）策略，如下图所示。

![决策树的基本流程][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70] ![决策树分析][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 1]

根据上面的分析可知，必须解决三个问题，**划分的选择、连续与缺失值、剪枝处理**。

1.  由第8行可知我们必须选择一最优化分属性，常用的**划分指标**有三种（信息增益、增益率、基尼指数），对应三种算法（ID3,C4.5,CART）。
2.  当我们进行划分时，遇到属性值是连续值或者缺失值的时候我们需要**连续值与缺失值**处理技术。
3.  当决策树建好之后，预测问题便成了树的查找问题，因此我们希望建立树的高度低的决策树，更重的要是，决策树的分支过多会导致“过拟合”，因此有必要进行**剪枝处理**，基本的剪枝处理有预剪枝和后剪枝

传统的决策树的划分是基于单一属性的，我们用多个属性的线性组合进行划分可以产生更加复杂的决策树，这种类型的决策树称为**多变量决策树**。

# 划分的选择 #

一般而言，随着划分的不断进行，我们希望决策树的分支点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

## 1. 信息增益 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 2]

### 优缺点 ###

\*\*信息增益准则最可取值数目多的属性有所偏好 \*\*

## 2. 增益率 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 3]

### 优缺点 ###

**1. 增益率准则对可取值数目少的属性有所偏好**

**2. 增益率准则倾向于不平衡的分裂，其中一个子集比其他小得多**

**C4.5并不是直接选取增益率大的作为候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。**

## 3. 基尼指数 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 4]

### 优缺点 ###

**1. 偏向于多值属性**

**2. 当类数目较大时，计算困难**

**3. 倾向于导致大小相等的分区和纯度**

# 三种算法 #

## 1. ID3 ##

ID3 算法是建立在奥卡姆剃刀原理（如无必要，勿增实体）的基础上：越是小型的决策树越优于大的决策树。

### 1.1 思想 ###

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

1.  初始化特征集合和数据集合；
2.  计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3.  更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4.  重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

### 1.2 划分标准 ###

ID3 使用的分类标准是信息增益

### 1.3 缺点 ###

*  ID3 没有剪枝策略，容易过拟合；
 *  信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
 *  只能用于处理离散分布的特征；
 *  没有考虑缺失值。

## 2. C4.5 ##

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。**C4.5并不是直接选取增益率大的作为候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。**

### 2.1 思想 ###

C4.5 相对于 ID3 的缺点对应有以下改进方式：

*  引入悲观剪枝策略进行后剪枝；
 *  引入信息增益率作为划分标准；
 *  将**连续特征离散化**，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其**排序**并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
 *  对于**缺失值的处理**可以分为两个子问题：
 *  问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
 *  问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
 *  针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
 *  针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值（乘以每一属性值的样本所占样本集的比重），其实也就是以不同概率划分到不同节点中。

### 2.2 划分标准 ###

利用信息增益率可以克服信息增益的缺点。**C4.5并不是直接选取增益率大的作为候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。**

### 2.3 剪枝策略 ###

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

**2.3.1 预剪枝**

**主要思想：在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分，并标记为叶节点**

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

*  节点内数据样本低于某一阈值；
 *  所有节点特征都已分裂；
 *  节点划分前准确率比划分后准确率高。  
    ![在这里插入图片描述][20200730213206201.png]

**2.3.2 后剪枝**

**主要思想： 后剪枝是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点**

C4.5 采用的**悲观剪枝方法**，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 5]

### 2.4 缺点 ###

*  剪枝策略可以再优化；
 *  C4.5 用的是多叉树，用二叉树效率更高；
 *  C4.5 只能用于分类；
 *  C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
 *  C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 6]

1.  [CART 树怎么进行剪枝?][CART]
2.  [决策树（上）——ID3、C4.5、CART（非常详细）][ID3_C4.5_CART]

[ID3_C4.5_CART]: https://zhuanlan.zhihu.com/p/85731206
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200730212829860.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 1]: /images/20230208/7330c595b3ba44bb93d7c7bc2ecfa8a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 2]: /images/20230208/dcceefaeee1947d09fad8bcd5b0bad08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 3]: /images/20230208/1a6b83f66bdb460c8399096107b89f8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 4]: /images/20230208/af92dca4b3b64707811887b96e761ac4.png
[20200730213206201.png]: /images/20230208/51d4d4dc6fd74e639b472feb965c90cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 5]: /images/20230208/79d03ad8159047e999d3c87b7637d4d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Rhcml1c19UYW56_size_16_color_FFFFFF_t_70 6]: /images/20230208/d37dca86522648aab961f21901721def.png
[CART]: https://www.zhihu.com/question/22697086