程序员经验分享-hwhale

机器学习（二）--- KNN（K-Nearest Neighbors）

2023-05-16

KNN

K-Nearest Neighbors

简单类比（Simple Analogy）

KNN：通过你周围的人来判断你是哪一类人

Tell me about your friends(who your neighbors are ) and I will tell you who you are

在这里插入图片描述

背景

KNN - K-Nearest Neighbors 别名：

  1. Memory-Based Reasoning
  2. Example-Based Reasoning
  3. Instance-Based Learning
  4. Lazy Learning

KNN在模式识别和数据挖掘领域有着非常广泛的应用；KNN利用某种相似性度量方案（常见的比如距离函数）对周围对结点进行度量，从而确定当前结点所属对类别。没错，它是一种分类算法，并且是无参数化的懒惰的学习算法。

K nearest neighbors stores all available cases and classifies new cases based on a similarity measure (e.g distance function)

说KNN懒惰是因为它不做任何的抽象和泛化，仅仅使用一种特定的相似性度量方案，不需要学习任何东西。

Using a strict definition of learning, in which the learner summarizes raw input into a model (equations, decision trees, clustering, if then rules), a lazy learner is not really learning anything.

与其他学习算法不一样，KNN在训练的时候只需要花费很短的时间，它只是存储训练数据，但是在测试的时候需要花费较长的时间；也不需要建立模型。这点和其他学习算法正好相反。

KNN使用多数投票的方式对新的样本进行分类，在邻近的K个样本中，某一类的样本个数最多，那么就新样本就属于这一类。

An object (a new instance) is classified by a majority votes for its neighbor classes.

The object is assigned to the most common class amongst its K nearest neighbors.(measured by a distant function)

在这里插入图片描述

比如在上面这个图种，绿色的新样本就被分类成B类。

KNN

前面说过KNN是一种懒惰的学习算法，对新样本进行分类是通过对邻近样本使用某种相似性指标得到的，并且是采用多数投票对方式。

那么这就有两个问题，第一：邻近样本中的“邻近”是如何定义的？第二：相似性度量指标是啥？

先来看第一个问题。KNN中的K就是解决这个问题的，K的值代表了取新样本周围最近邻居的数目。

“K” stands for number of data set items that are considered for the classification.
在这里插入图片描述

对于第二个问题，相似性度量指标一般用的是距离函数，即选择距离新样本最近的邻居。

在这里插入图片描述

如上图，左边是已经存储好的训练集，对于测试集中的每个样本都与训练集的样本计算距离，然后选择K个最近的训练集样本，接着在选择好的训练集样本中使用多数投票的方式来对测试集数据进行分类。

听起来好像没啥问题，但是这其中隐含了两个问题。第一，距离如何算？第二，从上面对流程能看出，KNN对时间复杂度是O(n2)。

第二个问题好像没啥解决办法，因为这是KNN本身的缺点。那如何计算距离呢？

  1. 欧几里得距离(Euclidean)

在这里插入图片描述

  1. 曼哈顿距离(Manhattan)

在这里插入图片描述

好的，到目前为止，已经讨论完了KNN算法的完整流程了，小结一下吧：

  • 所有的样本都是在一个n维的空间中的
  • 每个样本由数字类型的属性和标签组成
  • 选择距离新样本最近的K个训练集样本
  • 找出这K个样本里出现次数最多的标签

那么这个k值如何选择呢？或者说它的值对算法性能有什么影响呢？

  1. K值太小对话，算法对异常值就非常敏感。举个极端的例子，k=1，并且距离新样本最近的样本点是一个误分类点。
  2. 稍大点的k比较好，但是如何很大又回包含很多其他类大样本点。
  3. 根据经验，k < sqrt(n)，n是训练集样本的个数。并且最好选择奇数（二分类）。

从上面的描述可以得到如下结论：

  1. k太小的话，模型的bias小，variance高，过拟合，高复杂度。
  2. 随着k增大，bias增大，variance减小，走向欠拟合，低复杂度。
  3. 可以使用crass_validation来调整k值。

这部分可以参考下：KNN和K-means的区别 为什么KNN算法里的K越小模型会越复杂？ 过拟合和欠拟合的偏差和方差问题（https://blog.csdn.net/yanni0616/article/details/100008763）

直观地理解，过拟合就是学习到了很多“局部信息”，或者是“噪音”，使得我们的模型中包含很多“不是规律的规律”。在knn算法中，k越小，就越有可能让我们的学习结果被“局部信息”所左右。在极端情况下，k=1，knn算法的结果只由离我们待预测样本最近的那个点决定，这使得我们knn的结果高概率被“有偏差的信息”或者“噪音”所左右，是一种过拟合。

最后贴一下优缺点吧。

在这里插入图片描述

结语

这篇文章介绍了knn的一些基本问题，花了大概一个半小时的时间整理，图片都是来自于上课老师的ppt。考虑了许久要不要加sklearn的实现，如果加了是不是还要弄个不用sklearn的实现方案，但是想到这个东西遍地都是，懒得写了。

当然还有一些东西本文并未涉及到，比如说距离函数那里使用的都是数字类型的特征，如果特征是二分类的呢？如果是string呢？其实也有相应的衡量指标的，没加的原因主要是因为感觉没必要，因为我的初衷是为了应付期末考试的哈哈哈。

吐槽一下，notion笔记贴到csdn操作不友好。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

KNN

nearest

Neighbors

机器学习

机器学习（二）--- KNN（K-Nearest Neighbors） 的相关文章

随机推荐

  • 启明欣欣STM32开发板 --- 运行LWIP (使用FreeRtos)

    在上篇文章中 xff0c 我们生成了不带RTOS的LWIP工程 xff0c 本篇讲述如何生成带RTOS的LWIP工程 xff0c RTOS选择FreeRtos xff0c CubeMX工程以上篇文章中的工程为基础 文章目录 一 使能Free

  • python http 身份认证简介

    目录 授权方式简介 1 Basic Authentication 2 OAuth 3 Token Authentication 4 Digest Authentication xff08 重点说一下 xff09 代码实现 1 基本身份认证

  • 记录VScode调试过慢的问题

    目录 问题 xff1a 解决方案 xff1a 0806更新报错 问题 xff1a 最近在使用VScode的过程中调试慢到让人接受不了 xff0c 遂寻找解决方案 xff0c 重装VScode 在网上找了好多答案 xff0c 尝试后均无法解决

  • Android APP漏洞自动化静态扫描检测工具-Qark环境搭建与使用

    QARK 1 qark简介 LinkedIn最近开源了他的静态分析工具QARK xff0c 该工具用于分析那些用Java语言开发的Android应用中的潜在安全缺陷 QARK 全称 Quick Android Review Kit 这个工具

  • QT中CMakeLists添加第三方库

    1 新建项目 xff0c 打开CMakeLists txt文件 cmake minimum required VERSION 2 8 project fp test cm 括号内fp test cm为项目名称 add executable

  • Linux下curl模拟带header的Http请求

    格式 xff1a curl H 头部内容 http xxx 123 com curl span class hljs attribute H span span class hljs string 34 Accept text html a

  • 中断与查询方式的比较

    单片机在操作外部设备时 xff0c 常用的有中断和查询两种方式 除了在编程方面的区别外 xff0c 在性能和效率上都是有所区别 中断的性能要比查询强大 xff0c 反应速度快 xff0c 要求相应的ISR不能过于繁琐 xff0c 而且要求电

  • 解决nodejs报错TypeError: ParserIncomingMessage is not a constructor.

    当前最新的 node v8 12 v10 11 在 http模块里有一个bug bug报错如下 xff1a TypeError ParserIncomingMessage is not a constructor at HTTPParser

  • 串口通信基础知识（UART）

    目录 一 串口通信的具体分类 xff1a 二 常见的串行通信接口简介 xff1a 三 具体通信标准的实现 xff1a 1 UART xff08 通用异步收发传输器 xff09 xff1a 一 串口通信的具体分类 xff1a 总结一下 xff

  • ++声明、定义、类的定义、头文件作用、头文件重复引用

    转载至 xff1a 点击打开链接 C 43 43 声明 定义 类的定义 头文件作用 头文件重复引用 xff0c 不具名空间 转自 xff1a http www cnblogs com rocketfan archive 2009 10 02

  • 三维旋转矩阵；东北天坐标系(ENU)；地心地固坐标系(ECEF)；大地坐标系(Geodetic)；经纬度对应圆弧距离

    目录 TOC自动生成 旋转矩阵东北天 站心坐标系地心坐标系参考文献 旋转矩阵 Givens rotation 逆时针 Jacobi rotation 顺时针 箭头朝里朝外 xff0c 顺时针 逆时针 xff0c 61 61 旋转角的正负 6

  • libcurl进行异步并发

    libcurl的easy 接口 xff0c easy接口的使用非常的简单 xff0c curl easy init用来初始化一个easy curl对象 xff0c curl easy setopt对easy curl对象进行相关设置 xff

  • unbuntu运行VINS-MONO实验总结

    ubuntu16 04运行VINS ONO实验总结 初探 简介1 环境配置2 运行Euroc数据集 xff13 小觅摄像头运行vins mono 简介 VINS Mono是香港科技大学沈劭劼团队开源的单目视觉惯导SLAM方案 前端KLT稀疏

  • 电子硬件3.杜邦线

    杜邦线是常用于电路连接的导线 xff0c 能够刚好插在常用的2 54mm间距的排针上 杜邦线的三种类型为 xff1a 公公线 公母线 母母线

  • Android应用安全检测工具简介

    Android应用安全检测工具简介 1 测试工具集 Appie 轻量级的软件包 可以用来进行基于Android的渗透测试 不想使用VM的时候可以尝试一下 Android Tamer 可以实时监控的虚拟环境 可以用来进行一系列的安全测试 恶意

  • C语言浮点型数据存储结构

    1 float类型 float类型占四个字节 xff0c 每个字节占8位 xff0c 总共32位 xff0c 其内存结构如下图 xff1a 31位为符号位 xff1a 0表示正数 xff0c 1表示负数 31 23位 xff1a 共8位表示

  • sockaddr和sockaddr_in详解

    struct sockaddr和struct sockaddr in这两个结构体用来处理网络通信的地址 一 sockaddr sockaddr在头文件 include lt sys socket h gt 中定义 xff0c sockadd

  • python requests模拟登陆带验证码的网站

    作为之前专利爬虫的续篇 xff0c 本篇准备描述如何通过python的requests模块登录专利查询网站 环境准备 python 3 6requests chrome尝试 首先 xff0c 我们使用chrome尝试登录专利网站 xff0c

  • 兔子与兔子（下一篇解释原理：字符串哈希）

    文章目录 兔子与兔子题目描述解题思路 兔子与兔子 题目描述 很久很久以前 xff0c 森林里住着一群兔子 有一天 xff0c 兔子们想要研究自己的 DNA 序列 我们首先选取一个好长好长的 DNA 序列 xff08 小兔子是外星生物 xff

  • 机器学习（二）--- KNN（K-Nearest Neighbors）

    KNN K Nearest Neighbors 简单类比 xff08 Simple Analogy xff09 KNN xff1a 通过你周围的人来判断你是哪一类人 Tell me about your friends who your n

热门标签