机器学习决策树算法和分类原理 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=“活跃度”)


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


目录
相关文章
|
5月前
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty  敏感词
|
5月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
147 17
|
5月前
|
机器学习/深度学习 数据采集 人工智能
20分钟掌握机器学习算法指南
在短短20分钟内,从零开始理解主流机器学习算法的工作原理,掌握算法选择策略,并建立对神经网络的直观认识。本文用通俗易懂的语言和生动的比喻,帮助你告别算法选择的困惑,轻松踏入AI的大门。
|
5月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
128 7
|
4月前
|
机器学习/深度学习 算法 搜索推荐
决策树算法如何读懂你的购物心理?一文看懂背后的科学
"你为什么总能收到刚好符合需求的商品推荐?你有没有好奇过,为什么刚浏览过的商品就出现了折扣通知?
|
7月前
|
人工智能 算法 语音技术
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
清华大学与腾讯联合推出的Video-T1技术,通过测试时扩展(TTS)和Tree-of-Frames方法,显著提升视频生成的连贯性与文本匹配度,为影视制作、游戏开发等领域带来突破性解决方案。
208 4
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
|
6月前
|
机器学习/深度学习 存储 Kubernetes
【重磅发布】AllData数据中台核心功能:机器学习算法平台
杭州奥零数据科技有限公司成立于2023年,专注于数据中台业务,维护开源项目AllData并提供商业版解决方案。AllData提供数据集成、存储、开发、治理及BI展示等一站式服务,支持AI大模型应用,助力企业高效利用数据价值。
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
160 3
 算法系列之数据结构-Huffman树
|
7月前
|
机器学习/深度学习 人工智能 自然语言处理
AI训练师入行指南(三):机器学习算法和模型架构选择
从淘金到雕琢,将原始数据炼成智能珠宝!本文带您走进数字珠宝工坊,用算法工具打磨数据金砂。从基础的经典算法到精密的深度学习模型,结合电商、医疗、金融等场景实战,手把手教您选择合适工具,打造价值连城的智能应用。掌握AutoML改装套件与模型蒸馏术,让复杂问题迎刃而解。握紧算法刻刀,为数字世界雕刻文明!
228 6
|
8月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于机器学习的人脸识别算法matlab仿真,对比GRNN,PNN,DNN以及BP四种网络
本项目展示了人脸识别算法的运行效果(无水印),基于MATLAB2022A开发。核心程序包含详细中文注释及操作视频。理论部分介绍了广义回归神经网络(GRNN)、概率神经网络(PNN)、深度神经网络(DNN)和反向传播(BP)神经网络在人脸识别中的应用,涵盖各算法的结构特点与性能比较。

热门文章

最新文章