一种基于决策树的选项识别方法

雷俊杰 张伟池 余荣 张浩川

摘要：文章将机器学习中的决策树算法和图像处理技术相结合，提出了一种基于决策树的选项识别方法，该方法首先需要通过人工标注的方式从答题卡中抽取选项构造训练集和测试集，训练集和测试集都包括填涂的选项和未填涂的选项两类，接着将训练集中的答题卡选项切割成n个大小相同的小矩形，通过计算这些小矩形的占空比并通过设定阈值的方式将其离散化成{0，l}中的其中一个值，这些值将作为选项的填涂空间信息特征，然后将n个小矩形的离散后的值相加作为表征选项整体填涂信息特征，再将这n+l个特征构成特征向量的形式，去构造选项识别的决策树，最后，用测试集测试决策树的准确率和速度。经过仿真测试，在权衡识别准确率和识别效率之后，得出选项切割的最佳个数和最佳离散化阈值，在该参数的设置下，决策树的识别性能具有满意的结果。该方法实现方便、简单、易于理解，并具有很高的准确率和很快的识别速度。

关键词：机器学习；决策树；选项识别；特征提取；答题卡

1 相关概述

1.1研究背景

随着科学技术的日益发展，传统的教育行业也发生着巨大的变革，从以前的客观题需要人工手动批改，到后来使用光学标记阅读机去识别选项答案，效率得到了大大的提升。但光学标记阅读机虽然速度快，准确性高，但也存在着一些问题[1-3]：（1）设备成本高，一台普通的光学标记阅读机需要好几万的成本。（2）答题卡需要定制。（3）光学标记阅读机不能保存数字图像。基于上面的原因，出现了数码阅卷的方式，该方式只需要将试卷扫描到电脑上，通过一定的算法就可实现识别，通用性更好并且不需要额外的识别硬件。

1.2答题卡客观题选项识别的缺点和不足

虽然数码阅卷取得了长足的进展，但在客观题选项识别上仍然存在着一些不尽人意的地方。当前选项识别方法一般分为两种，一是简单通过计算占空比的方法，二是使用支持向量机（SVM）识别[4-5]。下面分别简单介绍两种方法的实现。

1.2.1计算占空比方法

该方法步骤为[67]：（1）判断像素是否为黑色像素，若是的话，则累加。（2）求得该选项的占空比，公式为：占空比=黑色像素总和/选项矩形面积。（3）判断计算出来的古空比是否大于某一设定阈值，若大于，则输出为填涂，否则，输出为未填涂。

这种方法实现简单，识别速度快，但由于需要设置固定的阈值，因此对一些填涂不全的选项会出现误识的结果，整体准确率不是太高。

1.2.2支持向量机识别

在王胜春的论文《基于SVM的信息识别系统》中，提出了用支持向量机识别选项的方法，该方法步骤为[8]（1）定义各识别块与水平定位块的相对坐标模板。（2）對水平定位区域进行图像分割。（3）获取各水平定位块重心。（4）根据各信息识别块与水平定位块的相对坐标模块，获取各信息识别块初步识别范围。（5）根据各信息识别块初步识别范围及所定义的环境因子构建输入向量集。（6）采用SVM对输入向量集进行训练与识别，获取识别结果。

该方法使用了较多的参数，使得实现起来具有一定的困难性，并且论文中提出的识别方法和论文中的识别系统耦合度过高。

1.3决策树简介

决策树是一种简单、高效的机器学习分类算法，它通俗易懂，跟人的思考方式很像，构建出来的树图形清晰明了，同时它也是其他复杂的机器学习算法，如boost、随机森林的基础。

从技术上讲，一个决策树由一系列节点和分支组成，而节点和子节点之间形成分支，节点代表着决策过程中所考虑的属性，而不同属性值形成不同分支。为了利用决策树对某一事例作出决策，可以利用这一事例的属性值并由树根向下搜索直至叶节点，叶节点上即包含着决策结果[9-10]。

决策树的构造包含以下4步[11]： （l）选择度量集合分类不纯度的计算方法，一般有熵、吉尼不纯度、错分类不纯度3种可选择。（2）遍历集合的每个特征，根据度量选择分类效果最好的属性对集合进行划分。（3）递归地构造整棵决策树。（4）使用剪枝策略修建决策树，防止其过拟合。2算法介绍

决策树具有良好的数学理论支持，方便调试，构造的模型易于理解，因此很适合用于答题卡选项的识别[12]。

构造决策树需要对象的特征，之前的论文中，选项的特征提取做法是[1]：对选项分割后计算各个小矩形的占空比，并以此为特征；这种做法是比较适合的，因为只有一个总体的占空比的做法，会丢失了填涂的空间信息。这就好比，在一个房间里，有许许多多本书，如果我们只知道房间内有多少本书，那么当我们要找一本书的时候就非常麻烦，但如果我们将这些书分门别类，分成一块区域一块区域去管理，那样就既可以保留了书本的数量信息，又可以保留书本的空间信息，寻找起来就会快很多。而将选项划分为多个小区域的做法，就做到了既保留了填涂的总体信息，又保留了填涂的空间信息。但决策树不适用于连续的数据，因此在这里我们需要将占空比离散化，离散化的方法也非常简单，就是设置一阈值，若占空比高于该阈值则将特征值置为l，否则为0。这个离散化的过程，其实很像我们人先教会计算机怎么样才算填涂的选项，但填涂的选项有太多的情况，不可能一一给计算机详细地罗列出来，既然如此，那我们就先教会计算机一个狭小的区域怎么样才算填涂，而一个狭小的区域往往是容易判断的，然后计算机再通过统计每个狭小区域的特征来判断整个选项区域是否填涂。于是，一个复杂的问题就变成了一个个小的问题。以往的占空比阈值判断方法往往会丢失选项填涂的空间信息，它只能够得到选项大致填涂了多少，而不会知道这些填涂是分散的还是集中的；现在通过将选项分割成一个个小的区域，其特征值代表了区域的填涂信息，能够在整体上保留填涂的空间信息。不过，由于特征值只会代表单个区域信息，我们还需要一个特征来表征整个区域的填涂信息，这个特征可以通过对所有小区域的特征求和来得到。

于是，基于决策树的选项识别算法步骤如下。

（1）构造训练样本和测试样本。

（2）设定划分个数Ⅳ和离散化阈值T。

（3）将训练样本中的选项图像分为NAI大小相同的小区域，逐一计算每个区域黑色像素的占空比。

（4）根据离散化阈值将占空比离散化，方法为：占空比大于阈值，特征值置为l；否则，特征值置为0。

（5）对该选项所有区域的特征值求和。

（6）根据上面的特征信息构造该选项图像的特征值向量，最后输出的特征值向量大概会是这样的形式：

Vector=[1，1，1，0，0，1，0，1，…，ll，l]

其中，II为前面的1的个数之和，最后的1是该选项的类别（这里1代表“填涂”，0代表“未填涂”）。

（7）将所有的训练样本的特征向量构造成特征矩阵的形式。

（8）将特征矩阵数据输入决策树训练算法中，构造用于识别选项的决策树模型。 在上面的步骤中，有两个参数是至关重要的，一个是选项区域划分成的矩形个数Ⅳ，一个是阈值To -般的选项图像大小长度在40像素内，高度在20像素内，为了方便计算，在这里使得n=m，即选项区域划分为nXn个大小相同的小矩形，n=2，3，4，5，玎若再大的话，会使到分割后区域过小而失去表征的作用。而根据经验，阈值可选择0.4-0.8的值。根据直观的经验，我们可以知道，当Ⅳ越大的时候，填涂的空间信息就会保存得越好，越能够表征选项的填涂特征，识别的准确率会越高，但计算的复杂度会增加，效率下降并有可能导致决策树的过拟合；而当阈值T越大的时候，识别的严格程度就会越高，这样一来导致的情况就是，对于填涂的识别会越来越准确，但对于未填涂的识别错误也会越来越高，反之亦然。也就是说，若n固定，将阈值作为横轴，识别正确率作为纵轴画出来的图形，应该是一个类似小山坡的形状；而当n增加的时候，由于表征性能更好，画出来的图形应该是比前者的形状更“高”。那么，应该大约会在n=3，4，也就是选项分成9个或16个矩形，阈值T为0.6左右的时候，构造出来的决策树识别性能会是最好的，因为在这个区间内，小矩形具有足够好的表征性能，而阈值的也是靠近中间的值，两者达到了对正样本和负样本都不偏不倚的平衡状态。下面我们通过仿真实验来验证猜想。

3仿真实验

本论文实现算法所用到的操作系统是Win7专业版，cpu为AMD A8 PRO，数据仿真的平台为vs20lO+opencv2.4.10，论文中关于效率的数据皆基于此，不同平台得到的结果会有所不同。在opencv中，已经有实现决策树的开源算法[5]而本论文也是在该算法的基础上进行调试和改进的。

3.1构造训练样本集和测试样本集

训练样本集的构造对决策树的生成非常重要。构造的训练样本集需要包含两部分，一是正样本集（填涂的选项图像集），二是负样本集（未填涂的选项图像集）。本论文从十多份不同的试卷中抽取了具有代表性的7 259张选项图像，其中正样本集共3 674张，负样本集共3 621张。

测试样本集中共有15 236张，其中正样本为7 590张，负样本为7 646张。

3.2结果分析

当设置n=2（即选项分为大小相等的4個小矩形），阈值为0.4-0.64时，通过上面的方法提取特征，构造决策树，并对测试集进行测试，结果统计如表1所示。

从上面的表格可以看出，在测试样本中，当阈值较低时，正样本的错误个数也较少，而负样本的错误个数则很多，因此总正确率不是很高；随着阈值增加，负样本识别正确率上升；而后面由于阈值过高导致了正样本识别正确率降低，这跟前面的推测是一样的。

同样地，增大n的值，记录识别结果。n=3，4，5时的阈值与准确率关系如图1所示。

可以看到，当n=3时总体的准确率要比n=2时高，而n=4时总体准确率又比n=3时高，并且当n=4，阈值为0.62时准确率达到最高值，为9 9.7%。而当n再增加的时候，会使得切割的矩形过小，增加决策树的复杂度，并增加额外的时间，但跟前面的性能所差无几，因此，在n=4时所提取的特征已经能够很好地表征填涂的信息，也具有很好的识别率。测试样本在n=4，离散化阈值为0.62时构造出来的决策树识别结果的详细准确率如表2所示。

从上面的数据可以看到，正样本和负样本都达到了较高的正确率。因此，将选项分割为4X4的小矩形，求出其占空比，并根据阈值为0.62将占空比离散化作为特征，构造决策树进行识别的方法是有效可行的。

3.3识别效率

本次测试共15 236份测试样本，识别耗费时间为8 237 ms，平均0.54 ms识别一道选项，可以说，决策树的识别效率是非常高的。

4结语

科技的发展日新月异，传统的纸质考试，人工批改的方式也在科技发展的潮流下发生着深刻的变革，越来越多的学校、考试都采用了数码自动化的批改方式；同时，图像识别，机器学习等算法也成为当下流行的研究热点；机器学习中的决策树算法具有方便、简洁、易于理解准确度高等特点。本文在决策树的基础上，结合改进的特征提取方法，提出一种答题卡选项识别算法，并通过仿真试验得出了特征提取中的最佳参数：n=4，T=0.62；在该参数组合下，构造出来的决策树具有良好的识别准确率和识别效率。该算法兼容性高，能够很方便地移植到当前的答题卡选项识别系统上。

[参考文献]

[1]杨燕青，彭延军基于灰度图像的答题卡识别技术[J]山东科技大学学报（自然科学版），2009（3）：99-102

[2]高育鹏，杨俊，何广军.基于图像识别的自动阅卷系统研究[J]现代电子技术，2006（ 22）：119-120.

[3]周万珍，郑广，王健霞.数字图像处理技术在客观中的应用[J]数学的实践与认识，2006 （8）：243-246

[4]郑广，秦敏基于图像识别的客观题阅卷研究[J]仪器仪表学报，2006 （6）：273-274，791

[5]阮秋琦数字图像处理学[M]北京：电子工业出版社，2001.

[6]刘洪涛，孙天泽嵌入式系统技术与设计[M].北京：人民邮电出版社，2011

[7]苏锦秀基于图像识别的答题卡研究[J].现代技术，2008 （22）：119-120

[8]王胜春.基于SVM的信息卡识别系统[D].长沙：湖南师范大学，2008

[9]周海涛，韩晓军.基于数字图像处理的答题卡识别方法研究[J].电脑知识与技术，2008 （10）：197-199

[lO]JohnD，蔡竞峰，蔡自兴.决策树技术及其当前研究方向[J]控制工程，2005 （1）：15-18

[11]彼得哈灵顿机器学习实战[M]李锐，李鹏，曲亚东，等，译北京：人民邮电出版社，2013.

[12]加里布拉德斯基，阿德里安.学习Opencv[M]._于-仕琪，刘瑞祯，译北京：清华大学出版社，2016