计算机网络论文网络考试系统自动评卷算法的应用研究

所属栏目：计算机网络论文
发布时间：2014-04-19 10:06:34 更新时间：2014-04-19 10:40:33

　　随着计算机技术的不断发展和网络技术的日益普及，如何能最大限度的利用各类资源，快速提高技术人员的知识和能力水平成为社会的强烈需求。不管是在目前的高等学校，还是各类异地教育和培训机构，考试都是教学活动的一个重要环节[1]，用来检测学习成效。

　　【摘要】随着网络化的发展，网络教学近几年逐渐兴盛起来，是未来教育发展的一种趋势，网络考试系统是网络教学的核心组成部分之一。本文针对当前已有考试系统的不足和学校的实际需求，设计和实现了一个新的网络考试系统，其中就主观题自动评卷技术作了分析与讨论。

　　【关键词】网络教学,网络考试,主观题自动评卷

　　一、相关背景

　　随着考试类型的增多和考试要求的不断提高，特别是考生数量比较大时，教师的工作量也越来越大，组织一次完整的考试至少包括以下几个步骤：考生报名、人工出卷、试卷印刷、考生考试、人工评卷和成绩统计分析等，在整个工作过程中，由于接触的人员较多，通常还要考虑保密性方面的问题，例如教师需要找大量试题出多份试卷，再由选择其中一份或者两份作为考试用卷，试卷选择随意性大，凭教师的主观意愿来评定一张试卷的难易程度；还要联系印刷和送试卷等，花费教师们大量的时间和精力，通常效率低下，可以说传统的考试方式己经不能适应现代考试的需要。

　　本文根据作者所在的院系教学的需要，利用校园网强大的服务功能，要研究和设计的是一个完全无纸化考试系统，采用B/S结构，易于安装使用。系统实现了从自动组卷、考试到自动评卷的全部功能。本文对其中主观题的自动评卷技术进行重点研究。

　　二、自动评卷技术

　　网络考试的主要优点之一就是可以快速、客观地给出考试成绩，有效地缩短了考试周期，这一优点主要得益于网络考试的自动评卷[2]。

　　一般情况下，网络考试系统对于客观题可以进行自动评卷。客观题一般有判断题、单选题等。对于这类题，计算机可以采用字符串比较的方法，将考生的答案与标准答案进行精确的匹配评卷。

　　如果一个考试系统中的考题都是客观题，这样的试卷不是一份好的试卷，仅有这类题型的试卷对测试考生的能力还存在欠缺。因此，理想的试卷针对不同的学科还应该包括有主观题（问答、证明、计算、设计题）等多种题型。但是对于主观题，如论述题、简答题等没有统一答案的试题，目前还没有一种考试系统能很好地完成其自动评卷。对此我们进行了一些尝试，对自动评卷技术做一些详细的介绍。

　　主观题自动评卷涉及到人工智能、模式识别和自然语言处理等方面的理论[3-4]，面临许多技术上的问题，从而成为网络考试系统中的一个技术难点[5]。主观题自动评卷技术主要由自然语言处理，中文分词技术[6]，语句相似度计算三方面构成。其中自然语言处理技术和中文分词技术到目前为止还没有得到广泛的应用，原因在于对自然语言处理技术的研究还处在一个初级阶段，无法实现计算机能够百分之百地“读懂”人类的语言，同时由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，目前基于理解的分词系统也还处在试验阶段。所以基于语句相似度的主观题自动批改系统的实现成为本文研究的重点。在本系统中，由于开发时间短促以及各项条件尚不成熟，因而没有全面地实现主观题自动评卷模块的设计，但在本文先分析了目前使用主观题自动评卷技术中的一些算法，以期能抛砖引玉。

　　（一）基于词语匹配的相似度法

　　1.思路分析

　　分析教师的评卷过程，教师在人工评阅主观题时一般是预先制定好一套评卷标准，然后将每道试题的总分划分成若干部分，将分数分配到试题的求解过程中的一些关键的步骤或关键的词语上，通常称之为得分点，评阅时看学生的答案和标准答案的各个得分点的贴近度，贴近度高则得分高，最后查看一下学生答案的语句是否通顺、是否有条理性等，综合地给出一个适当的分数。

　　根据上述分析，可以发现，影响评卷的因素主要有两个：一个是得分点，另一个是学生答案和标准答案的贴近度。可以将每个得分点转化为每道题目的标准答案关键字，用这些关键字去匹配学生答案，根据匹配程度的高低，决定得分的高低。对学生答案和标准答案的贴近度的表示可采用模糊数学中贴近度的概念进行描述[7]，而对于语法结构则不做过多考虑，这样，一方面可以避免对句子进行复杂的句法分析，另一方面也可增加系统的健壮性，如学生答案中出现无关大局的语法错误时，只要其概念表述正确，系统仍然可以给出相应的贴近度评价，这与教师的评卷过程是相符合的。最后，再根据关键字和贴近度在评卷时所占的权值比重，计算最终成绩。

　　2.算法设计

　　（1）相关定义

　　为解决学生答案和标准答案的贴近度表示问题，可以把学生答案和标准答案均看成字符串，下面对单向贴近度的概念进行定义。

　　把一个字符串分解为单个字符，并把它们构成的有序集合称为一个模糊集，U={u1，u2，……，un}称为论域，论域u上的全体模糊子集所组成的集合记作F（U）（也叫模糊幂集）[7]。

　　为度量两模糊集的接近程度，引入单向贴近度的概念。

　　定义1：

　　设U={u1，u2.......，un}，A，B∈F（U）。若映射d：F（U）×F（U）→[0，l]，满足条件：

　　d（A，A）=l；d（B，B）=1；

　　若A包含于B，而B包含于C或A包含B，而B包含C，则d（A，B）≥d（A，C）称d（A，B）为A贴近于B的单向贴近度。

　　定义2：

　　设A、B是字符串，A中包含n个字符，d（A，B）表示A贴近于B的单向贴近度，按照从左到右的顺序，集合A中的每个元素在集合中出现的有效次数之和记为m，则d（A，B）=m/n，容易验证，它满足单向贴近度的定义。

　　（2）算法说明

　　为说明方便，以字符串A和B为例介绍计算字符串A贴近于字符串B的单向贴近度d（A，B），步骤如下：把查找字符串A分解为单个有效字符。在分解前，首先判断左边第一个字符是双字节字符还是单字节字符，如果是双字节字符就按2个字节截取，如果是单字节字符则按l个字节截取。把字符串A分解为若干个有效字符u1，u2，……，un。

　　判断A分解后的单字符是否包含在被查询的字符串中。这里假定所要查找的字符串分解前和分解后是有顺序的，所以不能简单地使用是否包含来判断。本文的做法是：判断第一个字符u1是否包含在字符串B中，如果不包含则标记为0，否则标记为l，并从B2中去掉包含u1的字符，对B进行第二个字符u2的相同处理，一直把u1，u2，……，un。判断完毕。

　　计算单向贴近度d（A，B）。计算A分解后的单字符u1，u2，……，un在B中出现的次数之和m占A总有效字符数n的比值，并记为d（A，B）。

　　3.自动评卷实现

　　根据上述分析，可以得出主观题的评卷公式。

　　（1-1）[7]

　　式中各符号的含义如下：

　　Sim1（A，B）：是学生答案与标准答案的相似度；

　　A：学生的实际答案。学生交卷后保存在学生答卷库中；

　　B：试题的标准答案。出题时生成，从题库中读取；

　　P：关键词在该题目中所占分值的比例，0≤P≤1。组卷时生成，也可评卷时修改，从试卷库中读取；

　　1-P：关键词以外的因素在该题目中所占分值的比例；

　　n：关键词的个数。根据题库中的关键词信息由程序计算得到；

　　Ki：第i个关键词，1≤i≤n。根据题库中的关键词信息由程序拆分得到；

　　dki（Ki，A）：第i个关键词与学生答案的单向贴近度，1≤i≤n。由程序计算得到；

　　dk0（K，A）：关键词与学生答案的单向贴近度阀值。组卷时生成，也可评卷时修改，从试卷库中取得。

　　其含义是：

　　当dki（Ki，A）当dki（Ki，A）≥dk0（K，A）时，dki（Ki，A）=dki（Ki，A）。

　　da（A，B）：标准答案与学生答案的单向贴近度。由程序计算得到；

　　da0（A，B）：标准答案与学生答案的单向贴近度阀值。组卷时生成，也可评卷时修改，从试卷库中读取。其含义是：

　　当da（A，B）当da（A，B）≥da0（A，B）时，da（A，B）=da（A，B）。

　　从公式中可以看出，主观题的评卷受P，dk0（K，A），da0（A，B）三个参数影响，P增大，关键词在评卷中占的比重就增大，反之则减小；一般来说，dk0（K，A），da0（A，B）增大，则表示评卷标准提高，反之，评卷标准降低。因此，通过调整这三个参数，即可实现对评卷标准的调整。这三个参数可在组卷时设定，保存在试卷信息中，也可在评卷时进行调整。

　　（二）基于语义信息的相似度法

　　1.思路分析

　　基于关键词信息的方法由于没有考虑词本身的词义信息以及同义词、近义词等语义关系，实际应用于自动该卷系统有一定的局限性，基于语义信息的方法可以部分地解决这一问题。基于语义信息的相似度也就是两个词语意思的相近程度，它是句子之间意思相似程度的基础，也是答案比较研究的基础。它的相似度比较的准确性影响着答案比较的准确性，从而也影响着整个考试系统判卷的正确性[8]。

　　语义信息相似度对于主观试题评判非常重要，但是由于语义信息相似度是一个主观性很强的概念，所以一直以来如何更准确地计算两个词语之间的相似程度，都是国内外研究的难点。它很难直接给出一个公式来衡量两个词的语义信息相似程度。大部分国内外关于语义信息相似度的研究一般都是将所有的词语按其意思所属的类别组织成一棵或几棵树状结构，树状结构中每个节点相对应一个词语，该词语位于树的层次结构中所处的位置越高，表示它涵盖其他概念的能力就越强。那么，由于在一棵树形图中任何两个节点之间有且只有一条路径，可以将词语之间相似程度用树的节点之间的距离来衡量[9]。

　　2.算法说明

　　一般而言，词语距离是一个[0，∞]之间的实数。一个词语与其本身的距离为0，词距离与词语相似度之间有着密切的关系。

　　两个词语的距离越大，其相似度越低；反之，两个词语的距离越小，其相似度越大。二者之间可以建立一种简单的对应关系。这种对应关系需要满足以下几个条件[9]：

　　（1）两个词语距离为0时，其相似度为1。

　　（2）两个词语距离为无穷大时，其相似度为0。

　　（3）两个词语的距离越大，其相似度越小（单调下降）。

　　对于两个词语W1和W2，记其相似度为Sim（W1，W2），其词语距离为Dis（W1，W2）那么可以定义一个满足以上条件的简单的转换关系：

　　（1-2）[9]

　　其中是一个可调节的参数。的含义是：当相似度为0.5时的词语距离值。所以，假设词语组成的树的高度为H，那么两个节点最远距离为2H（根节点为0层），则可以等于树高H。当两个词语在不同的树中，那么它们的距离为∞。当然，的取值并不是唯一的。

　　本文主要是以知网的义原层次树为基础对词语的相似度进行研究[10]。在知网中，它认为词是由表达其意思的几个义原组合的，这些义原可以根据其义原之间的上下位关系构成义原层次树。在这棵树中，每个节点就是一个义原。由于所有的概念都最终归结于用义原来表示[11]，所以义原的相似度计算是概念相似度计算的基础。

　　因为所有的义原根据上下位关系构成了一个树状的义原层次体系，可以简单地通过词语距离来计算相似度。假设两个义原在这个层次体系中的路径距离为d，根据（公式1-2），我们可以得到这两个义原之间的语义距离：（1-3）[11]

　　其中p1和p2表示两个义原，d是p1和p2在义原层次体系中的路径长度，是一个正整数。如果两个词语处于不同的义原层次树中，那么d为无穷大。是一个可调节的参数，本文中值为各义原层次树的树高。

　　本文所讨论的方法是以义原层次树为基础的，而义原层次树仅仅是按义原上下位关系组成的，因此用这种方法计算义原相似度的时候，并没有考虑到义原的其他关系，如反义关系，对义关系等。尽管考虑其他义原关系会增加义原相似度计算的准确性，但是基于对系统复杂程度的考虑，只利用了义原层次树进行义原相似度的比较也是可以接受的，因此本论文中采用的都是单纯利用义原层次树来计算义原距离和词语相似度的方法，而没有考虑其它义原关系对词语相似度计算的影响。

　　3.算法实现

　　由于义原表达位置和词语多义的情况，使得两个词语的相似度比较要分为两个步骤：首先，在不考虑一词多意的情况下，对两个词语的比较。假设词语A（a1，a2，…，an）和词语B（b1，b2，...，bm），其中ai，bi分别为词语A，B的义原项。如果两个词语的第一个义原项相似度为0，说明这两个义原肯定不在一棵义原层次树中，由于第一义原对词语的影响最大，决定了词语的类型，因此，当两个第一义原相似度为0的时候，可以不用计算后面的其他义原相似度，直接认为两个词语的相似度为0。如果第一义原比较不为0的话，那么词语A与B的相似度就应该是A的第i个义原与B的第i个义原相比较的加权平均和[12]。即：

　　（1-4）[12]

　　其中义原项的权重：

　　（1-5）[12]

　　如果n不等于m，也就是说A和B的义原数目不相等，假设A>B，那么在B的义原项m之后的AB义原项比较的相似度可以看作是0。

　　在出现一词多义的情况下，假设词W有z个意思，那么它就有z个义原组合情况Ai（i=1，2，……，z），那么W的第i个意思Ai又是由j个义原项组成Ai（a1，a2，……aj），因此，词语W与词V比较时，应该把Ai分别与V的义原项进行比较，取最大相似度为词语W与V的相似度。

　　（三）基于融合的语句相似度法

　　完整地表达一个句子的信息，不但依赖于组成句子的词汇的信息，而且还依赖于词汇之间的语义信息。本论文从句子结构信息和词汇之间的语义信息进行研究，以便更准确地进行句子相似度计算。

　　我们的目标是将句子的词形（词语匹配技术）、词义（词语语义信息）组合起来，扬长避短，互为补充，共同描述一个句子，从而根据这些特征计算学生答案和标准答案之间的相似度，获得较高的准确率。

　　因此可将前两种方法相结合提出：

　　（1-6）

　　由于不同层次对句子相似度计算的贡献不同，该方法对每个层次加了不同的权值，从而使相似度计算达到最优。其中两个权值的设置规定为：

　　（1-7）

　　由此得出如果一道题目的分值为S0，则最后得分S为：

　　（1-8）

　　（四）自动评卷测试

　　为了验证用基于语句相似度的三种算法进行自动评卷的可行性和有效性，我们抽取了07网络1班的《数据结构》试卷来进行实验，班上一共有20个学生参加了考试。每份考卷中都有1道简答题，并且教师已经对其人工评卷完毕，这样能够方便地计算出准确率。

　　我们以考题“什么是算法”为例，标准答案为：“算法是问题求解规则的一种过程描述（即计算机解题的过程）。它具有5个基本性质：确定性、有穷性、可行性、输入和输出。”设定好该题目的分值为10分，其中一个学生的答案是“算法是一种求解的过程，它具有逻辑性、可计算性和穷尽性”。分别通过三种相似度方法的计算得出最终分值进行准确率的比较。

　　通过实验最后得出，基于融合的相似度计算方法把基于词表面信息的相似度计算和基于语义信息的相似度计算很好地结合在一起，充分发挥了采用词性和词义方法的长处，最后得到了较高的准确率。并且我们对测试错误的结果进行了分析，发现错误的主要原因在于两点，一个是在对基于词语匹配相似度计算中我们所定义的关键词拓展的不够，也就是未登录词导致的问题；另一个原因是在基于语义信息相似度计算中利用语义词典会给根本与题意无关的学生答案评了较高的分数，从而带来了错误的计算结果。

　　三、工作总结

　　本系统在做了大量的研究和调查的基础上，针对广东私立华联学院的实际情况进行开发建立了一个比较完善的网络考试系统原型，该系统可适用于各类学校、成人教育，职业培训和技术培训等机构在远程教育平台上进行考试管理，其推广使用对于教学管理的改革，使有限的师资发挥更大的作用等方面具有重要的意义。

　　参考文献

　　[1]罗红梅.基于J2EE架构的在线考试系统的设计与实现[D].硕士学位论文.

　　[2]孙卫.基于web的网络考试系统的设计与实现[D].河海大学计算机及信息工程学院，2007.

　　[3]魏晓宁.人工智能在自然语言理解技术上的应用[J].科技论坛，2005（10）.

　　[4]金博，史彦军，腾弘飞.基于语义理解的文本相似度算法[J].大连理工大学学报，2005（3）.

　　[5]董英斌等.基于网络的新型计算机考试系统[J].计算机工程，2001.

　　[6]龚汉明等.汉语分词技术综述[J].北京机械工业学院学报，2004.

　　[7]孟爱国等.一种网络考试系统中主观题自动评卷的算法设计与实现[J].计算机与数字工程，2005.

　　[8]高思丹，袁春凤.语句相似度计算在主观题自动批改技术中的初步应用[J].计算机工程与应用，2004.

　　[9]汪泱.主观文字试题评判相关技术研究[J].北京科技大学计算机学院，2006.