本章将学习k近邻（kNN）算法的核心概念。
理论基础
kNN是监督学习中最简单的分类算法之一。 其核心思想是：在特征空间中，寻找测试数据的最接近邻点（即与测试样本特征距离最近的训练样本）。 我们将通过下图进一步说明这一过程。
图中展示了两个家族，$Blue Squares and Red Triangles$。将每个家族称为类别。 它们的房屋分布在城镇地图上，我们称之为 $feature space$。 （可以将特征空间想象为所有数据投射的空间。例如，一个二维坐标空间中，每个数据拥有两个特征——x和y坐标。 你可以在二维坐标系中表示这个数据，对吧？ 如果有三个特征，就需要三维空间。现在假设有N个特征，就需要N维空间。 这个N维空间就是其特征空间。在图中可以将其视为拥有两个特征的二维案例。）
此时，一个新成员来到镇上并建了一座新房，图中用绿色圆圈表示。 需要被归入蓝/红家族之一。我们将这一过程称为分类。该怎么做？ 既然我们讨论的是kNN算法，那就应用它来解决。
一种方法是查看谁是它的最近邻居。 从图中可以明显看出，最近的是红色三角家族。 因此它也会被归入红色三角。这种方法称为最近邻算法，因为分类仅取决于最近的邻居。 但这里有一个问题。红色三角形可能是最近的，但如果它周围有很多蓝色方块呢？ 那么蓝色方块在该局部区域的力量就比红色三角形更强。 因此，仅检查最近的一个是不够的。相反需要检查最近的 $k$ 家族。 然后，在这 $k$ 个邻居中，哪个家族占多数，新成员就属于那个家族。
在图像中，假设 $k=3$，即最近的3个家族。 新成员有2个红色和1个蓝色邻居（虽然有2个蓝色距离相同，但由于 $k=3$，只取其中一个），因此它仍然应该被归为红色家族。 但如果 $k=7$ 呢？此时它有5个蓝色和2个红色邻居。太好了！现在它应该属于蓝色家族。 所以，分类结果完全取决于 $k$ 的取值。更有趣的是，如果 $k = 4$呢？ 它有2个红色和2个蓝色邻居，出现了平局！因此，最好选择奇数作为 $k$ 的值。
因此，这种方法被称为k-最近邻（k-Nearest Neighbour），因为分类取决于k个最近邻。
在kNN算法中，虽然确实考虑了 $k=4$ 个邻居，但对所有邻居都一视同仁，这公平吗？ 举个例子，当k=4时，我们说出现了平局（2红 vs 2蓝）。 但仔细观察，那两个红色家族其实比蓝色家族离新成员更近。 因此它更应该被归为红色家族。那么，如何用数学方式解释这一点呢？
可以根据每个家族与新成员的距离赋予不同的权重——离得越近的家族权重越高，离得越远的权重越低。 分别计算每个家族的总权重，最终将新成员归类到总权重更高的那个家族。 这种方法被称为改进版kNN（modified kNN）。
那么，这里有哪些关键点需要注意呢？
- 没错，您需要掌握镇上所有房屋的信息，对吧？ 因为我们必须计算新成员与每栋现有房屋的距离，才能找到最近的邻居。 如果房屋和家族数量庞大，这会占用大量内存，计算时间也会大幅增加。
- 这种方法几乎不需要任何训练或前期准备时间。
现在，让我们看看如何在OpenCV中实现kNN算法。
OpenCV中的kNN
接下来将做一个简单的示例，只包含两个家族（类别），就像前面的例子一样。 下一章会实现更复杂的案例。
在这里将红色家族标记为Class-0（用数字0表示），蓝色家族标记为Class-1（用数字1表示）。
我们创建了25个家族（即25个训练数据），并将它们分别归类为Class-0或Class-1。
这些数据的生成借助了NumPy的随机数生成器。
使用 Matplotlib 进行可视化：红色家族显示为红色三角形，蓝色家族显示为蓝色方块。
%matplotlib inline
import cv2
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()
/tmp/ipykernel_3645/2484227576.py:15: MatplotlibDeprecationWarning: Passing the marker parameter of scatter() positionally is deprecated since Matplotlib 3.9; the parameter will become keyword-only in 3.11. plt.scatter(red[:,0],red[:,1],80,'r','^') /tmp/ipykernel_3645/2484227576.py:19: MatplotlibDeprecationWarning: Passing the marker parameter of scatter() positionally is deprecated since Matplotlib 3.9; the parameter will become keyword-only in 3.11. plt.scatter(blue[:,0],blue[:,1],80,'b','s')
运行代码后，会得到类似第一张图的分布。 由于使用了随机数生成器，每次运行代码时生成的数据都会不同。
接下来初始化kNN算法，并传入训练数据 $trainData$ 和对应标签 $responses$ 来训练kNN模型（该过程会构建一个搜索树）。 然后将引入一个新成员，并通过 OpenCV 的 kNN 对其所属家族进行分类。 在使用kNN之前，需要明确测试数据（即新成员数据）的格式要求：数据必须是浮点型数组， 其尺寸为 $number \; of \; testdata \times number \; of \; features$。
算法会返回以下结果：
- 分配给新成员的标签：基于之前讨论的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 = cv2.knn()
# knn = cv2.KNearest()
# https://blog.csdn.net/zhangpan929/article/details/86217374
knn = cv2.ml.KNearest_create()
# knn.train(trainData,responses)
knn.train(trainData, cv2.ml.ROW_SAMPLE, responses)
# ret, results, neighbours ,dist = knn.find_nearest(newcomer, 3)
ret, results, neighbours ,dist = knn.findNearest(newcomer, 3)
print ("result: ", results,"\n")
print ("neighbours: ", neighbours,"\n")
print ("distance: ", dist)
plt.show()
result: [[1.]] neighbours: [[1. 1. 1.]] distance: [[125. 173. 194.]]
/tmp/ipykernel_3645/2220963273.py:2: MatplotlibDeprecationWarning: Passing the marker parameter of scatter() positionally is deprecated since Matplotlib 3.9; the parameter will become keyword-only in 3.11. plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
得到的结果如下所示：
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.