K 近邻算法是什么？看看离你最近的几个邻居是什么

K 近邻算法（K-Nearest Neighbors，KNN）是一种非常简单直观的机器学习方法：要判断一个新样本属于哪一类，就在训练数据中找出离它最近的 K 个样本，看这 K 个“邻居”大多属于哪一类，就把新样本归为这一类。俗话说“近朱者赤，近墨者黑”，K 近邻正是这个道理。它的思想可以追溯到 1951 年 Evelyn Fix 和 Joseph Hodges 的工作，1967 年 Thomas Cover 和 Peter Hart 对它进行了系统的理论分析。

它是怎么工作的

对于分类问题：计算新样本与所有训练样本之间的距离；找出距离最近的 K 个训练样本；统计这 K 个样本中各个类别出现的次数，选择出现次数最多的那个类别作为预测结果。还可以让距离更近的邻居拥有更大的投票权重。对于回归问题：做法类似，只是把 K 个邻居的目标值求平均，作为预测值。比如预测一套房子的价格，可以找出面积、位置、房龄最相似的几套房子，取它们价格的平均。

没有“训练”的算法

K 近邻有一个特别之处：它几乎没有训练的过程，只是把所有的训练样本存储起来，等到需要预测时才进行计算。这类方法被称为懒惰学习。与之相对，决策树、神经网络等方法在训练时就从数据中总结出一个模型，叫作急切学习。懒惰学习的好处是加入新数据非常方便，缺点是预测时计算量大，需要和所有的训练样本进行比较。

几个关键的选择

K 的取值：K 太小，比如只看最近的一个邻居，预测容易受到噪声和个别异常样本的影响，模型过于复杂，容易过拟合；K 太大，会把离得很远、不太相关的样本也考虑进来，决策边界变得过于平滑，可能欠拟合。K 通常通过交叉验证来选择，二分类时常选奇数以避免平票。距离的度量：最常用的是欧氏距离，也可以用曼哈顿距离、余弦距离等，应该根据数据的特点来选择。对于类别型的特征，需要专门定义距离。特征的标准化：K 近邻依赖距离的计算，如果不同特征的取值范围相差很大，比如年龄在 0 到 100 之间、收入在几千到几十万之间，取值范围大的特征会主导距离，因此通常需要先对特征进行标准化。

理论保证与局限

Cover 和 Hart 证明了一个有趣的结论：当训练样本无穷多时，最近邻分类器（K 等于 1）的错误率，不超过贝叶斯最优分类器错误率的两倍。考虑到它的简单程度，这是一个相当好的结果。但 K 近邻也有明显的局限：预测速度慢、需要存储全部的训练数据；对无关的特征和噪声敏感；在高维的数据上效果会明显下降，因为随着维度的增加，样本之间的距离会变得越来越相近，“最近的邻居”也不再那么有意义，这就是维度灾难。为了加快搜索，人们发展了 KD 树、球树等数据结构，以及各种近似最近邻搜索算法，比如基于图的 HNSW 方法。

今天的应用

K 近邻的思想在今天依然非常活跃：在推荐系统中，找出与你兴趣相似的用户或与你喜欢的商品相似的商品；在向量数据库和检索增强生成中，把文本或图片转换成嵌入向量，再检索出与查询最相近的若干个结果，本质上就是一种最近邻搜索；在异常检测中，离所有邻居都很远的样本可能是异常。