2019-09-25

KNN实现手写数字识别(KNN handwriting recognization)

by lucainiaoge

Intro

（这其实是我第一次真正意义上的手写数字识别，使用KNN方法）

之前在某宝上买来了一个小姐姐给的吴恩达作业（小姐姐讲解声音真的好听！），但是学完了（包括手写数字识别的手打BP神经网络实现），发现自己弄还是不会！现在，上了模式识别课程，一切重新开始！

学校开的模式识别选修课使我重新捡起python了。模式识别其实挺有意思的，就是需要有些代码工程开发经验才可以更好地学习。这篇博客记载了我完成这门课的第一个作业的过程。

What is KNN

KNN是什么？其实很简单：

看这里

kNN算法:K最近邻(kNN,k-NearestNeighbor)分类算法 - JYRoy - 博客园

机器学习(二):k近邻法(kNN) - E博客 - CSDN博客

没必要看完，知道概念就行。

Purpose

就是用手写数字图片训练你的机器，让你的机器可以识别其他的手写数字。

课程群里有人问有没有baseline，无知的我竟然不知道这个词是啥意思！果断百度！
Benchmark和Baseline是什么：CSDN-【简单易懂】Benchmark和baseline的区别！

助教回答：木有baseline。开心！

How to Read Dataset Using Python

拿到作业的时候，我的电脑Python是炸的，数据集怎么读不知道，甚至连能不能做出来都不知道……

课上头铁看书不听课，结果书的前面讲的贝叶斯分类，老师却直接讲KNN，并且留了KNN实现手写数字识别的作业，整的我挺慌。

那么，就这样开始了~

老舍友lmh大神花了一天时间，搞出来了并且把代码挂到了github上（看这里www.github.com/bugstop/handwritten-digit-recognition-knn），附带转发知乎回答：室友想抄我的代码，给还是不给……

首先，拿到大佬的开源代码，又是logging又是threading的（python里面我不明白的操作），我也是一脸懵逼的。不管了，立个小目标：读取数据集。

Information about the dataset format

怎么读这来自远古的文件？不好好看消息记录的我竟然不知道助教大大发了数据集官网！

来自几位大佬的手写数字数据集官网：http://yann.lecun.com/exdb/mnist/

没接触过的小伙伴，请认真阅读官网！你想知道的有关这个数据集的信息都在上面！

不要用txt打开这样的文件，否则你的下场是这样：

Deal with two Python versions

解决python无法使用的问题，自闭了半天后发现原因是我的电脑有两个版本的python：2.7和3.7

这可咋办？我的sublime text编译不了啊！在网上搜索相关博文，
这篇博客讲得不错：Windows下多版本Python的pip安装与使用的吐血总结

Python coding to read dataset

开始着手写代码了。阅读lmh大佬的代码后，少走了不少弯路！
再次贡上大佬的代码：www.github.com – (站内搜索)bugstop/handwriting-number-recognization-knn

给大佬点了个小星星！

基本的文件读取直接拿来大佬的代码：

training_image_file = './source/train-images.idx3-ubyte'
training_label_file = './source/train-labels.idx1-ubyte'
test_image_file = './source/t10k-images.idx3-ubyte'
test_label_file = './source/t10k-labels.idx1-ubyte'
with open(training_image_file, 'rb') as f:
	training_images = f.read()[16:]
with open(training_label_file, 'rb') as f:
	training_labels = f.read()[8:]
with open(test_image_file, 'rb') as f:
	test_images = f.read()[16:]
with open(test_label_file, 'rb') as f:
	test_labels = f.read()[8:]
print(test_labels)

Python读取文件还是蛮方便的。在前面加上这段代码就更好了！（lmh不知从哪学来的神操作）

#Lmh dalao's basic operation
class Log(object):
    def __init__(self):
        logging.basicConfig(level=logging.INFO, filemode='w', filename='knn.log', format='%(message)s')
        console = logging.StreamHandler()
        console.setLevel(logging.INFO)
        formatter = logging.Formatter('%(message)s')
        console.setFormatter(formatter)
        logging.getLogger('').addHandler(console)

    @staticmethod
    def info(msg):
        logging.info(f'{datetime.now().strftime("%H:%M:%S.%f")}： {msg}')
log = Log()
log.info('Read Files')

为方便后续使用，定义全局变量，并了解一下数据集的结构：

global num_of_training_img, num_of_test_img, dim_of_img
num_of_training_img = 60000
num_of_test_img = 10000
dim_of_img = 28
print('Type of images: ',type(training_images))

看傻了的小伙伴，请认真阅读官网！你想知道的有关这个数据集的信息都在上面！

print显示读取得到的数据集，发现长成这样：

b’\x07\x02\x01\x00\ …

类型是Byte，这个类型是啥？其实，就是16进制拼成的数组，两个16进制数字拼成一个byte作为一个成员，顺序访问即可。所以，后续这么读（示例）：

def read_training_img():
	current_pos=0
	imgs=[]
	for i in range(num_of_training_img):
		current_pos=i*dim_of_img*dim_of_img
		current_img=[None]*(dim_of_img*dim_of_img)
		for index in range(dim_of_img*dim_of_img):
			#不能通过切片逐行读取，否则无法存储每个像素点
			current_img[index]=training_images[current_pos+index]
		imgs.append(current_img)
	return imgs

读取训练标签集和测试集大家可以作为练手代码。调用函数如下：

log.info('Read Files: training imgs')
training_imgs_vec=read_training_img()
training_imgs_vec=np.array(training_imgs_vec)#不要用乱用np.matrix()方法
training_imgs_mat=np.empty((num_of_training_img,dim_of_img,dim_of_img))#一定要遵循(address,floor,room)原则
log.info('Reshaping: training imgs')
training_imgs_mat=training_imgs_vec.reshape(num_of_training_img,dim_of_img,dim_of_img)
print('shape of training image vectors:',training_imgs_vec.shape)
print('shape of training image matrices:',training_imgs_mat.shape)
log.info('Read Files: training labels')
training_labels_vec=read_training_label()
print('training labels:',training_labels_vec[0:4])

得到这样的结果：

shape of training image vectors: (60000, 784)
shape of training image matrices: (60000, 28, 28)
18:57:31/281304: Read Files: training labels
training labels: [5, 0, 4, 1]

具体把图片保存成图片还是向量，自己看着办咯。
为了确认读出来了，我还画了个图：

注意：plt.show()之后，程序不会继续运行，需要把图片窗口关掉，才可以继续.

接下来，就正式开始KNN了！

KNN algorthim using Python

###
#正式开始KNN算法  
###

#算法思路：
#将test图片和训练集图片比对计算距离
#距离计算方法：
#选择1，逐点计算欧式距离，利用compare_ssim(img1, img2)
#选择2，计算余弦距离
#可选处理，将图片下采样
#判断方法：
#选择1，直接选前k个，按照多的取胜
#可选处理1，随机选取一定数量训练集图片
#可选处理2，统计被比较的训练集每类数量作为权重，最后真正的数量需要除以每类的数量

其实很简单。直接贴出函数：

def identify_img(img_check,imgs_refer,labels_refer_list,k_rank):
#img_check为矩阵(dim,dim),
#imgs_refer为与img_check同维度的矩阵组(length,dim,dim)
#labels_refer_list为imgs_refer的标签(length,-)
#k_rank为KNN的前k名门限值
	train_length=len(labels_refer_list)
	#train_length=labels_refer.size
	#labels_refer_list=labels_refer.tolist()
	if(k_rank>train_length):
		k_rank=train_length//2
	cnt_per_id={}
	for i in set(labels_refer_list):
		cnt_per_id[i] = labels_refer_list.count(i)
	#计算距离
	dist=[None]*train_length
	for index in range(train_length):
		dist[index]=compare_ssim(img_check,imgs_refer[index],multichannel=False)
	#距离排序获取索引
	rank=np.argsort(-np.array(dist))
	#按照索引访问标签
	top_labels_list=[None]*k_rank
	for index in range(k_rank):
		top_labels_list[index]=labels_refer_list[rank[index]]
	#获取前k_rank名的标签数量并计算最终得分
	top_cnt_per_id={}
	score=[None]*10
	for i in set(labels_refer_list):
		top_cnt_per_id[i] = top_labels_list.count(i)
		score[i]=top_cnt_per_id[i]#/cnt_per_id[i]
	#获取第一名
	first_place=np.where(score==np.max(score))[0][0]
	return first_place

对test样本反复调用这个函数，就ok了。期间，计算两个图片之间的“距离”，我没有用基本的欧氏距离，而是用了专门计算图片相似度的函数，SSIM，后来排序的时候降序排列。

继续地，我是用了欧几里得距离进行计算。求距离就不用开方了！保持单调性就行！

根据欧几里得距离排序的方法这里就不贴出来了。

接下来，调用函数！

starttime = datetime.now()
#euclidian method with random
num_of_test=1000
result=[None]*num_of_test_img
check_vec=[None]*num_of_test_img
num_of_refer=5000
candidate_label=[None]*num_of_refer
candidate_img=np.empty((num_of_training_img,dim_of_img*dim_of_img))
for index in range(num_of_test):
	sample_list = random.sample(range(0,num_of_training_img),num_of_refer)
	for cad in range(num_of_refer):
		candidate_label[cad]=training_labels_vec[sample_list[cad]]
		candidate_img[cad]=training_imgs_vec[sample_list[cad]]
	log.info('Identifying: test '+str(index))
	result[index]=identify_img_euclidian(test_imgs_vec[index],candidate_img,candidate_label,3)
	check_vec[index]=(test_labels_vec[index]==result[index])
	#print('test_label='+str(test_labels_vec[index]),'result='+str(result[index]))
endtime = datetime.now()
num_of_correct=check_vec.count(True)
num_of_incorrect=check_vec.count(False)
print('time elapsed: ',endtime-starttime)
log.info(f'Accuracy: {num_of_correct / (num_of_correct+num_of_incorrect) * 100}%')

细心的同学会发现，我引入了随机！没错，在挑选样本的时候，我没把全训练集都用于KNN比较。既然不需要训练，那索性就随机取训练集样本。当然，不随机版本的更好些，拿来练练手。

Several attentions on python grammar

•python踩到的几个坑：

不能用list访问list，但可以用list访问numpy的array
numpy的array没有count()方法，不过可以通过tolist()方法转化成list再进行操作
不能对list取负号，但可以对numpy的array取负号
想初始化list就用[None]*数组大小，想初始化numpy的array就用np.empty(维度1，维度2，维度3……)
想转numpy的array就用np.array()函数，但不要用np.matrix()，后者兼容性不好
在用matplotlib画subplot的时候，不要直接对分图使用方法title()，要用set_title()，否则报错

本文作者： lucainiaoge
本文链接： https://lucainiaoge.github.io.git/2019/09/25/KNN-handwriting-recognization/
版权声明： 本作品采用 Creative Commons authorship - noncommercial use - same way sharing 4.0 international license agreement 进行许可。转载请注明出处！

Welcome to my little world