什么是 k 最近邻算法?
了解 k 最近邻算法,这是当今机器学习中使用的流行且最简单的分类和回归分类器之一
正在写代码的开发人员的后背视图
K-最近邻算法

k-最近邻算法,也称为 KNN 或 k-NN,是一种非参数、有监督的学习分类器,它使用邻近度对单个数据点的分组进行分类或预测。 虽然它可以用于回归或分类问题,但它通常用作分类算法,假设可以在彼此附近找到相似点。


对于分类问题,根据多数票分配类别标签,也就是使用在给定数据点周围最常表示的标签。 虽然这在技术上被认为是"最高票制",但"多数票"一词在文学中更常用。 这两个术语之间的区别在于,"多数票"在技术上要求超过 50% 的多数,这主要适用于只有两个类别的情况。 有多个分类时(例如四个类别),不一定要求 50% 的投票才能对一个分类下结论;您可以分配一个投票率超过 25% 的类别标签。 威斯康星大学麦迪逊分校通过 此处的 示例很好地总结了这一点 (PDF, 1.2 MB) (链接位于 ibm.com 外部)。 

回归问题使用与分类问题类似的概念,但在这种情况下,取 k 个最近邻的平均值来对分类进行预测。 这里的主要区别是分类用于离散值,而回归用于连续值。 但是,在进行分类之前,必须定义距离。 最常用的是欧几里得距离,我们将在下面深入研究。
还值得注意的是,KNN 算法也是"惰性学习"模型家族的一部分,这意味着它只是存储训练数据集,而不是经历训练阶段。 这也意味着所有计算都发生在进行分类或预测时。 由于这种算法严重依赖内存来存储其所有训练数据,因此也称为基于实例或基于内存的学习方法。
Evelyn Fix 和 Joseph Hodges 在 1951 年的这篇 论文  (PDF, 1.1 MB) (链接位于 ibm.com 外部) 中提出了围绕 KNN 模型的最初想法,而 Thomas Cover 在他的 研究  (PDF 1 MB)(链接位于 ibm.com 外部)中扩展了他们的概念:“最近邻模式分类”。 虽然这种算法不再像以前那样受欢迎,但由于其简单性和准确性,仍然是人们在数据科学中学习的首选算法之一。 然而,随着数据集的增长,KNN 变得越来越低效,影响了整体模型的性能。 这种算法通常用于简单的推荐系统、模式识别、数据挖掘、金融市场预测、入侵检测等。 


计算 KNN:距离度量

总结一下,k 最近邻算法的目标是识别给定查询点的最近邻,以便我们可以为该点分配一个类标签。 为了做到这一点,KNN 有几个要求:

确定距离度量

为了确定哪些数据点最接近给定查询点,需要计算查询点与其他数据点之间的距离。 这些距离度量有助于形成决策边界,而决策边界可将查询点划分为不同的区域。 你通常会看到使用 Voronoi 图可视化的决策边界。

虽然可以选择多种距离度量,但本文仅涵盖以下几种:

欧几里得距离(p=2) :这是最常用的距离度量,仅限于实值向量。 使用下面的公式,可以测量查询点和被测量的另一个点之间的直线。

曼哈顿距离(p=1):这也是另一种流行的距离指标,它测量两点之间的绝对值。 也称为出租车距离或城市街区距离,因为它通常用网格可视化,说明人们如何通过城市街道从一个地址导航到另一个地址。

闵可夫斯基距离:此距离度量是欧几里得和曼哈顿距离度量的广义形式。 下面公式中的参数 p 允许创建其他距离度量。 当 p 等于 2 时,欧几里得距离用这个公式表示,而曼哈顿距离用 p 等于 1 来表示。

汉明距离:这种技术通常与布尔或字符串向量一起使用,识别向量不匹配的点。 因此,它也被称为重叠度量。 这可以用以下公式表示:

举个例子,如果您有以下字符串,则汉明距离将为 2,因为只有两个值不同。


计算 KNN:定义 k

k-NN 算法中的 k 值定义了将检查多少个邻居以确定特定查询点的分类。 例如,如果 k=1,实例将被分配到与其单个最近邻相同的类。 定义 k 可以是一种平衡行为,因为不同的值会导致过拟合或欠拟合。 k 值越小,可能导致方差越大,但如果偏差较低,以及 k 值越大可能导致偏差较高且方差较低。 k 的选择将很大程度上取决于输入数据,因为具有更多异常值或噪声的数据可能会在 k 值较高时表现更好。 总体而言,建议 k 使用奇数以避免分类联系,交叉验证策略可以帮助你为数据集选择最佳 k。

k 最近邻和 python

要深入研究,您可以通过使用 Python 和 scikit-learn(也称为 sklearn)来了解有关 k-NN 算法的更多信息。 Watson Studio 中的 教程 可帮助您学习该库的基本语法,该库还包含其他流行的库,如 NumPy、pandas 和 Matplotlib。 以下代码是如何使用 KNN 模型创建和预测的示例:

from sklearn.neighbors import KNeighborsClassifier
model_name = 'K-Nearest Neighbor Classifier'
knnClassifier = KNeighborsClassifier(n_neighbors = 5, metric = 'minkowski', p=2)
knn_model = Pipeline(steps=[('preprocessor', preprocessorForFeatures), ('classifier' , knnClassifier)])
knn_model.fit(X_train, y_train)
y_pred = knn_model.predict(X_test)


k-NN 在机器学习中的应用

k-NN 算法已在各种应用中得到运用,主要是在分类中。 其中一些用例包括:

数据预处理:数据集经常有缺失值,但 KNN 算法可以在称为缺失数据插补的过程中估计这些值。

推荐引擎:通过使用来自网站的点击流数据,KNN 算法已被用于向用户提供有关其他内容的自动推荐。 这项研究(链接位于 ibm.com 外部)显示用户已分配到特定的分组,并根据该分组的用户行为,为他们提供建议。  然而,考虑到 KNN 的缩放问题,这种方法对于较大的数据集可能不是最优的。

金融:该算法也被用于各种金融和经济用例。 例如,一篇论文  (PDF, 439 KB)  (链接位于 ibm.com 外部) 展示了如何通过对信用数据使用 KNN 算法来帮助银行评估向组织或个人提供贷款的风险。 它用于确定贷款申请人的信用状况。 另一份期刊  (PDF, 447 KB)(链接位于 ibm.com 外部) 重点介绍了它在股票市场预测、货币汇率、交易期货和洗钱分析中的用途。

医疗保健:KNN 还应用于医疗保健行业,预测心脏病发作和前列腺癌的风险。 该算法用于计算最有可能的基因表达。

模式识别:KNN 还有助于识别模式,例如文本和数字分类 (链接位于 ibm.com 外部)。 这对于识别表格或邮寄信封上的手写数字特别有用。 


KNN 算法的优缺点

就像任何机器学习算法一样,k-NN 也有其优点和缺点。 根据项目和应用,它可能是也可能不是正确的选择。

优势

易于实现:鉴于算法的简单性和准确性,它是新数据科学家将学习的首批分类器之一。

轻松适应:随着新训练样本的增加,算法会根据任何新数据进行调整,因为所有训练数据都存储在内存中。

很少的超参数:KNN 只需要 a k 值和距离度量,与其他机器学习算法相比,所需的超参数很少。

缺点

不能很好地扩展:由于 KNN 是一种惰性算法,因此与其他分类器相比,它占用了更多的内存和数据存储。 从时间和金钱的角度来看,这可能是昂贵的。 更多的内存和存储将增加业务开支,而更多的数据可能需要更长的时间来计算。 虽然已经创建了不同的数据结构(例如 Ball-Tree)来解决计算效率低下的问题,但分类器是否理想可能取决于业务问题。

维度的诅咒:KNN 算法容易成为维度诅咒的受害者,这意味着它在高维数据输入时表现不佳。 这有时也称为峰值现象 (PDF,340 MB) (链接位于 ibm.com 外部),在算法达到最佳特征数量后,额外的特征会增加分类错误的数量,尤其是当样本尺寸较小时。

容易过拟合:由于"维度的诅咒",KNN 也更容易过拟合。 虽然利用特征选择和降维技术来防止这种情况发生,但 k 的值也会影响模型的行为。 较小的 k 值可能会过度拟合数据,而较大的 k 值往往会"平滑"预测值,因为它是对更大区域或邻域的值进行平均。 但是,如果 k 的值太高,那么可能会欠拟合数据。 


相关解决方案

IBM Cloud Pak for Data

IBM Cloud Pak for Data 是一个开放式、可扩展的数据平台,它提供的数据架构可使所有数据在任何云端用于 AI 与分析。


IBM Watson Studio

构建、运行和管理 AI 模型。 使用开源代码或可视化建模在任何云中准备数据和构建模型。 预测并优化结果。


IBM DB2 on Cloud



后续步骤

k-NN 节点和 IBM Cloud Pak for Data

Cloud Pak for Data 是一组工具,可帮助为 AI 实施准备数据。 k-NN 节点是 IBM Cloud Pak for Data 中可用的一种建模方法,可以让开发预测模型变得非常容易。 该插件部署在任何云上,并无缝集成到您的现有云基础设施中。