用人话讲明白近邻算法KNN
目录
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个点的大多数颜色是什么颜色。这里的距离怎么定义？当然还是可以用我们的老朋友——欧氏距离来度量。
给定两个样本
与
，其中n表示特征数 ，X和Y两个向量间的欧氏距离(Euclidean Distance)表示为：
当我们设定k=1时，距离目标点最近的点是黄色，就认为目标点属于黄色那类。当k设为3时，我们可以看到距离最近的三个点，有两个是蓝色，一个是黄色，因此认为目标点属于蓝色的一类。
所以，K的选择不同，得到的结果也会不同，那么最佳的K要怎么确定呢？
3.决策边界
为了理解K对模型的影响，要先说说决策边界这个概念。
还记之前讲的SVM中的线性分类器吗？WX+b=0就是SVM中的决策边界。在二分类问题中，决策边界就把空间划为两部分，两边就对应着两类。
KNN的决策边界一般不是线性的，也就是说KNN是一种非线性分类器，如下图。
image
K越小越容易过拟合，当K=1时，这时只根据单个近邻进行预测，如果离目标点最近的一个点是噪声，就会出错，此时模型复杂度高，稳健性低，决策边界崎岖。
但是如果K取的过大，这时与目标点较远的样本点也会对预测起作用，就会导致欠拟合，此时模型变得简单，决策边界变平滑。
如果K=N的时候，那么就是取全部的样本点，这样预测新点时，最终结果都是取所有样本点中某分类下最多的点，分类模型就完全失效了。
上图绿线展示的是随着K减小，测试误差值（之前介绍过，回归问题中误差值一般用均方误差，分类问题中误差值指的就是错判率）的变化，我们的目标就是找到测试误差最小时对应的K值。
4.K的选择
找合适的K的过程，也就是“调参”的过程，比较经典的方法是N折交叉验证。
上图展示的是5折交叉验证，也就是将已知样本集等分为5份，其中4份作为训练集，1份为验证集，做出5个模型。
具体来说：
- 把样本集分成5个小的子集，编号为set1、set2、set3、set4、set5；
- 先用set1、set2、set3、set4建模，得到model1，并在set5上计算误差error1；
- 在用set1、set2、set3、set5建模，得到model2，并在set4上计算误差error2；
- 重复以上步骤，建立5个模型，将5个误差值相加后除以5得到平均误差。
了解完交叉验证是什么，我们就可以从k=1开始尝试，计算K=1时的平均误差值，每次K增加2，最终能选到产生最小误差值的K（因为随着K变大，误差值会先变小后变大嘛）。
为什么是每次增加2？因为K最好取奇数。还是用最开始那个例子，如果K取4，最近的4个点有2个蓝色，2个黄色，这时打成了平手，就不好判断目标点属于哪一类了。
5.要注意的问题
第一个要注意的点——标准化！标准化！标准化！
假设我们有两个样本点，有两个特征值，X=(1,200)，Y=(2,300)，如果不做标准化，他们的欧式距离就是。这样计算的距离就会受第二个特征的影响特别大，因为第一个特征的量级与第二个相比太小了。
既可以用极差法消除量级：
也可以采用标准差标准化：
第二个要点，KNN实际上是没有训练过程的，因此也没有模型参数（训练数据时就在学习这个参数）。KNN在验证过程中计算验证样本点和已知样本点的距离，这时在学习超参数K，超参数是模型外面的参数。
最后一点，前面我们说的都是用KNN算法解决分类问题，但它同样可以用来处理回归问题，思路也一样，根据K个邻居的Y的平均值（或众数）求未知样本的Y，就将分类问题就转换成了回归问题了。
6.小结
KNN的优点在于原理简单，容易实现，对于边界不规则数据的分类效果好于线性分类器。
当然，也有一些缺点：
- 要保存全部数据集，需要大量的存储空间；
- 需要计算每个未知点到全部已知点的距离，非常耗时；
- 对于不平衡数据效果不好，需要进行改进；
- 不适用于特征空间维度高的情况。
文中图片的水印网址为本人CSDN博客地址：BeSimple
