基于KNN的手写体数字识别实验案例设计

安利 柳泉 张晗

摘要：本文以规范设计、夯实基础、科学考核、激励创新为宗旨精心设计了基于KNN的手写体识别的实验案例。试验过程中，首先逐步引导学生理解KNN算法的基本思想与原理，然后基于Python语言实现手写体数字的识别，最后通过科学完善的考核标准总结学生独立实验的能力。整个实验以理解算法设计为核心、代码实现与调试为重点、考核与总结为评价，提高了学生理论联系实际、分析与研究、变革与创新的能力，取得了良好的教学效果。

关键词： KNN算法  数字识别  Python语言 实验案例

中图分类号：G202           文献标识码：A

随着信息时代的到来，人们对于信息处理的要求更加严格，不仅要有非常高的准确率，还要有非常快的处理速度。手写体数字识别一直是多年来的研究热点，也是图像处理和模式识别领域中的研究内容[1]，手写体数字识别被应用在大规模数据统计中。例如，人口普查、成绩单录入、行业年检、财务报表录入等应用中。手写数字识别是利用机器或计算机自动辨认手写体阿拉伯数字的一种技术，是光学字符识别技术的一个分支。由于阿拉伯数字通用，并且数字识别和处理也常是一些自动化系统的核心和关键，所以对手写体数字识别的研究通用性强，且意义重大。

本文通过实验过程[2-6]，引导学生逐步熟悉KNN算法的设计方法。并通过Python语言中程序调试实现基于KNN算法，利用计算机自动辨认人手写在纸张上的阿拉伯数字的过程，以培养学生积极思考、精益求精的科学态度和创新意识，提高学生独立实验能力、分析与研究能力、理论联系实际能力和创新能力，最终达到培养学生基于算法和程序设计问题的求解基本方法和能力的目的。具体实验过程如图1：

1、实验思想

k最邻近算法（k-Nearest Neighbor， KNN）是一種分类算法[7-8]，也是最简单易懂的机器学习算法。1968年由 Cover 和 Hart 提出，应用场景有字符识别、文本分类、图像识别等领域。该算法的思想是：一个样本与数据集中的k个样本最相似，如果这k个样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法是由你的邻居来推断出你的类别。

如图2所示，绿色三角形要被决定赋予哪个类，是红色五角星还是蓝色四方形？如果K=4，由于红色五角星所占比例为3/4，绿色三角将被赋予红色五角星那个类，如果K=7，由于蓝色四方形比例为4/7，因此绿色三角被赋予蓝色四方形类。由此也说明了KNN算法的结果很大程度取决于K的选择。

2、实验指导

手写体数字识别是一个比较完整的工程实践过程，需要经历学习研究、方案论证、系统设计、实现调试、测试标定、设计总结等过程。因此在实验过程中需加强对学生的引导：

1）学习矩阵以及向量在Python环境中的表示，了解图像数据转换为矩阵的过程。

2）熟悉距离计算模型，了解各模型的特点。本实验中，在邻居距离的模型选择中，我们选择相对简单的欧式距离模型，但此模型在低维度计算时准确度较高，而在高维度对距离衡量，欧式距离的区分能力就越差。

3）对库函数以及参数的理解，如tile（A，n）就是将A重复n次，argsort（）是排序函数等

4）注意k值的选择，k值通常是采用交叉检验来确定（以k=1为基准）经验规则：k一般低于训练样本数的平方根。

5）理解类别的判断方法。本实验初始选择投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。后面对算法改进可采用加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）

6）在实验完成后，可以组织学生以项目演讲、答辩、评讲的形式进行交流，了解不同解决方案及其特点，拓宽知识面。

3、实验方案

1）实验数据

本次实验的数据集由学生在网站[9]下载。数据集包括数字0-9的手写体。每个数字大约有200个样本。每个样本保存在一个txt文件中。手写体图像本身的大小是32x32的二值图，转换到txt文件保存后，内容也是32x32个数字，0或者1，数据集解压后有两个目录，目录trainingDigits存放的是大约2000个训练数据，testDigits存放大约900个测试数据。一共1934个文件，最后构建的矩阵是1934x1024的矩阵，如图3所示。

这里我们还新建一个KNN.py脚本文件，文件里面包含四个函数，一个用来生成将每个样本的txt文件转换为对应的一个向量，一个用来加载整个数据库，一个实现kNN分类算法。最后就是实现这个加载，测试的函数。

2）K最近邻计算模型

KNN是采用测量不同特征值之间的距离方法进行分类，也就是说对于每个样本数据，需要和训练集中的所有数据进行欧氏距离计算。

3）KNN算法流程图（图4）

4）核心分类函数[10]，使用Python语言实现（图5）

5）结果分析

首先分析问题，将每一个手写体处理为一个向量，在本实验中处理为将32x32的二进制图像文本矩阵转换成1x1024的向量。循环读出文件的前32行，存储在向量中。

将训练数据中的数据进行分类训练，即给每个图像追加标签。标签是通过截取文件名的首数字字符得到。文件名的保存方式，如图1所示。

然后，通过欧式距离计算样本与训练集的距离（代码如上分类函数所示），并将得到的距离按从小到大排序。

接着，选择前K个作邻居，通过投票法，决定当前样本的标签，即分类。具体过程是，统计k个邻居的各分类标签训练图像个数，哪个分类标签里的邻居个数最多，那么当前样本即为该分类。

最后，统计识别的正确率，并思考对算法的改进。算法的改进可从两个方面考虑：一是性能问题：KNN构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。二是训练的时间：能否大幅减少训练样本量，同时又保持分类精度。4、实验考核

实验考核是实验过程中不可或缺的环节，是对实验所达到的效果和学生学习实践效果的有效检验，要求单人单组，询问学生是否单独完成程序的运行、确保每个同学都能够了解KNN算法以及程序运行的过程，根据完成质量进行打分。为体现考核的公正性、合理性和准确性以及强调实验结果的同时，注重实验的整个过程，不能仅凭实验结果和实验报告给出成绩，因此制定实验考核指标，见表1：

5、结束语

此案例是机器学习的入门案例，熟练掌握该案例的实现过程为后续实验的完成奠定了良好的基础。从实验教学效果上看，此案例贴近生活、应用广泛，学生比较容易接受，兴趣也更浓厚，特别在独立实验完成的过程中，学生从中获得巨大的成就感，实验的主动性明显增强。不足之处，算法优化方面学生还不够主动，后期将鼓励学生在前人的基础上进行创新，设计更好的解决方案，最终实现层次式的发展。

参考文献

[1]. 期刊：任美丽，孟亮，基于原型生成技术的手写体识别[J].计算机工程与设计，2015年，第36卷第8期：2211-2216

[2]. 期刊：刘福泉，案例+实验教学法在计算机网络教学中的应用—以一次教学活动为例[J].计算机时代，2015年，第8期：57-60

[3]. 期刊：贾翼婷，计算机实验教学浅谈[J].西安邮电学院学报，2006年，第11卷第4期：136-138

[4]. 期刊：胡旺，郑莉华，陈安龙 ，一种进阶式数据库课程实验方案设计[J]. 计算机教育，2012年，第1期：39-42

[5]. 期刊：汪志华，计算机组成原理實验教学的改革与实践[J].集美大学学报，2016年，第17卷第2期：83-87

[6]. 期刊：钟元生，曹权，APP开发教学案例设计[J].软件工程师，2015年，18卷第8期：65-68

[7]. 期刊：熊志斌，朱剑峰，尹国城等，基于KNN算法的文本分类器的设计与实现[J].软件研发与应用，2016年，第八期：11-13

[8]. 期刊：刘卓，K-最邻近算法在文本分类中的应用[J].苏州市职业大学学报，2010年，第21卷第2期：58-60

[9]. 电子文献： https：//www.kaggle.com/datasets[OL]

[10]. 期刊：赵明洪，张太红，王正敏，Python程序代码相似度检测[J].现代计算机，2014年12月上：30-32 59