写在前面

如果说上一篇博客的鸢尾花有一点抽象的话，那么我们可以在MNIST手写数字数据集中看到更加直观的结果。
利用KNN识别MNIST手写数字体。或许可以浅显地认为KNN在计算机视觉领域也有一定用武之地。算法最终可以达到90%的准确度。

说明

与上一篇博客一样，KNN算法没有任何的训练过程，test, train的起名只是为了叙说方便，其意义见下：

• test: 待分类样本
• train: 已分类样本(邻居)

KNN识别MNIST手写数字体流程

为了实现KNN算法分类手写字体集

• 首先需要从网上下载MNIST手写体数据集
• 接着需要对数据集进行处理，以得到np.array类型的image原始数据和label标签
• 同时进行数据集的划分与灰度二值化，得到最终的训练集与测试集
• 接下来使用在上一篇博客中已经编写好的KNN算法对数据进行近邻算法处理，最后对实验结果进行分析与讨论。

网络下载MNIST数据集

笔者采用手动下载的形式，即通过互联网，在网站：
http://yann.lecun.com/exdb/mnist/
进行数据包下载，最终可以得到四个文件。

可以看出，官网上其实已经对数据集进行分类，train数据集带有60000个image以及label，t10k也就是test数据集带有10000个image以及label.

对MNIST原始数据集进行处理

官网给出了数据集数据类型的介绍：
TRAINING SET LABEL FILE (train-labels-idx1-ubyte):

[offset] [type] [value] [description]
0000 32 bit integer 0x00000801(2049) magic number (MSB first)
0004 32 bit integer 60000 number of items
0008 unsigned byte ?? label
0009 unsigned byte ?? label
……..
xxxx unsigned byte ?? label
The labels values are 0 to 9.

#获取MNIST数据集
import os
import struct
import math
import numpy as np
import matplotlib.pyplot as plt

#获得np.array形式的原始样本数据
def load_mnist(path, kind="train"):
    labels_path = os.path.join(path, '%s-labels.idx1-ubyte' % kind)
    images_path = os.path.join(path, '%s-images.idx3-ubyte' % kind)

    with open(labels_path, 'rb') as lbpath:
        magic, n = struct.unpack('>II', lbpath.read(8))
        # 'I'表示一个无符号整数，大小为四个字节
        # '>II'表示读取两个无符号整数，即8个字节
        labels = np.fromfile(lbpath, dtype=np.uint8)

    with open(images_path, 'rb') as imgpath:
        magic, num, rows, cols =  struct.unpack('>IIII', imgpath.read(16))
        images = np.fromfile(imgpath, dtype=np.uint8).reshape(len(labels), 784)

    return images, labels

可以看出，其原始数据类型并不可以直接用来进行聚类(需要np.array类型)，因此需要对原始数据进行处理，首先使用os.path.join()读入磁盘上的文件，接着通过struct.unpack获得数据集大小，数据的行数以及列数，最后通过fromfile方法获得np.array类型的label以及image数据。通过函数shape、type观察返回的数据大小以及类型。输出如下：

行的个数代表样本个数，而列的个数意义为每一个构成image的28·28像素点展开的784个元素，简而言之每行代表了一张照片，为了形象的演示效果，利用reshape()将每一行向量重塑为28·28的灰度矩阵，并利用plt.imshow()绘制照片以显示：

可以看出，图片中的手写体数字为5，与label数据集相对应，证明代码处理正确。

x_train_data, y_train_data = load_mnist("/Users/xxx/Desktop/", kind="train")
#验证数据采样正确
    random_index = np.random.choice(len(x_train_data), 1, replace=False, p=None)
    img = x_train_data[random_index].reshape(28, 28)
    print('index为:', random_index, '该图片标签为:', y_train_data[random_index])
    plt.imshow(img, cmap='Greys', interpolation='nearest')
    plt.show()

数据集的划分与灰度二值化

即使原数据已经为我们分配好了参数，但是60000的样本大小对于程序来说仍然十分消耗时间，因此需要利用np.random.choice()进行样本的抽取，进而实现样本数量的减少。

def final_minst_data(x_test_data, x_train_data, y_test_data, y_train_data, test_num=0.3):
    #进行数据集处理 X_train_data是一个60000行28*28=784列数据，X_test_data是一个10000行28*28=784列数据,y_train是一个60000列行向量
    #数据量太大，进行random抽取
    data_num = int(input('请输入您想要训练的样本总个数（训练集和测试集之和）:'))
    test_num = round(data_num * test_num)
    train_num = data_num - test_num
    test_index = np.random.choice(len(x_test_data), test_num, replace = False)
    train_index = np.random.choice(len(x_train_data), train_num, replace = False)

    x_test = x_test_data[test_index , :]        #image的测试集数据
    y_test = y_test_data[test_index]            #label的测试集数据


    x_train = x_train_data[train_index , :]      #image的训练集数据
    y_train = y_train_data[train_index]          #label的训练集数据
    return x_test, y_test, x_train, y_train, test_index, train_index

如果简单的使用原始MNIST数据进行KNN聚类，会发现大多的数据都被分类为label=1，由于灰度通道的影响，距离收到了很大的印象，因此需要对原始数据进行灰度二值化，其处理简单且有效，即将行向量中>127的数值设为1，<=127的数值设为0，最终的准确率得到了大幅度提高。

def binaryzation(x_test, x_train):
    #二值化进行处理，大于127为1，小于127为0
    for i in range(int(x_test.shape[0])):
        for j in range(int(x_test.shape[1])):
            if x_test[i,j] > 127:
                x_test[i,j] = 1
            else:
                x_test[i,j] = 0

    for i in range(int(x_train.shape[0])):
        for j in range(int(x_train.shape[1])):
            if x_train[i,j] > 127:
                x_train[i,j] = 1
            else:
                x_train[i,j] = 0
    return x_test, x_train

距离矩阵获取

与上篇博客的实现过程基本一致:

• 即通过欧式距离公式(图片的每一个对应的像素进行灰度通道的做差)，创建test和train之间的带有顺序的欧式距离的二维距离矩阵，并且同时获得二维距离矩阵每一个距离元素，即train集合，相之对应的在原数据集中的索引以及label类别标签
• 最后根据K近邻算法的定义，获得不同K下的预测结果以及算法准确率，并在此过程中规避可能出现的非正常情况，下面各部分进行详细分析

根据欧式距离定义有：

根据此公式建立具有如下特性的欧式距离矩阵：

• 大小为number_test*number_train的矩阵，行的个数为待分类样本个数，列的个数为已分类样本个数，test与train比例默认为3:7
• 其中每一个元素都储存了该元素对所代表与train样本之间的欧式距离，接下来对距离进行排序
  • 首先将距离矩阵每一行与train各个元素相对应的索引利用zip()函数绑定为元组，并利用dict()函数创建字典，这样之后，字典中的key意义为train在原样本中的索引，字典中的value意义为行test与该train之间的欧式距离
  • 接着利用sorted()函数对字典中的value进行排序，同时更关键的可以提取与value相对应的keys值，即获得train排序后的在原样本中的索引，与此同时也可以通过该索引矩阵获得train所属的label(0-9)，其最终效果如下:

首先是未排序的欧式距离矩阵：

同时获得排序后的欧式距离矩阵：

其次是与已经排序的欧式距离矩阵相之对应的train索引矩阵：

且通过索引矩阵获得train在原样本中所属的种类矩阵：

最后统计与test相邻最近的train样本,即实现KNN算法：
当获得train在原样本中所属的种类矩阵之后，由于其本身就带有排序的距离信息，即第一列为相距test最近的元素，第二列次近，以此类推，这时，利用for循环查看K不同取值下的算法准确率，根据KNN算法定义，统计种类矩阵中前K列的出现最多的种类作为该待分类样本的种类，并且同时为了防止有两种及以上类型都是出现次数最多的类型情况出现，需要利用count()对数组中最大数出现的次数进行判断，最后根据公式：

获得不用K取值下的算法准确率，利用plt.plot()对结果进行可视化输出，其最终效果如下：

同时利用sklearn.metrics中的accuracy.score()获得准确率，与自己编写的进行对比：

结果一致，证明编写的程序正确，同时通过可视化图像可以看出，KNN聚类当K取值在5左右时的算法准确率最多高达90%，有着良好的分类效果。

写在最后

本文使用MNIST数据集，验证了KNN在图像分类问题中仍可以取得不俗的性能表现，但也不难发现，90%的准确率相较于基于学习的方法实在是不算很高。后浪退前浪，一浪更比一浪强。