8.1.1 了解k-最近邻算法 - OpenCV 中文文档

返回介绍

8.1.1 了解k-最近邻算法

发布于 2019-07-01 字数 5741 浏览 892 评论 0

目标

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

理论基础

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

image

在图像中,有两类家庭,蓝色方块和红色三角形。我们称每种家庭为一个为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算法,并入trainDataresponses来训练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个邻居,都来自蓝色家庭。 因此,他被称归类到蓝色家庭。 从下图可以看出:

image

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

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

更多资源

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

目前还没有任何评论,快来抢沙发吧!