基于K—近邻算法的光学符号识别

来源:用户上传      作者:

　　[摘 要]光学字符识别作为当今模式识别领域中最活跃的研究内容之一，而光学字符识别最关键的步骤是字符识别算法的设计。选用公开的UCI光学字符数据集来研究此问题，利用所给字符的数据特征，将前70%数据作为训练数据，后30%数据作为测试数据。建立K-近邻算法模型，对后30%数据进行识别，计算测试数据与训练数据的欧几里得距离，进而计算出对应相似度，最终得到其准确率高达95.51%，说明K-近邻算法相比于其他字符识别算法，精准度存在一定的优越性。
　　[关键词]UCI光学数据集；模式识别；K-近邻算法；欧几里得距离；相似度
　　中图分类号：TP115 文献标识码：A 文章编号：1009-914X（2018）12-0140-01
　　1引言
　　光学字符识别是通过图像处理和模式识别技术对光学的字符进行识别的过程，优质的字符识别的准确率及识别速度，已成为自动识别技术研究和应用领域中一个重要的研究方向。提高系统的识别率除了可以进行图像预处理外，还可以从识别算法上考虑[2]。K-近邻分类算法的最大优点在于对处理属性较多或数据量较大的问题上更优于其他算法，操作简单，不需要对训练样本先进行分类训练，而可以直接使用训练样本对数据样本进行分类，并确定其所属类别。本章将引进k-近邻算法对公开的UCI光学字符数据集进行识别处理，基于已知的16个数据特征，建立k-近邻算法来准确识别字符，并验证其识别准确率。
　　2基于K-近邻算法的光学符号识别
　　2.1数据准备
　　对UCI上公开的光学符号数据集中的26个字母频率进行统计，如表1：
　　2.2模型建立
　　假定有一待定字符，将16个特征值分别与14000组训练数据的16个特征值进行欧式距离计算，比较所得到的14000个欧式距离的大小，提前取出前K个最小的数据，也就是K个最近邻。将K个数据分成26类，得出这26类中类别数据的个数，个数最多的一类，即为待识别字符所属的那一类。
　　2.3模型求解与检验
　　以字符‘T’为例，选取测试集中一组‘T’数据，首先从训练集随机选取k组数据，分别计算其与训练集中k组数据的欧式距离，并将这k个距离值存入优先级队列，记优先级队列中最大为，接着计算与训练集中其他数据的欧式距离，记为，如果，则舍去该元组，如果，则将该元组存入优先级队列，并舍弃优先级队列中距离最大的元组，更新，最终得到优先级队列中与测试元组‘T’最相似的k组数据，绘出优先级队列中各类数据数量分布折线图，如图1所示：
　　根据数据折线图可以明显看出，优先级队列中‘T’的数量远大于其他字符的数量，可以说明与待识别字符的欧几里得距离较近的字符中字符‘T’占大多数，真实结果就是字符‘T’。
　　把分类好的训练集，同样先从训练集中随机抽取3组数据存入优先级队列，利用后30%数据作为测试集，根据上述K-近邻算法进行识别验证，最终得到识别结果如图2：
　　第一行为预测值，第一列为真实值，主对角线上值表示识别正确的数量，对角线以为表示误判情况。可以看出误判多的大多数在字符特征上是表交相似的，如字符P和F。
　　通过计算得出的确率如表2，数据说明该算法识别率还是很高的。
　　K值的选取：在使用K-近邻算法时，计算过程大多都集中在分类阶段，而且分类效果在很大程度上取决于k值，如果选取的k值较小，则得到的近邻数较少，会降低分类精度，同时也会放大噪声数据的干扰；如果选取的k值较大，会造成噪声增加从而导致分类效果降低[3]。因此选取的k值不同，对应模型的识别率也不同。而一般k取奇数，且不大于20。
　　下面选取多组不同的k值，得出其正确识别率如下：
　　通过对识别率高低进行比较，得出当k=5时，识别率最高。
　　3结束语
　　本文采用一种基于分类识别的kNN算法，对UCI公开的光学字符数据集作字符识别，并取得了很高的识别率。相比其他分类算法，该算法在对于多分类问题上，具有很高的优越性，但在识别效率上有待提高，比如可以用贪心法，二分查找法来优化算法，提高算法执行效率。
　　参考文献
　　[1]滕敏，卫文学，滕宁.K-最近邻分类算法应用研究[J].软件导刊，2015，14（03）：44-46.
　　[2]鄭宗良.基于模糊判别准则和特征加权模板匹配的字符识别[J].科学技术与工程，2012，12（23）：5794-5796+5805.
　　[3]闭小梅，闭瑞华.KNN算法综述[J].科技创新导报，2009（14）：31.
　　[4]范明，孟小峰，数据挖掘概念与技术[M].第3版，北京：机械工业出版社，2012.
　　[5]刘应东，牛慧民，基于K-最近邻图的小样本KNN分类算法[J].计算机工程，2011（6），37（9）：198-200.
转载注明来源:https://www.xzbu.com/1/view-15326251.htm