基于加权K—最近邻分类的手写数字识别

摘要：机器学习算法是人工智能应用领域的热点研究问题。将改进加权距离的K-最近邻分类算法应用到手写数字智能识别中，通過计算机仿真实验验证了该算法预测准确率为85%。为了减少算法计算量，Kd-Tree等高效的检索技术是今后的研究方向。

关键词：K-最近邻；智能识别；加权距离

the Handwritten Digit Recognition Based on Weighted K-Nearest Neighbor Algorithm

YU Yu-lian

（College of Communication Engineering，Shanghai Technical Institute of Electronics&Information，Shanghai 201411，China）

Abstract：Machine learning algorithms are hot research problems in the field of artificial intelligence applications. The improved weighted distance to K - nearest neighbor classification algorithm is applied to intelligent handwritten numerals recognition，the algorithm is verified through the code experiment forecast accuracy of 85%. In order to reduce the algorithm computation，the efficient retrieval technology such as Kd-Tree is the research direction in the future.

Key words：K-Nearest Neighbor；intelligent identification；the weighted distance

1 引言

近年来随着人工智能应用的发展，机器学习算法成了热点研究问题[1]。在众多机器学习算法中[2]，K-最近邻（K-Nearest Neighbor，KNN）算法是理论上比较成熟的分类算法[3-4]，有较高的分类准确率。该文首先阐述了KNN算法原理，提出了改进的加权距离，用以降低算法对K的选择的敏感度；其次通过计算机仿真实验论证了KNN算法在手写数字智能识别中的应用；最后展望了KNN算法改进的研究方向。

2 K-最近邻（KNN）算法原理

2.1 KNN算法概念

K-最近邻（KNN）算法是一种典型的非参模型，与生成方法（generalizing method）不同的是，在KNN算法中，通过以实例的形式存储所有的训练样本。对于一个待预测的样本，通过计算它与训练样本之间的差异性，并将差异按照由小到大排序，选出前面K个差异最小的类别，并统计在K个中类别出现次数最多的类别为最相似的类，最终将待预测样本分到最相似的训练样本的类中。

2.2 样本差异性算法

常用的差异性计算方法为欧式距离、曼哈顿距离等。该文实验中使用欧式距离：假设测

试样本，训练样本，两者之间的欧式距离为D，D

值越小，两者相似度越大。

2.3 KNN算法流程

（1）计算测试数据与各个训练数据之间的距离；

（2）按照距离的递增关系进行排序；

（3）选取距离最小的K个点；

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

（5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

2.4 改进的加权距离

在多数表决方法中，每个近邻对分类的影响都一样，这使得算法对K的选择很敏感。降低K的影响的一种途径是根据每个最近邻Xi距离的不同对其作用加权，取距离的倒数作为权重：

从而降低远离待分类样本的那些训练实例的影响，加权后的表决公式为：

3 计算机仿真实现KNN算法

以手写字体MNIST数据库识别为例，该数据库共包含7000幅图像：6000幅训练图像（用于创建模），1000幅测试图像（用于评估模型的精度）。每个 MNIST 图像是一个单一的手写的数字字符的数字化的图片，每个图像是 28 x 28 像素大小。每个像素值是范围是[0 255]，0表示白色，255表示黑色，中间像素值表示各灰度级。图1所示为MNIST库手写数字测试样本。通过计算机仿真实验实现KNN算法在在手写数字识别中的应用。

4 结束语

文中用加权距离的KNN算法进行了手写数字智能识别，最终的预测准确率为85%。由于每一个预测样本需要与所有的训练样本计算相似度，计算量比较大。为了降低为测试样本寻找最近邻的时间和计算量，今后将研究高效的索引技术，如Kd-Tree，Ball-tree、Cover-Tree等。

参考文献：

[1]曹承志. 人工智能技术. 北京：清华大学出版社，2010.

[2]陈凯，朱钰. 机器学习及其相关算法综述. 统计与信息论坛，2007，22（5）：105-112.

[3]石欣等. 基于K最近邻分类的无线传感器网络定位算法. 仪器仪表学报，2014，35（10）：2238-2247.

[4]苏毅娟等. 大数据下的快速KNN分类算法. 计算机应用研究，2016，33（4）：1003-1006.

通讯作者简介：

俞玉莲（1979-），女，副教授，硕士研究生，主要研究方向：信号与信息处理。