第六章-K近邻

第6章k 近邻算法k 近邻算法（kNN 算法）由Thomas 等人在1967年提出[1]。

它基于以下朴素思想：要确定一个样本的类别，可以计算它与所有训练样本的距离，然后找出和该样本最接近的k 个样本，统计这些样本的类别进行投票，票数最多的那个类就是分类结果。

因为直接比较待预测样本和训练样本的距离，kNN 算法也被称为基于实例的算法。

6.1基本概念确定样本所属类别的一种最简单的方法是直接比较它和所有训练样本的相似度，然后将其归类为最相似的样本所属的那个类，这是一种模板匹配的思想。

k 近邻算法采用了这种思路，下图6.1是使用k 近邻思想进行分类的一个例子：图6.1k 近邻分类示意图在上图中有红色和绿色两类样本。

对于待分类样本即图中的黑色点，我们寻找离该样本最近的一部分训练样本，在图中是以这个矩形样本为圆心的某一圆范围内的所有样本。

然后统计这些样本所属的类别，在这里红色点有12个，绿色有2个，因此把这个样本判定为红色这一类。

上面的例子是二分类的情况，我们可以推广到多类，k 近邻算法天然支持多类分类问题。

6.2预测算法k 近邻算法没有要求解的模型参数，因此没有训练过程，参数k 由人工指定。

它在预测时才会计算待预测样本与训练样本的距离。

对于分类问题，给定l 个训练样本(),i i y x ，其中i x 为维特征向量，i y 为标签值，设定参数k ，假设类型数为c ，待分类样本的特征向量为x 。

预测算法的流程为：1.在训练样本集中找出离x 最近的k 个样本，假设这些样本的集合为N 。

2.统计集合N 中每一类样本的个数,1,...,i C i c =。

3.最终的分类结果为arg max i i C 。

在这里arg max i i C 表示最大的i C 值对应的那个类i 。

如果1k =，k 近邻算法退化成最近邻算法。

k 近邻算法实现简单，缺点是当训练样本数大、特征向量维数很高时计算复杂度高。

因为每次预测时要计算待预测样本和每一个训练样本的距离，而且要对距离进行排序找到最近的k 个样本。

K最近邻算法K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。

所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。

kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。

该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

kNN方法在类别决策时，只与极少量的相邻样本有关。

由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

KNN算法的机器学习基础显示相似数据点通常如何彼此靠近存在的图像大多数情况下，相似的数据点彼此接近。

KNN算法就是基于这个假设以使算法有用。

KNN利用与我们童年时可能学过的一些数学相似的想法(有时称为距离、接近度或接近度)，即计算图上点之间的距离。

例如，直线距离(也称为欧氏距离)是一个流行且熟悉的选择。

KNN通过查找查询和数据中所有示例之间的距离来工作，选择最接近查询的指定数字示例( K )，然后选择最常用的标签(在分类的情况下)或平均标签(在回归的情况下)。

在分类和回归的情况下，我们看到为我们的数据选择正确的K是通过尝试几个K并选择最有效的一个来完成的。

KNN算法的步骤1.加载数据2.将K初始化为你选择的邻居数量3.对于数据中的每个示例4.3.1 根据数据计算查询示例和当前示例之间的距离。

5.3.2 将示例的距离和索引添加到有序集合中6.按距离将距离和索引的有序集合从最小到最大(按升序)排序7.从已排序的集合中挑选前K个条目8.获取所选K个条目的标签9.如果回归，返回K个标签的平均值10.如果分类，返回K个标签的模式'为K选择正确的值为了选择适合你的数据的K，我们用不同的K值运行了几次KNN算法，并选择K来减少我们遇到的错误数量，同时保持算法在给定之前从未见过的数据时准确预测的能力。

机器学习--K近邻（KNN）算法的原理及优缺点⼀、KNN算法原理 K近邻法(k-nearst neighbors,KNN)是⼀种很基本的机器学习⽅法。

它的基本思想是：在训练集中数据和标签已知的情况下，输⼊测试数据，将测试数据的特征与训练集中对应的特征进⾏相互⽐较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类。

由于KNN⽅法主要靠周围有限的邻近的样本，⽽不是靠判别类域的⽅法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN⽅法较其他⽅法更为适合。

KNN算法不仅可以⽤于分类，还可以⽤于回归。

通过找出⼀个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。

更有⽤的⽅法是将不同距离的邻居对该样本产⽣的影响给予不同的权值(weight)，如权值与距离成反⽐。

KNN算法的描述： （1）计算测试数据与各个训练数据之间的距离； （2）按照距离的递增关系进⾏排序； （3）选取距离最⼩的K个点； （4）确定前K个点所在类别的出现频率 (5）返回前K个点中出现频率最⾼的类别作为测试数据的预测分类。

算法流程： （1）准备数据，对数据进⾏预处理。

（2）选⽤合适的数据结构存储训练数据和测试元组。

（3）设定参数，如k。

（4）维护⼀个⼤⼩为k的的按距离由⼤到⼩的优先级队列，⽤于存储最近邻训练元组。

随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存⼊优先级队列。

（5）遍历训练元组集，计算当前训练元组与测试。

元组的距离，将所得距离L 与优先级队列中的最⼤距离Lmax。

（6）进⾏⽐较。

若L>=Lmax，则舍弃该元组，遍历下⼀个元组。

若L < Lmax，删除优先级队列中最⼤距离的元组，将当前训练元组存⼊优先级队列。

（7）遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别。

第一部分、K近邻算法1.1、什么是K近邻算法何谓K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。

为何要找邻居？打个比方来说，假设你来到一个陌生的村庄，现在你要找到与你有着相似特征的人群融入他们，所谓入伙。

用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

根据这个说法，咱们来看下引自维基百科上的一幅图：如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。

也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。

我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。

我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。

但一次性看多少个邻居呢？从上图中，你还能看到：∙如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

∙如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。

这就是K近邻算法的核心思想。

1.2、近邻的距离度量表示法上文第一节，我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。

k近邻算法应用k近邻算法应用于现代机器学习的领域广泛。

它可以用于解决分类问题和回归问题。

本文将会对k近邻算法进行详细介绍，并探讨它的应用。

一、什么是k近邻算法？k近邻算法是一种非参数算法，它基于实例进行学习。

在k近邻算法中，分类标记给实例是依据一个特征空间中邻近的k个训练实例的多数分类。

在回归问题中，输出值是邻近的k个实例的平均值。

二、k近邻算法的应用1. 图像分类k近邻算法可用于图像分类中。

基于这种算法，先对对待测图像计算特征向量，然后找到一个能最小化距离度量的簇分类该向量。

这种分类器能够对图像的种类进行非常准确的分类。

2. 疾病预测k近邻算法也是一种用于预测疾病的方法。

它可以根据患者的特征和疾病的症状，找到临床数据库中其他病例的最相似的病例，从而制定出最佳的治疗方案。

3. 个性化推荐k近邻算法可用于实现个性化推荐系统。

它能够通过分析用户的购买历史，找到与之最相似的消费者，然后建议类似的产品给他们。

三、k近邻算法的优点和缺点1. 优点- k近邻算法简单有效，精度高。

- k近邻算法无需假设数据分布模型，因此适用性很广。

- k近邻算法的训练过程快速简单，通常只需存储数据即可。

2. 缺点- k近邻算法的复杂度随着样本增长而增长很快。

- k近邻算法对训练数据中的噪声敏感。

- k近邻算法在处理高维数据时效率较低。

四、结论总的来说，k近邻算法是一种很重要的机器学习方法，它经常被应用于分类、回归和其他任务中。

在实际应用时，根据具体情况选择一个合适的k值是很重要的，因为k值的选择直接影响到算法的准确度和性能。

k近邻算法概念嘿，朋友！今天咱们来聊聊一个挺有意思的东西——K 近邻算法。

你知道吗，这 K 近邻算法就像是你在陌生城市找路时，向身边几个看起来靠谱的路人打听。

比如说你在一个错综复杂的胡同里迷路了，不知道该往哪儿走，这时候你看到前面有几个人，你就问问他们，然后根据他们给你的建议来决定自己的方向。

K 近邻算法也是这么个理儿。

它是通过看离给定数据点最近的那几个“邻居”来做出判断或者预测。

这几个“邻居”就像是给你指路的热心路人。

那怎么确定谁是这“邻居”呢？这就好比选朋友，得有个标准。

在 K近邻算法里，这个标准通常是距离。

距离的计算方法有好多，就像不同人衡量朋友亲疏的方式不一样。

比如说，我们有一堆数据，就像一个班级里的同学们的成绩和身高。

现在来了一个新同学，我们想知道他的成绩大概会怎么样。

这时候 K近邻算法就出马啦，它会看看在成绩和身高这个“空间”里，离这个新同学最近的那几个同学的成绩，然后根据他们的成绩来推测新同学的成绩。

你说这是不是挺神奇？这就好像是在茫茫数据的大海里，找到了和目标最相似的那几个“小伙伴”，然后从它们身上获取有用的信息。

再比如说，你要预测明天的天气。

K 近邻算法就会去找历史上和明天相似的那些天，看看那些天的天气情况，然后告诉你一个可能的结果。

这是不是有点像翻老黄历，但可比老黄历靠谱多啦！不过，这 K 近邻算法也不是完美无缺的。

就像你问路人指路，万一他们也不太清楚或者故意给你指错了呢？K 近邻算法也可能会因为数据的质量不好，或者选择的“邻居”数量不合适，给出不太准确的结果。

那怎么解决这些问题呢？这就得靠咱们不断地去调整和优化啦，就像你在不断地学习怎么分辨靠谱的路人一样。

总的来说，K 近邻算法是个挺有用的工具，能在很多领域帮咱们做出预测和判断。

咱们得好好琢磨它，让它更好地为咱们服务！。