Hunt' s Algorithm| 学习笔记

简介: 快速学习 Hunt' s Algorithm。

开发者学堂课程【高校精品课-北京理工大学-数据仓库与数据挖掘(上):Hunt' s Algorithm】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/921/detail/15642


Hunt' s Algorithm

 

hunt 算法

image.png

在决策树模型构建中,我们需要使用到有标记的数据对决策树模型进行训练,得到训练好的决策树模型,但是我们根据训练集是可以得到很多棵决策树模型的。决策树模型的数量非常巨大,我们不可能列出所有的决策树模型并选择最优的决策数。

一般我们采用的策略是采用贪心策略,在构建决策树模型的时候,使用局部最优策略去选择一个比较合适的属性测试条件,从而完成我们决策树的构建,Hunt 算法就是这一类策略的集中代表。后续决策树算法的 C4.5算法、ID3 算法和 cart 算法都是基于 hunt 算法改造而来的。

所以我们首先向大家介绍 Hunt 算法,用的算法构建决策树的过程是一个自顶向下递归、分而自知的过程。我们用 DT 代表录入到一个节点T上的数据。那如果 DT 中所有数据对象的类都是一致的,当前的T就是一个叶子节点。我们可以构建一个叶子节点器,然后把它标上所有数据对象的类标签。那如果 DT 所包含的数据对象有多个类别,我们的节点T就是一个中间节点,这时我们需要确定一个合理的属性测试条件。根据属性测试条件,我们把落入到节点器上的数据集合 DT 划分成为若干个更小的子集。我们迭代循环以上步骤,一直到满足我们的终结条件。

终结条件主要有三种情况,第一种情况就是落入到这个节点上的所有数据对象,它的类标签是一致的。第二种条件就是没有属性供我们选择去构造我们的属性测试条件。第三种情况就是我们训练集中的所有数据对象都已经被使用完。

我们通过一个例子向大家来介绍 hunt 算法构建决策树模型的过程。首先从根节点开始,我们所有的数据对象落入到根节点上,在根节点上我们确定一个合适的属性测试条件。比如这里我们选择了 home owner 作为我们的测试条件,将我们的数据集一分为二,其中在我们的划分中,我们的这样的一个分支,也就是我们的  home owner 取值为 yes 的时候,那么他的所有数据对象的集合都是一致的,那这时候我就可以为它构建一个叶子节点。

对于 home owner 取值为 no 的这一部分集合,它所包含数据对象的取值有多种情况,因此这个节点就是一个中间节点,在这个节点上,我们选择合适的属性测试条件,这个时候我们选择的是婚姻状态,根据婚姻状态,我们又将我们的数据对象集合划分成两个小的集合,那么其中一部分是他的婚姻状态为 single 和  divorce 的,那么另一部分是maried,在这两个集合中,我们会发现对于我们的婚姻状态是 maried 的情况下,那么它所包含的数据对象的类标签是一致的,我们就构造一个叶子节点被标上它的类标签,对于我们的婚姻状态是 divorce 和 single 的时候,我们发现这个集合中数据对象的类标签有多种情况,那我们就选择合适的属性测试条件将这样一个集合继续划分,一直到我们最后所有的集合中的数据对象的类标签都是一致的,那我们就完成了决策树的构建。

image.png

对于我们决策树构建过程中,其中一个重要的环节就是用来测试属性条件。对于不同属性,测试条件的表达形式是不一样的。

如果我们的属性是标称属性。由于标称属性,它的取值是离散的。那我们就可以根据标称属性的取值。将我们的集合划分为若干个小的子集。实现多路划分。当然我们也可以实现两路划分,我们以这样的一个 Mary state 这样的一个属性为例。它的取值有三种情况。

image.png

我们可以根据它的取值实现自然的三路划分,那如果想实现两路划分的时候,我们可以把它的取值进行划分,比如说我们可以把它的取值划分成为 Mary 的,Single divorce 的,Single divorce married,还有 single married 和 divorce 的。那么这种就是对标称属性的属性测试条件的表达。

我们再来看一下连续属性。对于连续属性,如果我们想实现多路划分,那我们就可以设置多个取值范围取值。取值范围的表达形式就是这样的。那么通过设置多个取值范围,我们可以得到多个子集。

对于联系属性,我们同样也可以实现二路划分,对于要实现二路划分,我们可以选择一个最佳的分裂值V,然后将这个属性分成 a 小于 V 和 a 大于等于V2个部分。

image.png

在我们刚才介绍的 hunt 算法中,我们对于落入到一个节点上的数据集合,他的属性测试条件是有多种选择的。那我们怎么样才能得到一个合理的属性测试条件,从而实现最佳的划分?

我们这里举一个例子,比如说我们这里有一个数据集,它是由20个数据对象主。那我们怎么样去选择合理的属性测试条件,对这个数据集进行划分?

在一般的决策树算法中,我们是通过贪心策略用来评估这个属性测试条件分裂之后各个节点的纯度。如果节点的纯度越高,那么我们认为这样的一个属性测试条件是比较理想的,得到的划分是比较好的。那什么是节点的纯度?

image.png

节点的纯度就指的是这个节点中数据对象它的类的倾斜性。如果一个节点中所有的数据对象都是一个类别,那么它的纯度就最高。我们下面向大家通过举例介绍这样的一个数据节点的纯度,比如说我们这里有两个节点。

这两个节点中,它的数据对象的个数都是十个。其中第一个节点,它的 C0 类别的数据对象有五个,C1 类别的数据对象有五个,那么对于这样的一种节点,它的纯度是非常低的,因为 C0 和 C1 出现的概率是一样的。但是对于第二个节点,我们可以看一下,同样是十个数据对象,其中有九个数据对象是属于  C0 类别,只有一个数据对象属于 C1 类别,也就是在这个节点中,大部分的数据对象都是属于 C0 类别的,那么我们认为这个节点它的纯度就比较高。

那么在决策树模型中,我们主要是通过设定评估节点纯度的方法来判断我们的属性测试题是否合理。

相关文章
|
开发工具 C++ git
《人生苦短,我用python·三》pybind11简单使用
《人生苦短,我用python·三》pybind11简单使用
2467 0
|
人工智能 安全 中间件
阿里云 AI 中间件重磅发布,打通 AI 应用落地“最后一公里”
9 月 26 日,2025 云栖大会 AI 中间件:AI 时代的中间件技术演进与创新实践论坛上,阿里云智能集团资深技术专家林清山发表主题演讲《未来已来:下一代 AI 中间件重磅发布,解锁 AI 应用架构新范式》,重磅发布阿里云 AI 中间件,提供面向分布式多 Agent 架构的基座,包括:AgentScope-Java(兼容 Spring AI Alibaba 生态),AI MQ(基于Apache RocketMQ 的 AI 能力升级),AI 网关 Higress,AI 注册与配置中心 Nacos,以及覆盖模型与算力的 AI 可观测体系。
2175 95
|
9月前
|
机器学习/深度学习 人工智能 编解码
大模型应用:CLIP 模型全维度解析:理解理论基础强化基础范例.16
CLIP是OpenAI提出的跨模态模型,通过对比学习将图像与文本映射至统一语义空间,实现零样本图文对齐。无需微调即可完成图像分类、图文检索等任务,显著降低标注成本,成为多模态AI的核心基础。
3569 21
|
算法 JavaScript 数据可视化
基于leaflet-velocity的二维动态风场展示
本文讲解了leaflet-velocity插件,并利用插件进行了模拟的动态风场、洋流等信息的综合展示,让读者掌握集成方式。
2395 0
基于leaflet-velocity的二维动态风场展示
|
存储 持续交付 虚拟化
|
区块链 Python
最详细Python打包exe教程,并修改图标,只需30秒
最详细Python打包exe教程,并修改图标,只需30秒
2456 4
最详细Python打包exe教程,并修改图标,只需30秒
|
算法 Python
群智能算法:【WOA】鲸鱼优化算法详细解读
本文详细解读了鲸鱼优化算法(WOA),这是一种受鲸鱼捕食行为启发的新兴群体智能优化算法,具有强大的全局搜索能力和快速收敛速度。文章分为五个部分,分别介绍了引言、算法原理、主要步骤、特点及Python代码实现。通过模拟鲸鱼的捕食行为,该算法能够在复杂的优化问题中找到全局最优解。
|
机器学习/深度学习 算法
【机器学习】揭秘GBDT:梯度提升决策树
【机器学习】揭秘GBDT:梯度提升决策树
1230 0
|
机器学习/深度学习 数据可视化 Serverless
4种SVM主要核函数及相关参数的比较
本文将用数据可视化的方法解释4种支持向量机核函数和参数的区别
839 1