基于决策树和加权KNN混合算法的光学符号识别技术

张岩 李洋 博柳姗 等

摘要：光学字符识别是针对印刷体字符，采用光学的方式将纸质文档中的文字转换成为黑白点阵的图像文件，并且通过字符识别模型将图像中的文字处理成可编辑的文本格式.本文首先对样本数据进行预处理，采用局部离群因子法剔除无效数据，通过信息增益率计算各个自变量相关性的强弱来找出恰当的特征，并将样本分为五类，建立决策树法和加权KNN算法相结合的混合算法，预测每类数据的结果并给出准确率，将结果中未识别的样本放在所有训练集下再次通过混合算法进行训练预测，最终总预测正确率达到了96.406%.最后通过混淆矩阵来评价模型，结果表明其拒识率较低，准确率较高，训练预测时间较短，具有可行性.

关键词：决策树法;加权KNN算法;局部离群因子法;信息增益率;混淆矩阵

中图分类号：TP391.43  文献标识码：A  文章编号：1673-260X（2019）02-0026-04

1 前言

光学字符识别是光学符号识别的核心，但是对于许多类型的机器学习算法来说，将像素模式连接到更高概念的关系是非常复杂的，而且用严格的规则来定义这些模式是很困难的.本文的数据来源于公开的UCI的光学字符识别数据集（数据来源：http：//archive.ics.uci.edu/ml/index.php），该数据集包含了26个英文大写字母的20000个样本，每一个样本代表光学图像中的一个矩形区域，该区域只包含單一字符，每一个样本包含16个自变量和letter目标变量，letter指示当前样本是哪一个字母，我们对图像数据运用一定的统计方法进行初步的统计描述，分析所给图像数据集，选取恰当的特征，通过恰当的数学模型来准确判断识别每个字符，由于每一个模型不会是100%最优，所以应当建立适合的评价模型对建立的数学模型进行性能评估，主要包括正确率率、拒识率的评价，最后提出模型的性能提升方案，即将所给数据中的70%用上述数学模型来验证剩下的30%的样本数据，测试出正确率，分析错误原因.

2 数据预处理

2.1 数据整体分析

对所有样本数据中的每个目标变量出现的次数进行统计分析可以得出，每个目标变量出现的次数大致相同且每个目标变量均呈现正态分布趋势，说明分布较好;对所有样本数据的同一目标变量的自变量的出现次数进行统计分析可以得均呈现正态分布趋势，进一步说明数据分布比较好;通过Excel表进行缺失值查找，并未发现缺失值，说明该数据完整;通过Excel表筛选，共发现1332个自变量相同并且结果也相同的样本，但考虑到该样本经归一化处理，已经被缩放到从0到15的整数值范围内，所以此处重复并不代表原数据重复，因而不删除此处重复值;通过Excel表筛选，并未发现自变量相同但目标变量不同的样本，即没有不一致的数据.

2.2 局部离群因子法[1]剔除离群数据

离群点可分为全局离群点和局部离群点，在很多情况下，局部离群点的挖掘比全局离群点的挖掘更有意义[2].通过计算每个样本的局部离群因子来定量分析某个样本的离群程度，有效地剔除离群数据.具体步骤如下：

Step1：找到离各个样本xi距离最近的k个样本，其中样本xij表示距离样本xi最近的第j个样本，样本xijj表示距离样本xij最近的第j个样本，d（xi，xij）为xi与xij之间的欧氏距离，d（xij，xijj）表示xij与其距离最近的第m个样本之间的欧式距离，k取5，i=1，2…20000， j=1，2…k，

计算并分析所有自变量的信息增益率可得出结果：a7，a8，a9，a10，a11，a12，a13，a14，a15，a16等属性取值数目所带来的影响大;a2，a3，a4，a5，a6等属性取值数目所带来的影响小.综上，得出特征变量是：a7，a8，a9，a10，a11，a12，a13，a14，a15，a16.

3.2 对数据进行分类

根据上述分类依据，运用决策树法将上述十个特征变量分为2类处理，分类结果如图1所示：

3.3 分别对每类样本进行预测

分别用加权KNN算法及决策树法来对每类样本进行预测，每类70%的样本作为训练，30%的样本作为预测.以第一类样本集合为例.

3.3.1 用加权KNN算法对第一类样本进行训练预测（a14≤1）

KNN算法最早是由Cover和Hart提出的[5]，其核心思想是一个样本与离它最近的k个样本同属一个类别，具有相似的特征.在传统的KNN算法中，当相近的样本过于密集且每类样本容量差别过大时，k值的选取就很重要，有可能导致预测新样本时，这一区域内容量大的类别起决定性作用[6，7].为避免传统KNN算法的不足，本文采用加权KNN算法对样本进行预测，利用高斯函数来把距离转换为权值[4].具体步骤如下.

3.3.2 用决策树算法对第一类样本进行训练预测

利用3.3.1挑选的70%的样本进行训练，并计算信息增益率，从中选择信息增益率高的属性标记节点，最后对其进行剪枝，经过反复调试参数、优化，得出最佳树结构（置信度阈为0.20，分枝数为100）.对剩余30%的样本进行预测，对于a14≤1所在分支，共有样本1435个，预测错误39个，预测正确率为97.282%.

3.3.3 混合预测

将上述两种方法预测的结果进行比较，若预测结果相同，则输出预测结果，若预测结果不同，则划入未识别集，进行下一步预测.预测结果如表1：

3.4 对未识别样本的进一步预测

进一步预测经3.3处理得到801个未识别集，为提高识别正确率降低拒识率，选取原训练集和集合Sw作为未识别集的训练集，其中集合Sw为原训练集经训练好的决策树算法、加权KNN算法进行预测而得出的未识别数据组成的集合，重复上述步骤，预测结果如表2所示：

从表2可看出训练集为集合Sw时预测结果要优于训练集为原训练集的预测结果，故选择集合Sw作为未识别集的训练集.

4 预测结果分析

随机挑选70%的数据作为已知数据进行学习和训练，将剩下的30%随机数进行预测验证.调用本文提出的混合预测模型对其预测，预测结果如下表3.

该模型识别光学字符错误率仅为1.525%，正确率达到96.406%，拒识率为2.07%，通过混淆矩阵计算出Kappa系数为0.97396，也表明此模型具有很好的一致性.

该模型中将策树算法和加权KNN算法预测不一致的数据计入未识别集中，但对于未别集的预测的正确率较低，而且拒识率过高，所以未识别集的预测属于此模型的短板，可通过降低未识别集的拒识率来对此模型进行改进.通过统计得出预测错误和拒绝识别主要出现在B，D，E，F，H，N，O，Q，R，S，U，X等12个字母中，也可从这些字母入手，来降低拒识率和提高正确率.

5 结论

5.1 对初始数据进行预处理，通过计算信息增益率的计算找出恰当的特征变量，并利用决策树法和加权KNN算法建立混合预测的数学模型.

5.2 对数据进行分类预测，不仅避免了相近数据的影响，还大大减少了运算次数，节约了时间;在预测之后，将全部样本分成识别集和未识别集，并分别给出来两个集合的识别正确率和拒识率，避免了过模拟现象，该计算結果更为精确，训练时间更短.

5.3 通过混淆矩阵来评价模型，模型拒识率较低，准确率较高，训练预测时间较短，具有可行性.

参考文献：

〔1〕Breuning M M.LOF： Identifying density-based local outliers [J].ACM SIGMOD Record，2000，29（2）：93-104.

〔2〕胡彩平，秦小麟.一种基于密度的局部离群点检测算法DLOF[J].计算机研究与发展，2010，47（12）：2110-2116.

〔3〕袁梅宇.数据挖掘与机器学习[M].北京：清华大学出版社，2014.

〔4〕戴健，丁治明.基于MapReduce快速kNN Join方法[J].计算机学报，2015，38（1）：99-108.

〔5〕Cover T M， Hart P E. Nearest neighbor pattern classification. IEEE Trans Inf Theory IT-13（1）：21-27[J]. IEEE Transactions on Information Theory， 1967， 13（1）：21-27.

〔6〕Sun S， Huang R. An adaptive k-nearest neighbor algorithm[C]// Seventh International Conference on Fuzzy Systems and Knowledge Discovery. IEEE， 2010：91-94.

〔7〕Ghosh A K， Azen S P. On optimum choice of k in nearest neighbor classification[J]. Computational Statistics & Data Analysis， 2006， 50（11）：3113-3123.