K最近邻

简介

K最近邻(KNN, k-NearestNeighbor)是一种常见的机器学习方法，维基百科解释：

在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。

• 在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数)，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。
• 在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。

由此我们可知, KNN不仅可以用于分类任务中, 同样也可以将其用在回归问题上。

至于什么是非参数统计方法，虽然维基百科已经给出了解释，但我习惯将他理解为消极学习（Lazy Learning）。好吧，另外一个问题出现了，什么又是消极学习呢，有消极学习一定也会有积极学习吧，以下摘自另一篇博客的解释：

积极学习

这种学习方式是指在进行某种判断（例如，确定一个点的分类或者回归中确定某个点对应的函数值）之前，先利用训练数据进行训练得到一个目标函数，待需要时就只利用训练好的函数进行决策，显然这是一种一劳永逸的方法，SVM就属于这种学习方式。

消极学习

这种学习方式指不是根据样本建立一般化的目标函数并确定其参数，而是简单地把训练样本存储起来，直到需要分类新的实例时才分析其与所存储样例的关系，据此确定新实例的目标函数值。也就是说这种学习方式只有到了需要决策时才会利用已有数据进行决策，而在这之前不会经历 Eager Learning所拥有的训练过程。KNN就属于这种学习方式。

简单理解，积极学习需要训练过程，消极学习不需要训练（时间复杂度为0）过程直接预测就可以

原理（以分类问题为例）

KNN利用的思想是人们所熟知的一句古话，物以类聚，人以群分。他周围一定范围内的样本哪个类别多就认为他是哪个类别。具体过程如下：

• 计算预判断类别的样本与其他所有样本的相似度（时间复杂度O(n)）；
• 将结果按相似度由大到小排序；
• 取前K个样本，统计其类别，将类别最多的一类记为该预测样本的类别

我们通过一个例子来说明，假设有 ○ 和 □ 两种数据，其分布如下：
[图片上传失败...(image-df2758-1565583011308)]
这时新增了一个未知分类的样本，位置如下，要判断其类别：

image
跟据 KNN “物以类聚，人以群分”的特点, 我们观察其周围的样本的类别以此来推断这个样本的类别。好了看到与他最近的样本的分类是个 ○，我们就认为这个样本也是 ○。如果只看了1个离他最近的样本，那么你的KNN中的K值取的就是1（我们好像知道KNN中的K指的是什么了）。
但是站在上帝视角看，显然这个样本应该被分为 □ 类更合适。○ 是一个噪声样本。由此我们可以得出一个结论：
K值太小容易过拟合

那么K值应该取什么值比较合理呢，我们再看下另一种极端的情况, 取K=N(N为样本数)，如下图：

image

我们算下一共有8个 □，9个 ○，少数服从多数，我们认为这个样本属于 ○。也不合理

K过大或过小都不合适，最合理的K值应该是下边这种情况：

image

这种情况下样本会被正确分为 □

实际应用当中我们一般使用交叉验证(Cross-validation)的方法取得最优K值，一般不超过20，上限是

相似度

上述示例我们默认使用欧氏距离的方法计算两个样本的距离(相似度)，即：

实际上计算相似度的方法还有很多，具体可以参看我的另一篇文章8种相似度度量方式的原理及实现