改进的基于知识点均衡的智能组卷方案

周千明，朱欣娟

（西安工程大学 计算机科学学院，陕西 西安710048）

计算机辅助教学CAI(Computer Assistant Instruction)是当前高等教育的重点工程，在线考试已经成为CAI的一个重要研究课题。智能组卷是在线考试的核心目标之一。目前智能组卷算法主要有随机抽取法、回溯试探法以及遗传算法[1]。决定组卷效率和试卷质量的主要因素有两个：一是试题库的结构；二是组卷算法的设计是否合理[2]。随着在线考试智能组卷需求的提升，人们提出了一些基于知识点的组卷方案，这些方案在实际应用中取得了一定的效果，但仍存在一些问题与不足，归纳起来主要有：(1)在知识点的划分中没有明确区分元知识点与复合知识点，组卷时仅从元知识点着手，对于综合试卷的组卷，容易造成所选择的多数试题来自所属科目的同一章节的元知识点，不符合实际要求；(2)在建立试题库结构时缺乏对实际问题中题干及答案多样性的分析处理；(3)没有涉及到知识点出题数量的平衡策略，如在实际按章节范围组卷中，当要求的出题数目大于或几倍于限制知识点的数目时的处理策略。基于此，本文将在知识点的划分、试题库结构与算法实现上作一些探讨，以期对今后组卷方案的设计与优化起到一定的借鉴作用。

1 知识树的构建

知识点是教学活动过程中传递教学信息的基本单元，包括理论、原理、概念、定义、范例和结论等[3]。知识点可以分为元知识点和复合知识点，元知识点是不能再被分割的知识点，复合知识点是由若干个元知识点或复合知识点组成的知识点。知识树(Knowledge Tree)是知识点及其关系的集合，即知识树={知识点集合，知识点关系集合}，其中知识点关系集合是指知识点之间的父子关系集合[4]。根据知识体系结构，知识点的划分一般以教材为基础，采用细化的思想进行。从提高组卷效率的实际出发，将知识点按照科目的章节和内容自上而下划分为3个层次，构建一棵深度为4的知识树，如图1所示。

知识树根结点为科目名称，除根结点之外的所有结点为各级知识点，分为一、二、三级。对于不同的科目，各级知识点可以有不同的表征。一、二级知识点可分别表征为相应科目的章、节，三级知识点可表征为章节下的元知识点。一般地，一、二级知识点最多下辖20个左右下级知识点。因此，设定每个结点最多可以有26个孩子结点，用字母A到Z表示。为了便于处理，除根结点之外的所有结点统一采用4个字符编码，编码的最后一个字符为“*”。由于各级知识点的孩子结点数目存在差异，当叶子结点的层次不足3时，编码时在后面追加字符“*”以补足编码。例如，图1中二级知识点C编码为AC**，三级知识点 A编码为 ACA*。

2 试题库结构的设计

建立合理的试题库结构是实现智能组卷的重要环节。为了客观全面地反映试题固有的特征，试题库结构的建立必须综合考虑以下方面因素：

(1)各类题型格式的多样性。题型格式的多样性主要体现在：一部分试题只有1个问题，而另一部分试题则囊括2个或更多的子问题。前者如传统的单项选择题、只有1个空的填空题等；后者如英语试卷的阅读理解题、含有多个空的填空题等。

(2)试题答案可能不唯一，并且答案出现位置可能具有不确定性。这种情况主要体现在填空题上。例如有以下试题：“数据库的三级模式结构是指数据库系统是由____、____和 ____三级构成。”答案是“外模式;内模式;模式”，但各答案的位置不确定，具体有=6种情况。再如有以下试题：“面向对象的三大特征是 ____、____和 ____。”答案可以是“封装性;继承性;多态性”，也可以是“封装;继承;多态”，并且各答案位置也不确定。这就明显为试题库的建立增加了难度。

(3)便于智能组卷。建立试题库是以智能组卷为出发点，必须为智能组卷提供便利。

综合上述因素考虑，设计试题库结构如图2所示。

试题的属性有试题 ID、题型 ID、试题内容、试题扩展、试题分值、难度等级、是否试题组、估计用时、曝光度、知识点ID及科目ID。其中，题型包括选择题、填空题、判断题与问答题。选择题又包括单选题、多选题和不定项选择题。计算题、分析题、设计题、叙述题等均可以归到问答题中。试题内容和试题扩展共同体现整个试卷完整的试题内容。扩展内容、答案、答案扩展作为试题扩展的属性存在。难度等级包括简单、基本、中等、较难、难题 5个级别，分别用整型常数 1、2、3、4、5 表示。是否试题组标识该试题是否囊括两个或两个以上的子问题。曝光度反映了试题被选中使用的次数，曝光度越大说明在以往的试卷中该题被考的次数越多[5]。 曝光度设为整型常数-1、0、1、2、3、4。组卷时在曝光度为0到4的试题中选题，对选中的试题使其曝光度递增。每次组卷结束后，修改试题库中曝光度为-1与5的试题，曝光度为-1的增加为0，以进入下次组卷选题范围；曝光度为5的重置为-1，避免其下次组卷时被选中。试题内容有文字内容和图形内容，相应的试题答案也有文字内容答案和图形内容答案[6]。在试题库中以记录的形式组织上述的数据结构。

3 组卷控制参数的确立

组卷控制参数表征组卷的要求，由系统界面人机交互的方式获得。本文采用的组卷控制参数有考试科目、题型、题型的知识点(可选)、题型的题量、题型的分值分配、题型的时间分配、试卷平均难度等级以及试卷允许时间误差。

其中，为了满足实际中诸如单元试卷、期中试卷、期末试卷、专题试卷等不同形式的组卷需求，设定题型的知识点为可选的组卷控制参数。组卷人员可以根据实际需求灵活地指定考试科目相应知识树中的一级知识点、二级知识点、三级知识点或它们的任意组合，也可以不指定任何知识点，系统在组卷时将根据下文所述的知识点均衡策略进行知识点均衡。

4 智能组卷方案的实现

4.1 知识点均衡策略

为了保证组卷最大限度地趋近真实效果，知识点均衡很关键。本文采用如下策略在组卷过程中对各题型进行知识点均衡，结合图1所示，下面分两种情况讨论：

图3 知识点均衡核心策略简图

(1)当组卷人员没有指定知识点时，按图3所示策略实施。首先遍历考试科目对应的知识树，检索该科目中一级知识点的数目，然后再依次检索隶属于每级知识点的下一级知识点的数目，分别存入到数组中。然后根据题型的题量确定该题型的各级目标知识点及相应的目标题量，步骤如下：

①设考试科目的一级知识点数目为K1，题型的题量为 Q1， 首先求得 Q1相对于 K1的倍数 M1与余数 R1：M1=Q1/K1；R1=Q1%K1；然后进行相应的判断。 若 M1=0，则在这K1个一级知识点中随机选择R1个作为目标一级知识点，再分别在以这R1个目标一级知识点为根结点的子树的所有叶子结点中随机选择1个知识点作为目标三级知识点，各目标题量为1，知识点均衡结束；若M1>0，并且 R1=0，则这K1个一级知识点均作为目标一级知识点，各目标题量为 M1；若 M1>0，并且 R1>0，则这 K1个一级知识点仍均作为目标一级知识点，再在目标一级知识点中随机选择 R1个，各目标题量为 M1+1，剩下的目标一级知识点的目标题量均为M1。

②若步骤①中的“M1>0，并且 R1=0”或“M1>0，并且R1>0”成立，用步骤①中同样的策略逐级进行知识点均衡。

(2)当组卷人员指定知识点时，按以下策略实施：

①若组卷人员指定的知识点既有知识树中的叶子结点(设其数目为X)，又有非终端结点，则首先遍历考试科目对应的知识树，检索以这些非终端结点为根结点的子树对应的叶子结点的数目(设其总数目为Y)，设题型的题量为Q，然后求得Q相对于X+Y的倍数M：M=Q/(X+Y)。若M=0，则对于叶子结点构成的目标知识点，各目标题量为1，对于非终端结点，分配题量为 Q-X，再按(1)中策略进行均衡；若M>0，则对于叶子结点构成的目标知识点，各目标题量为M；对于非终端结点，分配题量为Q-M，再按(1)中策略进行均衡。

②若组卷人员指定的知识点全部为知识点树中的叶子结点，仍按(1)中策略进行均衡。

4.2 算法描述

经过知识点均衡之后，组卷控制参数中的考试科目、题型、题型的知识点(可选)、题型的题量4项已满足要求。为了最大限度地满足所有组卷控制参数的要求，在组卷过程中，各题型的选择顺序应按平均分值从大到小的顺序进行，优先选择试题平均分值高的题型。组卷的具体算法如下：

定义general_d表示试卷当前实际难度等级，初值赋为0；question_d表示当前选择的试题的难度等级；direct_d表示难度等级调节方向；定义general_s表示试卷当前的总分，初值赋为0；question_s表示当前选择的试题的分值；direct_s表示分值调节方向；定义 question_t表示当前选择的试题的估计用时；direct_t表示时间调节方向；各调节方向的调节规则均为：取1时表示向上调节，取0时表示向下调节，取-1时表示暂时不调节。

(1)对组卷人员提出的组卷要求进行合理性验证。

(2)确定各题型的选择顺序。对各种题型，比较它们组卷控制参数中的平均分值 (题型的分值分配/题型的题量)的大小，确定其大小顺序，该顺序即为各题型的选择顺序。

(3)进行知识点均衡。采用上文所述的知识点均衡策略实施，确定最终的各目标知识点及目标题量。

(4)按照组卷控制参数与确定的目标知识点及目标题量，从试题库未选择的试题中随机选题。定义各种题型的已选试题数组，每选择一道题，将其试题ID存入相应题型的已选试题数组中，并按以下方法修改或调整相关定义的参数的值[6]：

①难度系数调节方向direct_d的调整：

②分值调节方向direct_s的调整：

③时间调节方向 direct_t的调整：

(5)所有题型的试题选择完成之后，整体上对试卷的平均难度等级、总分和总时间进行核对及相应优化调整。通过反复地组卷试验发现，试卷的平均难度等级基本得到满足，需要进行微调的一般是总分及总时间。在保证试题其他属性不变的情况下，可以采用试题库中相应的试题替换试卷中个别试题的办法进行试卷优化调整。

(6)算法结束。

本文针对现有的基于知识点组卷方案存在的问题与不足，提出了一种改进的基于知识点均衡的智能组卷方案。通过多次试验，证明了该方案具有较高的有效性和鲁棒性。将该方案分别应用到学校针对在校学生的在线考试系统与企事业单位的在线考试系统中，知识点覆盖与分布合理，满足试卷平均难度等级、分值分配、时间分配等要求，取得了比较理想的效果。

[1]王友仁，张砦，施玉霞，等.题库系统智能成卷理论和组卷方法研究[J].电子科技大学学报，2006，35(3)：363-366.

[2]王雍钧，黄毓瑜.基于知识点题型分布和分值的智能组卷算法研究[J].计算机应用与软件，2004，21(8)：111-113.

[3]施岳定，张树有，项春.网络课程中知识点的表示与关联技术研究[J].浙江大学学报(工学版)，2003，37(5)：508-511.

[4]黄万艮.基于知识树的多媒体课件[J].中国教育信息化，2009(7)：56-58.

[5]林雪明，张钧良，蒋伟钢.基于知识点的试题库组卷算法的建立[J].微机发展，2001，11(2)：77-80.

[6]周文举.一种基于知识点的遗传算法组卷的改进应用[J].山东师范大学学报(自然科学版)，2006，21(3)：39-42.