Skip to content

理解 K-最近邻算法

目标

在本章中,我们将理解 K-最近邻(kNN)算法的基本概念。

原理

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

图片

在上图中,有两个家族,蓝色方块和红色三角形。我们将每个家族称之为 。他们的房子在我们称之为特征空间的城镇地图上显示出来。*(你可以把特征空间理解为一个投影了所有数据的空间。例如,想象一个二维坐标空间。每个元素有两个特征,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 的帮助下绘制它。 红色家族显示为红色三角形,蓝色家族显示为蓝色方块。

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

# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0,2,(25,1)).astype(np.float32)

# Take Red families and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')

# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')

plt.show()

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

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

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

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

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 个邻居,全部来自蓝色家族。因此,他被贴上了蓝色家族的标签。下图更为明显:

图片

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

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

其他资源

  1.NPTEL notes on Pattern Recognition, Chapter 11

练习



回到顶部