目标

在本章，我们将了解 K 近邻 (KNN) 算法的概念。

理论

KNN 是有监督学习中最简单的分类算法之一。其创意是在特征空间中搜索测试数据的最近匹配项。我们将会借助下图对此进行了解。

图像

图像中，有两个家族：蓝色正方形和红色三角形。我们将每个家族称为一个类别。他们的房子在他们的城镇地图中显示，我们称之为特征空间。你可以将特征空间看作一个所有数据都投影到的空间。例如，考虑一个二维坐标空间。每个数据有两项特征，一个 X 坐标和一个 Y 坐标。你可以在自己的二维坐标空间中表示这个数据，对吧？现在想象一下如果有三项特征，那你就需要三维空间了。现在再考虑 N 项特征：你需一个 N 维空间，对吧？这个 N 维空间就是其特征空间。在我们的图像中，你可以将其看作一个有两项特征的二维案例。

现在，考虑如果一个新成员进入这个城镇并建造了一所新房子，这个房子用绿色圆圈表示。他应该被归入蓝色或红色家族（或类别）之一。我们将该过程称为分类。具体来说，这个新成员应该如何进行分类？由于我们在处理 KNN，因此让我们应用这一算法。

一个简单的方法是检查谁是他的最近邻。从图像中，很明显，他属于红色三角形家族。因此，他被归类为红色三角形。这种方法被称为最近邻分类，因为分类仅取决于最近邻。

但这种方法存在一个问题！红三角可能是最近邻，但如果附近也有很多蓝色方块呢？那么，在本区域内蓝色方块比红三角更有优势，因此仅检查最近邻是不够的。相反，我们可能希望检查k个最近族。在这些族中，无论是哪个族占多数，新手都应该属于那个族。在我们的图像中，我们取k=3，即考虑3个最近邻。新成员有两个红邻和一个蓝邻（有两个蓝邻距离相等，但由于k=3，我们只能选择其中一个），因此他应该再次添加到红族中。但如果我们取k=7呢？然后，他有5个蓝邻和2个红邻，应该并入蓝族。结果会根据所选的k值而变化。请注意，如果k不是奇数，我们可能会得到平局，就像上面的k=4的情况一样。我们会发现，我们的新成员有两个红邻和两个蓝邻作为他的四个最近邻，我们需要选择一种方法来打破平局以进行分类。因此，重申一下，这种方法称为k-最近邻，因为分类取决于k个最近邻。

仍然，在kNN中，我们确实要考虑k个邻居，但是我们要对所有邻居赋予同等重要性，对吗？这是合理的么？例如，取k=4时的平局情况。正如我们所看到的，两个红邻实际上比其他两个蓝邻更接近新成员，因此他更有资格被添加到红族中。我们如何从数学角度解释这一点？我们根据新成员与每个邻域的距离为其赋予一些权重：越近的邻域获得的权重越高，而越远的邻域获得的权重越低。然后，我们分别添加每个族的总权重，并将新成员归类为获得较高总权重的族。这称为修正kNN或加权kNN。

那么，您在这里看到的一些重要事项是什么？

因为我们必须检查从新成员到所有现有房屋的距离以便找到最近邻，所以您需要了解镇上所有房屋的信息，对吗？如果有很多房屋和家庭，则需要占用大量内存，并且需要更多的时间进行计算。
几乎没有时间用于任何类型的“训练”或准备。我们的“学习”仅涉及在测试和分类之前记忆（存储）数据。

现在，让我们看看该算法在OpenCV中的运行情况。

OpenCV中的kNN

我们将在此处做一个简单的示例，其中包含两个家族（类别），就像上面一样。然后，在下一章中，我们将完成一个更好的示例。

因此，在此处，我们将红色家族标记为类别 0（记为 0），蓝色家族标记为类别 1（记为 1）。我们创建 25 个邻域或 25 个训练数据，并将它们中的每一个标记为类别 0 或类别 1 的一部分。我们可以借助 NumPy 中的随机数生成器来实现此目的。

然后，我们可以借助 Matplotlib 绘制它。红色邻域显示为红色三角形，蓝色邻域显示为蓝色正方形。

import cv2 as cv
import numpy as np
import matplotlib.pyplot as plt
 
# 特征集，包含 25 个已知/训练数据的 (x,y) 值
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)
 
# 使用数字 0 和 1 将每个数据标记为红色或蓝色
responses = np.random.randint(0,2,(25,1)).astype(np.float32)
 
# 获取红色邻域并绘制它们
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')
 
# 获取蓝色邻域并绘制它们
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')
 
plt.show()

您将获得与我们的第一张图片类似的内容。由于您使用的是随机数生成器，因此每次运行代码时，您会获得不同的数据。

接下来，启动 kNN 算法并将 trainData 和 responses 传递给 kNN 以进行训练。（在此过程中，它构建了一棵搜索树：有关此内容的更多信息，请参见以下附加资源部分。）

然后，我们带一个新人并借助 OpenCV 中的 kNN 将其归类为属于一个家族。在运行 kNN 之前，我们需要了解一些关于测试数据（新人的数据）的内容。我们的数据应该是具有大小\（测试数据数 X 特征数\）的浮点数组。然后，我们找到新人的最近邻域。我们可以指定k：我们需要的邻域数。（此处我们使用了 3。）它返回

根据我们在前面看到的 kNN 理论，赋予新人的标签。如果您需要最近邻域算法，只需指定 k=1。
k-最近邻域的标签。
从新人到每个最近邻域的对应距离。

因此，让我们看看它的工作原理。新人标记为绿色。

newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
 
knn = cv.ml.KNearest_create()
knn.train(trainData, cv.ml.ROW_SAMPLE, responses)
ret, results, neighbours ,dist = knn.findNearest(newcomer, 3)
 
print( "result: {}\n".format(results) )
print( "neighbours: {}\n".format(neighbours) )
print( "distance: {}\n".format(dist) )
 
plt.show()

我获得以下结果

result: [[ 1.]]
neighbours: [[ 1. 1. 1.]]
distance: [[ 53. 58. 61.]]

它说我们的新成员的 3 个最近邻域都来自蓝色家族。因此，他被标记为蓝色家族的一部分。这从下图中可以明显看出

图像

如果您有多个新成员（测试数据），您只需将它们作为数组传递。相应的 Ergebnis也作为数组获得。

# 10 个新成员
newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)
ret, results,neighbours,dist = knn.findNearest(newcomer, 3)
# 结果还将包含 10 个标签。

其他资源

练习

尝试使用更多课程和不同的 k 值重复以上操作。在同一 2D 特征空间中，随着课程增多，选择 k 是否变得更加困难？