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中的操作,直到优先级队列为空,或者超出规定的时间,返回当前的最近邻结点和距离。

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

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

相关文章

dwd_traffic_page_view_inc装载数据很慢

dwd_traffic_page_view_inc dwd_traffic_page_view_inc 装载数据很慢 可能原因 1.加载数据的小文件太多,saprk 加载这些小文件时,需要消耗资源。

ITK 重采样 resample

Itk 重新采样有二多种情况&#xff0c;这里说二种情况 1. 输入参数 &#xff0c;和输出相关数据&#xff0c;输出范围&#xff0c;spacing &#xff1b; typedef itk::Image< float, 3 > itkFloatImageType;typedef itk::ResampleImageFilter < itkFloatImageType, i…

【Gem5】获取构建教程

gem5-tutorial-hpca-2023 1 介绍 1.1 Gem5是什么1.2 Gem5可以用来做什么1.3 获取并构建gem5 gem5-tutorial-hpca-2023 打开网址&#xff1a; github 创建教程代码空空间 “Code” -> “Codespaces” -> “Create Codespace on master” GitHub Codespaces 是一个由…

网络安全加密算法---对称加密

三位同学一组完成数据的对称加密传输。 三位同学分别扮演图中 A、B 和 KDC 三个角色&#xff0c;说明 KA、KB&#xff0c;KAB 和发送的数据Data 的内容。 给出图中 2 和 3 中的数据&#xff0c;以及 Data 加密后的密文。可以完成多轮角色互换的通信 过程。其中一轮过程要求 K…

jni 开发 调用dll 函数的流程

jni 调用dll方法以及dll内调用java方法的流程 编写java类 public class abc{static{System.loadLibrary("abc.dll");}public String getResponse(String ReqStr) {return "ok";}public native void InitDiagObj();public native void CarryabcEntry(Stri…

Vulnhub:DEVCONTAINER: 1

目录 信息收集 arp nmap nikto whatweb WEB 信息收集 dirmap 文件上传 提权 系统信息收集 横向提权 信息泄露 get root 信息收集 arp ┌──(root㉿ru)-[~/kali/vulnhub] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:50:56:2f:dd…

一例简单的文件夹病毒的分析

概述 这是一个典型的文件夹病毒&#xff0c;使用xp时代的文件夹图标&#xff0c;通过可移动存储介质传播&#xff0c;会向http://fionades.com/ABIUS/setup.exe下载恶意载荷执行。 其病毒母体只是一个加载器&#xff0c;会在内存是解密加载一个反射型的dll&#xff0c;主要的…

python使用uiautomator2操作雷电模拟器9找图

接上篇文章python使用uiautomator2操作雷电模拟器9并遇到解决adb 连接emulator-5554 unauthorized问题-CSDN博客 搭建好uiautomator2后&#xff0c;主要就是使用了。 本文就利用uiautomator2的截屏、模拟点击和aircv的找图功能&#xff0c;实现对指定寻找的图片的位置的点击。…

观察者模式与发布-订阅模式的对决

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

javaWeb网上零食销售系统

1 绪 论 目前&#xff0c;我国的网民数量已经达到7.31亿人&#xff0c;随着互联网购物和互联网支付的普及&#xff0c;使得人类的经济活动进入了一个崭新的时代。淘宝&#xff0c;京东等网络消费平台功能的日益完善&#xff0c;使得人们足不出户就可以得到自己想要的东西。如今…

PCB学习记录---原理图

一、注释 NC&#xff1a;no connect,默认不连接 NF: no fix&#xff0c;默认不安装 0R: 0R的电阻&#xff0c;即可以短路 二、看图流程 1、看标题&#xff0c;了解功能 2、浏览有几个模块 3、找芯片对应的数据手册&#xff0c;了解芯片功能和使用 例如CH224&#xff…

gradio简单搭建——关键词匹配筛选【进一步优化】

gradio简单搭建——关键词匹配筛选[进一步优化] 任务回顾新的想法&#xff1a;无效元素筛选界面搭建数据处理与生成过程交互界面展示 任务回顾 在 apply \text{apply} apply方法的使用一节中&#xff0c;简单提到了任务目标&#xff1a;通过关键词的形式&#xff0c;在文本数据…

Harmony鸿蒙南向驱动开发-DAC

DAC&#xff08;Digital to Analog Converter&#xff09;是一种通过电流、电压或电荷的形式将数字信号转换为模拟信号的设备。 DAC模块支持数模转换的开发。它主要用于&#xff1a; 作为过程控制计算机系统的输出通道&#xff0c;与执行器相连&#xff0c;实现对生产过程的自…

【讲解下Fiddler的安装和使用】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

支小蜜校园刷脸支付系统的优势在哪里?

在当今社会&#xff0c;校园欺凌问题日益受到人们的关注。校园欺凌不仅影响学生的身心健康&#xff0c;还可能导致其产生厌学、逃学甚至报复社会的行为。建立校园防欺凌系统对于学校而言&#xff0c;具有极其重要的意义。本文将详细探讨校园防欺凌系统对学校的好处。 一、保障…

3.1 基本形式 机器学习

从本章本节开始就开始正式介绍机器学习的算法了&#xff01;我们首先登场的是---------线性模型。 w可以理解为权重&#xff0c;我们的x就是我们的样本点的各个特征数值&#xff0c;最后输出模型f&#xff08;x&#xff09;。其代表我们把样本点带入&#xff0c;以二分类为例&a…

金三银四面试题(十七):MySQL面试都问什么(2)

今天我们继续盘点那些高频的MySQL面试题。 说说InnoDB与MyISAM的区别 InnoDB 支持事务&#xff0c;MyISAM 不支持&#xff0c;对于InnoDB 每一条SQL 语言都默认封装成事务&#xff0c;自动提交&#xff0c;这样会影响速度&#xff0c;所以最好把多条SQL 语言放在begin 和comm…

密码学基础--搞清RFC和PKCS(1)

目录 1. CryptoDriver里KeyElement格式 2. 挖掘RFC标准 3.小结 昨天从生成密钥对开始逐步了解了公钥、证书等各种编码方式&#xff0c;今天继续趁热打&#xff0c;做一个理论知识汇总。 Ps:我只是标准的翻译搬运工。 1. CryptoDriver里KeyElement格式 在 CryptoKeyElemen…

基于达梦数据库开发-python篇

文章目录 前言一、搭建demo前提初始化简单demo 二、可能出现的异常情况DistutilsSetupErrorNo module named dmPythonlist报错 总结 前言 出于信创的考虑&#xff0c;近年来基于国产数据库达梦的应用开发逐渐变多。本文将介绍在windows环境下基于DM8版本的python的简单开发使用…

【自控笔记】线性系统时域分析法

动态稳态性能 一阶系统 二阶系统 二阶系统单位阶跃 系统稳定性分析