来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。
k-近邻（k-Nearest Neighbor, 简称 kNN）是一种常见的监督学习算法，它是 Cover T 和 Hart P 在 1967 年提出的一种既可以用于分类，也可以用于回归的学习方法。它的工作原理非常简单：用一句古话来说就是，“近朱者赤，近墨者黑”，给定测试样本，基于某种距离度量找出训练集中与其最靠近的 k 个训练样本，这 k 个距离最近的样本就是 k-Nearest Neighbor。如果是在分类任务中，我们把这 k 个样本中出现最多的类别作为预测结果；如果是在回归任务中，我们把这 k 个样本的平均值作为预测结果。一般情况下，用 kNN 处理回归问题比较少见，我们这一节使用 kNN 解决分类问题。
如上图所示，这是一个简单的分类任务，有两类不同的样本数据，分别用蓝色正方形和红色三角形表示，而图正中间的那个绿色的圆点则是待分类的数据。使用 kNN 来解决这个问题的基本思路是，从样本数据中找出距离绿色圆点最近的 k 个数据，然后看这 k 个数据中哪个类别出现的最多。可以看出，当 k = 3 时，有 2 个红色三角形和 1 个蓝色正方形，可以判定绿色圆点和红色三角形一类；但是当 k = 5 时，有 2 个红色三角形和 3 个蓝色正方形，可以判定绿色圆点和蓝色正方形一类。所以，在 kNN 算法中 k 值的选择很重要。
在李航的《统计学习方法》中，将 k值的选择、距离度量 和 分类决策规则 作为 kNN 算法的三个基本要素：
- 首先是参数 k，它是一个超参数，它的取值对分类结果有着显著的影响，所以一般会通过交叉验证法，选择不同的 k 值进行计算，最后取一个分类结果最好的 k 值；
- 其次是距离度量的方法，最常用的是欧氏距离，除此之外，还有切比雪夫距离、马氏距离、巴氏距离等，要根据实际求解的问题来选择；
- 最后是分类决策规则，通常使用多数表决规则（majority voting rule），即将 k 个最近的样本中出现最多的类别作为预测结果。
要注意的是，kNN 算法没有显式的训练过程，它的训练开销为零，这种学习算法又被称为 懒惰学习（lazy learning），相反的，那些有训练过程的算法被称为 急切学习（eager learning）。
kNN 优缺点
- 优点
- 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
- 可用于数值型数据和离散型数据；
- 训练时间复杂度为O(n)；无数据输入假定；
- 对异常值不敏感；
- 缺点
- 计算复杂性高；空间复杂性高；
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
- 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分；
- 最大的缺点是无法给出数据的内在含义；