KNN（K-近邻算法）：靠跟自己关系的远近来做预测的算法

假设你是某影视网站序员中的一员。你们网站的用户热衷于观看《延禧攻略》《如懿传》这类古装宫廷剧，而你们平台有机会花1000万买下《扶摇》的版权。

作为序员你完全不了解这个《扶摇》，到底是个健身课程还是都市言情，1000万可不是个小数目，那么你应不应该买呢？买了以后你的用户会不会喜欢呢？

这个时候跟你配对的序员走过来说，让我们用 KNN 算法来预测一下吧。我们先提出几个关键数据进行统计.

首先统计影片中出现古代官员职称的次数 EP（皇上、父王、臣妾…），再统计一下出现健身词汇的次数 ML（俯卧撑、抽动、抖动…），再统计一下出现现代词汇的次数 MD（打电话、打车、打胎…）

统计发现（以下数据本禅师嘻咦啊写的，只为说明问题没有真实性）

然后一算距离，发现《扶摇》的数据跟古装很接近，跟健身和都市言情比较远，基本可以认为这是一部古装剧了。

所以我们知道，KNN 是在处理上述类似问题上非常简单快速。KNN 中的 K 是一个整数参数，通常 K ≤ 20。那么这个 K 应该怎么选？KNN 具体的算法又是什么？ KNN 都在什么时候使用？KNN 有哪些优势哪些劣势？接下来，由我们的特约作者章华燕来给大家做一个详细的解读。

KNN 是个啥？

KNN（K-Nearest Neighbor）算法是机器学习中算法中最基础和简单的算法之一。它既能用于分类，也能用于回归。k-近邻算法采用测量不同特征值之间距离的方法进行分类。

KNN 算法的思想非常简单：对于任意的 n 维输入向量，其对应于特征空间一个点，输出为该特征向量所对应的类别标签或者预测值。

KNN 算法在机器学习算法中有一个十分特别的地方，那就是它没有一个显示的学习过程。

它实际上的工作原理是利用训练数据对特征向量空间进行划分，并将其划分的结果作为其最终的算法模型。

存在一个样本数据集合，也称作训练样本集，并且样本集中的每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。

输入没有标签的数据后，将这个没有标签的数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本中特征最相似的数据（最邻近）的分类标签。

一般来说，我们只选择样本数据集中前 k 个最相似的数据，这就是 k-近邻算法中 k 的出处，通常 k 是不大于 20 的整数。最后，选择 k 个最相似数据中出现次数最多的类别，作为新数据的分类。

KNN 分类算法

KNN 分类算法的分类预测过程十分的简单和容易理解：对于一个需要预测的输入向量 x，我们只需要在训练数据集中寻找 k 个与向量 x 最近的向量的集合，然后把 x 的类标预测为这 k 个样本中类标数最多的那一类。

图1 KNN 分类算法示意图

如上图所示，w1、w2、w3 分别代表的是训练集中的三个类别。图中与 xu 最相近的5（k=5）个点如图中箭头所指，很明显与 xu 最相近的5个点中最多的类标为 w1，因此 KNN 算法将 xu 的类别预测为 w1。

基于上述思想给出如下所示的 KNN 算法：

输入： 训练数据集

其中：

为 n 维的实例特征向量。

为实例的类别，i=1,2,...,N，预测实例 x。

输出： 预测实例 x 所属类别 y。

算法执行步骤：

1. 根据给定的距离度量方法（一般情况下使用欧氏距离）在训练集 T 中寻找出与 x 最相近的 k 个样本点，并将这 k 个样本点所表示的集合记为 N_k(x)；
2. 根据如下所示的多数投票的原则确定实例 x 所属类别 y：

式(5.1)中 I 为指示函数：

从上述的 KNN 算法原理的讲解中，我们会发现有两个因素必须确定才能使 KNN 分类算法真正能够运行：（1）算法超参数 K；（2）模型向量空间的距离度量。

k 值的确定

KNN 算法中只有唯一的一个超参数 K，很明显 K 值的选择对最终算法的预测结果会产生至关重要的影响。接下来就简单的讨论一下 K 值的大小对算法结果的影响以及一般情况下如何选择 K 值。

如果 K 值选择的比较小，这时候我们就相当于使用较小的领域中的训练样本对实例进行预测。这时候，算法的近似误差（Approximate Error）会减小，因为只有与输入实例相近的训练样本才能才会对预测结果起作用。

但是它也会有明显的缺点：算法的估计误差会偏大，预测的结果会对近邻点十分敏感，也就是说如果近邻点是噪声点的话，那么预测就会出错。也就是说，K 值太小会使得 KNN 算法容易过拟合。

同理，如果 K 值选的比较大的话，这时候距离较远的训练样本都能够对实例的预测结果产生影响。这时候，而模型相对比较鲁棒，不会因个别噪声点对最终的预测产生影响。但是缺点也是十分明显的：算法的近似误差会偏大，距离较远的点（与预测实例不相似）也会同样对预测结果产生作用，使得预测产生较大偏差。此时相当于模型发生欠拟合。

因此，在实际的工程实践过程中，我们一般采用交叉验证的方式选取 K 值。从上面的分析也可以知道，一般 K 值取得比较小。我们会选取 K 值在较小的范围，同时在测试集上准确率最高的那一个确定为最终的算法超参数 K。

距离度量

样本空间中两个点之间的距离度量表示的是两个样本点之间的相似程度：距离越短，表示相似程度越高；相反，距离越大，表示两个样本的相似程度低。

常用的距离度量方式有：

1. 闵可夫斯基距离
2. 欧氏距离
3. 曼哈顿距离
4. 切比雪夫距离
5. 余弦距离

1. 闵可夫斯基距离

闵可夫斯基距离不是一种距离，而是一类距离的定义。对于 n 维空间中的两个点 x(x1,x2,...,xn) 和 y(y1,y2,...,yn) ，那么 x 和 y 两点之间的闵可夫斯基距离为：

其中 p 是一个可变参数：

• 当 p=1 时，被称为曼哈顿距离；
• 当 p=2 时，被称为欧氏距离；
• 当 p=\infty 时，被称为切比雪夫距离。

2.欧氏距离

由以上说明可知，欧式距离的计算公式为：

欧式距离（L2 范数）是最易于理解的一种距离计算方法，源自欧式空间中两点间的距离公式，也是最常用的距离度量方式。

3.曼哈顿距离

由闵可夫斯基距离定义可知，曼哈顿距离的计算公式为：

KNN 算法的核心：KDTree

通过以上的分析，我们知道 KNN 分类算法的思想非常简单，它采用的就是 K 最近邻多数投票的思想。所以，算法的关键就是在给定的距离度量下，对预测实例如何准确快速地找到它的最近的 K 个邻居？

也许绝大多数初学者会说，直接暴力寻找呗，反正 K 一般取值不会特别大。确实，特征空间维度不高并且训练样本容量小的时候确实可行，但是当特征空间维度特别高或者样本容量大时，计算就会非常耗时，因此该方法并不可行。

因此，为了快速查找到 K 近邻，我们可以考虑使用特殊的数据结构存储训练数据，用来减少搜索次数。其中，KDTree 就是最著名的一种。

KD 树简介

KD 树（K-dimension Tree）是一种对 K 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。KD 树是是一种二叉树，表示对 K 维空间的一个划分，构造 KD 树相当于不断地用垂直于坐标轴的超平面将 K 维空间切分，构成一系列的 K 维超矩形区域。KD 树的每个结点对应于一个 K 维超矩形区域。利用 KD 树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

KD 树的构造

KD 树的构造是一个递归的方法：（1）构造根节点，使根节点对应于 K 维空间中包含的所有点的超矩形区域；（2）不断地对 K 维空间进行切分，生成子节点。

• 构造根节点

首先，在包含所有节点的超矩形区域选择一个坐标轴和在此坐标轴上的一个切分点，确定一个垂直于该坐标轴的超平面，这个超平面将当前区域划分为两个子区域（也即二叉树的两左右孩子节点）。

• 递归构造子节点

递归地对两个子区域进行相同的划分，直到子区域内没有实例时终止（此时只有叶子节点）。

通常我们循环地选择坐标轴对空间进行划分，当选定一个维度坐标时，切分点我们选择所有训练实例在该坐标轴上的中位数。此时我们来构造的 KD 树是平衡二叉树，但是平衡二叉树在搜索时不一定是最高效的。

KNN 回归算法

上面我们讲的 KNN 算法主要是用于分类的情况，实际上，KNN 算法也能够用于回归预测。本节我们就介绍一下 KNN 算法如何用于回归的情况。

众所周知，KNN 算法用于分类的方法如下：首先，对于一个新来的预测实例，我们在训练集上寻找它的最相近的 K 个近邻；然后，采用投票法将它分到这 K 个邻居中的最多的那个类。

但是，怎么将 KNN 算法用于回归呢？其实大致的步骤是一样的，也是对新来的预测实例寻找 K 近邻，然后对这 K 个样本的目标值去均值即可作为新样本的预测值：

KNN 预测实战

接下来，我们使用 scikit-learn 库中的 KNN 对 iris 数据集分类效果进行预测实战。众所周知，iris 数据集有四个维度的特征，但是为了方便展示效果，我们只使用其中的两个维度。完整的代码实现如下：

代码运行结果如下图所示：

• 对代码进行解释：

代码中邻居数ke的是 n_neighbors = 15，只使用 iris 的前两维特征作为分类特征。权重度量采用了两种方式：均值（uniform）和距离（distance）。均值代表的是所有的 K 个近邻在分类时重要性选取的是一样的，该参数是默认参数；距离也就是说，分类时 K 个邻居中每个邻居所占的权重与它与预测实例的距离成反比。

KNN 的局限性

KNN 有着非常明显的有点和缺陷：

优点：精度高、对异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型和标称型

在理想化的经典场景中，KNN 是非常好用的，但是在非理想化、非经典场景中，KNN 这种方式就有点力不从心了。K 值到底选多少？我们需要跟哪些关键属性计算距离？如果我们需要计算的属性很多，对计算机的资源消耗也很大，非常不划算。

还是拿电视剧举例子。你又拿到的了一部《寻秦记》，里面出现官职的次数也可能是1000，出现打车的次数有50次。这个时候，KNN 会认为这是一部古装片，而实际上这是一部穿越片。

所以，当 KNN 算法不给力的时候，我们还有哪些算法可以选择？本禅师推荐章华燕的《机器算法各个击破》课程。这是本禅师想大家承诺的，人工智能相关技术课程推荐的第二期。