【机器学习笔记】7 KNN算法

距离度量

欧氏距离(Euclidean distance)

在这里插入图片描述
欧几里得度量(Euclidean Metric)(也称欧氏距离)是一个通常采用的距离定义,指在𝑚维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
在这里插入图片描述

曼哈顿距离(Manhattan distance)

在这里插入图片描述
想象你在城市道路里,要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直
线距离吗?显然不是,除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源, 曼哈顿距离也称为城市街区距离(City Block distance)
在这里插入图片描述

切比雪夫距离(Chebyshev distance)

在这里插入图片描述
二个点之间的距离定义是其各坐标数值差绝对值的最大值。国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格,因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距f6位置的切比雪夫距离。
在这里插入图片描述

闵可夫斯基距离(Minkowski distance)

在这里插入图片描述
𝑝取1或2时的闵氏距离是最为常用的
𝑝 = 2即为欧氏距离,
𝑝 = 1时则为曼哈顿距离。
当𝑝取无穷时的极限情况下,可以得到切比雪夫距离

汉明距离(Hamming distance)

在这里插入图片描述
汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以表示两个字之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。
在这里插入图片描述

余弦相似度

两个向量有相同的指向时,余弦相似度的值为1;两个向量夹角为90°时,余弦相似度的值为0;两个向量指向完全相反的方向时,余弦相似度的值为-1。
在这里插入图片描述
假定𝐴和𝐵是两个𝑛维向量,𝐴是 𝐴1, 𝐴2, … , 𝐴𝑛 ,𝐵是𝐵1,𝐵2, … , 𝐵𝑛 ,则𝐴和𝐵的夹角的余弦等于:
在这里插入图片描述
在这里插入图片描述

KNN算法

𝑘近邻法(k-Nearest Neighbor,kNN)是一种比较成熟也是最简单的机器学习算法,可以用于基本的分类与回归方法。

算法的主要思路

如果一个样本在特征空间中与𝑘个实例最为相似(即特征空间中最邻近),那么这𝑘个实例中大多数属于哪个类别,则该样本也属于这个类别。
对于分类问题:
对新的样本,根据其𝑘个最近邻的训练样本的类别,通过多数表决等方式进行预测。
对于回归问题:
对新的样本,根据其𝑘个最近邻的训练样本标签值的均值作为预测值

𝑘近邻法的三要素

• 𝑘值选择。
• 距离度量。
• 决策规则。

算法流程

1.计算测试对象到训练集中每个对象的距离
2.按照距离的远近排序
3.选取与当前测试对象最近的k的训练对象,作为该测试对象的邻居
4.统计这k个邻居的类别频次
5.k个邻居里频次最高的类别,即为测试对象的类

在这里插入图片描述以上图中绿点位置的分类问题为例,图中有正方形和三角形两类,K=3即选取距离绿点最近的三个对象,这三个对象中三角形的类别较多因此将绿点位置归为三角形类,而当K=5时选取距离绿点位置最近的五个对象,此时正方形的数量较多,则此时绿点为正方形类

KD树划分

KD树(K-Dimension Tree),,也可称之为K维树,可以用更高的效率来对空间进行划分,并且其结构非常适合寻找最近邻居和碰撞检测。
假设有 6 个二维数据点,构建KD树的过程:𝐷 = (2,3), (5,7), (9,6), (4,5), (6,4), (7,2) 。
①从𝑥轴开始划分,根据𝑥轴的取值2,5,9,4,6,7得到中位数为6 ,因此切分线为:𝑥 = 6 。
在这里插入图片描述
②可以根据𝑥轴和𝑦轴上数据的方差,选择方差最大的那个轴作为第一轮划分轴。
左子空间(记做 𝐷1)包含点 (2,3),(4,5),(5,7),切分轴轮转,从𝑦轴开始划分,切分线为𝑦 = 5
右子空间(记做 𝐷2 )包含点 (9,6),(7,2),切分轴轮转,从𝑦轴开始划分,切分线为:𝑦 = 6 。
在这里插入图片描述
③𝐷1的左子空间(记做 𝐷3)包含点(2,3),切分轴轮转,从x 轴开始划分,切分线为:𝑥 = 2。
其左子空间记做 𝐷7 ,右子空间记做 𝐷8 。由于 𝐷7,𝐷8都不包含任何点,因此对它们不再继续拆分。
𝐷1 的右子空间(记做 𝐷4 )包含点(5,7),切分轴轮转,从x 轴开始划分,切分线为:𝑥 = 5。
其左子空间记做 𝐷9,右子空间记做 𝐷10 。由于𝐷9,𝐷10都不包含任何点,因此对它们不再继续拆分。
在这里插入图片描述
④𝐷2的左子空间(记做 𝐷5 )包含点(7,2),切分轴轮转,从x 轴开始划分,切分线为:𝑥 = 7。
其左子空间记做 𝐷11,右子空间记做 𝐷12 。由于𝐷11,𝐷12 都不包含任何点,因此对它们不再继续拆分。
𝐷2的右子空间(记做 𝐷6)不包含任何点,停止继续拆分。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

KD树搜索

1.首先要找到该目标点的叶子节点,然后以目标点为圆心,目标点到叶子节点的距离为半径,建立一个超球体,我们要找寻的最近邻点一定是在该球体内部。
搜索(4,4)的最近邻时。首先从根节点(6,4)出发,将当前最近邻设为(6,4),对该KD树作深度优先遍历。以(4,4)为圆心,其到(6,4)的距离为半径画圆(多维空间为超球面),可以看出(7,2)右侧的区域与该圆不相交,所以(7,2)的右子树全部忽略。
在这里插入图片描述
2.返回叶子结点的父节点,检查另一个子结点包含的超矩形体是否和超球体相交,如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。
接着走到(6,4)左子树根节点(4,5),与原最近邻对比距离后,更新当前最近邻为(4,5)。以(4,4)为圆心,其到(4,5)的距离为半径画圆,发现(6,4)右侧的区域与该圆不相交,忽略该侧所有节点,这样(6,4)的整个右子树被标记为已忽略
在这里插入图片描述
3.如果不相交直接返回父节点,在另一个子树继续搜索最近邻。
4.当回溯到根节点时,算法结束,此时保存的最近邻节点就是最终的最近邻。遍历完(4,5)的左右叶子节点,发现与当前最优距离相等,不更新最近邻。所以(4,4)的最近邻为(4,5)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/389930.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

分布式文件系统 SpringBoot+FastDFS+Vue.js【四】

分布式文件系统 SpringBootFastDFSVue.js【四】 八、文件的下载和删除功能8.1.FastDFSClient.java8.2.FileServerController.java8.3.Vue的fast.js8.4.fastdfsimg.vue8.5.效果 九、总结endl 八、文件的下载和删除功能 8.1.FastDFSClient.java Slf4j public class FastDFSClie…

websocket数据帧格式

客户端、服务端数据的交换,离不开数据帧格式的定义。因此,在实际讲解数据交换之前,我们先来看下WebSocket的数据帧格式。 WebSocket客户端、服务端通信的最小单位是帧(frame),由1个或多个帧组成一条完整的消…

Atcoder ABC339 C - Perfect Bus

Perfect Bus(完美的公交车) 时间限制:2s 内存限制:1024MB 【原题地址】 所有图片源自Atcoder,题目译文源自脚本Atcoder Better! 点击此处跳转至原题 【问题描述】 【输入格式】 【输出格式】 【样例1】 【样例输…

排序算法---计数排序

原创不易,转载请注明出处。欢迎点赞收藏~ 计数排序(Counting Sort)是一种线性时间复杂度的排序算法,其核心思想是通过统计待排序元素的个数来确定元素的相对位置,从而实现排序。 具体的计数排序算法步骤如下&#xff…

Netty Review - 直接内存的应用及源码分析

文章目录 Pre概述应用访问效率: 堆内存 VS 直接内存申请效率: 堆内存 VS 直接内存数据存储结构: 堆内存 VS 直接内存结论 ByteBuffer.allocateDirect 源码分析unsafe.allocateMemory(size) ---> C方法 JVM参数 -XX:MaxDirectMemorySize直接…

视觉slam十四讲学习笔记(五)非线性优化

已经知道,方程中的位姿可以由变换矩阵来描述,然后用李代数进行优化。观测方程由相机成像模型给出,其中内参是随相机固定的,而外参则是相机的位姿。 目录 前言 一、状态估计问题 1 最大后验与最大似然 2 最小二乘的引出 二、非…

JavaScript中null和undefined的区别

JavaScript中null和undefined是两个特殊的值,经常在编程中遇到。虽然它们经常被混淆,但它们有着不同的含义和用法。本文将详细介绍JavaScript中null和undefined的区别,帮助开发者更好地理解和使用它们。 首先,让我们来了解一下nu…

css篇---移动端适配的方案有哪几种

移动端适配 移动端适配是指同一个页面可以在不同的移动端设备上都有合理的布局。主流实现的方案有 响应式布局通过rem或者vw,vh 等实现不同设备有相同的比例而实现适配 首先需要了解viewport 【视口】 视口代表了一个可看见的多边形区域(通常来说是矩形&#xff0…

函数递归与迭代附n的阶乘+顺序打印一个整数的每一位数+求第n个斐波那契数

1. 什么是递归&#xff1f; 递归其实是一种解决问题的方法&#xff0c;在C语言中&#xff0c;递归就是函数自己调用自己。 下面是一个最简单的C语言递归代码&#xff1a; #include <stdio.h> int main() {printf("hehe\n");main();//main函数中⼜调⽤了main函数…

BBC英式口语~发音练习~笔记整理

参考资料 原视频地址&#xff1a; https://www.bilibili.com/video/BV1D7411n7bS/?spm_id_from333.1245.0.0&vd_source5986fc7c8e6d754f3ca44233573aeaff 笔记图片

2.11题目

#include <stdio.h> int main() { char a; while((a getchar()) ! -1) { if(a > A && a < Z) a32; putchar(ch); } return 0;} ———————————————— 版权声明&#xff1a;本文为博主原创文章…

阿里云/腾讯云幻兽帕鲁服务器据点最大帕鲁工作数量最多15个,改成20不生效?

例如&#xff0c;在阿里云的计算巢管理中&#xff0c;找到你的这台部署幻兽帕鲁的服务器实例&#xff0c;选择右上角的“修改游戏配置” 然后选择“基地内工作帕鲁的最大数量”改成20 有人说更改上面的数字&#xff0c;根本不起作用。原因可能如下&#xff1a; 参考资料&#…

css篇---分辨率物理像素和逻辑像素

物理分辨率和逻辑分辨率 物理分辨率是生产屏幕时就固定的&#xff0c;它是不可改变的 -----电脑像素 逻辑分辨率是由软件决定的 【电脑的设置中可以修改分辨率】----css像素 设备像素比 dpr同一方向上的物理像素/css像素 &#xff08;缩放比是1的情况&#xff09; 假设dpr4/…

网络安全最典型基础靶场-DVWA-本地搭建与初始化

写在前面&#xff1a; 之前也打过这个 DVWA 靶场&#xff0c;但是是在虚拟机环境下的一个小块分区靶场&#xff1b; 本篇博客主要介绍在本地搭建 DVWA 靶场以及靶场的初始化&#xff0c;后续会陆续更新通关教程。 由于我们是在本地搭建&#xff0c;则需要基于你已经装好 phpstu…

cefsharp121(cef121.3.7Chromium121.0.6167.160)升级测试及其他H264版本

一、版本说明 1.1 本此版本 此版本CEF 121.3.7+g82c7c57+chromium-121.0.6167.160 / Chromium 121.0.6167.160 1.2 其他支持H264版本 支持H264推荐版本:V100,V109,V111,V119版本,其他V114,V115,V108,V107 支持win7/win8/win8.1最后版本v109.x 支持NET4.5.2最后版本v114.x …

一览大模型长文本能力

前言 如今的大模型被应用在各个场景&#xff0c;其中有些场景则需要模型能够支持处理较长文本的能力(比如8k甚至更长)&#xff0c;其中已经有很多开源或者闭源模型具备该能力比如GPT4、Baichuan2-192K等等。 那关于LLM的长文本能力&#xff0c;目前业界通常都是怎么做的&…

STM32 寄存器操作 GPIO 与下降沿中断

一、如何使用stm32寄存器点灯&#xff1f; 1.1 寄存器映射表 寄存器本质就是一个开关&#xff0c;当我们把芯片寄存器配置指定的状态时即可使用芯片的硬件能力。 寄存器映射表则是开关的地址说明。对于我们希望点亮 GPIO_B 的一个灯来说&#xff0c;需要关注以下的两个寄存器…

leetcode hot100不同路径

本题可以采用动态规划来解决。还是按照五部曲来做 确定dp数组&#xff1a;dp[i][j]表示走到&#xff08;i&#xff0c;j&#xff09;有多少种路径 确定递推公式&#xff1a;我们这里&#xff0c;只有两个移动方向&#xff0c;比如说我移动到&#xff08;i&#xff0c;j&#x…

【机器学习】数据清洗之识别重复点

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步…

React入门到精通:掌握前端开发的必备技能!

介绍&#xff1a;React是一个由Facebook开发和维护的JavaScript库&#xff0c;用于构建用户界面&#xff0c;特别是用于构建单页应用程序和移动应用程序的用户界面。以下是对React的详细介绍&#xff1a; 虚拟DOM&#xff1a;React通过使用虚拟DOM&#xff08;Document Object …