Question

目标

在本章中，我们将理解k-最近邻（kNN）算法的概念。

理论基础

kNN是可用于监督学习的最简单的分类算法之一。这个想法是在特征空间中搜索最接近的测试数据。我们用下面的图片来看看它是怎么工作的。

在图像中，有两类家庭，蓝色方块和红色三角形。我们称每种家庭为一个为Class。他们的房子被显示在他们的城镇地图上，我们称之为特征空间。

(您可以将一个特征空间视为所有数据投影的空间，例如，考虑一个二维坐标空间，每个数据有两个特征，x和y坐标，您可以在二维坐标空间中表示这个数据，对吗？现在想象一下，如果有三个特征，就需要3D空间，现在考虑N个特征，需要N维空间，对吗？这个N维空间就是它的特征空间。在我们的图像中，您可以将其视为具有两个特征的2D空间。)

现在一个新成员来到这个城镇，创建一个新的家，这个家被表现为绿色的圆圈。他应该被添加到蓝色/红色这两类家庭之一。我们把这个过程称为Classification。我们该怎么做？由于我们正在学习kNN，让我们应用这个算法。

一种方法是检查谁是他最近的邻居。从图象上来看，很明显是红三角家庭。所以他也被加入了红三角。这种方法被称为简单最近邻，因为分类只取决于最近的邻居。

但是有一个问题。红三角可能是最近的。但是如果靠近他的地方有很多蓝色方块呢？那么蓝色方块比红色三角在当地有更多的实力。所以只检查最近的一个是不够的。相反，我们检查一些（K个）最近的家庭。他们中谁占大多数，新人就属于那个家庭。在我们的图像中，让我们取k = 3，即3个最近的家庭。他有两个红色和一个蓝色（有两个蓝色等距，但是因为k = 3，我们只拿其中一个），所以他应该再加上红色家族。但是如果我们取k = 7呢？然后他有5个蓝色家庭和2个红色家庭。现在他应该被添加到蓝色家庭。所以这一切都随k的值而变化。更有趣的是，如果k = 4呢？他有2个红色和2个蓝色的邻居。这是个平局！所以k最好取成一个奇数。

所以这种方法称为 k-最近邻，因为分类依赖于k个最近的邻居。

接下来，在kNN中，我们考虑k个邻居，但我们同样重视所有的邻居，对吗？这对吗？例如，以k = 4的情况。我们说过这是一个平局。但是可以看到，这两个红色家庭比两个蓝色家庭更接近他。所以他更有资格加入到红色。那么我们如何数学解释呢？我们给每个家庭一些权重，取决于他们与新来者的距离。对于那些靠近他的人来说，获得更高的权重，而那些距离较远的人则获得更低的权重。然后我们分别对每个家庭的权重求和。谁拥有最高的总权重，新来者就会去那个家庭。这被称为修改过的kNN。

那么你在这里看到了什么重要的事情呢？

• 你需要了解城镇所有房屋的信息，对吧？因为，我们必须检查从新来者到所有现有房屋的距离，找到最近的邻居。如果有足够的房屋和家庭，需要大量的内存，还有更多的时间来计算。
• 几乎没有任何训练或准备的时间。

现在我们来看 OpenCV 中的 kNN。

OpenCV 中的 kNN

我们将在这里做一个简单的例子，有两个家庭（Classes），就像上面一样。 下一章我们会做一个更好的例子。

在这里，我们将红色家族标记为 Class-0（用0表示），将蓝色家族标记为 Class-1（用1表示）。 我们创建25个家庭或者说25个训练数据，并将其标记为Class-0或Class-1。 我们将Numpy的随机数生成器的帮助下完成所有这些工作。

然后我们在 Matplotlib 的帮助下绘制它。 红色家庭显示为红色三角形，蓝色家庭显示为蓝色正方形。

import cv2
import numpy as np
import matplotlib.pyplot as plt

# 25个已知（训练用）数据的(x,y)值集合
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# 给每一个数据一个label（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 特征数量$的浮点数组。然后我们找到新来者的最近邻居。我们可以指定我们想要的邻居数量。它返回：

1. 给新来者的标签，这取决于我们之前看到的 kNN 理论。如果您想要使用简单最近邻算法，只需指定 k = 1，其中k是邻居数。
2. 最近邻居的标签。
3. 从新来者到每个最近邻居的相应距离。

那么让我们看看它是如何工作的。新来者被标记为绿色。

newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
knn = cv2.ml.KNearest_create()
knn.train(trainData, cv2.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个邻居，都来自蓝色家庭。 因此，他被称归类到蓝色家庭。

如果你有大量的数据，你可以将它作为数组传递。 相应的结果也可以作为数组获得。

# 10个新来的
newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)
ret, results,neighbours,dist = knn.findNearest(newcomer, 3)
# 结果也会包含10个labels

更多资源

NPTEL notes on Pattern Recognition, Chapter 11