特别说明：文中含有大量公式，只能转化为图片后才能正常显示，造成阅读不畅请谅解。

​目录

1.KNN简介

2.KNN算法步骤

3.决策边界

4.K的选择

5.要注意的问题

6.小结

1.KNN简介

KNN（K-NearestNeighbor）是机器学习入门级的分类算法，非常非常简单。

上一篇我们讲过Kmeans，初学者常常把这两者搞混，虽然KNN是有监督算法，Kmeans是无监督算法，但KNN和Kmeans确实有相同之处：

· 两者都有"近朱者赤近墨者黑"的思想，将距离近的样本点划为同一类别；

虽然两者名称中都有"K"，但是：

· KNN中的K指的是近邻个数，也就是最近的K个点 ；

· Kmeans中的K指的是最终聚类的个数，也就是要将所有点分成K类。

2.KNN算法步骤

我们有一堆样本点，类别已知，如下图左，蓝色为一类，黄色为另一类。现在有个新样本点，也就是图中黑色的叉叉，需要判断它属于哪一类。

KNN做的就是选出距离目标点黑叉叉距离最近的k个点，看这k个点的大多数颜色是什么颜色。这里的距离怎么定义？当然还是可以用我们的老朋友——欧氏距离来度量。

当我们设定k=1时，距离目标点最近的点是黄色，就认为目标点属于黄色那类。当k设为3时，我们可以看到距离最近的三个点，有两个是蓝色，一个是黄色，因此认为目标点属于蓝色的一类。

所以，K的选择不同，得到的结果也会不同，那么最佳的K要怎么确定呢？

3.决策边界

为了理解K对模型的影响，要先说说决策边界这个概念。

还记之前讲的SVM中的线性分类器吗？WX+b=0就是SVM中的决策边界。在二分类问题中，决策边界就把空间划为两部分，两边就对应着两类。

KNN的决策边界一般不是线性的，也就是说KNN是一种非线性分类器，如下图。

K越小越容易过拟合，当K=1时，这时只根据单个近邻进行预测，如果离目标点最近的一个点是噪声，就会出错，此时模型复杂度高，稳健性低，决策边界崎岖。

但是如果K取的过大，这时与目标点较远的样本点也会对预测起作用，就会导致欠拟合，此时模型变得简单，决策边界变平滑。

如果K=N的时候，那么就是取全部的样本点，这样预测新点时，最终结果都是取所有样本点中某分类下最多的点，分类模型就完全失效了。

上图绿线展示的是随着K减小，测试误差值（之前介绍过，回归问题中误差值一般用均方误差，分类问题中误差值指的就是错判率）的变化，我们的目标就是找到测试误差最小时对应的K值。

4.K的选择

找合适的K的过程，也就是"调参"的过程，比较经典的方法是N折交叉验证。

上图展示的是5折交叉验证，也就是将已知样本集等分为5份，其中4份作为训练集，1份为验证集，做出5个模型。

具体来说：

1. 把样本集分成5个小的子集，编号为set1、set2、set3、set4、set5；

2. 先用set1、set2、set3、set4建模，得到model1，并在set5上计算误差error1；

3. 在用set1、set2、set3、set5建模，得到model2，并在set4上计算误差error2；

4. 重复以上步骤，建立5个模型，将5个误差值相加后除以5得到平均误差。

了解完交叉验证是什么，我们就可以从k=1开始尝试，计算K=1时的平均误差值，每次K增加2，最终能选到产生最小误差值的K（因为随着K变大，误差值会先变小后变大嘛）。

为什么是每次增加2？因为K最好取奇数。还是用最开始那个例子，如果K取4，最近的4个点有2个蓝色，2个黄色，这时打成了平手，就不好判断目标点属于哪一类了。

5.要注意的问题

第一个要注意的点——标准化！标准化！标准化！

第二个要点，KNN实际上是没有训练过程的，因此也没有模型参数（训练数据时就在学习这个参数）。KNN在验证过程中计算验证样本点和已知样本点的距离，这时在学习超参数K，超参数是模型外面的参数。

最后一点，前面我们说的都是用KNN算法解决分类问题，但它同样可以用来处理回归问题，思路也一样，根据K个邻居的Y的平均值（或众数）求未知样本的Y，就将分类问题就转换成了回归问题了。

6.小结

KNN的优点在于原理简单，容易实现，对于边界不规则数据的分类效果好于线性分类器。

当然，也有一些缺点：

· 要保存全部数据集，需要大量的存储空间；

· 需要计算每个未知点到全部已知点的距离，非常耗时；

· 对于不平衡数据效果不好，需要进行改进；

· 不适用于特征空间维度高的情况。

文中图片的水印网址为本人CSDN博客地址