knn邻近算法

Ⅰ knn算法是什么

KNN（K- Nearest Neighbor）法即K最邻近法，最初由Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。

作为一种非参数的分类算法，K-近邻（KNN）算法是非常有效和容易实现的。它已经广泛应用于分类、回归和模式识别等。

介绍

KNN算法本身简单有效，它是一种lazy-learning算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么KNN的分类时间复杂度为O(n)。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

Ⅱ knn是什么意思

knn是邻近算法，或者说K最邻近分类算法，全称为K-NearestNeighbor，是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，是K个最近的邻居的意思，说的是每个样本都可以用最接近的K个邻近值来代表。近邻算法是将数据集合中每一个记录进行分类的方法。

knn算法的核心思想：

如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

Ⅲ 01 KNN算法 - 概述

KNN算法 全称是K近邻算法 （K-nearst neighbors，KNN）

KNN是一种基本的机器学习算法，所谓K近邻，就是k个最近的邻居。即每个样本都可以用和它 最接近的k个邻近位置的样本 来代替。

KNN是个相对比较简单的算法，比起之前提过的回归算法和分类算法更容易。如果一个人从来没有接触过机器学习的算法，拿到数据后最容易想到的分类方式就是K近邻。打个比方：你们想了解我是个怎样的人，然后你们发现我的身边关系最密切的朋友是一群逗逼，所以你们可以默认我也是一个逗逼。

KNN算法即可以应用于 分类算法 中，也可以应用于 回归算法 中。

KNN在做回归和分类的主要区别，在于最后做预测时候的决策不同。在分类预测时，一般采用 多数表决法 。在做回归预测时，一般使用 平均值法 。

多数表决法： 分类时，哪些样本离我的目标样本比较近，即目标样本离哪个分类的样本更接近。

平均值法： 预测一个样本的平均身高，观察目标样本周围的其他样本的平均身高，我们认为平均身高是目标样本的身高。

再举个例子：
分别根据甜度和脆度两个特征来判断食物的种类。
根据样本我们普遍发现：
比较甜，比较脆的食物都是水果。
不甜，不太脆的食物是蛋白质。
不甜，比较脆的食物是蔬菜。
于是根据目标的样本甜度和脆度两个特征，我们可以对其进行分类了。

k值的选择:
先选一个较小的值，然后通过交叉验证选择一个合适的最终值。
k越小，即使用较小的领域中的样本进行预测，训练误差会减小，但模型会很复杂，以至于过拟合。
k越大，即使用交大的领域中的样本进行预测，训练误差会增大，模型会变得简单，容易导致欠拟合。

距离的度量:
使用欧几里得距离：欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

决策规划:
分类：多数表决法、加权多数表决法。
回归：平均值法、加权平均值法。

加权多数表决法：

平均值法和加权平均值法：
同样看上面的图，上方的三个样本值为3，下面两个样本值为2，预测？的值。
如果不考虑加权，直接计算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6

加权平均值：权重分别为1/7和2/7。计算加权平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43

1、蛮力实现(brute)：
计算预测样本到所有训练集样本的距离，然后选择最小的k个距离，即可得到k个最邻近点。
缺点：当特征数多、样本数多时，算法的效率比较低。

2、KD树 (kd_tree)：
首先对训练数据进行建模，构建KD树，然后根据建好的模型来获取邻近样本数据。
后续内容会介绍KD树搜索最小值的方式，让大家直观感受到KD树比蛮力实现要少检索多少数据。

Ⅳ K-近邻算法（KNN）

简单地说，K-近邻算法采用测量不同特征值之间的距离方法进行分类。

欧氏距离是最常见的距离度量，衡量的是多维空间中各个点之间的绝对距离。公式如下：

身高、体重、鞋子尺码数据对应性别

导包，机器学习的算法KNN、数据鸢尾花

获取训练样本 datasets.load_iris()

画图研究前两个特征和分类之间的关系（二维散点图只能展示两个维度）

第二步预测数据：所预测的数据，自己创造，就是上面所显示图片的背景点

生成预测数据

对数据进行预测

ocr 光学字符识别（Optical Character Recognition） 我们先做一个基础班：识别数字

Ⅳ 什么是knn算法

作为一种非参数的分类算法，K-近邻（KNN）算法是非常有效和容易实现的。它已经广泛应用于分类、回归和模式识别等。在应用KNN算法解决问题的时候，要注意两个方面的问题——样本权重和特征权重。利用SVM来确定特征的权重，提出了基于SVM的特征加权算法（FWKNN,feature
weighted
KNN）。实验表明，在一定的条件下，FWKNN能够极大地提高分类准确率。

Ⅵ kNN（k-NearestNeighbor）算法

参考《数据挖掘10大算法》对kNN算法进行基本总结，附有一个Python3的简例。

基本思想
从训练集中找出 k 个最接近测试对象的训练对象，再从这 k 个对象中找出居于主导的类别，将其赋给测试对象。

定位
由于这种总体占优的决策模式，对于类域的交叉、重叠较多的或者多模型、多标签的待分样本集来说，kNN方法较其他方法更为适合。kNN算法属于有监督学习的分类算法。

避开了两个问题
（1）分类时对象之间不可能完全匹配（kNN方法计算的是对象之间的距离）；
（2）具有相同属性的对象有不同的类别（kNN方法依据总体占优的类别进行决策，而不是单一对象的类别进行决策）。

需要考虑几个关键要素
（1）训练集；
（2）用于计算对象之间临近的程度或者其他相似的指标；
（3）最近邻的个数 k；
（4）基于 k 个最近邻及其类别对目标对象类别进行判定的方法。

kNN方法很容易理解和实现，在一定条件下，其分类错误率不会超过最优贝叶斯错误率的两倍。一般情况下，kNN方法的错误率会逐渐收敛到最优贝叶斯错误率，可以用作后者的近似。

基本算法

算法的存储复杂度为O(n)，时间复杂度为O(n)，其中 n 为训练对象的数量。

影响kNN算法性能的几个关键因素
（1）k 值的选择；
如果 k 值选得过小，结果就会对噪声点特别敏感；k 值选得过大就会使得近邻中包含太多别的类的点。最佳 k 值的估计可以使用交叉验证的方法。通常，使用 k=1会有一个比较好的结果（特别是对于小数据集的情况）。但是，在样本很充足的情况下，选择较大的 k 值可以提高抗噪能力。

（2）类别决策时的综合方法；
对目标对象的类别进行决策，最简单的就是使用总体占优方法（简单投票，票数最多的一类胜出）。稍微复杂一点，考虑近邻中每个点与目标对象的距离不同，对决策的份量进行加权考虑。

（3）距离测量标准的选择。
距离测量的标准一般选择 欧几里得距离 或者 曼哈顿距离 。

简单例子

Ⅶ K-近邻算法简介

1.K-近邻(KNearestNeighbor,KNN)算法简介 ：对于一个未知的样本，我们可以根据离它最近的k个样本的类别来判断它的类别。

以下图为例，对于一个未知样本绿色小圆，我们可以选取离它最近的3的样本，其中包含了2个红色三角形，1个蓝色正方形，那么我们可以判断绿色小圆属于红色三角形这一类。
我们也可以选取离它最近的5个样本，其中包含了3个蓝色正方形，2个红色三角形，那么我们可以判断绿色小圆属于蓝色正方形这一类。

3.API文档

下面我们来对KNN算法中的参数项做一个解释说明：

'n_neighbors'：选取的参考对象的个数（邻居个数），默认值为5，也可以自己指定数值，但不是n_neighbors的值越大分类效果越好，最佳值需要我们做一个验证。
'weights': 距离的权重参数，默认uniform。
'uniform': 均匀的权重，所有的点在每一个类别中的权重是一样的。简单的说，就是每个点的重要性都是一样的。
'distance'：权重与距离的倒数成正比，距离近的点重要性更高，对于结果的影响也更大。
'algorithm':运算方法，默认auto。
'auto'：根绝模型fit的数据自动选择最合适的运算方法。
'ball_tree'：树模型算法BallTree
'kd_tree'：树模型算法KDTree
'brute'：暴力算法
'leaf_size'：叶子的尺寸，默认30。只有当algorithm = 'ball_tree' or 'kd_tree'，这个参数需要设定。
'p'：闵可斯基距离，当p = 1时，选择曼哈顿距离；当p = 2时，选择欧式距离。
n_jobs：使用计算机处理器数目，默认为1。当n=-1时，使用所有的处理器进行运算。

4.应用案例演示
下面以Sklearn库中自带的数据集--手写数字识别数据集为例，来测试下kNN算法。上一章，我们简单的介绍了机器学习的一般步骤：加载数据集 - 训练模型 - 结果预测 - 保存模型。这一章我们还是按照这个步骤来执行。
[手写数字识别数据集] https://scikit-learn.org/stable/moles/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits

5.模型的方法
每一种模型都有一些它独有的属性方法（模型的技能，能做些什么事），下面我们来了解下knn算法常用的的属性方法。

6.knn算法的优缺点
优点：
简单，效果还不错，适合多分类问题
缺点：
效率低（因为要计算预测样本距离每个样本点的距离，然后排序），效率会随着样本量的增加而降低。