正文 

当前位置： 首页 > IT > java教程

决策树算法常见问题（面试相关）

smile-yan smile-yan     2023-03-09     394

关键词：

整理一下决策树常见问题。

0. 相关术语

  • 决策树（Decision Trees, DTs）
  • ID3
  • C4.5
  • CART
  • 信息熵
  • 信息增益
  • 信息增益率
  • 基尼系数

1. 简单描述什么是决策树算法

决策树算法是一种用于分类和回归的非参数化的监督学习方法。在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if-then的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

2. 决策树算法的分类

算法ID3C4.5CART
支持算法分类分类分类/回归
树结构多叉树多叉树二叉树
特征选择信息增益信息增益率基尼系数
均方差
连续值处理不支持支持支持
缺失值处理不支持支持支持
剪枝不支持支持支持

3. 决策树算法的优缺点

sklearn 决策树

优点：

  • 是一种白盒模型，易于理解和解释，支持可视化；。
  • 几乎不需要预处理；
  • 计算成本低。使用树（即预测数据）的成本与用于训练树的数据点的数量成对数关系；
  • 能够处理数字和分类数据；
  • 能够处理多输出问题；
  • 支持统计测试验证模型。这就有可能解释模型的可靠性。

缺点：

  • 容易过拟合；
  • 决策树可能不稳定，因为数据中的微小变化可能会导致生成完全不同的树。通过在集成算法中使用决策树，可以缓解此问题。
  • 分类样本数量不一致时，结果可能出现偏差。
  • 有些概念很难学习，因为决策树不容易表达它们。例如异或、奇偶校验或多路复用器问题。

4. 相关概念

4.1 信息熵（Entropy）

香农把信源所含有的信息量称为信息熵(Entropy)，是指数据分区 D D D 所含信息量的统计平均值。

对 D D D 中有 m m m 个元组分类的信息熵计算如下：

i n f o ( D ) = − ∑ i = 1 m p i log ⁡ 2 p i info(D) = - \\sum_i=1^m p_i \\log_2 p_i info(D)=−i=1∑m​pi​log2​pi​

其中 p i p_i pi​ 是指某事件发生的概率。

4.2 信息增益 --> ID3

信息熵增益是指一个特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。

I G ( Y ∣ X ) = I n f o ( Y ) − I n f o ( Y ∣ X ) IG(Y|X) = Info(Y) - Info(Y|X) IG(Y∣X)=Info(Y)−Info(Y∣X)

I n f o ( Y ∣ X ) Info(Y|X) Info(Y∣X) 表示条件熵，表示当 X X X 条件下 Y Y Y 的信息熵。

以信息增益作为特征选择依据的弊端：信息增益会偏向分支较多的特征。

4.3 信息增益率 --> C4.5

信息增益率能改善以上问题。

I G r a t i o = I G ( Y ∣ X ) I n f o ( X ) IG_ratio = \\fracIG(Y|X)Info(X) IGratio​=Info(X)IG(Y∣X)​

4.4 基尼系数 --> CART

基尼系数（Gini），也称基尼不纯度，来自经济学中的概念，用来衡量一个国家和地区的财富分配水平，在机器学习中，主要用于分类，推荐等算法。

Gini 系数的计算公式为：

G i n i ( D ) = 1 − ∑ i = 1 n p i 2 Gini(D) = 1-\\sum_i=1^n p_i^2 Gini(D)=1−i=1∑n​pi2​

Gini 用于特征选择时，

5. 三种决策树算法

5.1 ID3

参考博客 https://blog.csdn.net/choven_meng/article/details/82878018

ID3 算法的核心思想是：以 信息增益 度量属性选择，选择分裂后 信息增益最大 的属性进行分裂。

ID3 算法的缺点：

  • 不能对连续数据进行处理，只能通过连续数据离散化进行处理；
  • 采用信息增益进行数据分裂容易偏向取值较多的特征；
  • 缺失值不好处理。
  • 没有采用剪枝，决策树的结构可能过于复杂，出现过拟合。

C4.5

C4.5 算法的核心思想是：以 信息增益率 度量属性选择，选择分裂后 信息增益率最大 的属性进行分裂。

C4.5 在 ID3 的基础上的改进部分（4个问题一一对应）：

  • 将连续的特征离散化，使得 C4.5 能处理连续值；

  • 采用信息增益率作为度量标准；

  • 添加了对缺失值的处理方法。

  • 引入正则化系数进行初步的减枝，降低模型复杂度，降低过拟合可能性。

4.6 CART

CART，classification and regression tree，分类回归树。

CART 算法的 核心思想 是：以 基尼增长率 度量属性选择，选择 基尼增长率最大 的属性进行分裂。

分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近于真实值。

  • 当 CART 是分类树时，采用 GINI 值作为节点分裂的依据；
  • 当 CART 是回归树时，采用 样本的最小方差作为分裂依据。

在训练的过程中，

  • 当 CART 是分类树时，基尼系数最小化准则；
  • 当 CART 是回归树时，平方误差最小化准则。

回归方差计算公式为：

σ = ∑ ( x i − μ ) 2 \\sigma = \\sqrt\\sum (x_i-\\mu)^2 σ=∑(xi​−μ)2 ​

CART 算法主要分为两个步骤：

  • 将样本递归划分构建决策树。
  • 用验证数据进行剪枝。

5. 决策树的基本过程

决策树分类算法通常分为三个步骤：

  • 特征选择；
  • 决策树生成；
  • 决策树修剪。

构造好的决策树的关键在于如何选择好的逻辑判断或属性。

决策树相关算法的不同主要是纯度的计算方法不同（ID3 和 ID4.5，CART)。

5.1 特征选择

CSDN 博客

特征选择在于选取对训练数据具有分类能力的特征，可以提高决策树学习的效率。通常特征选择的准则是信息增益或信息增益率。

特征选择的划分依据：这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就应该选择这个特征。（将数据集划分为纯度更高，不确定性更小的子集的过程。)

5.2 决策树生成

5.3 决策树剪枝

决策树最容易出现过拟合，因而一般情况下需要进行剪枝，缩小树的规模，缓解过拟合。

两种基本的剪枝决策：

  • 预先剪枝：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。
  • 后剪枝：为一种拟合-化简的两阶段方法。首先生成与训练数据完成拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用一个测试数据集，如果存在某个叶子剪去后使用在测试集上的准确度或其他测度不降低，则剪去该叶子。

6. 决策树停止生长的条件

  1. 达到最大叶子节点数；
  2. 达到树的最大深度；
  3. 所有特征用完，无法继续分裂；
  4. 特征没有用完，达到不了分裂阈值或者分裂后叶子的样本数不满足特定条件。

7. 更多内容

其他内容将会继续更新添加。希望能够帮到需要的小伙伴们。

Smileyan
2021.10.24 22:22

机器学习算法之决策树

一.简介　　决策树的一个重要任务是理解数据中蕴含的知识信息。    决策树优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。    缺点：可能产生过... 查看详情

ml之监督学习算法之分类算法一————决策树算法

一、概述　　决策树的一个重要任务是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，在这些机器根据数据创建规则时，就是机器学习的过程。二、决策树的构造　　决策树：... 查看详情

决策树状态栏&相关数值栏

】决策树状态栏&相关数值栏【英文标题】：DecisionTreestatuscolumn&relatednumericalvaluecolumn【发布时间】：2019-08-1214:41:11【问题描述】：我的数据包括两列，其中一列明确显示功能的状态，另一列以数字形式显示相关值。如下所... 查看详情

关于机器学习中决策树的相关问题也谈随机森林

前言   决策树可能是对于相关样本进行分类示性最为直观的一种方法，使用决策树方法来演示分类的过程对于读者而言可能也是最简单的一种方式，我们可以称之为它是白箱算法，所谓白箱就是直接可以对其进行观察... 查看详情

学习笔记|机器学习决策树

...值处理五、总结通过这篇博客，您将收获如下知识：熟悉决策树相关的基础知识：自信息、信息熵与条件熵，信息增益和增益率，Gini值和Gini指数。熟悉决策树算法的关键原理，模型、策略与优化算法。了解决策树中过拟合问题... 查看详情

学习笔记|机器学习决策树

...值处理五、总结通过这篇博客，您将收获如下知识：熟悉决策树相关的基础知识：自信息、信息熵与条件熵，信息增益和增益率，Gini值和Gini指数。熟悉决策树算法的关键原理，模型、策略与优化算法。了解决策树中过拟合问题... 查看详情

第三章决策树

1.经常使用决策树处理分类问题，决策树也是最经常使用的数据挖掘算法。2.kNN可以完成很多分类任务，最大的缺点是无法给出数据的内在含义，决策树的优势在于数据形式容易理解。3.1决策树的构造决策树的优点：计算复杂度... 查看详情

机器学习之决策树与随机森林模型

...毅雄 导语 本文用容易理解的语言和例子来解释了决策树三种常见的算法及其优劣、随机森林的含义，相信能帮助初学者真正地理解相关知识。决策树引言决策树，是机器学习中一种非常常见的分类方法，也可以说是所有... 查看详情

r语言︱决策树族——随机森林算法

R语言︱决策树族——随机森林算法笔者寄语：有一篇《有监督学习选择深度学习还是随机森林或支持向量机?》（作者Bio：SebastianRaschka）中提到，在日常机器学习工作或学习中，当我们遇到有监督学习相关问题时，不妨考虑下先... 查看详情

机器学习算法学习02：决策树的学习以及应用决策树解决cora数据集论文分类问题(代码片段)

机器学习算法学习02：决策树的学习以及应用决策树解决Cora数据集论文分类问题文章目录机器学习算法学习02：决策树的学习以及应用决策树解决Cora数据集论文分类问题1.前言2.算法分析2.1算法概述2.2算法优化3.算法代码3.... 查看详情

id3算法实现的决策树生成

.../p/easytry/git/tree/master/src/com/ml目录结构decision目录下主要为决策树的相关接口及entity，id3目录下为实现类以及相关测试测试测试训练数据 训练结果 解释一下，如下图  测试数据测试结果  查看详情

决策树--id3算法小结

...eDichotomiser3迭代二叉树3代)，是一个由RossQuinlan发明的用于决策树的算法；简单理论是越是小型的决策树越优于大的决策树。算法归纳：1、使用所有没有使用的属性并计算与之相关的样本熵值；2、选取其中熵值最小的属性3、生成... 查看详情

决策树之c4.5算法

...3中的相关数学公式及概念还有些迷惑，欢迎移步至《决策树之ID3算法》。版权说明著作权归作者所有。商业转载请联系作者获得授权ÿ 查看详情

决策树算法

文章目录决策树1.决策树的整体理解2.决策树的构造2.1决策树----熵2.2构造决策树3.C4.5算法4.决策树剪枝决策树1.决策树的整体理解​决策树，顾名思义，首先它是一棵树，其次，这棵树可以起到决策的作用（即... 查看详情

ml:决策树算法

...sp;在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(DecisionTreeModel)和朴素贝叶斯模型（NaiveBayesianModel，NBC）。决策树模型通过构造树来解决分类问题。首先利用训练数据集来构造一棵决策树，一旦树建立起来，... 查看详情

实验四决策树算法及应用(代码片段)

博客班级机器学习作业要求实验四作业目标决策树算法及应用学号3180701124一、【实验目的】理解决策树算法原理，掌握决策树算法框架；理解决策树学习算法的特征选择、树的生成和树的剪枝；能根据不同的数据类型，选择不... 查看详情

机器学习算法实践：决策树(decisiontree)（转载）

...现一遍以便加深印象。本文为这系列博客的第一篇，关于决策树(DecisionTree)的算法实现，文中我将对决策树种涉及到的　　算法进行总结并附上自己相关的实现代码。所有算法代码以及用于相应模型的训练的数据都会放到GitHub上(... 查看详情

提升算法

...采用加法模型(即基函数的线性组合)与前向分布算法，以决策树为基函数的提升方法称为提升树，对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树，其根据特征x<v与x>v将根结点直接连接两个叶结点，以作为... 查看详情