基于k-邻近算法的手写识别系统的研究与实现

2018-05-11辛英

电子设计工程 2018年7期

辛英

（山东工商学院数学与信息科学学院，山东烟台264005）

近年来人工智能与模式识别技术飞速发展，成为当前的热门技术。手写字符的识别是模式识别领域的重要分支。国内外对手写输入文字的识别技术历经了多年的研究并取得了很好的应用性成果。手写输入字符由于输入时的随意与笔画的不规则，使得同一字符的输入有着多样性，给识别增添了难度。经过多年的研究，针对手写字符的识别提出了多种解决方案，每种方法采用不同的数学模型进行手写字符的特征提取，常用的模式识别方法大致有两类：第一类通过现成的模板、矩阵、集成特征直接比照识别，第二类通过字符的关键节点、端点或者粗糙处等结构特征直接识别。大致的方法包括模板匹配、统计决策与句法构造等方法。简单容易的事情。本文基于机器学习的思想进行手写字符的识别，力求把人工智能的新技术应用到手写字符识别领域进行字符的预处理和特征提取，最终达到提高识别精度与准确率的目的。本文选取的机器学习算法是k-邻近算法，基于该算法设计了手写识别系统。系统包括学习与识别两大模块，采用Python语言编写完成。

1 系统简介

1.1 K-邻近算法

k-邻近算法（kNN）是机器学习领域中的一个简单易用的算法，常用语分类之中。它的原理非常简单，却是数据挖掘领域的十大算法之一。它的基本思想是丈量样本点与不同特征值之间的距离来确定样本点的类别。它的工作原理如图1所示：假设存在一个样本数据，在机器学习中常把这样的样本数据称作训练数据，该数据集合中的每一个数据都有各自对应的标签属性，即该集合存在着数据到样本集合的映射。当输入一个没有标签的数据时，k邻近算法要求我们将该数据与样本集合中的每一个数据特征一一比较，然后提取前k个与该数据最相似的特征对应的样本标签。最后统计这k个数据中出现频率最多的标签对应的分类，把该类别作为新数据的标签分类。通常k是一个不大于20的整数，其选取需要根据训练数据集的大小确定。

图1 k-邻近算法原理

由上述阐述，总结k邻近算法的步骤如下

1）数据搜集与准备：在Python中通常采用写网络爬虫的方式，从各大互联网站上搜集数据。大数据时代，也有各种现成的数据库提供所需的数据。在机器学习中，数据的搜集是开始系统构建的重要步骤。数据搜集完成后，需要对数据进行整理，最好化成结构化的形式，为后续的使用提供便利。

2）训练算法：对于大多数的机器学习算法，利于决策树、神经网络等，算法的训练是模型构建的必须步骤，通过训练算法，获得模型的参数，然后对需要预测的数据进行分析。但在k邻近算法中，却不需要进行预先的训练。

3）实施kNN算法：根据k邻近算法的原理，先计算样本数据与当前数据的特征之间的距离，随后对所有计算出的距离递增排序，选取前k个距离最小的样本点，统计前k个样本点中所在类别的频率，并将出现频率最高的样本点对应的分类作为当前数据的分类。

4）算法测试：由于所有的算法都不是百分之百完美的，预测的结果可能与真实值存在一定的偏差。在使用k邻近算法构建分类器之后需要对该分类器的性能进行评估。在测试的过程中，为了客观的评估k邻近算法的正确率，文中选取已有数据的90%来训练模型生成分类器，用剩下的10%数据作为测试样本来测试分类器的正确率。在选取过程中，注意数据的随机性即可。

1.2 系统框架设计

通过参考相关文献，并结合本系统的实际需求，建立如图2所示的手写识别系统。具体包括通过手写板或者触摸屏进行数据的采集，然后通过数据的预处理将数据进行归一化抽取相关的特征，根据由k-邻近算法生成的识别字典进行特征匹配，最后输出识别结果。

图2 手写识别系统原理框图

1）预处理：在进行手写字符的识别之前，系统需要先对输入到手写版或者触摸屏的文字进行预处理。在预处理的第一阶段，需要做的是对手写版或者触摸屏上笔的位置检测错来，并化作x，y坐标输入计算机，通过A/D转换技术，化成数字信号进行处理。得到的坐标由于含有干扰和噪声需要进行平滑、去噪与插入处理。噪声、干扰往往是由人在输入时手部的抖动、感应噪声等造成，不可避免。因此预处理阶段十分重要，是手写字符识别的基础。

2）特征提取：在机器学习的系统中特征工程中，特征的提取是核心步骤之一。对于样本的特征提取可以分为两个类别，分别是结构特征与统计特征。关于结构特征：手写字符的结构性很强，表达信息丰富。在进行结构特征提取时，本文采用自底向上的方法，由预处理后的像素开始，得到笔段，再用笔段合成笔画，用笔画生成字根，用字根识别手写字符。结构特征的提取对于用户按笔画输入的字符优势十分明显。关于统计特征：统计特征是指字符输入的轮廓、边缘信息以及水平、竖直、对角、反对角等特征信息。按照统计特征进行特征提取是将字符识别视作模式识别问题，用机器学习的思想通过对象特征学习、经验积累多次训练计算机，再应用于字符的识别。统计特征又分为全局特征与局部特征，良好的特征工程可以大大提高算法的精确度，提高识别准确率。

3）特征匹配：特征匹配是特征提取的目的所在。通过测试样本与学习样本之间的特征匹配，可以得到测试样本的分类。针对结构特征的匹配取采用结构特征匹配的方法，结构特征的匹配需要将提取出的输入信息与标准模板中的信息进行比对，找到最相似的字体完成识别。在当前的手写识别系统中，常常采用按照笔划顺序输入一笔识别一笔的方法，完成结构特征的识别。统计特征匹配对应于统计特征提取。在本文中采取k-邻近算法计算提取出的特征与样本特征的距离，进行分类判决。距离度量采用欧式距离，以简化特征工程与模板建立，同时可以提高模型的抗干扰能力。其他常用的算法还有支持向量机与人工神经网络。

2 系统实现与仿真

文中描述的手写识别系统采用Python语言实现，Python版本为2.7，开发环境选择Windows7下的Spyder。Python语言具有结构清晰、易于操作文本文件等优点，在开发中有非常丰富的开发文档，针对机器学习，Python中集成了现在最流行的SciPy、NumPy等科学计算库，在数据可视化上，有Matplotlib用于2D、3D图形的绘制。同时，Python还提供了shell交互环境，为用户在开发过程中的查看与检测程序提供便利。

2.1 算法实现

文中先建立kNN.py模块保存系统的所有代码。

第一步是导入系统所需的相关模块，第一个是科学计算包numpy，第二个是运算符operator。

在数据预处理中包括两个函数，一个是将文本记录转化为Numpy库可以处理的矩阵的file2matrix函数，一个是将图像格式化处理的img2vector函数，其中img2vector函数可以将从手写板获取的32*32的二进制图像转化为1*1024的向量，系统选取的学习样本如图3所示。

图3 学习样本

数据的预处理还包括归一化函数autoNorm，采取的归一化公式如下：

然后根据1.1中的步骤实施k-邻近算法，在kNN.py中添加classify0函数

Classfy0中输入4个参数，其中inX是用于分类的向量，dataSet是训练所需的样本数据，labels是每个训练样本对应的标签，k表适用于选择最近邻居的数目。在特征距离的计算上，采用欧式距离：

文中用提供的数据集进行模型的训练，并选取剩下的10%进行测试，算法的错误率为1.2%，在算法中更改模型的参数k，更改随机选取的样本与测试样本的数目都会对错误率造成影响，本文经多次调整参数进行优化，获得较优值。

2.2 算法测试

文中在测试时，从网上截取了一段200字的新闻稿，在文稿的选取上，文中特意关注了字符的多样性，在本段文字中，包括文字、标点、数字等多种符号。然后选择了10名用户对该段文字进行手写输入，新闻稿与用户的输入数据分别如图4、图5所示。

图4 新闻稿数据

图6为系统对用户书写样本的识别情况，在编辑区域可以清晰地看到用户的笔迹与系统的识别结果。其中黑色的为系统的首先字符，浅灰色的为二选字符，在k邻近算法判别二选字符与首选字符类别判别模糊时，本系统为用户提供第二接近的字符，供用户判别。通过计算机智能自动识别与人工识别相结合的方式，提高手写字符的准确率。经过十个用户的输入数据的测试，本系统的首选加二选识别准确率达到95%以上。