基于语义相似性的选择题自动生成优化方法

温雪峰 崔仙姬 张俊星

（大连民族大学信息与通信工程学院 大连 116600）

1 引言

近年来，线上教育发展得更加丰富和多元化。线上教育是指通过互联网、移动设备等传播媒体实施教学的教育形式［1］。现阶段线上教育已经成为主流教育方式之外的另一大教育方式［2］。2020年1月爆发的新冠肺炎疫情，对在校学生的学习生活造成极大影响，大中小学寒假被迫延长，政府号召“停课不停学”，各大学校纷纷开展线上教育，以保证学生的学习生活。线上教育的一大重点便是线上考试，但现阶段大多数线上考试系统的实现原理基本类似，都是人工将试题输入到数据库中，然后从数据库中抽取试题组成试卷［3］。这种人工构建试题库的方式不仅需要耗费大量的人力和时间资源，而且难以控制试题的规范性以及试题的难度。通过自动生成试题，可以大大地减少出题时间，节省人力资源，试题更具规范，难度易于控制。

随着语义网的发展以及在线知识库发布知识的便利性，本体论进入了研究者的视野，研究人员开始研究如何通过本体测试特定领域的内容。本体是通过抽象出客观世界中一些现象的相关概念而得到的模型［4］，从不同层次的形式化模式上给出词汇和词汇之间相互关系的明确定义［5］。通过使用本体不仅可以让电脑识别信息，人也可以明确其中含义，实现人机交互［6］。基于本体的上述特点，使用本体生成选择题是一种便捷且高效的方法。本体作为知识的有效组织和表示形式，在线上考试当中受到了广泛的关注和应用［7］。

国内外的研究人员将基于本体的试题自动生成的重点放在了选择题自动生成方法的研究中。国外的研究工作有以下内容，Edmond等首次将本体应用于教育方面［8］，并于2006年提出了使用本体来生成评估问题的策略［9］。Andreas Papasalouros等提出了一种自动生成选择题的方法，该方法基于本体公理以及OWL（Web Ontology Language）开发的知识库中的断言生成选择题［10］。2010年Cubric和Tosic提出使用问题模板来避免自动生成的问题中的语法问题，并通过考虑新的本体元素（即注释）扩展了他们以前的工作［11～12］。Al-Yahya等使用本体中有关领域实体（如类、属性和个体）的固有知识来生成语义正确的评估项［13～14］。Vinu E.V等提出使用谓词模式应用本体以生成选择题的方法［15］。2017年Vinu E.V等对谓词模式生成选择题的方法进行了改进，改进后的方法可以使用二元以上的谓词模式生成题干，并提出了一种控制问题难度的方法［16］。

目前国内的相关研究有以下内容，刘明等提出了一种混合相似策略，用于自动生成汉语多项选择题，该策略通过统计回归模型生成汉语多项选择干扰源［17］。肖文彦等提出了一种适合不同语言水平的非英语母语学习者的介词多项选择题生成方法［18］。刘昭麟等提出了一种词义辨析的演算法，利用词典和selection preference所提供的资讯，分析试题答案的词义，并以collocation为基础的方法筛选干扰项［19］。盐城师范学院的丁向民等提出了通过元知识点模式和本体技术来自动生成多项选择题的方法［20］。

目前基于本体自动生成选择题的技术具有生成的问题数量庞大、问题相似度高、问题难度无法控制、干扰项质量较低等问题。因此，需要对自动生成的题目进行进一步筛选，从而选择合适的、具有代表性的问题进行测试，并选择所需难度的高质量干扰项对问题进行难度控制。基于上述问题，本文提出一种结合最小顶点覆盖问题的相似性筛选方法对选择题问题进行筛选，并通过计算选择题选项之间的语义相似性生成对应难度的干扰项来控制问题的整体难度。

2 基于本体的选择题自动生成系统框架

如图1所示，基于本体的选择题自动生成系统主要包括三个模块：题干生成模块，问题筛选模块以及干扰项生成模块。题干生成模块的主要作用是生成选择题的题干部分；筛选模块主要作用是通过筛选以减少问题的数量，选择更具代表性的问题用于测试；整个系统中最后的一步是干扰项生成，干扰项是决定选择题质量和难度的主要因素，通过干扰项可以控制问题的难度级别。

图1 选择题自动生成系统

在基于本体的选择题自动生成系统中，输入一个本体文件，通过题干生成模块生成数量庞大的问题，题干生成的主要方法是基于本体的元组，利用简单的SPARQL查询模板来生成问题。对于已生成的问题需要进一步进行筛选，否则问题的数量过于庞大、问题不具有代表性，不适合用于测试特定领域的知识。干扰项生成模块用于生成选择题的干扰项，使用可能答案减去正确选项的方法生成干扰项，选择题的质量难以保证，难易程度无法估计。通过计算干扰项与正确选项之间的相似性，进一步选择干扰项，可以控制选择题的质量以及难易程度。为了解决上述问题，生成高质量的选择题题库，应用基于图的最小顶点覆盖问题的相似性筛选方法对问题进行筛选，并进一步应用基于语义距离的相似性计算方法对干扰项进行筛选，选择适当难度的干扰项。

3 选择题自动生成优化

3.1 选择题问题筛选

在本体中存在大量的语义相似的元组，这些元组将产生大量的相似问题。以Geography本体为例，如表1所示，其中x表示核心实例，将作为问题的正确选项，O为对象属性，i为实例。表中数据为题干生成模板的SPARQL查询结果，该模板由两个三元组构成。从表1可以看出，在同一问题生成模板下，本体中存在大量对象属性O1、O2相同的相似元组，而这些相似元组将产生大量的相似问题。在用于测试时，相似的问题降低了测试的效率以及质量。为了避免问题集中存在语义相似的问题，必须从相似的元组中只选择一组具有代表性的元组来生成问题。

表1 本体中部分相似的三元组

根据两个元组中谓词之间的关系和元组中语义相似三元组的数目，可以计算出两个元组的相似度得分如式（1）。

在式（1）中P（t）表示三元组t的属性序列，X（P（t））表示满足属性序列P（t）的实例。S imil ari ty(t1，t2)是确定两个三元组相似性的对称函数。#S E(t1，t2)表示t1与t2中语义相似的三元组个数，Max(#t1，t2)表示取t1与t2中三元组个数的最大值。公式的第一部分给出了基于对应元组中匹配谓词的分数。当元组中谓词的一对一对应时，X（P（t1））和X（P（t2））变得相等。在公式的第二部分中，通过考虑匹配时属性之间的子性质、对称关系和逆关系，计算了三元组的语义等价性。

根据上面给出的两个元组相似性得分，构造一个无向图G=(V，E)，无向图的顶点集为V={t|t∈S}，其中t为三元组，S为三元组集合，根据元组之间的相似性关系构建无向图的边，无向图的边集为E={(t1，t2)|t1，t2∈S and S imi larity(t1，t2)≤c}，其中c为最小相似性得分阈值，元组间的相似性得分作为无向图边的权重。

选择题问题筛选的主要思想是从大量相似的元组中获得少量的相似性较低的、能够代表整个本体的元组。因此，可以将问题的筛选转换为求无向图G的最小顶点覆盖问题。图的最小顶点覆盖问题是指给定一个无向图G=（V，E），找到其最小的顶点覆盖集，使得每条边至少有一个顶点存在于最小顶点覆盖集中。在文献［15］中，研究者通过使用JGraphT（https：//jgrapht.org）中提供的最小顶点覆盖近似算法进行了问题的筛选。这种筛选方法在构建图时仅将元组间的相似性关系作为构建边的条件，随机选择满足条件的节点，这使得所筛选问题集并未充分考虑到元组之间相似性对于最小顶点覆盖集的影响，不能保证筛选后得到的元组具有代表性。为了提高结果的质量，使问题能够更好地代表整个本体，本文将元组之间的相似性得分作为无向图边的权重，在求无向图的最小顶点覆盖集的过程中，将权重的影响加入其中。

基于NUMVC（A Novel Local Search for Minimum Vertex Cover Problem）的相似性筛选算法将元组之间的相似性得分作为权重，并且加入顶点删除策略，使得最小顶点覆盖集的结果更加准确，算法的搜索效率更高。利用基于NUMVC的相似性筛选算法可以得到无向图中最少的顶点，使得这些顶点具有较小的相似性，顶点更具有代表性。包含不同问题的问题集比包含相似问题的问题集更倾向于检查更广泛的知识。为了使一个问题集足够小，检查相同的知识，删除相似类型的问题，在其中保留一个有代表性的问题。

算法1：基于NUMVC的相似性筛选算法

输入：无向图G=（V，E）

输出：无向图G=（V，E）的最小顶点覆盖子集V’。

1.InitializeV'←∅No-improve←0 rmv-num←α；

2.while not found min（V'）

3.if No-improve==βand rmv-num≠1

4. rmv-num--；

5.for i=0；i

6. remove vertex v

7.whileV'exist uncovered edges

8. add vertex v

9.Remove redundant vertices inV'to getV''

10.if|V''|<|V'|

11.V'←V''

12.No-improve←0；

13.else No-improve++；

14.return min（V'）

基于NUMVC的相似性筛选算法的算法时间复杂度包括以下两个部分：计算顶点的相似性（O(S|V|)），查找图的最小顶点覆盖（O(N|V|)），其中S表示式（1），由此可得算法1的时间复杂度为O(S|V|+N|V|)。

表2 相似性筛选后的元组

表2给出了表1中数据使用基于NUMVC的相似性筛选算法筛选之后的数据（m<

3.2 干扰项难度控制

在问题难度控制方面，目前的主要方式是通过题干与正确选项的关联性控制问题难度，然后利用干扰项进一步调整问题的整体难度，将干扰项作为问题难度控制的辅助。

本文考虑在同一个问题模板下，利用干扰项的难度直接控制问题的整体难度，忽略题干对于问题难度的影响，可以避免题干形式不统一、问题难以管理等问题。通过计算正确选项与干扰项的相似性，选择对应难度的干扰项，可以控制问题的整体难度，以生成高质量且所需难度等级的选择题。

干扰项是从问题的可能答案集合中减去正确答案而产生的。正确答案指的是本体中那些满足题干中给出的条件的实例。如果通过上述操作得到空集或与所需的选项数相比较少的干扰项（d≤3），除了可能答案集合中的干扰项之外，可以选择其他任何元组中的实例或数据类型值作为干扰项。

正确选项与干扰项相似度计算的主要方法是考虑二者之间的距离，其基本原理是：从本体结构图出发，相似程度较低的概念之间的距离就会越长。路程不同的两个概念之间对于语义相似度计算的结果也会产生一定的影响甚至是误差。为了避免这种影响与误差的存在，在计算两个概念之间的相似度时，可以充分利用另外一种对语义相似度计算有影响的因素，也就是两个概念之间最近共同父节点深度。如果两个本体概念之间的最近共同父节点的深度越浅，那就表示分类越不明确，进而可以说明继承语义的信息越少，也就是两个本体概念之间的相似度越低。式（2）和式（3）为根据语义距离和父节点深度计算正确选项与干扰项的相似性得分公式。

式（2）表示概念c1到c1与c2的最近公共父节点的最短路径，mp（c2，RCPN（c1，c2））表示概念c2到c1与c2的最近公共父节点的最短路径，RCPN（c1，c2）表示c1与c2的最近公共父节点。考虑到节点深度对相似性的影响，利用式（3）来计算正确选项与干扰项之间的相似性。式（3）为基于本体语义距离的正确选项与干扰项的相似度计算公式，其中d p(R C PN(c1，c2)，c1)表示概念对c1和c2的最近公共父节点，在概念c1所在本体结构图中的深度，max（dp（c1））表示概念c1的本体树的最大深度。

基于式（2）和式（3）的计算结果，设计了一种干扰项难度控制算法，如算法2所示。通过输入正确选项、干扰项集合以及问题难度等级，利用式（2）和式（3）分别计算正确选项与干扰项集合中干扰项d的相似度，将相似性得分作为干扰项的难度得分Dscore，结合对应的难度等级，对Dscore进行判断，获取满足难度等级的干扰项d。最后输出干扰项d以及其难度得分Dscore。

干扰项难度控制算法通过节点之间的距离因素以及节点最近父节点因素的共同作用计算节点之间的相似性，使得相似性结果更加精确。

干扰项难度控制算法的算法时间复杂度包括以下两个方面：计算选项之间的相似性（O(D||d+S|d|)），选择对应难度的干扰项（O(C|d|))），其中D表示式（2），S表示式（3），由此可得算法2的时间复杂度为O(D||d+S||d+C|d|)。

算法2：干扰项难度控制算法

输入：key，一个实例（正确选项）

D，干扰项集合

Difficulty-level∈｛high，medium，low｝

输出：d，干扰项，Dscore，难度得分

1.whileD≠∅

2.for each instance d in D

3. countS ims d(c1，c2)

4. dscore←Simsd(c1，c2)

5. if Difficulty-level==hight

6.d={d|0.50≤d score<1}

7. if Difficulty-level==low

8.d={d|0≤d score<0.50}

9. if Diffaculty-level==medium

10.d={d|0.35≤d sc ore≤0.75}

11. Remove d in D to getD'

12.D←D'

13.return d andDscore

4 实验评估

下面评价题干筛选方法以及干扰项难度控制方法的有效性，主要围绕以下两个方面来展开：1）测试基于NUMVC的相似性筛选算法对于题干筛选的可行性与有效性；2）测试干扰项难度控制算法在干扰项生成中的可行性与有效性。

本次实验在如下环境中进行：Inter core i5 1.4Ghz CPU；4.0GB RAM，MasOS Catalina，而本体的解析通过调用JenaAPI（https：//jena.apache.org）实现。

4.1 问题筛选

实验中使用的本体数据集由德克萨斯大学奥斯汀分校的Ray Mooney和他的团队提供，数据集中包含三个OWL知识库组成，三个OWL知识库涉及三个不同的领域：地理信息（Geography）、工作信息（Job）以及餐厅信息（Restaurant）。如表3中的数据所示，表中第一行数据为本体名称，第二行数据为本体中的对象属性数目（Object properties），如表1和表2中的O1和O2，第三行为数据类型属性的数目（Datatype properties），第四行为本体中元组总数（Total tuple count）。在本体中存在大量的元组，这些元组将生成难以管理、数量众多的问题。

首先根据元组的属性进行初步的筛选，筛选结果如表4所示。根据属性对元组进行筛选的主要目的是将元组中那些不太可能用于测试的元组筛选掉，这些元组构成的问题可能太过简单或者太过难以回答。

表3 样本本体的属性与相应的元组计数

表4 属性筛选后本体的属性与相应的元组计数

在根据属性进行初步筛选后，对剩余的元组分别使用文献［15］中的算法和本文中的NUMVC算法进行相似性筛选，结果如表5所示，表中最后一行给出了元组的减少比例（TR）。从表5的对比结果可以看出，基于NUMVC的相似性筛选算法在对三个本体进行问题筛选操作时，分别比其他问题筛选方法多减少了15%、20%、10%的三元组数量，由此可见基于NUMVC的相似筛选算法在问题筛选方面有较为明显的优势。

从大量的相似的元组中获得数量较少具有代表性的元组，使用这些元组生成选择题，使得问题集中问题的数量减少，更加易于管理，问题也更具有代表性。由于不同本体获得的代表性元组数量不同，所以不同本体问题集中的问题数量也不同。

表5 问题筛选结果及对比结果

4.2 干扰项生成

在测试干扰项难度控制算法时，对输入相应问题难度等级，能否准确输出对应得分的干扰项进行了多次实验。在表6～8中展示了从Geography本体中生成的三种不同难度等级的例题，展示了选择题的难度得分以及干扰项的难度得分（Dscore）。如表6～8所示，根据对应的问题难度等级，可以准确地选择适当难度得分的干扰项，良好地控制问题的整体难度。

在表6中，设置选择题的难度为medium，选择三个难度得分为0.50的干扰项，使得问题的整体难度值为0.50，该问题的质量中等，难易程度中等。在表7中，设置选择题的难度为low，选择难度得分为0.00的三个干扰项，使得问题的整体难度为0.00，该问题质量较低，易于回答。在表8中，设置选择题的难度为high，分别选择难度得分为0.85、0.70、0.50三个干扰项，使得问题的整体难度为0.65，该问题的质量较高，较为难以回答。

表6 Choose a geopolitical dependency，a member of exactly one sovereign state（Difficulty：0.50）

表7 Choose a nation（Difficulty：0.00）

表8 Choose the largest city in the United States（Difficulty：0.65）

5 结语

针对现有基于本体的选择题自动方法中存在的问题，本文提出了一种生成高质量选择题的优化方法。在控制问题数量以及问题质量方面，提出了一种基于NUMVC的相似性问题筛选算法。算法将问题筛选转化为对应无向图的最小顶点覆盖问题，并将元组之间的相似性得分作为权重，加入顶点删除策略，使得最小顶点覆盖集的结果更加准确。在问题难度控制方面，提出了一种通过干扰项难度控制问题难度的方法。算法通过计算正确选项与干扰项的相似性，选择对应难度的干扰项，控制问题的整体难度，以生成高质量且所需难度等级的选择题，实验结果表明，基于NUMVC的相似性筛选算法与干扰项难度控制算法能够在一定程度上提高自动生成选择题的质量。