理解 K-最近邻算法

目标

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

原理

kNN 是可用于监督学习的最简单的分类算法之一。其主要思路是在特征空间中搜索最接近测试数据的匹配项。我们可以用下图来表示它

理解 K-最近邻算法 - 图1
图像

在上图中，有两个家族，蓝色方块和红色三角形。我们将每个家族称之为类 。他们的房子在我们称之为特征空间的城镇地图上显示出来。*（你可以把特征空间理解为一个投影了所有数据的空间。例如，想象一个二维坐标空间。每个元素有两个特征，x 和 y 坐标。你可以在你的二维坐标空间里表示这些元素，对不对？现在想象一下，如果有 3 个特征，你需要 3 维空间。如果有 N 个特征，你需要 N 维空间，对不对？这个 N 维空间就是它的特征空间。在我们的图像中，你可以把它当作一个有着两个特征的 2 维案例）*。

现在，一个新成员进入城镇并创建了一个新家，显示为绿色圆圈。他将被加入到 Blue/Red 家族中的一个。我们将该过程称为分类。那么，我们该怎么做？由于我们正在研究 kNN，那么让我们应用这个算法。

一种方法是检查谁是他最近的邻居，从图像来看，很明显是红色三角形家族。所以他也被加入到红色三角形家族。此方法简称为最近邻，因为分类仅取决于最近邻居。

但是，这有个问题。红色三角形可能是最近的，但如果有很多蓝色方块也和他很近，那会怎么样呢？那么，蓝色方块在该地区有着比红色三角形更强的影响力，因此，仅仅检查最近的一个邻居是不够的。取而代之，我们检查 k 个最近的邻居，然后，谁占大多数，新人就属于那个家族。在我们的图像中，让我们取 k=3，即 3 个最近的邻居。他有 2 个红色邻居和 1 个蓝色邻居（有两个蓝色邻居的距离是一样的，但因为 k=3，所有我们只取他们中的一个），因此，他再一次应该被加到红色家族。但是，如果我们取 k=7 又会如何？会发现，他有 5 个蓝色邻居和 2 个红色邻居。很好！！现在，他应该被加入到蓝色家族。我们可以看到，这些变化都取决于 k 的值。更有趣的是，如果 k=4 会怎么样？他将有 2 个红色邻居和 2 个蓝色邻居。一个平局！！！因此，k 最好取一个奇数。因为分类取决于 k 个最近的邻居，所有这种方法被称为 K-最近邻算法

再想想，在 kNN 中，我们考虑了 k 个邻居，这没问题，但是，每个邻居我们都给了相同的权重，这样对吗？这样公平吗？举例来说，就举 k=4 的例子吧，我们说这是一个平局，但是，仔细想想，2 个红色邻居比 2 个蓝色邻居离他更近，所以他更有资格加入到红色家族。那么我们怎么在数学上表示这一点呢？我们根据他们与新来者的距离给每个家庭一些权重。对于那些靠近他的家庭来说，获得更高的权重，而那些距离较远的家庭则获得较低的权重。然后，我们分别计算每个家族的总权重。谁的总权重高，新来者就加入那个家族。这就是修改后的 kNN

那么，讲到这里，什么是重要的呢？

  • 你需要小镇上所有房子的信息，对不对？因为，我们必须检查新人到所有现有房屋的距离，以找到最近的邻居。如果有很多房屋和家族，那么将占用很多内存，计算上也将更费时间。
  • 在训练和预处理上几乎不花时间

现在，让我们看看 OpenCV 中的 kNN。

OpenCV 中的 kNN

我们将在这里举一个简单的例子，有两个家族（类），就像上面一样。然后在下一章中，我们将举一个更好的例子。

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

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

  1. import cv2 as cv
  2. import numpy as np
  3. import matplotlib.pyplot as plt
  5. # Feature set containing (x,y) values of 25 known/training data
  6. trainData = np.random.randint(0,100,(25,2)).astype(np.float32)
  8. # Labels each one either Red or Blue with numbers 0 and 1
  9. responses = np.random.randint(0,2,(25,1)).astype(np.float32)
  11. # Take Red families and plot them
  12. red = trainData[responses.ravel()==0]
  13. plt.scatter(red[:,0],red[:,1],80,'r','^')
  15. # Take Blue families and plot them
  16. blue = trainData[responses.ravel()==1]
  17. plt.scatter(blue[:,0],blue[:,1],80,'b','s')
  19. plt.show()

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

接下来初始化 kNN 算法，并把训练数据和响应传递给它，以训练 kNN（构建一个搜索树）。

然后我们将引入一个新成员，并在 OpenCV 的 kNN 的帮助下将他归类到某个家族。在讲 kNN 之前，我们需要了解一些关于测试数据（新成员的数据）的知识。我们的数据应该是一个浮点数数组，其大小为 测试数据的个数 × 特征数。然后，我们找到了新成员的最近的邻居们。我们可以指定最近的邻居的数量。返回如下内容：
  1.新成员的标签取决于我们之前所说的 kNN 理论。如果你想用最近邻算法，只要指定 k=1 就可以了，这里的 k 是邻居的个数。
  2.k 个邻居的标签
  3.从新成员到每个邻居的距离

接下来，让我们看看它是如何工作的。新成员被标记为绿色。

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

我得到了如下结果：

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

这说明我们的新成员有 3 个邻居，全部来自蓝色家族。因此，他被贴上了蓝色家族的标签。下图更为明显：

理解 K-最近邻算法 - 图2
图像

如果你的测试数据很多，你可以使用数组。对应的结果也是个数组。

  1. # 10 new comers
  2. newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)
  3. ret, results,neighbours,dist = knn.findNearest(newcomer, 3)
  4. # The results also will contain 10 labels.

其他资源

  1.NPTEL notes on Pattern Recognition, Chapter 11

练习