目标
- 本节要理解 k 近邻（kNN）的基本概念。
原理
kNN 可以说是最简单的监督学习分类器了。 想法也很简单，就是找出测试数据在特征空间中的最近邻居。 将使用下面的图片介绍它。
上图中的对象可以分成两组，蓝色方块和红色三角。 每一组也可以称为一个类。 可以把所有的这些对象看成是一个城镇中房子， 而所有的房子分别属于蓝色和红色家族， 而这个城镇就是所谓的特征空间。 （可以把一个特征空间看成是所有点的投影所在的空间。 例如在一个 2D 的坐标空间中， 每个数据都两个特征 x 坐标和 y 坐标， 可以在 2D 坐标空间中表示这些数据。 如果每个数据都有 3 个特征呢， 就需要一个 3D 空间。N 个特征就需要 N 维空间， 这个 N 维空间就是特征空间。 在上图中，可以认为是具有两个特征色2D 空间）。
现在城镇中来了一个新人， 他的新房子用绿色圆盘表示， 要根据他房子的位置把他归为蓝色家族或红色家族。 我们把这过程成为 分类。 应该怎么做呢？ 因为正在学习看 kNN， 那么就使用一下这个算法吧。
一个方法就是查看他最近的邻居属于那个家族， 从图像中知道最近的是红色三角家族。 所以他被分到红色家族。 这种方法被称为简单 近邻， 因为分类仅仅决定与它最近的邻居。
但是这里还有一个问题。 红色三角可能是最近的， 但如果他周围还有很多蓝色方块怎么办呢？ 此时蓝色方块对局部的影响应该大于红色三角。 所以仅仅检测最近的一个邻居是不足的。 所以检测 k 个最近邻居。 谁在这 k 个邻居中占据多数， 那新的成员就属于谁那一类。 如果 k 等于 3，也就是在上面图像中检测 3 个最近的邻居。 他有两个红的和一个蓝的邻居， 所以他还是属于红色家族。 但是如果 k 等于 7 呢？他有 5 个蓝色和 2 个红色邻居， 现在他就会被分到蓝色家族了。k 的取值对结果影响非常大。 更有趣的是，如果 k 等于 4呢？两个红两个蓝。这是一个死结。 所以 k 的取值最好为奇数。 这中根据 k 个最近邻居进行分类的方法被称为 kNN。
在 kNN 中考虑了 k 个最近邻居， 但是给了这些邻居相等的权重，这样做公平吗？ 以 k 等于 4 为例，我们说她是一个死结。 但是两个红色三角比两个蓝色方块距离新成员更近一些。 所以他更应该被分为红色家族。 那用数学应该如何表示呢？ 要根据每个房子与新房子的距离对每个房子赋予不同的权重。 距离近的具有更高的权重， 距离远的权重更低。 然后根据两个家族的权重和来判断新房子的归属， 谁的权重大就属于谁。这被称为 修改过的kNN。
那这里面些是重要的呢？
需要整个城镇中每个房子的信息。 因为要测量新来者到所有现存房子的距离，并在其中找到最近的。 如果那里有很多房子，就要占用很大的内存和更多的计算时间。
训练和处理几乎不需要时间。
现在看看 OpenCV 中的 kNN。
OpenCV 中的 kNN
这里来举一个简单的例子，和上面一样有两个类。 下一节会有一个更好的例子。
这里将红色家族标记为 Class-0，蓝色家族标记为 Class-1。 还要再创建 25 个训练数据， 把它们非别标记为 Class-0 或者 Class-1。 Numpy中随机数产生器可以帮助完成这个任务。 然后借助 Matplotlib 将这些点绘制出来。 红色家族显示为红色三角蓝色家族显示为蓝色方块。
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_779/1971010778.py:13: 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_779/1971010778.py:17: 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 算法分类器的初始化，要传入一个训练数据集， 以及与训练数据对应的分类来训练 kNN 分类器（构建搜索树）。 最后要使用 OpenCV 中的 kNN 分类器，给它一个测试数据， 让它来进行分类。 在使用 kNN 之前，应该对测试数据有所了解。 数据应该是大小为数据数目乘以特征数目的浮点性数组。 然后就可以通过计算找到测试数据最近的邻居了。 可以设置返回的最近邻居的数目。返回值包括：
- 由 kNN 算法计算得到的测试数据的类别标志（0 或 1）。如果想使用最近邻算法，只需要将 k 设置为 1，k 就是最近邻的数目。
- 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()
/tmp/ipykernel_779/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: [[0.]] neighbours: [[0. 0. 0.]] distance: [[ 34. 160. 292.]]
下面是得到的结果：
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.