机器学习决策树算法和分类原理 1

简介: 机器学习决策树算法和分类原理

1 决策树算法简介

决策树思想的来源非常朴素,程序设计中的条件分支结构就是if-else结构,最早的决策树就是利用这类结构分割数据的一种分类学习方法

决策树:

  • 是一种树形结构,本质是一颗由多个判断节点组成的树
  • 其中每个内部节点表示一个属性上的判断,
  • 每个分支代表一个判断结果的输出,
  • 最后每个叶节点代表一种分类结果

怎么理解这句话?通过一个对话例子

想一想这个女生为什么把年龄放在最上面判断!!!!!!!!!

上面案例是女生通过定性的主观意识,把年龄放到最上面,那么如果需要对这一过程进行量化,该如何处理呢?

此时需要用到信息论中的知识:信息熵,信息增益

  • 决策树定义:
  • 一种树形结构
  • 本质是一颗由多个判断节点组成的树

2 决策树分类原理

2.1 熵

2.1.1 概念

物理学上,熵 Entropy 是“混乱”程度的量度。

系统越有序,熵值越低;系统越混乱或者分散,熵值越高

1948年香农提出了信息熵(Entropy)的概念。


  • 信息理论

1、从信息的完整性上进行的描述:

系统的有序状态一致时,数据越集中的地方熵值越小,数据越分散的地方熵值越大。

2、从信息的有序性上进行的描述:

数据量一致时系统越有序,熵值越低;系统越混乱或者分散,熵值越高

“信息熵” (information entropy)是度量样本集合纯度最常用的一种指标。

假定当前样本集合 D 中第 k 类样本所占的比例为 pk (k = 1, 2,. . . , |y|) ,

p_k=\frac{C^k}{D}p**k=DCk,

其中:D为样本的所有数量,Ck 为第k类样本的数量。

则 D的信息熵定义为((log是以2为底,lg是以10为底):

其中:Ent(D) 的值越小,则 D 的纯度越高.

2.1.2 案例

课堂案例:
假设我们没有看世界杯的比赛,但是想知道哪支球队会是冠军,
我们只能猜测某支球队是或不是冠军,然后观众用对或不对来回答,
我们想要猜测次数尽可能少,你会用什么方法?
答案:
二分法:
假如有 16 支球队,分别编号,先问是否在 1-8 之间,如果是就继续问是否在 1-4 之间,
以此类推,直到最后判断出冠军球队是哪支。
如果球队数量是 16,我们需要问 4 次来得到最后的答案。那么世界冠军这条消息的信息熵就是 4。
那么信息熵等于4,是如何进行计算的呢?
Ent(D) = -(p1 * logp1 + p2 * logp2 + ... + p16 * logp16),
其中 p1, ..., p16 分别是这 16 支球队夺冠的概率。
当每支球队夺冠概率相等都是 1/16 的时:Ent(D) = -(16 * 1/16 * log1/16) = 4
每个事件概率相同时,熵最大,这件事越不确定。
随堂练习:
篮球比赛里,有4个球队 {A,B,C,D} ,获胜概率分别为{1/2, 1/4, 1/8, 1/8}
求Ent(D)

答案:

2.2 划分依据一 :信息增益

2.2.1 概念

信息增益:以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性,熵越大,样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏

信息增益 = entroy(前) - entroy(后)

注:信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度

  • 定义与公式

假定离散属性a有 V 个可能的取值:

假设离散属性性别有2(男,女)个可能的取值

若使用a来对样本集 D 进行划分,则会产生 V 个分支结点,

其中第v个分支结点包含了 D 中所有在属性a上取值为av的样本,记为Dv.

我们可根据前面给出的信息熵公式计算出Dv的信息熵,再考虑到不同的分支结点所包含的样本数不同,给分支结点赋予权重

即样本数越多的分支结点的影响越大,于是可计算出用属性a对样本集 D 进行划分所获得的"信息增益" (information gain)

其中:

特征a对训练数据集D的信息增益Gain(D,a),定义为**集合D的信息熵Ent(D)给定特征a条件下D的信息条件Ent(D|a)**之差,即公式为:

公式的详细解释:

信息熵的计算:

条件熵的计算:

其中:

Dv表示a属性中第v个分支节点包含的样本数

Ckv表示a属性中第v个分支节点包含的样本数中,第k个类别下包含的样本数

一般而言,信息增益越大,则意味着使用属性 a 来进行划分所获得的"纯度提升"越大。因此,我们可用信息增益来进行决策树的划分属性选择,著名的 ID3 决策树学习算法 [Quinlan, 1986] 就是以信息增益为准则来选择划分属性。

其中,ID3 名字中的 ID 是 Iterative Dichotomiser (迭代二分器)的简称

2.2.2 案例

如下图,第一列为论坛号码,第二列为性别,第三列为活跃度,最后一列用户是否流失。

我们要解决一个问题:性别和活跃度两个特征,哪个对用户流失影响更大

通过计算信息增益可以解决这个问题,统计上右表信息

其中Positive为正样本(已流失),Negative为负样本(未流失),下面的数值为不同划分下对应的人数。

可得到三个熵:

a.计算类别信息熵

整体熵:

b.计算性别属性的信息熵(a=“性别”)

c.计算性别的信息增益(a=“性别”)

b.计算活跃度属性的信息熵(a=“活跃度”)

c.计算活跃度的信息增益(a=“活跃度”)


**活跃度的信息增益比性别的信息增益大,也就是说,活跃度对用户流失的影响比性别大。**在做特征选择或者数据分析的时候,我们应该重点考察活跃度这个指标。


目录
相关文章
机器学习/深度学习 算法 自动驾驶
277 0
|
1月前
|
机器学习/深度学习 算法 搜索推荐
从零开始构建图注意力网络:GAT算法原理与数值实现详解
本文详细解析了图注意力网络(GAT)的算法原理和实现过程。GAT通过引入注意力机制解决了图卷积网络(GCN)中所有邻居节点贡献相等的局限性,让模型能够自动学习不同邻居的重要性权重。
252 0
从零开始构建图注意力网络:GAT算法原理与数值实现详解
|
2月前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
540 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
2月前
|
传感器 算法 定位技术
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
|
2月前
|
算法
离散粒子群算法(DPSO)的原理与MATLAB实现
离散粒子群算法(DPSO)的原理与MATLAB实现
128 0
|
3月前
|
机器学习/深度学习 分布式计算 Java
Java 大视界 -- Java 大数据机器学习模型在遥感图像土地利用分类中的优化与应用(199)
本文探讨了Java大数据与机器学习模型在遥感图像土地利用分类中的优化与应用。面对传统方法效率低、精度差的问题,结合Hadoop、Spark与深度学习框架,实现了高效、精准的分类。通过实际案例展示了Java在数据处理、模型融合与参数调优中的强大能力,推动遥感图像分类迈向新高度。
|
3月前
|
机器学习/深度学习 人工智能 编解码
AI视觉新突破:多角度理解3D世界的算法原理全解析
多视角条件扩散算法通过多张图片输入生成高质量3D模型,克服了单图建模背面细节缺失的问题。该技术模拟人类多角度观察方式,结合跨视图注意力机制与一致性损失优化,大幅提升几何精度与纹理保真度,成为AI 3D生成的重要突破。
286 0
|
3月前
|
算法 区块链 数据安全/隐私保护
加密算法:深度解析Ed25519原理
在 Solana 开发过程中,我一直对 Ed25519 加密算法 如何生成公钥、签名以及验证签名的机制感到困惑。为了弄清这一点,我查阅了大量相关资料,终于对其流程有了更清晰的理解。在此记录实现过程,方便日后查阅。
307 1
|
机器学习/深度学习 算法 搜索推荐
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
|
机器学习/深度学习 分布式计算 算法
大模型开发:你如何确定使用哪种机器学习算法?
在大型机器学习模型开发中,选择算法是关键。首先,明确问题类型(如回归、分类、聚类等)。其次,考虑数据规模、特征数量和类型、分布和结构,以判断适合的算法。再者,评估性能要求(准确性、速度、可解释性)和资源限制(计算资源、内存)。同时,利用领域知识和正则化来选择模型。最后,通过实验验证和模型比较进行优化。此过程涉及迭代和业务需求的技术权衡。
464 2

热门文章

最新文章