当前位置: 首页 > news >正文

20240326-1-KNN面试题

KNN面试题

在这里插入图片描述

1.简述一下KNN算法的原理

KNN算法利用训练数据集对特征向量空间进行划分。KNN算法的核心思想是在一个含未知样本的空间,可以根据样本最近的k个样本的数据类型来确定未知样本的数据类型。
该算法涉及的3个主要因素是:k值选择,距离度量,分类决策

2. 如何理解kNN中的k的取值?

在应用中,k值一般取比较小的值,并采用交叉验证法进行调优。

3. 在kNN的样本搜索中,如何进行高效的匹配查找?

线性扫描(数据多时,效率低)
构建数据索引——Clipping和Overlapping两种。前者划分的空间没有重叠,如k-d树;后者划分的空间相互交叠,如R树。(对R树了解很少,可以之后再去了解)

4. KNN算法有哪些优点和缺点?

  • 优点:

    ​ 算法思想较简单,既可以做分类也可以做回归;可以用于非线性分类/回归;训练时间复杂度为O(n);准确率高,对数据没有假设,对离群点不敏感。

  • 缺点:

    ​ 计算量大;存在类别不平衡问题;需要大量的内存,空间复杂度高。

5. 不平衡的样本可以给KNN的预测结果造成哪些问题,有没有什么好的解决方式?

输入实例的K邻近点中,大数量类别的点会比较多,但其实可能都离实例较远,这样会影响最后的分类。 可以使用权值来改进,距实例较近的点赋予较高的权值,较远的赋予较低的权值。

6. 为了解决KNN算法计算量过大的问题,可以使用分组的方式进行计算,简述一下该方式的原理。

先将样本按距离分解成组,获得质心,然后计算未知样本到各质心的距离,选出距离最近的一组或几组,再在这些组内引用KNN。 本质上就是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本,该方法比较适用于样本容量比较大时的情况。

##7. K-Means与KNN有什么区别

  • KNN

    • KNN是分类算法
    • 监督学习
    • 喂给它的数据集是带label的数据,已经是完全正确的数据
    • 没有明显的前期训练过程,属于memory-based learning
    • K的含义:来了一个样本x,要给它分类,即求出它的y,就从数据集中,在x附近找离它最近的K个数据点,这K个数据点,类别c占的个数最多,就把x的label设为c
  • K-Means

    • 1.K-Means是聚类算法
    • 2.非监督学习
    • 3.喂给它的数据集是无label的数据,是杂乱无章的,经过聚类后才变得有点顺序,先无序,后有序
    • 有明显的前期训练过程
    • K的含义:K是人工固定好的数字,假设数据集合可以分为K个簇,由于是依靠人工定好,需要一点先验知识
  • 相似点

    • 都包含这样的过程,给定一个点,在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法,一般用KD树来实现NN。

##9. KD树改进

  • Kd-tree在维度较小时(例如:K≤30),算法的查找效率很高,然而当Kd-tree用于对高维数据(例如:K≥100)进行索引和查找时,就面临着维数灾难(curse of dimension)问题,查找效率会随着维度的增加而迅速下降。通常,实际应用中,我们常常处理的数据都具有高维的特点,例如在图像检索和识别中,每张图像通常用一个几百维的向量来表示,每个特征点的局部特征用一个高维向量来表征(例如:128维的SIFT特征)。因此,为了能够让Kd-tree满足对高维数据的索引,Jeffrey S. Beis和David G. Lowe提出了一种改进算法——Kd-tree with BBF(Best Bin First),该算法能够实现近似K近邻的快速搜索,在保证一定查找精度的前提下使得查找速度较快。

  • 在介绍BBF算法前,我们先来看一下原始Kd-tree是为什么在低维空间中有效而到了高维空间后查找效率就会下降。在原始kd-tree的最近邻查找算法中(第一节中介绍的算法),为了能够找到查询点Q在数据集合中的最近邻点,有一个重要的操作步骤:回溯,该步骤是在未被访问过的且与Q的超球面相交的子树分支中查找可能存在的最近邻点。随着维度K的增大,与Q的超球面相交的超矩形(子树分支所在的区域)就会增加,这就意味着需要回溯判断的树分支就会更多,从而算法的查找效率便会下降很大。

  • 从上述标准的kd树查询过程可以看出其搜索过程中的“回溯”是由“查询路径”决定的,并没有考虑查询路径上一些数据点本身的一些性质。一个简单的改进思路就是将“查询路径”上的结点进行排序,如按各自分割超平面(也称bin)与查询点的距离排序,也就是说,回溯检查总是从优先级最高(Best Bin)的树结点开始。

    bbf的算法:
    输入:kd树,查找点x.
    输出:kd树种距离查找点最近的点以及最近的距离

    1. 若kd树为空,则设定两者距离为无穷大,返回;如果kd树非空,则将kd树的根节点加入到优先级队列中;

    2. 从优先级队列中出队当前优先级最大的结点,计算当前的该点到查找点的距离是否比最近邻距离小,如果是则更新最近邻点和最近邻距离。如果查找点在切分维坐标小于当前点的切分维坐标,则把他的右孩子加入到队列中,同时检索它的左孩子,否则就把他的左孩子加入到队列中,同时检索它的右孩子。这样一直重复检索,并加入队列,直到检索到叶子节点。然后在从优先级队列中出队优先级最大的结点;

    3. 重复1和1中的操作,直到优先级队列为空,或者超出规定的时间,返回当前的最近邻结点和距离。

相关文章:

20240326-1-KNN面试题

KNN面试题 1.简述一下KNN算法的原理 KNN算法利用训练数据集对特征向量空间进行划分。KNN算法的核心思想是在一个含未知样本的空间,可以根据样本最近的k个样本的数据类型来确定未知样本的数据类型。 该算法涉及的3个主要因素是:k值选择,距离度…...

【论文速读】| MASTERKEY:大语言模型聊天机器人的自动化越狱

本次分享论文为:MASTERKEY: Automated Jailbreaking of Large Language Model Chatbots 基本信息 原文作者:Gelei Deng, Yi Liu, Yuekang Li, Kailong Wang, Ying Zhang, Zefeng Li, Haoyu Wang, Tianwei Zhang, Yang Liu 作者单位:南洋理工…...

jvm运行情况预估

相关系统 jvm优化原则-CSDN博客 执行下面指令 jstat gc -pid 能计算出一些关键数据,有了这些数据,先给JVM参数一些的初始的,比堆内存大小、年轻代大小 、Eden和Srivivor的比例,老年代的大小,大对象的阈值,…...

Day105:代码审计-PHP原生开发篇SQL注入数据库监控正则搜索文件定位静态分析

目录 代码审计-学前须知 Bluecms-CNVD-1Day-常规注入审计分析 emlog-CNVD-1Day-常规注入审计分析 emlog-CNVD-1Day-2次注入审计分析 知识点: 1、PHP审计-原生态开发-SQL注入&语句监控 2、PHP审计-原生态开发-SQL注入&正则搜索 3、PHP审计-原生态开发-SQ…...

Python:如何对FY3D TSHS的数据集进行重投影并输出为TIFF文件以及批量镶嵌插值?

完整代码见 Github:https://github.com/ChaoQiezi/read_fy3d_tshs,由于代码中注释较为详细,因此博客中部分操作一笔带过。 01 FY3D的HDF转TIFF 1.1 数据集说明 FY3D TSHS数据集是二级产品(TSHS即MWTS/MWHS 融合大气温湿度廓线/稳定度指数/…...

CentOS 镜像下载

CentOS 镜像下载:https://www.centos.org/download/ 选择合适的架构,博主选择x86_64,表示CentOS7 64位系统x86架构,如下: 或者直接访问以下网站下载 清华大学开源软件镜像站:https://mirrors.tuna.tsin…...

yum和配置yum源

yum 以及配置yum 源。 文章目录 一、Linux 软件包管理器yum二、使用yum安装软件三、配置yum源四、yum源仓库五、lrzse 实现linux远端和本地 互传文件 一、Linux 软件包管理器yum (1)什么是yum? yum 是一个软件下载安装管理的一个软件包管理器,它就相当于我们手机…...

jQuery笔记 02

目录 01 jq中预定义动画的使用 02 jq中的自定义动画 03 jq的动画的停止 04 jq节点的增删改 05 属性节点的操作 06 jq中的值和内容的操作 07 jq中宽高的操作 08 jq中坐标的操作 01 jq中预定义动画的使用 jq的预定义动画: 1.显示隐藏动画 显示 : jq对象.show() 不传参数 表…...

基于Java+SpringBoot+Vue文学名著分享系统(源码+文档+部署+讲解)

一.系统概述 随着世界经济信息化、全球化的到来和互联网的飞速发展,推动了各行业的改革。若想达到安全,快捷的目的,就需要拥有信息化的组织和管理模式,建立一套合理、动态的、交互友好的、高效的文学名著分享系统。当前的信息管理…...

C/S医学检验LIS实验室信息管理系统源码 医院LIS源码

LIS系统即实验室信息管理系统。LIS系统能实现临床检验信息化,检验科信息管理自动化。其主要功能是将检验科的实验仪器传出的检验数据经数据分析后,自动生成打印报告,通过网络存储在数据库中,使医生能够通过医生工作站方便、及时地…...

liunx环境变量学习总结

环境变量 在操作系统中,环境变量是一种特殊的变量,它们为运行的进程提供全局配置信息和系统环境设定。本文将介绍如何自定义、删除环境变量,特别是对重要环境变量PATH的管理和定制,以及与环境变量相关的函数使用。 自定义环境变…...

对于Redis,如何根据业务需求配置是否允许远程访问?

1、centos8 Redis安装的配置文件目录在哪里? 在 CentOS 8 中,默认情况下 Redis 的配置文件 redis.conf 通常位于 /etc/ 目录下。确切的完整路径是 /etc/redis.conf。 2、redis如何设置允许远程登录 修改redis.conf文件 # 继承默认注释掉的bind配置 # …...

深入分析Linux上下文与上下文切换

Linux 进程运行空间与特权等级 在 Linux 操作系统中,进程的运行空间被划分为内核空间和用户空间,这种划分是为了保护系统的稳定性和安全性。这两个空间对应着 CPU 的特权等级,分别为: Ring 0(内核态)Ring…...

Docker快速上手及常用命令速查

Docker快速上手 安装 在ubuntu上安装docker: sudo apt-get install docker docker -v #查看版本在centos7上安装docker:(docker在YUM源的Extras仓库中) yum install docker systemctl start dockerdocker常用命令速查 #查看docker信息 docker info #查看本地镜…...

学习笔记:解决拖延

1 解决拖延、减轻压力的关键心态和方法 1.1 要点梳理 拖延是因为自己一直在逃避,重点是要有效突破逃避圈,进入学习圈,扩展成长圈。 毒蛇曲线(见思维导图)中越是临近截止期限,拖延的焦虑越上升&#xff0…...

第一个Swift程序

要创建第一个Swift项目,请按照以下步骤操作: 打开Xcode。如果您没有安装Xcode,可以在App Store中下载并安装它。在Xcode的欢迎界面上,选择“Create a new Xcode project”(创建新Xcode项目)。在模板选择界面上,选择“App”(应用程序)。在应用模板选择界面上,选择“Si…...

Anthropic Claude 3 加入亚马逊云科技 AI“全家桶”

编辑 | 宋慧 出品 | CSDN AIGC 每天都有新动态发生。最新的消息是亚马逊在 3 月底完成了对 Anthropic 的 40 亿美元投资(也是亚马逊 30 年来最大一笔外部投资),以及 GPT-4 最强对手的 Anthropic Claude 3 已经在亚马逊云科技 Amazon Bedrock…...

学习基于pytorch的VGG图像分类 day3

注:本系列博客在于汇总CSDN的精华帖,类似自用笔记,不做学习交流,方便以后的复习回顾,博文中的引用都注明出处,并点赞收藏原博主. 目录 VGG模型训练 1.导入必要的库 2.主函数部分 2.1使用cpu或gpu 2.2对数据…...

Spring Boot统一功能处理之拦截器

本篇主要介绍Spring Boot的统一功能处理中的拦截器。 目录 一、拦截器的基本使用 二、拦截器实操 三、浅尝源码 初始化DispatcherServerlet 处理请求(doDispatch) 四、适配器模式 一、拦截器的基本使用 在一般的学校或者社区门口,通常会安排几个…...

stm32之基本定时器的使用

在上文我们使用到了HAL库的自带的延时函数,HAL_Delay();我们来看一下函数的原型 __weak void HAL_Delay(uint32_t Delay) {uint32_t tickstart HAL_GetTick();uint32_t wait Delay;/* Add a freq to guarantee minimum wait */…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name:3ddown Serial:FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名:Axure 序列号:8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...