零、摘要
本篇文章主要讲述KNN算法（K-nearest neighbor）的原理与技术细节，并简单提及了数据预处理的方法。
主要参考资料:
斯坦福CS231n课程笔记：分类《机器学习》周志华《机器学习实战》Peter Harrington维基百科：K-nearest_neighbors_algorithm
一、从1NN到KNN
近朱者赤，近墨者黑
考虑这样一个问题：给定平面上十个点，其中五个红色的点，五个黑色的点。现在要求预测虚线描出的点属于哪一个类别。当然对于我们人类来说，显然能断定这一点更有可能是红色的，但是我们应该怎样设计一个算法让机器也这样认为呢？
我们可以这样做：
计算虚线圈出的点与给定的所有点之间的距离找出与他距离最小的那个点距离最小的点是什么颜色，则预测所求点是什么颜色
A点距离最短，是红色的，断定所求点应该是红色的。这就使1NN即最近邻算法。
为了更好地理解最近邻算法，我们做这样一件事情：在这个平面的所有位置都摆放一次要预测的点，然后用1NN算法对他们进行预测。预测的点布满整个平面后，我们就能得到两个区域：
如果要预测的点出现在红色边界线左边的黑色区域里面，那么他就会被预测为黑色，对于右侧区域同理。从这张图来看，我们的1NN分类器表现得还不错。
但是如果我们换一个点集，再做一次同样的事情呢？我们得到下面图里的结果：
显然，点B有可能是统计数据时因为马虎出现的错误，我们通常称他为噪声。点B附近的那一小块区域看起来更应该属于黑色才对。那么我们怎么让机器也这样认为呢？
考虑这样一个方法：
- 计算要预测的点与给定的所有点之间的距离
- 找出与他距离最小的K个点
- 这K个点中那种颜色的点出现次数最多，则预测所求点是什么颜色
（通常，我们把第三步称作投票）
好的，我们想一下这样的话会得出什么样的结果：
当K=1时， 我们的这个方法与之前的方法没有任何不同。当K=3时，对于上图B点附近红色区域中的点（注意我们是要讨论这一区域里面的点而不是B点），我们找出离他最近的三个点，会得出这样的结果：两黑一红。选出出现次数最多的颜色——黑色，预测这一点的颜色是黑色的。搞定。
下图时真正程序跑出来的分类结果。左边起第一张是原始数据，第二张是我们的1NN，第三张是K=5时的情形。（白色区域表示有至少两个颜色得票相同）
我们看到，相对于1NN，KNN算法对于噪声更加不敏感，我们称这一特性为鲁棒性。
至于超参数*K值的确定，我们通常是通过交叉验证*来获得。即在验证集上尝试不同的K值，使用错误率最低的那个。
二、加权KNN
考虑下图中的预测问题：
显然这点应该属于红色，但是比如说当K=6时，预测结果就容易出错。这是因为KNN考虑了很多距离更远的黑点。要解决这个问题，我们可以让距离越近的点对于决策越重要。于是我们就有了加权KNN。
我们原来的KNN是在比较所求点与所有给定点之间的距离d，如果说加权KNN要比较的是关于d的函数f(d)，那么只要这个函数关于d单调递减，就能满足要求。
最简单地，我们有f(d)=1/d。但是，想到当d趋向于零时，该函数值 f(d)=d 趋向于正无穷。这相当于为距离很近的点分配了无限大的权重，假如恰巧有一个噪声的点在离要预测的点非常近的位置，那么这一噪音对于预测结果的干扰就非常大了。
考虑高斯函数f(d)=exp(−d2/2)f(d)=exp(−d2/2)
这个函数就很好地弥补了反比例函数的缺点，当d趋向于零时，函数值趋向于1。当d>0时，f(d)单调递减（显然距离d取正值）。同时高斯函数还有一个优点就是，当距离d很大时，函数值f(d)始终会保持正值，而不会跌入负值。
加权KNN做的事情就是，比较 最近的K个点的距离d 的单调递减函数f(d)的函数值
三、距离的选择
我们之前一直在说，选择距离最近的K个点，那么这个距离是怎么计算的呢？
我们知道，对于平面上的两点的距离，是x, y轴坐标各自的平方差之和再开根号。一般地，对于n维空间中的点，有
d(I1,I2)=∑p(Ip1−Ip2)2−−−−−−−−−−−√d(I1,I2)=∑p(I1p−I2p)2，
其中I1I1,I2I2是两个点的坐标，p表示维度。我们通常称他维L2距离
当然，还有L1距离d(I1,I2)=∑p|Ip1−Ip2|d(I1,I2)=∑p|I1p−I2p|
L1和L2距离都是常用的距离度量方法。他们之间的区别可以这样来思考：在某一维度上，如果两点相距较远，则L2距离比L1距离要更大，而若两点相距很近，则反之。这是由于平方的存在，可以参考y=xy=x和y=x2y=x2在第一象限内的图像。
四、归一化
在处理实际问题时，事情可能变得与处理平面时有些区别。
比如说我们要用KNN处理这样一个问题：
我们手中有这样一个数据集，河海大学100个学生的
- 每学期天在图书馆的总小时数
- 每学期使用电脑的总小时数
- 每学期交作业总次数
- 所属院系
前三个是数值，每个学生有三个对应数值，相当于每一个学生是三维空间中的一个点，三个对应数值是这个点的坐标，而所属院系则是类似于红或黑的属性。
我们要做的事情是根据数据集里没有的一名学生的前三个数据，来判断他的院系。
如果直接使用KNN的话，我们会发现，三个维度上的数据相差过大，即前两个维度对于“距离”的影响要比第三个维度大得多。为了解决这个问题，我们要对数据进行预处理：归一化。
如果我们能将三个维度上的数值都压缩到同样一个区间上（比如说0到1或者-1到1），这样三个维度的数据对与最后决策的影响差距就会基本相等。
我们有： 归一化后数值 = （原数值 - 平均值）/ （最大值 - 平均值）
上式能将原数据压缩至0到1的区间。
五、数据精简
剔除噪声
我们的KNN算法，并没有显示的训练过程（但我们仍把给定点集称作“训练集”），这是一种比较“懒惰”的机器学习方法。这也导致了在实际预测过程中，需要对训练集的每一个点都进行距离计算，这是十分耗时的。如果我们能减少一部分冗余的样本，自然就能减少使用时计算的负担。
首先，之前提到过的噪声点是最应该被去掉的。我们来思考如何能判断训练集中的样本（点）是否属于噪声。通常，噪声样本都有“孤军深入”这样的特点。那我们就可以这样设计算法：
只要某一个样本的周围都是与它属性不同的点，那我们就判断这个样本属于噪声。
比较严谨地：
给定超参数K，取小于K的正整数R，若某样本的“R近邻”都是属性不同的样本，则删除该样本
这样，我们就可以删除一部分噪声了，同时也精简了数据集。
选择原型
我们说，数据精简的目的是：用留下的最少的部分数据，完成与完整训练集差不多的分类性能。这一部分里，我们把那留下的最少的那部分数据称作“原型”，接下来，我们来讨论应该如何选择这一训练集的子集。
试想这样一个情景，你坐在河海大学文体中心小剧场听新生入学教育，剧场观众席的学生是按班级分布的。你觉得台上的演讲十分无聊，便想要确定观众席中每个班级的具体位置以及边界。
你可以这样做：首先对于你附近的人，询问他们的班级。如果他属于一个没见过的的班级，就那小本本把他的位置记下来。一小会之后，你的小本本上就会有几个不同班的学生了。
然后对于在场的每一位学生：
询问他的班级，再询问离他最近的那个人的班级。
如果两个不一样，则拿出小本本把这位学生记下来；如果一样，那么我们说，你这位学生对于我确定边界没什么用，不记下你了。
在遍历一遍在场的所有同学之后，你就可以用你手中的小本本来做KNN分类啦。我们把这个小本本上的同学就称作原型。
比较严谨地，我们有：
有原型（样本集合）U遍历所有样本，对于当前样本x：{如果他和他的最近邻属性不同：就将x加入U；如果他和他的最近邻属性相同：继续循环，即舍弃该样本；}
这样，当我们完成遍历，就得到了原型U，这时我们就可以用精简后的U做1NN分类了。这一方法被称为CNN(Condensed nearest neighbor)，有趣的是，他与卷积神经网络——convolutional neural networks, CNN重名。
边界率
还有一个技术细节，就是我们要指定遍历样本的顺序，来获得更好的原型U。
定义边界率 a(x)=||x’-y||/||x-y||，我们要对于训练集中的每一个样本x，挨个计算边界率a。
其中，x表示当前样本；y表示离x最近的，不同属性的样本；x’表示离y最近的，与x同属性的样本。
如图所示，当前样本是红色的，y是与当前样本不同的绿色，x’是与当前样本相同的红色。
要指出，由于||x’-y|| <= ||x-y||， 边界率a的值在0和1之间。
计算完所有边界率a之后，我们对训练集中的样本，按边界率a从大到小的顺序进行排序，再按这个顺序来进行遍历。
这样的顺序有助于我们获得更经济且性能更好的原型U。
对于之前的例子：
进行了数据精简后，我们得到
其中，标有x的点是去掉的噪音，标方框的点是原型U中的样本，标圆圈的则是丢弃的冗余样本。
用这一原型U做1NN分类，我们得到如下结果：
与上面使用完整训练集得1NN相比，原型U的分类性能并不差。同时，原型U中的样本数只占完整训练集的15%-20%
六、简单实现（python）
def KNN(input, dataSet, labels, k):# 计算距离dataSetSize = dataSet.shape[0]# 计算每个维度上的坐标差 difference matrixdiffMat = tile(input, (dataSetSize,1)) - dataSet# 这里用L2距离, 计算平方后的各维度坐标差 squared difference matrixsqDiffMat = diffMat**2#求和, squared distance sqDistances = sqDiffMat.sum(axis=1)#开根号, distancedistances = sqDistances**0.5# 排序sortedDistIndicies = distances.argsort()classCount={} # 投票 for i in range(k):voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)return sortedClassCount[0][0]
这段代码使用L2距离
d(I1,I2)=∑p(Ip1−Ip2)2−−−−−−−−−−−√d(I1,I2)=∑p(I1p−I2p)2
输入为要判断的点input、给定点dataSet， 给定属性labels， 以及**超参数**K
输出为经过投票后得票最高的属性。
七、总结与讨论
在本文中，我们讨论了从最近邻到K-最近邻的升级、介绍了为了减少密集敌对样本影响的加权KNN、浅谈了距离度量方法的选择，之后是数据预处理，包括归一化和精简数据，最后，我们给出了实现最简单KNN的一段代码。
KNN是机器学习中相对简单的一个入门算法，他原理相对简单，但使用时需要存储大量样本（即使有数据精简），而且计算成本很高。他没有显式的训练过程，是一种“懒惰学习”。这个算法最初由Cover和Hart于1968年提出，历史久远，但是仍能应用在当今的很多实际问题上，并且性能不差：他的泛化错误率不超过贝叶斯最优分类器错误率的两倍。
