K最近邻(k-Nearest Neighbour，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

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

注意：KNN在图像分类中表现不好。

一旦我们用KNN来区分图片的时候，得先找到计算图片差异的方法，比如L1距离，这个计算的是两幅图片所有像素之间的差的绝对值的总和，此计算方法对坐标比较依赖，一旦改变了坐标，这个值就不一样了，以此不是很可靠；但是另外一种常见的选择是L2距离，也就是欧式距离，求的是图片的所有像素的差的平方和的平方根，这个值就不再依赖于坐标系，比较可靠了。如果你输入的特征向量，如果向量中的一些值有一些重要的意义，那么也许L1可能更加合适；但是如果它只是某个空间中的一个通用向量，而你不知道其中的不同的元素，你不知道它们实际上代表的含义，那么L2可能更加自然一些。我们可以使用不同的距离度量将KNN分类器泛化到许多不同的数据类型上，不仅仅是向量和图像，比如想对文本进行分类，那么你唯一需要做的就是对KNN指定一个距离函数，这个函数可以测量两段话或者两句话或者类似的东西之间的距离。因此，简单地通过指定不同的距离度量，我们便可以很好地应用这个算法，在基本上任何类型的数据上，尽管这是一种简单的算法，但是总的来说，当你研究一个新的问题的时候，尝试它是一件很好的事情。

在几何上，我们使用不同的记录度量的时候，会出现不同的决策边界。使用L1度量时，这些决策边界倾向于跟随坐标轴，而根据L2度量的决策边界就自然很多。

当我们选择不同的K值以及不同的距离度量的时候，这个决策边界就不同，那么我们怎么根据自己的数据来选择这些超参数呢？超参数就是不能通过训练数据而得到的参数。我们要提前为算法做出的选择。很多人的做法就是根据自己的数据，选择不同的超参数，然后进行训练，看哪一个值是最好的。但是其实这个一种非常糟糕的算法，比如，在之前的KNN算法中，假如K=1，我们总能完美分类训练数据，所以如果我们采用这一策略总是选择K=1，但是如之前的案例所见的，在实践中让K取更大的值，尽管会在训练集中分错个别数据，但对于在训练集中出现过的数据分类性能更佳。归根到底在机器学习中我们关心的不是尽可能拟合训练集，而是要让我们的分类器、我们的算法，在训练集之外的未知数据上表现得更好。

还有一种想法就是把所有的数据，分成训练数据和测试数据两个部分，然后在训练集上使用不同的超参数来训练算法，然后将训练好的分类器用在测试集上。再选择一组在测试集上表现最好的超参数。这种做法同样很糟糕，因为机器学习系统的目的是让我们理解算法表现究竟如何，所以测试集的目的，是给我们一种预估方法。如果采用这种使用不同的超参数训练不同算法的策略，然后选择在测试集上表现最好的超参数，那么有可能我们选择了一直超参数只是让我们的算法在这组测试集上表现良好，但是这组测试集的表现，无法代表在全新的未见过的数据上的表现，所以再说一遍不要这么做，这个想法很糟糕。更常见的额做法是将数据分成三部分，大部分作为训练集，然后分成一部分作为验证集，剩下的一部分作为测试集。我们通常所做的就是在训练集上用不同的超参来训练算法，在验证集上进行评估，然后用一组超参数，选择在验证集上表现最好的分类器。当完成了这些步骤之后，我们就完成了所有的测试。再把这组在验证集上表现最佳的分类器拿出来，在测试集上跑，这个才是你需要写到论文中的数据。因此我们必须分类验证数据和测试数据。

另外一个设定超参数的办法是交叉验证。这在小数据集中更常用一些。在深度学习中不那么常用。它的理念是我们取出整个数据，然后将整个数据集中的部分数据保留作为最后使用的测试集，然后剩余部分，不是分成一个训练集合验证集，而是将训练数据分成很多份，在这种情况下，我们轮流将每一份当做验证集，用一组超参数来训练你的算法，现在前4份上训练，在第五份上验证，然后再次训练算法，在1、2、3、5份上训练，在第4份上验证，然后对不同分进行循环，当这么做了你会有更强的信心，哪组超参数的表现更稳定。所以这似乎是一种黄金法则，但是事实上，在深度学习中，当我们训练大型模型时，训练本身非常消耗计算能力，因此这些方法实际上不常用。

一般的做法是将收集到的数据随机打乱，然后随机分成训练集、验证集、测试集。最后你会根据验证集上的表现选择相应的K值和超参数。

但是KNN很少用在图像分类中，首先是它在测试时运算时间比较长，这和我们刚刚提到的需求不符。另外一个问题是像L2或者L1距离的衡量标准，用在比较图像上不合适。这种向量化的距离函数，不太适合表示图像之间视觉的相似度。究竟我们是如何区分图像中的不同的呢？比如原始图片是左边这位女士的图片，需要对比的图片是右边三张经过不同处理的图片，如果计算原图和后面三张图之间的L2距离，其值是一样的。但是这并不是我们想要的，因此L2不适合用来表示图像之间视觉感知的差异。

KNN算法还有另外一个问题，计算维度灾难。根据KNN的描述，它有点像是用训练数据，把样本空间分成几块，这意味着如果我们希望分类器有好的效果，我们需要训练数据能够密集地分布在空间中，否则最近邻点的实际距离可能很远，也就是说和待测样本的相似性没有那么高。而问题在于想要密集地分布在空间中，我们需要指数倍的训练数据，我们不可能拿到那么多的图片去密布到整个空间中。

注意：维度灾难

假设样本点取n维，样本选取的标准是为了覆盖总体20%的范围特征。 
我们假设样本点每个维度都有10个可能的取值。 
1. 当n为1时 
则总体数量为10，只需要2个样本就能覆盖总体的20% 
2. 当n取2时 
有两个维度，这时总体的数量变为100（10*10），那么就需要20只了。 
3. 当取n时 
共有10n个数量，样本应取10n∗0.2个。 
注意，这与我们平时理解的总体不一样。 
因为总体的数量从一开始就是固定的，比如，全世界有1亿只苍蝇，如果只需要拿红眼和白眼来作为区分，那么可能取5只就够了，但如果增加属性的维度，比如在增加翅膀长度，个体大小，年龄，那么需要的果蝇数量将呈指数级增长。这是导致维度灾难的主要原因。 
从这个意义上说，不仅是knn,其他分类算法都会遇到维度灾难的问题。