【机器学习】决策树算法理论：算法原理、信息熵、信息增益、预剪枝、后剪枝、算法选择

淩亂°似流年 2024-02-18 10:33 44阅读 0赞

### **1. 决策树概念** ###

**通过不断的划分条件来进行分类**，决策树最关键的是**找出那些对结果影响最大的条件，放到前面**。

我举个列子来帮助大家理解，我现在给我女儿介绍了一个相亲对象，她根据下面这张决策树图来进行选择。比如年龄是女儿择偶更看中的，那就该把年龄这个因素放在最前面，这样可以节省查找次数。收入高的话就去见，中等的话还要考虑工作怎么样。

![0a10d3f214354cb4997913a3b7c2801e.png][]

决策树通过历史数据，找出数据集中对结果影响最大的特征，再找第二个影响最大的特征。若新来一个数，只要根据我们已经建立起的决策树进行归类即可。

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

### **2. 决策树的信息熵** ###

用来表示随机数据不确定性的度量，**信息熵越大，表示这组数据越不稳定**，而信息熵越小，则数据越稳定、越接近、越类似。

#####  **信息熵公式：**H(x)=−∑ni=1P(i)∗logP(i)2 **代表某一个特征中每一个值出现的概率**  上个例子中的年龄的基尼系数是：**Gini(年龄) = 1 – (5/15)^2 - (5/15)^2 - (5/15)^2**  **在建立决策树时，基尼系数越小的，就把它放在最前面**。 #####

### **5. 预剪枝和后剪枝** ###

**树的层级和叶子节点不能过于复杂**，如果过于复杂，会导致**过拟合现象**（过拟合：训练时得分很高，测试时得分很低）。预剪枝和后剪枝都是为了防止决策树太复杂的手段

#### **5.1 预剪枝** ####

在决策树的建立过程中**不断调节来达到最优**，可以调节的条件有：

**（1）****树的深度：**在决策树建立过程中，发现深度超过指定的值，那么就不再分了。

**（2）****叶子节点个数：**在决策树建立过程中，发现叶子节点个数超过指定的值，那么就不再分了。

**（3）****叶子节点样本数：**如果某个叶子结点的个数已经低于指定的值，那么就不再分了。

**（4）信息增益量或Gini系数：**计算信息增益量或Gini系数，如果小于指定的值，那就不再分了。

**优点：**预剪枝可以有效**降低过拟合现象**，在决策树建立过程中进行调节，因此显著减少了训练时间和测试时间；**预剪枝效率比后剪枝高**。

**缺点：**预剪枝是通过限制一些建树的条件来实现的，这种方式**容易导致欠拟合现象**：模型训练的不够好。

#### **5.2 后剪枝** ####

在决策树建立完成之后再进行的，根据以下公式：

##### **C = gini(或信息增益)\*sample(样本数) + a\*叶子节点个数** #####

**C表示损失**，C越大，损失越多。**通过剪枝前后的损失对比，选择损失小的值，考虑是否剪枝。**

a是自己调节的，**a越大，叶子节点个数越多，损失越大**。因此a值越大，偏向于叶子节点少的，a越小，偏向于叶子节点多的。

**优点：**通常比预剪枝保留更多的分支，因此欠拟合风险比预剪枝要小。

**缺点：**但因为后剪枝是再数建立完成之后再自底向上对所有非叶子节点进行注意考察，因此训练时间开销比预剪枝要大。

[0a10d3f214354cb4997913a3b7c2801e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/8e4cda885af948f19bd56620373c43e3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，44人围观）

还没有评论，来说两句吧...

相关阅读

相关机器学习决策树算法cart剪枝

目录 1 为什么要剪枝 2 常用的减枝方法 2.1 预剪枝 2.2 后剪枝 3 小结 -------------------

系统管理员/ 2024年04月03日 09:12/ 0 赞/ 83 阅读

相关 educoder机器学习-实验四-编程实现基于信息增益进行划分选择的决策树算法

> 这是educoder平台，机器学习-实验四-编程实现基于信息增益进行划分选择的决策树算法的代码详解与解决过程详解，创造不易，请大家点点赞，收藏藏！目录 1.导包加载

梦里梦外;/ 2023年10月11日 19:33/ 0 赞/ 31 阅读

相关决策树基本算法及其剪枝优化

1、信息论（1）比特化假设存在一组随机变量X，各个值出现的概率关系为：P(X=A)=1/4，P(X=B)=1/4，P(X=C)=1/4，P(X=D)=1/4。现在

傷城~/ 2023年07月17日 12:48/ 0 赞/ 77 阅读

相关信息熵、信息增益

关于信息熵、信息增益的一些思考 1.为什么信息熵越大，蕴含的信息量越多？拿二分类问题来说，首先信息熵的公式是 Ent(D) = -(p\log\_2( p)+(

客官°小女子只卖身不卖艺/ 2022年12月29日 15:26/ 0 赞/ 208 阅读

相关信息增益、信息增益率、gini、特征选择、决策树

先简单介绍一下概念熵：表示随机变量的不确定性。条件熵：在一个条件下，随机变量的不确定性。信息增益：熵 - 条件熵。在一个条件下，信息不确定性减少的程度

浅浅的花香味﹌/ 2022年06月16日 03:52/ 0 赞/ 886 阅读

相关【机器学习】决策树算法整理

决策树决策树是一种分类和回归的基本模型，可从三个角度来理解它，即：一棵树 if-then规则的集合，该集合是决策树上的所有从根节点到叶节点的路径的集合

清疚/ 2022年06月03日 02:36/ 0 赞/ 641 阅读

相关机器学习算法——决策树

搬运工：原理：[https://blog.csdn.net/liqiutuoyuan/article/details/77245738][https_blog.csdn.n

╰半夏微凉°/ 2022年05月26日 12:16/ 0 赞/ 310 阅读

相关机器学习之决策树熵&信息增量求解算法实现

此文不对理论做相关阐述,仅涉及代码实现: 1.熵计算公式: P为正例,Q为反例 Entropy(S) = -PLog2(P) - QLog2(Q); 2.信息增量计算:

浅浅的花香味﹌/ 2022年03月27日 05:14/ 0 赞/ 277 阅读

相关信息熵与信息增益

前言熵在机器学习中用的非常普遍，但这个又难以理解，经常忘记，写一篇博客记录一下，也方便其他人学习了解。什么是熵一开始接触熵是大二的信息论，非常难的一门课，当

红太狼/ 2022年03月15日 16:07/ 0 赞/ 322 阅读

相关机器学习算法02 - 决策树

决策树 > ID3 & C4.5 & CART ![d02e69930c8cf00c93578536933ad07a.png][] ![5cfe1151f88befc

快来打我*/ 2022年01月23日 10:23/ 0 赞/ 339 阅读