这篇博客将介绍将K-最近邻 (KNN K-Nearest Neighbor) 算法及改进版的K近邻，并演示如何根据K近邻进行简单的分类；
KNN 是可用于监督学习的最简单的分类算法之一，是在特征空间中搜索测试数据的最接近匹配。
KNN & 改进的KNN
- 分类时，仅考虑距离，最好将 k 作为奇数，称之为 k-Nearest Neighbor，K近邻。
- 同样的，对于靠近它的人获得更高的权重，而远离它的人获得更低的权重。 谁的总权重最高，新人就会进入哪个类，这称为改进的 KNN。
如上图有俩个类（红色三角和蓝色方形），假设新进来一个绿色圆，那么仅考虑K近邻，如果k=1，则绿色圆属于红色；
如果k=3，则绿色圆属于红色；如果k=7，则绿色圆属于蓝色方形。那么k=4时，2个方形、2个三角，这应该怎么分类呢？
因此K近邻中最好k为奇数，以及使用改进的KNN。
1. 效果图
随意生成若干点图如下：
任意生成25个点，0：红色三角，1：蓝色方形；
随意增加一个绿色点，并预测其属于哪种类别，效果图如下：
result: [[0.]]
neighbours: [[0. 0. 0.]]
distance: [[ 25. 122. 1765.]]
可以看到下图中绿色近邻3个点为红色，预测结果也为0红色；
随意增加10个新加入的绿色点，效果图如下：
可以看到如下的预测结果中，10个点中9个的近邻点多为0：红色三角，1个点的3个近邻点多为1：蓝色方形。
result: [[0.]
[0.]
[0.]
[0.]
[0.]
[0.]
[0.]
[1.]
[0.]
[0.]]
2. 源码
# K近邻 & 改进版的K近邻(权重)
# K近邻，随机生成一堆点分类为0：红色三角，1：蓝色方形。并训练KNN模型
# 然后对新加入的一个点或者多个点寻找K近邻，并预测其属于哪个分类。
# K必须为奇数，因此当3近邻时，平均法确保能找到属于固定的哪个类别；
# 改进的KNN,K为奇数,且不同的类别具有不同的权重.
import cv2
import matplotlib.pyplot as plt
import numpy as np
# 随机构建25个点，用于测试
trainData = np.random.randint(0, 100, (25, 2)).astype(np.float32)
# 随机分类标签为 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()
# 增加1个新来者，根据k近邻3近邻来确定属于哪个分组
# newcomer = np.random.randint(0, 100, (1, 2)).astype(np.float32)
# 增加10个新来者
newcomer = np.random.randint(0,100,(10,2)).astype(np.float32)
plt.scatter(newcomer[:, 0], newcomer[:, 1], 80, 'g', 'o')
knn = cv2.ml.KNearest_create()
print('knn: ', knn)
print(type(trainData))
knn.train(trainData, cv2.ml.ROW_SAMPLE, responses)
ret, results, neighbours, dist = knn.findNearest(newcomer, 3)
print("ret: ", ret)
print("result: ", results)
print("neighbours: ", neighbours)
print("distance: ", dist)
plt.show()