机器学习经典算法——决策树（Decision Tree）

叁歲伎倆 2023-10-04 21:51 38阅读 0赞

#### 文章目录 ####

*  决策树的基本原理
 *  决策树的三要素
 *  决策树学习基本算法
 *  熵与信息增益
 *  决策树的剪枝方法
 *   *  预剪枝
     *  后剪枝

## 决策树的基本原理 ##

决策树是⼀种分⽽治之的决策过程。⼀个困难的预测问题，通过树的分⽀节点，被划分成两个或多个较为简单的⼦集，从结构上划分为不同的⼦问题。将依规则分割数据集的过程不断递归下去。随着树的深度不断增加，分⽀节点的⼦集越来越⼩，所需要提的问题数也逐渐简化。当分⽀节点的深度或者问题的简单程度满⾜⼀定的停⽌规则时, 该分⽀节点会停⽌分裂。

决策树是一种自上而下，对样本数据进行树形分类的过程，由结点和有向边组成。结点分为内部节点和叶结点，其中内部结点表示一个特征或属性，叶结点表示类别。从顶部根节点开始，所有样本聚在一起。经过根结点的划分，样本别分到不同的子结点中。在根据子结点的特征进一步划分，直至所有样本都被归到某一个类别（即叶结点）中。

*  优点：不需要任何领域知识或参数假设；适合⾼维数据；短时间内处理⼤量数据，得到可⾏且效果较好的结果；能够同时处理数据型和常规性属性。
 *  缺点：对于各类别样本数量不⼀致数据，信息增益偏向于那些具有更多数值的特征；易于过拟合；忽略属性之间的相关性；不⽀持在线学习。

## 决策树的三要素 ##

一般而言，决策树的生成包括**特征选择**、**树的构造**、**树的剪枝**三个过程。

1.  特征选择：从训练数据中众多的特征中选择⼀个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准，从⽽衍⽣出不同的决策树算法。
2.  决策树⽣成：根据选择的特征评估标准，从上⾄下递归地⽣成⼦节点，直到数据集不可分则决策树停⽌⽣长。树结构来说，递归结构是最容易理解的⽅式。
3.  剪枝：决策树容易过拟合，⼀般来需要剪枝，缩⼩树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

## 决策树学习基本算法 ##

![在这里插入图片描述][dd19cee6b8b0475c8ac25fa47c9ef3a2.png]

## 熵与信息增益 ##

**熵**

熵可以表⽰样本集合的不确定性，熵越⼤，样本的不确定性就越⼤。

假设随机变量X的可能取值有x1,x2, …, xn，对于每⼀个可能的取值xi，其概率为:  
![在这里插入图片描述][88e9ec17d90d491994857cec9681a7bb.png]  
随机变量的熵为：  
![在这里插入图片描述][7f4c5d7c3abf41dcbc67b8a277d14ef2.png]  
对于样本集合，假设样本有k个类别，每个类别的概率为![在这里插入图片描述][a56d7afcc947422f8251347c9046c553.png]其中|Ck|为类别为k的样本个数， |D| 为样本总数。样本集合D的熵为：  
![在这里插入图片描述][1b75e4c3eed449318d8f4d410c314c9c.png]

**信息增益**  
假设划分前样本集合D的熵为H(D)。使⽤某个特征A划分数据集D，计算划分后的数据⼦  
集的熵为H(D|A)，则A特征的信息增益为：  
![在这里插入图片描述][f8a695c2fccf4b76922b95979436e6be.png]

## 决策树的剪枝方法 ##

剪枝处理是决策树学习算法⽤来解决过拟合问题的⼀种办法。通过对决策树进行剪枝，剪掉一些枝叶，提升模型的泛化能力。决策树的剪枝通常有两种方法：预剪枝（pre-pruning）和后剪枝（post-pruning）。

*  预剪枝：在生成决策树的过程中提前停止树的增长；
 *  后剪枝：⽣成决策树以后，再⾃下⽽上对⾮叶结点进⾏剪枝，得到简化版的剪枝决策树。

### 预剪枝 ###

预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类别的样本同时存于结点中，按照多数投票的原则判断该结点所属类别。预剪枝对于何时停止决策树的生长有以下几种方法。

1.  当树到达一定深度的时候，停止树的生长。
2.  当到达当前结点的样本数量小于某个阈值的时候，停止树的生长。
3.  计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展。

预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题。但预剪枝存在一定局限性，有欠拟合的风险，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能会有显著上升。

### 后剪枝 ###

后剪枝的核心思想是让算法生成一棵完全生 长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝。

相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。

常见的后剪枝方法包括：错误率降低剪枝( Reduced Error Pruning,REP)、悲观剪枝( Pessimistic Error Pruning, PEP) 、代价复杂度剪枝( Cost Complexity Pruning, CCP )、最小误差剪枝(MinimumEror Pruning, MEP )、CVP(Critical Value Pruning)、OPP (OpttimalPruning)等

[dd19cee6b8b0475c8ac25fa47c9ef3a2.png]: https://img-blog.csdnimg.cn/dd19cee6b8b0475c8ac25fa47c9ef3a2.png
[88e9ec17d90d491994857cec9681a7bb.png]: https://img-blog.csdnimg.cn/88e9ec17d90d491994857cec9681a7bb.png
[7f4c5d7c3abf41dcbc67b8a277d14ef2.png]: https://img-blog.csdnimg.cn/7f4c5d7c3abf41dcbc67b8a277d14ef2.png
[a56d7afcc947422f8251347c9046c553.png]: https://img-blog.csdnimg.cn/a56d7afcc947422f8251347c9046c553.png
[1b75e4c3eed449318d8f4d410c314c9c.png]: https://img-blog.csdnimg.cn/1b75e4c3eed449318d8f4d410c314c9c.png
[f8a695c2fccf4b76922b95979436e6be.png]: https://img-blog.csdnimg.cn/f8a695c2fccf4b76922b95979436e6be.png