基于KNN算法的手写数字识别

李诗语+王峰+曹彬+梅琪+肖飞

摘要：一直以来，让机器具有模式识别能力一直是计算机科学家们的努力方向。研究模式识别，是理解人类智能的本质的重要途径。字符识别是一个典型的模式识别问题，手写数字识别具有不同字符体型相差不大，相同字符有多种不同写法，数字没有上下文关联等特点，这些特点使手写数字识别比较困难。该论文设计了一套基于KNN算法，用Python语言实现手写数字识别系统。先对图片进行预处理，预处理包括灰度化、去噪、二值化等等，再用KNN算法对图片进行分类，手写数字识别也是一个十分类的问题。实验结果表明该文所设计的手写数字识别具有较好的识别率，同时也说明KNN算法在手写数字识别上具有良好的应用。

关键词：KNN算法；Python语言；模式识别；预处理；手写数字识别

中图分类号：TP391.43 文献标识码：A 文章编号：1009-3044（2017）25-0175-03

Abstract： All along， There always been a direction of computer scientists' efforts of Making the machine a pattern recognition capability. Research pattern recognition is an important way to understand the essence of human intelligence. Character recognition is a typical pattern recognition problem. Handwritten digital recognition has different characters. The same characters have many different Wordings， and the numbers are not context-sensitive. These features make handwritten digital recognition difficult. This paper designs a set of KNN algorithm Based on Python language to achieve handwritten digital recognition system. First of all， the image preprocessing， including gray， denoising， binarization， etc.， and then use KNN algorithm to classification image， the handwritten digital recognition is a ten classification problem. The experimental results show that the handwritten digital recognition in this paper has a good recognition rate， and also shows that KNN algorithm has a good application in handwritten numeral recognition.

Key words： KNN algorithm； Python language； pattern recognition； preprocessing； handwritten numeral recognition

1 绪论

1.1 研究的背景

光学字符识别是图像处理与模式识别领域的一个重要分支。其目的就是通过扫描，摄像等光学输入方式将汉字报刊，书籍，文稿及其他印刷品的文字转化为图像信息，将图形，表格的图像进行保存，再利用文字识别技术讲图像内的文字或表格中的资料一律变成计算机能识别的文字，以便于计算机的管理维护。它能够减少存储容量，通信交流的信息，循环利用已识别出的文字以及节省因键盘输入而浪费的人力，物力，财力和时间。

手写数字识别是光学字符识别的一个分支，它的研究对象是，如何利用电子计算机自动辨认人手写在纸张上的阿拉伯数字[1]。手写数字识别属于模式识别，是人工智能的一个重要分支，涉及模式识别和图像处理，人工智能，统计对策理论，模糊数学，组合数学，信息论，计算机等学科。

1.2 手写数字识别的意义和前景

手写数字识别不仅有重大的现实意义，而且有广阔的应用前景，由于当今的经济发展，金融市场发展日益加快，票据业务发展很快，例如个人凭证，支票，发票，进账单等票据都需要处理大量信息，如果这些信息全依赖人工输入，无疑会浪费大量人力物力，会造成成本高，效率低等问题。所以，手写数字识别显得很有必要。由于阿拉伯数字是唯一的被世界各国通用的符号，所以对手写数字识别的研究基本上与文化背景无关，研究者研究出这一技术，世界可以通用，也为各国研究者提供了一个共同探讨的平台。并且，手写数字识别的方法很容易被推广到其他相关问题上，比如英文字母识别等。

2 KNN算法

2.1 KNN算法的基本介绍

K最近邻（k-Nearest Neighbor，KNN）是一种基于统计学的分类方法，该算法最早于1968年由Cover和Hart提出，作为最简单的机器学习方法，理论上研究已比较成熟[2]。

KNN算法主要是在文本分類上有着极好的分类效果，包括信息检索、机器翻译、自动文摘、信息过滤、邮件分类等任务。文本分类在搜索引擎中也有这大量的使用，KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的K个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值，如权值与距离成正比。还可以用KNN算法做现有用户产品推荐，基于用户的最近邻买了什么产品来推荐。endprint

2.2 KNN算法的实现

KNN分类算法是最简单的机器学习算法之一，理论上比较成熟[3]。KNN算法的核心思想是如果一个样本在特征空间中的K个最近邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。KNN方法在类别决策时，只与极少量的相邻样本有关。KNN算法的原理如图1，圆要被决定赋予哪个类，是三角形还是四方形，如果K = 3，由于三角形所占比例为2/3，圆将被赋予三角形那个类，如果K = 5，由于四方形比例为3/5，因此圆被赋予四方形类。

该算法对未知类别属性的数据集中的每个点依次执行以下操作：

1） 计算已知类别数据集中的点与当前点之间的距离；

2） 按照距离递增次序排序；

3） 选取与当前点距离最小的k个点；

4） 确定前k个点所在类别的出现频率；

5） 返回前k个点出现频率最高的类别作为当前点的预测分类。

KNN算法的优点是计算简单，在基于统计的模式识别中有效性及其突出，已成为在模式识别、回归、文本分类和数据挖掘领域比较常见的一种分类方法，该算法准确率高容易实现，使用简单易于操作，一些文献表明KNN算法分类效果好，并且在训练过程中投入的时间最少[2]。但KNN算法仍然存在不足，主要表现为对于高维文本向量样本规模较大时，算法的时间和空间复杂度较高，当新待分类样本到来时，每次都要计算其与所有训练样本的距离（或相似度），这就大大降低了算法的效率[4]。

3 手写数字识别的实现

手写数字识别中图像的预处理非常重要，在处理图像照片的时候，由于光照，背景，拍摄角度等外界因素的影响，会造成图像失真并带有噪声，因为这些噪声的缘故，识别图片中的数字时会发生误差，造成数字识别错误，所以要对图像进行预处理。预处理的目的是去除图像中的噪声，压缩图像中的冗余信息，得到规范化的点阵，为识别做好准备，预处理是把图像转化成识别器能接受的二进制形式。

预处理的过程如图2，先把图像灰度化，所谓的灰度图像是指图像的每一个像素的R，G，B分量的值都是相等的，彩色图像的每个像素的R，G，B都是不同的，所以显示出不同颜色，由于图像拍出来是彩色的，而彩色的图片比较复杂，使得很多算法没办法展开，所以要对图像进行灰度化。

对图像进行了灰度化之后，每个像素只有一个灰度值，它的大小决定了图像的亮暗程度，为了更加便利地对图形进行处理，要对图像进行二值化处理，二值化处理就是根据像素中的灰度值把图片处理成黑白两种颜色，对图像二值化处理后要能在现原数字，即笔画要能保持原特征，笔画中不能出现空白点。

图像在扫描过程中会产生噪声，所以要对图像进行去噪处理，平滑去噪的目的在于去除孤立的噪聲点，填充字符边缘的凹陷或者去除凸点。

归一化是预处理中非常重要的一环，由于原始图像在大小上存在差异，所以要进行归一化把图像变得大小一样，有利于提高识别的准确度，预处理结果如图3。

因为Python适用于处理纯文本文档，所以先把经过上述预处理后的图片转化成纯文本文档，本实验是把图片转化成32*32的纯文本文档，如图4 ，图片上写数字的地方的数字为非零的常数，空白地方的数字为零。然后把转化好的图片和已经存在的图片集用KNN算法进行比较，找出图片属于哪一类，从而识别出图片中的数字。

如图5为本实验的结果，由于本实验一次性只验证了十个数字，所以正确率为百分之百。如验证数字足够多，则会出现一定量的误差，一般来讲，训练集越大，则验证时的误差就会越小，用KNN算法做手写数字识别，识别准确，误差小。

4 结束语

本实验选用Python语言来进行编程，用KNN算法实现功能，Python具有清晰的语法结构，使用广泛，代码范例也很多，相比于JAVA和C，Python的代码量要少很多， KNN算法理解简单，易于实现，精度高，对异常值不敏感，缺点是计算量大，所以仍需改进。目前主要通过两种途径来减小KNN方法的计算量：一种是通过对高维文本向量进行降维处理。另一种是通过使用小样本库代替原来的大样本库进行分类。这类分类方法一般是在原来的训练样本库中选取一些代表样本作为新的训练样本，或删除原来的训练样本库中的某些样本，将剩下的样本作为新的训练样本库，从而达到减小训练样本库的目的[4]。

参考文献：

[1] 任丹， 陈学峰. 手写数字识别的原理及应用[J]. 计算机时代， 2007（3）：17-18.

[2] 潘登. KNN算法的相似度研究[D]. 东北师范大学， 2014.

[3] 肖辉辉， 段艳明. 基于属性值相关距离的KNN算法的改进研究[J]. 计算机科学， 2013， 40（11a）：157-159.

[4] 卜凡军. KNN算法的改进及其在文本分类中的应用[D]. 江南大学， 2009.endprint