k近邻（一种基本的经典机器学习(ML)算法）

k近邻算法，通常称为KNN算法，是一种简单而有效的分类和回归监督机器学习算法。本文将介绍KNN算法，其应用，优缺点，其背后的数学知识及其在Python中的实现。

什么是K最近邻居（KNN）算法？

KNN算法是一种主要的经典机器学习算法，其重点是从新的未分类/未标记的数据点到现有的已分类/标记的数据点的距离。无论出于何种原因，都可以将其视为在学年中期进入大学的过程。正如我们所看到的，学生之间可能已经有志趣相投的小组，我们现在要弄清楚我们适合哪个小组，尤其是与哪个小组联系起来，这只是时间问题。 或换句话说，距离较小。

图1：示例数据集中的三种花卉类别的颜色，红色，黄色和绿色。

我们已经从数据集中标记了数据点。我们将它们绘制在二维图上。这些数据点属于三个类别，分别由红色，绿色和黄色表示，如图1所示。

接下来，我们将考虑一个由黑色十字标记表示的新的未标记数据点。现在可以从三种颜色中确定此新数据点属于哪个类别。首先，我们采用一个随机值，即k值。k值指示要从新的未标记数据点查找的最近点的数量。将k值视为5。接下来，我们计算从未标记的数据点到图形上每个数据点的距离，并选择最短的5个最短距离。

图2：从我们的数据集中测量类别之间的距离。

在最接近的5个数据点中，3个属于红色类别，1个属于绿色类别，1个属于黄色类别。这些被称为新数据的k（5）最近邻居。现在很明显，新数据点属于红色类别，因为它的最近邻居大部分来自红色类别。

图3：从示例数据集中查看新数据点如何属于红色类别。

同样，在回归问题中，目标是预测新数据点的值，而不是其所属的类别。再次举例说明，绘制一个二维图，该图由给定数据集中的数据点组成。由于它是二维图形，因此每个数据点都有2个特征。x轴表示特征1，y轴表示特征2。

接下来，我们引入一个新的数据点，对于该数据点，仅特征1值是已知的，我们需要预测特征2值。我们将k值设为5，并从新数据点获取5个最近的相邻点。新数据点的特征2的预测值是5个最近邻居的特征2的平均值。

图4：我们的示例引入了一个新的数据点，以说明k最近邻（KNN）算法。

何时使用KNN？

KNN算法可以进行最准确的预测，因此可以与最准确的模型竞争。因此，我们可以将KNN算法用于需要高精度但又不需要人类可读模型的应用程序[11]。当为我们的任务提供的数据集很小时。正确标记数据后，预测值将位于给定的标签中。如果存在类别1，类别2和类别3，则预测类别应该是其中之一，而不是其他任何类别。KNN用于解决回归，分类或搜索问题

使用KNN的利与弊

优点

由于该算法仅需要两个参数：k值和距离函数，因此实现起来简单明了。k的一个好的值将使该算法对噪声具有鲁棒性。它学习非线性决策边界。给定数据几乎没有任何假设。唯一假定的是附近的/相似的实例属于同一类别。这是一种非参数方法。无需模型拟合/培训。数据说明一切。由于不需要模型训练，因此很容易更新数据集。

缺点

对于大型数据集而言效率低下，因为必须在每个点都计算距离，每次算法遇到新数据点时都要循环计算。KNN假设相似的数据点彼此靠近。因此，该模型容易受到异常值得影响。即使新数据属于不同的类别，来自特定类别的一些离群值也可以向其吸引新数据。它无法处理不平衡的数据。当数据不平衡时，属于一个特定类别的数据要多于其余类别。该算法将有偏差。因此，需要对其进行明确处理。如果我们的数据集需要一个很大的K，它将增加算法的计算费用。

深入研究KNN背后的数学

如所讨论的，该算法计算从新数据点到每个现有数据点的距离。问题是，如何测量距离？我们将在本工作中讨论三种方法。

图5：Minkowski距离的表示。

Minkowski距离：

a）Minkowski距离是范数向量空间中的广义距离函数。向量空间必须满足以下要求：

零向量：零向量的长度为0标量因数：将向量与标量相乘只会改变长度，而不会改变方向三角不等式：任意两个给定点之间的最短距离是一条直线。

图6：Minkowski距离的公式。

b）在某些情况下，

当p = 1时-这是曼哈顿距离当p = 2时-这是欧几里德距离当p = infinity时-这是切比雪夫距离

欧氏距离

在数学中，欧几里得空间中两点之间的欧几里得距离是两点之间的线段长度。可以使用勾股定理根据点的笛卡尔坐标来计算，因此有时称为勾股距离[10]。

要计算二维平面上两个点（x1，y1）和（x2，y2）之间的距离，我们使用以下公式：

图7：欧几里得距离公式。

曼哈顿距离

曼哈顿距离的计算与欧几里得距离的计算相似，唯一的区别是我们采用绝对值而不是求平方差之和的平方根。通过获取绝对值，我们不会像欧几里得距离那样计算两点之间的最短距离。

从根本上说，欧氏距离代表“从一个点到另一个点的飞行”，而曼哈顿距离则是“沿着路径或道路从一个点到另一个点的行进”。

图8：曼哈顿距离公式。

但是，最有可能的是，用于计算距离的方法是欧几里得距离公式。原因之一是，欧几里德距离可以计算任何维度上的距离，而Manhattan在垂直或水平平面上找到元素。

如何为K选择合适的值？

选择K对于每个数据集都是唯一的。没有标准的统计方法来计算最佳K值。我们想选择一个K值，以减少误差。随着K的增加，由于平均或多数表决，我们的预测变得更加稳定。但是，如果K太大，则错误率将再次增加，因为它将不适合模型。换句话说，小K产生低偏差和高方差（较高的复杂度），而大K产生高偏差和低方差。话虽这么说，几乎没有其他方法可以尝试：

领域知识：如前所述，K高度依赖数据。例如，如果分析一个独特的花卉种类数据集，则很容易看出K应该是特定数量的花卉种类。交叉验证：这项众所周知的技术可用于比较一系列K值（例如，K为1到10）的精度度量。此技术需要将训练集分解为测试/验证集，以调整K以找到K。最佳值。平方根：当一个人对数据了解甚少时，尝试的一种简单方法是对训练集中的数据点数进行平方根。

用Python实现KNN

为了实现KNN算法，我们将使用Iris数据集。鸢尾花数据集是三个相关物种的鸢尾花形态变化的集合：Setosa，Versicolor和Virginica。观察到的形态变化是萼片长度，萼片宽度，花瓣长度和花瓣宽度。

Sklearn是一个Python库，具有各种分类，回归和聚类算法。它还将虹膜数据集保存为样本数据。我们将导入必要的库，例如NumPy，Pandas和matplotlib。

import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns from sklearn.model_selection import train_test_split from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import cross_val_score from sklearn.datasets import load_iris iris = load_iris()

下表显示了将数据放入Pandas DataFrame中后前5行的外观。目标值为0.0、1.0和2.0，分别代表Setosa，Versicolor和Virginica。

图9：该表显示了Pandas数据框中数据的前5行。

由于KNN对异常值和不平衡数据敏感，因此检查和处理异常值非常重要。通过绘制目标变量的计数图来检查不平衡数据，每种花都有50个样本。因此，数据是完美平衡的。

sns.countplot(x=’target’, data=iris)

图10：

通过使用箱线图检查异常值，似乎没有太多异常值要处理。

for feature in [‘sepal length (cm)’, ‘sepal width (cm)’, ‘petal length (cm)’, ‘petal width (cm)’]: sns.boxplot(x=’target’, y=feature, data=iris) plt.show()

图11：

接下来，我们将数据分为训练集和测试集，以衡量模型的准确性。该模型将在训练集上进行训练，该训练集是从原始数据的60％中随机选择的，然后使用测试集进行评估，该测试集是原始数据的剩余40％。在将其分为训练和测试集之前，必须将特征/因变量和目标/因变量分开。

X = iris.drop([‘target’], axis=1) y = iris[‘target’] X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.4, random_state=0)

用k值为1来构建初始模型，这意味着将仅考虑1个最近邻居来对新数据点进行分类。在内部，将计算从新数据点到所有数据点的距离，然后从最小到最大以及它们各自的类别进行排序。由于k值为1，因此已排序数组中第一个实例的类（目标值）将确定新的数据类。如我们所见，我们获得了91.6％的不错的准确性得分。但是，需要选择最佳k值。

knn = KNeighborsClassifier(n_neighbors=1) knn.fit(X_train, y_train) print(knn.score(X_test, y_test)) Output: 0.9166666666666666

为了通过交叉验证方法找到最佳k值，在这种情况下，我们计算k值的精度范围为1到26，然后选择最佳k值。准确性得分的范围大约在86％到96％之间。正如观察到的那样，准确性得分从一个较低的值开始，在某个点达到峰值，在一段时间内保持近似恒定，然后再次下降。分数在一段时间内保持恒定的范围可以视为给定数据集的最佳k值。

k_range = list(range(1,26)) scores = [] for k in k_range: knn = KNeighborsClassifier(n_neighbors=k) knn.fit(X_train, y_train) y_pred = knn.predict(X_test) scores.append(metrics.accuracy_score(y_test, y_pred)) plt.plot(k_range, scores) plt.xlabel(‘Value of k’) plt.ylabel(‘Accuracy Score’) plt.title(‘Accuracy Scores for different values of k’) plt.show()

图12：

引入一个新的未标记数据点，我们需要预测其类别是花类型，该花类型根据其形态特征属于一个类别。我们将以11的k值构建模型。

knn = KNeighborsClassifier(n_neighbors=11) knn.fit(iris.drop([‘target’], axis=1), iris[‘target’]) X_new = np.array([[1, 2.9, 10, 0.2]]) prediction = knn.predict(X_new) print(prediction) if prediction[0] == 0.0: print(‘Setosa’) elif prediction[0] == 1.0: print(‘Versicolor’) else: print(‘Virginica’) Output: [2.] Virginica

KNN应用

从预测流行病[2]和经济到信息检索[4] [5]，推荐系统[3]，数据压缩和医疗保健[1]，k最近邻（KNN）算法已成为此类应用程序的基础。正如我们所讨论的，KNN以最直接的监督式机器学习算法之一而闻名，其实现主要用于回归和分类任务。

推荐系统[3] [6]是k最近邻算法最重要的用例之一。一个简单的Google搜索为我们提供了一些关于使用KNN [7]在推荐系统上实现的有希望的文章，这主要是由于KNN能够针对一组特定项目传播类似的建议。

例如，想象一下，我们将一群对电影具有多种伪随机兴趣的用户放在了一起。推荐系统比较用户的个人资料，以发现一组用户是否具有相似的品味。然后，假设两个用户在比较期间对两个或多个项目的口味相似。在那种情况下，第二用户可能会喜欢第一用户喜欢的项目。

同样，在分类任务中可以使用KNN [8]。

结论

KNN是一种高效，简单且易于实施的监督式机器学习算法，可用于分类和回归问题。该模型通过计算最接近预测点的选定数量的示例K的距离来运行。

对于分类问题，标签将成为最接近的K点的多数票。对于回归问题，标签变为最接近的K点的平均值。无论何时进行预测，模型都会搜索整个训练集，以找到K个最相似的示例来标记原始预测点。

该算法的主要缺点是，随着数据数量的增加，计算费用和时间也会增加。但是，如果我们正在使用的数据集是适当大小的数据集（例如Iris数据集），则KNN是一种易于实现的简单算法，无需构建模型，调整参数或对模型进行任何其他假设。模型。