目录
一、环境
二、读取数据
三、基于KNN实现分类
四、总结
python, opencv
用到的数据集是mnist数据集，下载地址，数据集每个文件的格式在官网中都有介绍，训练集一共60000张图像，测试集一共10000张图像，图像大小为28*28，以下代码注意更改文件路径：
import numpy as np from struct import unpack # 读入图像 def ReadImgFile(filepath): with open(filepath, 'rb') as f: _, img_num, h, w = unpack('>4I', f.read(16)) # fromfile()函数读取数据时需要用户指定文件中的元素类型 img = np.fromfile(f, dtype = np.uint8).reshape(img_num, h * w) return img_num, h, w, img # 读入图像标签 def ReadLableFIle(filepath): with open(filepath, 'rb') as f: _, img_num = unpack('>2I', f.read(8)) label = np.fromfile(f, dtype = np.uint8).reshape(img_num, 1) return img_num, label # 读取训练集和测试集的图像和标签 train_img_num, train_h, train_w, train_img = ReadImgFile('./mnistdata/train-images.idx3-ubyte') train_label_num, train_label = ReadLableFIle('./mnistdata/train-labels.idx1-ubyte') test_img_num, test_h, test_w, test_img = ReadImgFile('./mnistdata/t10k-images.idx3-ubyte') test_label_num, test_label = ReadLableFIle('./mnistdata/t10k-labels.idx1-ubyte')数据集读入完成后可以调用matplotlib显示训练集和测试集的前5张图片
import matplotlib.pyplot as plt def Display(img, label, h, w, num): fig = plt.figure() # 使用figure()命令来产生一个图 for i in range(num): im = img[i].reshape([h, w]) # 将一维的像素矩阵reshape成原图像大小的二维矩阵 # add_subplot把图分割成多个子图，三个参数分别为行数、列数、当前子图位置 ax = fig.add_subplot(1, num, i + 1) ax.set_title(str(label[i])) # 每个子图的命名为其标签 ax.axis('off') # 隐藏坐标 ax.imshow(im, cmap='gray') plt.show() Display(train_img, train_label, train_h, train_w, 5) # 显示训练集前5张图像 Display(test_img, test_label, test_h, test_w, 5) # 显示测试集前5张图像KNN是监督学习中最简单的算法之一，这里只讨论将KNN用于分类的情况，其基本思想是将已知类别的数据映射到特征空间中，对于未知类别的数据，在特征空间中寻找与它最接近的匹配。以mnist数据集为例，KNN的输入是训练集所有图像的特征向量和图像对应的标签，这里选取图像的像素值作为特征向量，即28*28=784维，对于新来的测试图像，计算它的特征向量与训练集每个特征向量的距离，选择距离最近的k个训练数据的标签的众数作为当前测试图像的标签，即k个邻居中，哪种标签出现的频率最高，就认为测试图像属于该分类，具体的理解可以参照OpenCV-KNN的官网
基于OpenCV的实现可以参考OpenCV官网：OpenCV-KNN，调用cv2.ml.KNearest_create()创建一个KNN分类器，然后调用train方法进行训练，调用findNearest方法进行测试，findNearest的返回值result表示根据knn算法得到的测试图像对应的标签，neighbours表示测试图像的k个最近邻，dist表示相应最近邻的距离
以下代码中k = 5表示选择5个最近邻（k的取值一般小于20），用5个邻居标签的众数作为当前测试图像的标签，取众数是因为这里的分类任务一张图像对应一个标签。代码中result.shape = (10000, )，neighbours.shape = (10000, 5)，dist.shape = (10000, 5)，最后测试得到的准确率是96.88%，修改k的值会得到不同的准确率
import cv2 # 将所有数据转成np.float32类型 train_img = train_img.astype(np.float32) train_label = train_label.astype(np.float32) test_img = test_img.astype(np.float32) test_label = test_label.astype(np.float32) # 调用OpenCV的knn实现分类 knn = cv2.ml.KNearest_create() knn.train(train_img, cv2.ml.ROW_SAMPLE, train_label) ret, result, neighbours, dist = knn.findNearest(test_img, k = 5) # 计算预测准确率 matches = result == test_label correct = np.count_nonzero(matches) accuracy = float(correct)/float(test_img_num) print("accuracy:", accuracy)测试得到result后可以调用之前的Display函数显示前10张图像，看预测的标签是否和真实标签一致，从下面图片中可以看到前10张图像预测的标签和真实标签是一致的
Display(test_img, test_lable, test_h, test_w, 10) # 显示前10张图像及其真实标签 Display(test_img, result, test_h, test_w, 10) # 显示前10张图像及其预测标签也可以自己实现KNN算法，距离度量可以选择L1距离，L2距离(欧氏距离)，余弦距离等，下面的代码选取了1000张图像作为训练集，200张图像作为测试集，当k = 5时，选择L1距离的准确率为82.5%，选择L2距离的准确率为86%，选择余弦距离的准确率为82.5%，调整训练图像和测试图像的数量可以得到不同的结果
def MyKNN(train, test, train_num, test_num, train_label, test_label, k): test_predict = np.zeros([test_num, 1]) for test_id in range(test_num): t_img = test[test_id] diff = np.sum(np.abs(train - t_img), axis = 1) # L1距离 # diff = np.sqrt(np.sum(np.square(train - t_img), axis = 1)) # L2距离 # diff = 1 - np.sum(train * t_img, axis = 1) / \ # (np.sqrt(np.sum(train**2, axis = 1)) + np.sqrt(np.sum(t_img**2))) # 余弦距离 index = np.argsort(diff)[:k] # 找出k个最近邻的下标 k_label = train_label[index].reshape([1,-1])[0].astype(np.int64) # 找出对应的标签 test_predict[test_id] = np.argmax(np.bincount(k_label)) # 计算k个最近邻标签的众数作为测试图像的标签 return test_predict # 将所有数据转成np.float32类型 train_img = train_img.astype(np.float32) train_label = train_label.astype(np.float32) test_img = test_img.astype(np.float32) test_label = test_label.astype(np.float32) train_num = 1000 test_num = 200 result = MyKNN(train_img[:train_num,:], test_img[:test_num,:], train_num, test_num, \ train_label[:train_num,:], test_label[:test_num,:], 1) # 计算准确率 matches = result == test_label[:test_num,:] correct = np.count_nonzero(matches) accuracy = float(correct)/float(test_num) print("accuracy:", accuracy)调用Display函数输出前10张图像的真实标签和用预测标签（L2距离），结果如图，可以看到画红线的几个测试图像预测错误
以上实现需注意在计算之前先转换数据类型，把np.uint8转成np.float32，否则会导致计算错误，在调用OpenCV的KNN时如果不转换数据类型会报错：error: (-215:Assertion failed) samples.type() == CV_32F || samples.type() == CV_32S in function 'setData'，但自己实现时如果不转换会直接导致计算错误，原因是numpy的加减运算会自动返回输入数据类型，np.uint8在内存中占8位，只能表示0~255之间的数，两个像素相减如果等于负数就会导致结果出错，比如3 - 5 = -2，而在计算机中的运算为0000 0101 (3) + 1111 0111 (-5，用补码表示) = 1111 1100 (254)
KNN算法的优点在于简单、易于理解，对异常值不敏感，不需要参数估计，也不需要预先训练；缺点是计算量大，且训练数据必须存储在本地，内存开销大。
