决策树理论--Decision tree

电玩女神 2022-05-24 09:25 147阅读 0赞

决策树面试被提及的题目：

1、决策树的原理：

从根结点开始，对实例的某一特征进行测试，根据测试的结果，将实例分配到其子结点；每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。

2、决策树的过程（步骤）：

决策树学习通常包括3个步骤：特征选择、决策树的生成和树的剪枝。

附：决策树的选择特征包括哪些，和各自的优缺点：

信息增益，信息增益比，基尼系数

3、决策树的终止条件：

节点中的样本个数小于预定的阈值，或样本集的基尼指数小于预定值，或者没有更多的特征；

4、决策树如何防止过拟合：

树的剪枝；

5、决策树的生成：

经典的有：ID3的生成算法、C4.5的生成算法、

1）ID3的生成算法

思路：ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可选为止。最后得到一个决策树。

算法如下：

输入：训练数据集D，特征集A，阈值e

SS：决策树T

（1）若D所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类的标记，返回T；

（2）若A =空，则 T为单结点树，并将D中实例最大的类Ck作为该结点的类标记，返回T；

（3） 否则，按照信息增益算法计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；

（4）如果银的信息增益小于阈值e，则置T为单节点树，并将D中实例数最大类Ck作为该节点的类标记，返回T；

（5）否则，对Ag的每一个可能取值ai，依Ag = ai 将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由结点以其子节点构成树T，返回T；

（6）对第我个结点，以D为训练集，以A-\{Ag\}为特征集，递归地调用1~5    ，得到子树Ti，返回Ti

2）C4.5的生成算法：

思路：C4.5与ID3算法相似，    C4.5    算法对ID3算法进行了改进，C4.5在生成的过程中，用信息增益比来选择特征。

1，为什么选择信息增益比？

以信息增益作为划分训练数据集的特征，存在偏向于选择值较多的特征的问题，使用信息增益比可以对这一问题进行校正。具体是再信息增益除以关于某个特征的熵

6，决策树的剪枝：

具体地，剪枝从已生成的树山剪掉一些子树或叶结点，并将其根结点或父节点作为新的叶节点，从而简化树模型。

决策树剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

算法思想：

输入：生成算法产生的整个树T，参数a；

输出：修剪后子树Ta；

（1）计算每个结点的jingyansha经验熵

（2）递归地从树的叶结点先杀向上回缩。

设一组叶节点回缩到其父节点之前与之后的整体树分别为Ta 和 Tb，其对应的损失函数值分别为Ca(Ta) 与Ca(Tb)，如果Ca(Ta) <= Ca(Tb),则进行剪枝，即将父节点变为新的叶节点。

（3）返回(2),直到不能继续为止，得到损失函数最小的子树Ta。

发表评论取消回复

表情：

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

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

相关阅读

相关监督学习算法中梯度提升决策树（Gradient Boosting Decision Trees）

梯度提升决策树（Gradient Boosting Decision Trees，简称GBDT）是一种监督学习算法，它是以决策树为基础分类器的集成学习方法。 GBDT通过迭代地

分手后的思念是犯贱/ 2024年03月24日 22:29/ 0 赞/ 18 阅读

相关 Python遇见机器学习 ---- 决策树 Decision Tree

综述 > “独木难成林” 本文采用编译器：jupyter 决策树 (decision tree) 是一类常见的机器学习方法，顾名思义，决策树是基于树结构来进行决策的

末蓝、/ 2024年02月19日 19:37/ 0 赞/ 42 阅读

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

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

叁歲伎倆/ 2023年10月04日 21:51/ 0 赞/ 44 阅读

相关决策树(decision tree)——(1)生成与度量指标

\\注：本博客为李航《统计学习方法》与周志华《机器学习》读书笔记，虽然有一些自己的理解，但是其中仍然有大量文字摘自李老师和周老师的书籍内容。决策树(decision tr

野性酷女/ 2023年09月29日 10:45/ 0 赞/ 98 阅读

相关【深度学习】模式识别技术探索之决策树（Decision tree）

【深度学习】模式识别技术探索之决策树（Decision tree） ![在这里插入图片描述][resize_m_lfit_w_962_pic_center] 文

女爷i/ 2022年10月06日 00:58/ 0 赞/ 129 阅读

相关机器学习经典算法详解及Python实现–决策树（Decision Tree）

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树

谁践踏了优雅/ 2022年09月21日 15:23/ 0 赞/ 259 阅读

相关机器学习之决策树（Decision Tree）及其Python代码实现

> 　决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点

约定不等于承诺〃/ 2022年07月12日 02:59/ 0 赞/ 424 阅读

相关决策树理论--Decision tree

决策树面试被提及的题目： 1、决策树的原理：从根结点开始，对实例的某一特征进行测试，根据测试的结果，将实例分配到其子结点；每一个子结点对应着该特征的一个取

电玩女神/ 2022年05月24日 09:25/ 0 赞/ 148 阅读

相关机器学习算法系列(3)--决策树(decision-tree)

本文转载自： [decision tree|endymecy][decision tree_endymecy] 一、决策树理论 1.1 什么是决策树所谓决策

小灰灰/ 2022年05月17日 10:41/ 0 赞/ 162 阅读

相关分类算法之决策树(Decision tree)

决策树引导通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：女儿：多大年纪了？母亲：26。

左手的ㄟ右手/ 2021年09月13日 23:24/ 0 赞/ 321 阅读