目标

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

理论

kNN是最简单的监督学习分类算法之一。其思想是在特征空间中搜索测试数据的最近匹配项。我们将结合下图进行讲解。

图像

图像中，有两个家族：蓝色正方形和红色三角形。我们将每个家族称为一个类别。他们的房屋显示在城镇地图上，我们称之为特征空间。您可以将特征空间视为所有数据都被投影的空间。例如，考虑一个二维坐标空间。每个数据有两个特征，一个x坐标和一个y坐标。您可以将此数据表示在您的二维坐标空间中，对吧？现在假设有三个特征，您将需要三维空间。现在考虑N个特征：您需要N维空间，对吧？这个N维空间就是它的特征空间。在我们的图像中，您可以将其视为一个具有两个特征的二维情况。

现在考虑一下如果一个新成员来到城镇并建造一个新家（如图中的绿色圆圈）会发生什么。他应该被添加到蓝色或红色家族（或类别）中的一个。我们称这个过程为分类。这个新成员究竟应该如何分类？由于我们正在处理kNN，让我们应用该算法。

一种简单的方法是检查谁是他最近的邻居。从图像可以看出，他是红色三角形家族的成员。因此，他被分类为红色三角形。这种方法被称为简单的最近邻分类，因为分类仅取决于最近邻。

但是这种方法有一个问题！红色三角形可能是最近的邻居，但如果附近也有很多蓝色正方形呢？那么蓝色正方形在该区域的影响力就大于红色三角形，因此仅仅检查最近的一个是不够的。相反，我们可能需要检查k个最近的家族。然后，哪个家族是其中的多数，新成员就应该属于哪个家族。在我们的图像中，让我们取k=3，即考虑3个最近的邻居。新成员有两个红色的邻居和一个蓝色的邻居（有两个蓝色邻居与新成员距离相等，但由于k=3，我们只能取其中一个），因此他仍然应该被添加到红色家族。但是如果我们取k=7呢？那么他将有5个蓝色邻居和2个红色邻居，应该被添加到蓝色家族。结果将随着所选k值的不同而变化。请注意，如果k不是奇数，我们可能会得到平局，就像上面k=4的情况一样。我们会看到，我们的新成员的四个最近邻居中有2个红色和2个蓝色邻居，我们需要选择一种方法来打破平局以执行分类。因此，重申一下，这种方法被称为k近邻，因为分类取决于k个最近邻。

同样，在kNN中，我们确实考虑了k个邻居，但我们给予所有邻居同等的重要性，对吧？这是合理的么？例如，考虑k=4的平局情况。我们可以看到，2个红色邻居实际上比另外2个蓝色邻居更靠近新成员，因此他更有资格被添加到红色家族。我们如何用数学方法解释这一点？我们根据每个邻居到新成员的距离赋予每个邻居一定的权重：离他越近的邻居权重越高，离他越远的邻居权重越低。然后我们分别添加每个家族的总权重，并将新成员分类为获得较高总权重的家族的一部分。这被称为改进的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之前，我们需要了解一些关于我们的测试数据（新成员的数据）的信息。我们的数据应该是一个浮点数组，大小为\(测试数据数量 \; \times \; 特征数量\)。然后我们找到新成员的最近邻居。我们可以指定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( "结果: {}\n".format(results) )
print( "邻居: {}\n".format(neighbours) )
print( "距离: {}\n".format(dist) )
 
plt.show()

我得到了以下结果：

结果: [[ 1.]]
邻居: [[ 1. 1. 1.]]
距离: [[ 53. 58. 61.]]

结果表明，新加入者的3个最近邻都来自蓝色家族。因此，他被标记为蓝色家族的一部分。从下面的图中可以明显看出。

图像

如果您有多个新加入者（测试数据），您可以将它们作为数组传递。相应的结果也将作为数组获得。

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

附加资源

练习

尝试使用更多类别和不同的k值重复上述操作。在相同的二维特征空间中，随着类别的增加，选择k是否变得更加困难？