什么是 k近邻算法 (KNN)？

虽然 KNN 算法可用于回归或分类问题，但它通常会用作分类算法，其假设为可在彼此附近找到相似点。

对于分类问题，类标签会根据多数票来分配；即，使用在给定数据点周围出现频率最高的标签。虽然此举在技术上被视为“多数投票”，但“多数票”一词在文献中却更常被使用。这些术语之间的区别在于，“多数票”在技术上要求实现大于 50% 的多数，而这主要是在只有两个类别时才有效。存在多个类时（例如有 4 个类别），则并非必须有 50% 的选票才能对一个类下结论；只要选票超过 25%，便可分配一个类别标签。威斯康星大学麦迪逊分校用此处的一个示例充分总结了这一点。

回归问题使用与分类问题类似的概念，但在此情况下，会使用 k 个最近邻的平均值来预测某一分类。此处的主要区别在于：分类被用于离散值，而回归则被用于连续值。但在进行分类之前，还须定义距离。欧几里德距离是最常用的距离，而下文将对其进行详细介绍。

此外还需注意，KNN 算法也是一系列“懒惰学习”模型的其中一部分；因此，它只存储训练数据集，而不会经历训练阶段。这也意味着，所有计算均会在进行分类或预测时进行。由于它严重依赖内存来存储所有训练数据，因此也被称为基于实例或基于内存的学习方法。

在这篇 1951 年的论文中，Evelyn Fix 和 Joseph Hodges 被认为是提出了有关 KNN 模型的最初想法，而 Thomas Cover 在他的研究“最近邻模式分类”中扩展了他们的概念。虽然它不像以前那样普及，但由于其简便性和准确性，仍是大众在数据科学领域最早学习的算法之一。但是，随着数据集的增长，KNN 变得越发低效，从而降低了整体模型性能。它通常用于简单的推荐系统、模式识别、数据挖掘、金融市场预测、入侵检测等。

概括而言，k近邻算法 (KNN) 的目标是识别给定查询点的最近邻，以便可为该点分配类标签。为此，k近邻算法 (KNN) 有几个要求：

为确定哪些数据点最接近给定查询点，则需计算查询点与其他数据点之间的距离。这些距离指标有助于形成决策边界，从而将查询点划分为不同的区域。您通常会看到用 Voronoi 图呈现的决策边界。

虽然有多种距离测量方法可供选择，但本文仅介绍以下几种：

欧几里德距离 (p=2)：它是最常用的距离测量方法，且仅限于实值向量。通过使用以下公式，它可测量查询点与当前所测量的另一点之间的直线距离。

曼哈顿距离 (p=1)：它是另一种常用的距离测量方法，可用于测量两点之间的绝对值。同时，它也被称为出租车距离或城市街区距离，因为它通常会使用网格来呈现，以便说明如何通过城市街道从一个地址导航到另一个地址。

闵科夫斯基距离：此距离测量方法是欧几里德距离与曼哈顿距离指标的广义形式。以下公式中的参数 p 可用于创建其他距离指标。当 p 等于 2 时，欧几里德距离可通过此公式来表示，而曼哈顿距离则由 p 等于 1 来表示。

汉明距离：此技术通常会用于布尔矢量或字符串矢量，以便识别这些矢量出现互不匹配的点。因此，它也被称为重叠指标。该指标可用以下公式来表示：

例如，如果存在以下字符串，则汉明距离为 2，因为只有其中两个值不同。

KNN 算法中的 k 值定义了会检查多少个近邻以确定特定查询点的分类。例如，如果 k=1，则会将该实例分配给与其单个最近邻相同的类。

定义 k 可作为一种平衡手段，因为不同的值可能会导致过拟合或欠拟合。较小的 k 值可能会导致较高的方差和较低的偏差，而较大的 k 值则可能会导致较高的偏差和较低的方差。k 值的选择很大程度上取决于输入数据，因为包含更多异常值或噪声的数据使用较高的 k 值可能会效果更好。总体而言，建议将 k 值设为奇数以免分类时出现平局，而交叉验证策略可帮助您为数据集选择最佳 k 值。

要想深入了解，您可以使用 Python 和 scikit-learn（也称为 sklearn）来了解有关 KNN 算法的更多信息。Watson Studio 中的教程可帮助您了解此库中的基本语法，而该库还包含其他常用库，如 NumPy、pandas 和 Matplotlib。以下示例代码演示了如何创建 KNN 模型并用其进行预测：

k近邻算法 (KNN) 已用于各种应用，其中主要是在分类领域。其中一些用例包括：

• 数据预处理：数据集经常会有缺失值，但 KNN 可在缺失数据估算流程中对这些值进行估算。
  
  
• 推荐引擎：借助网站的点击流数据，KNN 算法可用于向用户自动推荐更多内容。这项研究表明，将用户分配到特定组，可以根据该组的用户行为向他们提供建议。但是，考虑到 KNN 的扩展问题，此方法对于较大的数据集可能并非最佳方法。
  
  
• 金融：它还被用于各种金融与经济用例中。例如，一篇论文展示了对信用数据使用 KNN 如何帮助银行评估向组织或个人提供贷款的风险。它可用于确定贷款申请人的信用度。另一份期刊强调了它在股票市场预测、货币汇率、期货交易和洗钱分析中的用途。
  
  
• 医疗保健：KNN 还被应用于医疗保健行业，以便对心脏病发作与前列腺癌的风险进行预测。该算法可通过计算最可能的基因表达来发挥作用。
  
  
• 模式识别：KNN 还协助识别模式，例如文本和数字分类。这对于识别表格或邮件信封上可能出现的手写数字非常有用。

如同所有机器学习算法一样，k近邻算法 (KNN) 也有其优缺点。根据具体的项目和应用，它可能是正确的选择，也可能不是。

• 易于实现：鉴于该算法的简易性和准确性，它是新数据科学家应学习的首批分类器之一。
  
  
• 易于调整：由于所有训练数据均存储在内存中，因此在添加新的训练样本时，此算法会根据所有新数据进行调整。
  
  
• 极少超参数：KNN 仅要求提供 k 值和距离指标，因而较之其他机器学习算法，其要求较低。

• 无法良好扩展：由于 KNN 是一种懒惰算法，因而较之其他分类器，它需占用更多内存和数据存储空间。从时间和金钱的角度来看，它的成本可能十分昂贵。更多的内存和存储空间会增加业务支出，而更多的数据则可能需要更长的时间来进行计算。虽然已创建不同数据结构（例如 Ball-Tree）来解决计算效率低下的问题，但根据实际业务问题，其他分类器可能才是理想之选。
  
  
• 维数灾难：KNN 算法往往会受到“维数灾难”的影响，因此它在处理高维数据输入时效果不佳。有时，此问题也被称为峰值现象，即在该算法达到最佳特征数后，其他特征会导致分类误差数量的上升，尤其是在样本规模较小时。
  
  
• 容易过拟合：由于“维度诅咒”，KNN 也更容易过度拟合。虽然特征选择和降维技术可以利用来防止这种情况发生，但 k 的值也会影响模型的行为。较低的 k 值可能会过拟合数据，而较高的 k 值往往会“平滑”预测值，因为它是在更大的区域或邻域上求值的平均量。但是，如果 k 的值过高，则可能会使数据欠拟合。