机器学习-K近邻算法(KNN)

目录

什么是KNN算法

图解KNN基本算法

(1)k近邻算法中k的选取

 (2)距离函数

(3)归一化处理

(4)概率kNN

KNN算法的优缺点

优势

缺点

KNN算法总结


什么是KNN算法

        k近邻算法,也称为 KNN 或 k-NN,是一种非参数、有监督的学习分类器,KNN 使用邻近度对单个数据点的分组进行分类或预测。 虽然 k近邻算法 (KNN) 可以用于回归或分类问题,但它通常用作分类算法,假设可以在彼此附近找到相似点。

表示 K 最近邻算法图的插图

        回归问题使用与分类问题类似的概念,但在这种情况下,取 k 个最近邻的平均值来对分类进行预测。 这里的主要区别是分类用于离散值,而回归用于连续值。 但是,在进行分类之前,必须定义距离。 最常用的是欧几里得距离,我们将在下面深入研究。
        还值得注意的是,k近邻算法 (KNN) 也是"惰性学习"模型家族的一部分,这意味着它只是存储训练数据集,而不是经历训练阶段。 这也意味着所有计算都发生在进行分类或预测时。 由于 k近邻算法 (KNN) 严重依赖内存来存储其所有训练数据,因此也称为基于实例或基于内存的学习方法。
        Evelyn Fix 和 Joseph Hodges 在 1951 年的这篇 论文 中提出了围绕 k近邻算法 (KNN) 模型的最初想法,而 Thomas Cover 在他的 研究 中扩展了他们的概念:“最近邻模式分类”。 虽然这种算法不再像以前那样受欢迎,但由于其简单性和准确性,仍然是人们在数据科学中学习的首选算法之一。 然而,随着数据集的增长,k近邻算法 (KNN)  变得越来越低效,影响了整体模型的性能。 k近邻算法 (KNN) 通常用于简单的推荐系统、模式识别、数据挖掘、金融市场预测、入侵检测等。 


图解KNN基本算法

        假设有三种兔子,第一种兔子叫作绿兔(Green),它们的平均身高是 50厘米,平均体重 5公斤。选取100个样本,分别测量它们的身高和体重,画在坐标图上,用绿色方块表示。

  第二种兔子叫蓝兔(blue),它们体型比较小,平均身高是 30厘米,平均体重是 4公斤。同样,选取100个样本,分别测量它们的身高和体重,并将它们画在同一个坐标图上,用蓝色三角表示。

  最后一种兔子叫黄兔(yellow),它们的平均身高45厘米,但体重较轻,平均只有2.5公斤。100只黄兔的数据用黄色圆圈表示。

  在这些数据中,(身高,体重)的二元组叫做特征(features),兔子的品种则是分类标签(class label)。我们想解决的问题是,给定一个未知分类的新样本的所有特征,通过已知数据来判断它的类别。

  现在假设有一只兔子R,想要确定它属于绿兔、蓝兔和黄兔中的哪一类,应该怎么做呢?按照最普通的直觉,应该在已知数据里找出几个和我们想探究的兔子最相似的几个点,然后看看那些兔子都是什么个情况;如果它们当中大多数都属于某一类别,那么兔子R大概率也就是那个类别了。

  为了确定兔子R属于哪一类,首先测量出其身长为 40 厘米,体重 2.7 公斤,为了直观展示,将其画在上述同一坐标系中,用红色五角星表示。


  现在预设一个整数k,寻找距离兔子R最近的k个数据样本进行分析。kNN 算法如何对这次观测进行分类要取决于k的大小。直觉告诉我们兔子R像是一只黄兔,因为除了最近的蓝色三角外,附近其他都是黄色圆圈。的确,如果设 k = 15,算法会判断这只兔子是一只黄兔。但是如果设 k = 1,那么由于距离最近的是蓝色三角,会判断兔子R是一只蓝兔。

  如果按照15NN和1NN的方法对这个二维空间上的每一个点进行分类,会形成以下的分割:

  在两组分类中,1NN 的分类边界明显更“崎岖”,但是对历史样本没有误判;而 15NN 的分类边界更平滑,但是对历史样本有发生误判的现象。选择k的大小取决于对偏差和方差之间的权衡。

(1)k近邻算法中k的选取

  • 对于K值的选择,一般根据样本分布选择一个较小的值,然后通过交叉验证来选择一个比较合适的最终值;

  • 当选择比较小的K值的时候,表示使用较小领域中的样本进行预测,训练误差会减小,但是会导致模型变得复杂,容易导致过拟合;

  • 当选择较大的K值的时候,表示使用较大领域中的样本进行预测,训练误差会增大,同时会使模型变得简单,容易导致欠拟合;

 如果我们选取较小的k值,那么就会意味着我们的整体模型会变得复杂,容易发生过拟合。假设我们选取k=1这个极端情况,并且有训练数据和待分类点如下图:

  上图中有俩类,一个是黑色的圆点,一个是蓝色的长方形,现在我们的待分类点是红色的五边形。根据我们的k近邻算法步骤来决定待分类点应该归为哪一类。我们由图中可以得到,五边形离黑色的圆点最近,k又等于1,因此,我们最终判定待分类点是黑色的圆点。

  由这个处理过程我们很容易能够感觉出问题了,如果k太小了,比如等于1,那么模型很容易学习到噪声,也就非常容易判定为噪声类别。而在上图,如果,k大一点,k等于8,把长方形都包括进来,我们很容易得到我们正确的分类应该是蓝色的长方形!如下图:

  所谓的过拟合就是在训练集上准确率非常高,而在测试集上准确率低,经过上例,我们可以得到k太小会导致过拟合,很容易将一些噪声(如上图离五边形很近的黑色圆点)学习到模型中,而忽略了数据真实的分布。

  如果我们选取较大的k值,就相当于用较大邻域中的训练数据进行预测,这时与输入实例较远的(不相似)训练实例也会对预测起作用,使预测发生错误,k值的增大意味着整体模型变得简单。

  我们想,如果k=N(N为训练样本的个数),那么无论输入实例是什么,都将简单地预测它属于在训练实例中最多的类。这时,模型压根就没有训练,只是直接拿训练数据统计了一下各个数据的类别,找最大的而已。这好像下图所示:

  我们统计了黑色圆形是8个,长方形个数是7个,那么,如果k=N,我就得出结论了,红色五边形是属于黑色圆形的。这个时候,模型过于简单,完全忽略训练数据实例中的大量有用信息,是不可取的。

  综上分析,k值既不能过大,也不能过小,在我举的这个例子中,我们k值的选择,在下图红色圆边界之间这个范围是最好的,如下图:


  注:这里只是为了更好让大家理解,真实例子中不可能只有两维特征。


 (2)距离函数

        为了确定哪些数据点最接近给定查询点,需要计算查询点与其他数据点之间的距离。 这些距离度量有助于形成决策边界,而决策边界可将查询点划分为不同的区域。 你通常会看到使用 Voronoi 图可视化的决策边界。

        可以选择多种距离度量,但本文仅涵盖以下几种:

        欧几里得距离(p=2) :又叫欧式距离,这是最常用的距离度量,仅限于实值向量。 使用下面的公式,可以测量查询点和被测量的另一个点之间的直线。

欧几里得距离公式

        曼哈顿距离(p=1):这也是另一种流行的距离指标,它测量两点之间的绝对值。 也称为出租车距离或城市街区距离,因为它通常用网格可视化,说明人们如何通过城市街道从一个地址导航到另一个地址。

曼哈顿距离公式

        闵可夫斯基距离:闵氏距离不是一种距离,而是一组距离的定义,是对多个距离度量公式的概括性的表述。无论是欧式距离还是曼哈顿距离,都可视为闵可夫斯基距离的一种特例。

闵可夫斯基距离公式

        其中p是一个变参数:

                当p=1时,就是曼哈顿距离;

                当p=2时,就是欧氏距离;

                当p→∞时,就是切比雪夫距离。

        因此,根据变参数的不同,闵氏距离可以表示某一类 / 种的距离。

闵氏距离,包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。


e.g. 二维样本(身高[单位:cm],体重[单位:kg]), 现有三个样本:a(180,50)b(190,50)c(180,60)。那么a与b的闵氏距离(无论是曼哈顿距离、欧氏距离或切比雪夫距离)等于a与c的闵氏距离。但实际上身高的10cm并不能和体重的10kg划等号。


闵氏距离的缺点:
(1)将各个分量的量纲(scale),也就是"单位"相同的看待了;
(2)未考虑各个分量的分布(期望,方差等)可能是不同的。 


(3)归一化处理

        使用 kNN 时需要根据特征数据的取值区间来调整坐标轴的比例,这个做法叫作标准化或者归一化。为什么要这么做呢?拿上面的例子来说,一只兔子的身长(cm)数值平均是它的体重(kg)的 10倍左右,如果我们在这组数值上直接使用闵科夫斯基距离函数的话就会导致横轴的距离比重明显放大,分类结果也不合理,如下图所示:


  如果把坐标轴成其他的单位,比如毫米和吨,并用相应的新数值来计算距离,又会得到完全不同的分类标准。甚至,在极端情况下,如果身高用纳米并且体重用吨计量,那么相比之下身高的数值会奇高无比,以至于两点之间的距离是完全由身高决定的,体重则没有任何权重。为了解决这个问题,我们应该在计算距离时把所有坐标轴进行归一化。
  在之前的例子中,由于横轴数值大约是竖轴的 10 倍左右,所以我们将横轴(身高)的数值压缩 10倍,即计算距离时使用:


(4)概率kNN

        上面的kNN算法返回的是对一组特征的绝对分类,告诉我们这只兔子被判断为哪一个类别。可有时我们并不想知道一个确切地分类,而想知道它属于某个分类的概率是多大。比如我们发现一只身长 37厘米,体重 4.84公斤的小兔兔,在下图五角星的位置。


  这只兔子的特征数据在绿兔和蓝兔的分界处,机器不论判断它属于哪个类别都很有可能是错的。这时,类似“它有一半可能性是绿兔,一半可能性是蓝兔”的反馈会更有意义。
  为了这个目的,我们同样找出距离问题特征最近的k kk个样本,但与其寻找数量最多的分类,我们统计其中每个类别的分别有多少个,再除以k kk得到一个属于每一个类别概率值。比如在上面的图里,距离五角星最近的 15个样本中,有 8只绿兔和 7 只蓝兔,由此判断:它有 53% 的可能性是绿兔,47% 的可能性是蓝兔,0%的可能性是黄兔。
  在整个二维空间中的每一个点上进行概率 kNN 算法,可以得到每个特征点是属于某个类别的概率热力图,图中颜色越深代表概率越大。


                                                                15NN 绿兔的概率                                    
                                                                15NN 黄兔的概率

                                                                 15NN 蓝兔的概率

        相比于绝对的分类,这些概率的计算会给我们更有效的表述以及更多的应用空间。 


KNN算法的优缺点

        就像任何机器学习算法一样,k近邻算法 (KNN) 也有其优点和缺点。 根据项目和应用,它可能是也可能不是正确的选择。

优势

  • 易于实现:鉴于算法的简单性和准确性,它是新数据科学家将学习的首批分类器之一。
  • 轻松适应:随着新训练样本的增加,算法会根据任何新数据进行调整,因为所有训练数据都存储在内存中。
  • 很少的超参数:k近邻算法 (KNN) 只需要 a k 值和距离度量,与其他机器学习算法相比,所需的超参数很少。

缺点

  • 不能很好地扩展:由于 k近邻算法 (KNN) 是一种惰性算法,因此与其他分类器相比,它占用了更多的内存和数据存储。 从时间和金钱的角度来看,这可能是昂贵的。 更多的内存和存储将增加业务开支,而更多的数据可能需要更长的时间来计算。 虽然已经创建了不同的数据结构(例如 Ball-Tree)来解决计算效率低下的问题,但分类器是否理想可能取决于业务问题。
  • 维度的诅咒:k近邻算法 (KNN) 容易成为维度诅咒的受害者,这意味着它在高维数据输入时表现不佳。 这有时也称为峰值现象 ,在算法达到最佳特征数量后,额外的特征会增加分类错误的数量,尤其是当样本尺寸较小时。
  • 容易过拟合:由于"维度的诅咒",k近邻算法 (KNN) 也更容易过拟合。 虽然利用特征选择和降维技术来防止这种情况发生,但 k 的值也会影响模型的行为。 较小的 k 值可能会过度拟合数据,而较大的 k 值往往会"平滑"预测值,因为它是对更大区域或邻域的值进行平均。 但是,如果 k 的值太高,那么可能会欠拟合数。 

        KNN算法作为一种较简单的算法,它的不足之处也明显,由于上述的不足,为了提高kNN搜索的速度,可以利用特殊的数据存储形式来减少计算距离的次数。kd树就是一种以二叉树的形式存储数据的方法。kd树就是对k维空间的一个划分。构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分,构成一系列k维超矩阵区域。kd树的每一个节点对应一个超矩阵区域。(深入了解请参看李航老师的《统计机器学习》P41页)


KNN算法总结

        根据上述对kNN算法原理的解析,可以总结出其实现主要包含以下几个步骤:

  •   (1)计算已知类别数据集中的点与当前点之间的距离;
  •   (2)按照距离递增次序排序;
  •   (3)选取与当前点距离最小的k个点;
  •   (4)确定前k个点所在类别的出现频率;
  •   (5)返回前k个点出现频率最高的类别作为当前点的预测分类。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

农作物害虫检测数据集VOC+YOLO格式18975张97类别

数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):18975 标注数量(xml文件个数):18975 标注数量(txt文件个数):18975 标…

周三多《管理学原理》第3版/考研真题/章节练习题

普通高等教育“十一五”国家级规划教材《管理学原理》(第3版,周三多、陈传明、龙静编著,南京大学出版社)是我国高校广泛采用的管理学权威教材之一,也被众多高校(包括科研机构)指定为考研考博专业…

电脑技巧:推荐一款非常好用的媒体播放器PotPlayer

目录 一、 软件简介 二、功能介绍 2.1 格式兼容性强 2.2 高清播放与硬件加速 2.3 自定义皮肤与界面布局 2.4 多音轨切换与音效增强 2.5 字幕支持与编辑 2.6 视频截图与录像 2.7 网络流媒体播放 三、软件特色 四、使用技巧 五、总结 一、 软件简介 PotPlayer播放器 …

排序-八大排序FollowUp

FollowUp 1.插入排序 (1).直接插入排序 时间复杂度:最坏情况下:0(n^2) 最好情况下:0(n)当数据越有序 排序越快 适用于: 待排序序列 已经基本上趋于有序了! 空间复杂度:0(1) 稳定性:稳定的 public static void insertSort(int[] array){for (int i 1; i < array.length; i…

使用Android Studio 搭建AOSP FrameWork 源码阅读开发环境

文章目录 概述安装Android Studio编译源码使用Android Studio打开源码制作ipr文件直接编译成功后自动打开Android Studio 修改SystemUI验证开发环境 概述 我们都知道Android的系统源码量非常之大&#xff0c;大致有frameworka层源码&#xff0c;硬件层(HAL)源码&#xff0c;内…

能源监控新方案:IEC104转MQTT网关在新能源发电中的应用

需求背景 近些年&#xff0c;我国新能源产业快速发展&#xff0c;光伏、风电等新能源项目高速增长&#xff0c;新能源发电已经成为国家能源结构的重要组成部分。 打造数字化、智能化、信息化的电力物联网系统&#xff0c;实现光伏风电等新能源发电站的远程监控、远程维护是新能…

DRF中的请求入口分析及request对象分析

DRF中的请求入口分析及request对象分析 django restframework框架是在django的基础上又给我们提供了很多方便的功能&#xff0c;让我们可以更便捷基于django开发restful API 1 drf项目 pip install django pip install djangorestframework1.1 核心配置 INSTALLED_APPS [d…

数据库开发关键之与DQL查询语句有关的两个案例

案例 案例1 条件分页查询 查看项目经理提供给我们的需求文档 模糊匹配的含义是 只要包含"张"就可以 use dduo;-- 按照需求完成员工管理的条件分页查询 根据输入条件 查询第一页的数据 每页展示10条记录 -- 输入条件&#xff1a; -- 姓名&#xff1a; 张 -- 年龄&…

【Java】基本程序设计结构(一)

前言&#xff1a;现在&#xff0c;假定已经成功安装了JDK&#xff0c;并且能够运行上篇示例程序。本篇将开始介绍Java程序中的基本设计结构&#xff0c;其中包括&#xff1a;一个简单的Java应用&#xff0c;注释&#xff0c;数据类型&#xff0c;变量与常量&#xff0c;运算符&…

n-Track Studio Suite for Mac激活版:打造您的专属音频工作室

n-Track Studio Suite for Mac是一款功能强大的数字音频工作站软件&#xff0c;让您在家中就能享受到专业录音棚的待遇。无论是录制人声、乐器还是MIDI序列&#xff0c;都能轻松应对。 n-Track Studio Suite for Mac激活版下载 这款软件拥有实时音高校准、时间拉伸和自动补足功…

HT32F52352 -- 解锁电调、电机速度控制

一、问题背景 1.1 硬件&#xff1a; 电池组&#xff0c;电子调速器&#xff08;好盈电调 /ESC&#xff09;&#xff0c;接收机&#xff08;HT32F52352&#xff09;&#xff0c;风扇。 1.2 软件 keil5 二、问题分析 通过1.1图中可知&#xff0c;我们只需要使用 HT32F52352 模拟…

TouchGFX 总结

文章目录 使用中文字体多屏幕间交换数据UI to MCUMCU to UI API文档参考横竖屏切换 使用中文字体 添加一个textArea&#xff0c;默认的英文文本可见&#xff0c;输入中文字体后就看不见了&#xff0c;是因为这个默认的字体不支持中文&#xff0c;改一下字体就可以了&#xff1…

【介绍下有那些常见的ssh功能】

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

使用mapinfo软件的在线地图插件运行错误解决

使用mapinfo软件的在线地图插件运行错误解决 一、如何解决win10/win11家庭版运行MapInfo中的在线地图插件报错【unexpected error&#xff1b;quitting】问题&#xff1f;二、如何解决在线地图切换地图源时的报错问题&#xff1f; 一、如何解决win10/win11家庭版运行MapInfo中的…

java下乡扶贫志愿者招募管理系统springboot-vue

计算机技术在现代管理中的应用&#xff0c;使计算机成为人们应用现代技术的重要工具。能够有效的解决获取信息便捷化、全面化的问题&#xff0c;提高效率。 技术栈 前端&#xff1a;vue.jsElementUI 开发工具&#xff1a;IDEA 或者eclipse都支持 编程语言: java 框架&#xff1…

vue+element-ui实现横向长箭头,横向线上下可自定义文字(使用after伪元素实现箭头)

项目场景&#xff1a; 需要实现一个长箭头&#xff0c;横向线上下可自定义文字 代码描述 <div><span class"data-model">{{ //上方文字}}</span><el-divider class"q"> </el-divider>//分隔线<span class"data-mod…

【UnityRPG游戏制作】Unity_RPG项目_玩法相关

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;就业…

Vitis HLS 学习笔记--Schedule Viewer 调度查看器

目录 1. 简介 2. Schedule Viewer详解 2.1 视图说明 2.1.1 Operation\Control Step 2.1.2 周期关系图 2.1.3 Schedule Viewer 菜单栏 2.1.4 属性视图 2.2 内容说明 2.2.1 实参&#xff08;b&#xff09;解释 2.2.2 实参&#xff08;a&#xff09;解释 2.2.3 变量&am…

【C++】详解STL的容器之一:list

目录 简介 初识list 模型 list容器的优缺点 list的迭代器 常用接口介绍 获取迭代器 begin end empty size front back insert push_front pop_front push_back pop_back clear 源代码思路 节点设计 迭代器的设计 list的设计 begin() end() 空构造 ins…

C# Web控件与数据感应之 TreeView 类

目录 关于 TreeView 一些区别 准备数据源 范例运行环境 一些实用方法 获取数据进行呈现 ​根据ID设置节点 获取所有结点的索引 小结 关于 TreeView 数据感应也即数据捆绑&#xff0c;是一种动态的&#xff0c;Web控件与数据源之间的交互&#xff0c;本文将继续介绍与…