基于知识点与难度的组卷算法及应用

董晓璇， 叶建芳， 孙一萍

(东华大学 信息科学与技术学院， 上海 201620)

0 引言

作业训练与考试作为评测手段是教学过程中不可或缺的一环，而信息技术的快速发展使得基于Web在线作业与试卷生成系统成为计算机辅助教学中重要的组成部分[1]。该系统在一定程度上避免传统作业模式下普遍存在的作业抄袭现象；另一方面，克服任课老师命题的主观性。系统根据教学大纲要求，能够选择一个高效、科学、强壮的算法组卷是关键[2]。

目前常用的组卷算法有随机抽取法、回溯试探法与遗传算法。遗传算法具有全局寻优和收敛速度快的特点，但算法复杂、容易“早熟”[3]，而且当试题库比较大时，容易导致染色体编码过长，所花费的时间开销呈线性增长，同时对于小规模的试题库而言，有可能导致两次产生的试卷具有较高的试题重复率。

随机抽取法尽管结构简单，易于理解与实现，适合于小型的题库系统，在现有的大量考试系统中也有广泛应用，但是传统的随机抽取法是根据组卷状态空间的控制指标，随机抽取一道符合指标的试题，不断重复此过程。不难发现，该算法可能在证明已无法抽取合适试题的区域反复选题，进行大量无效操作，导致访问数据库过于频繁，从而增加组卷时间，甚至进入死循坏导致组卷失败[4]。在文献[5]中提出集合随机组卷算法，采用集合和题号预存的方法解决了反复回溯匹配问题，但是预存题号加大了空间的占用，对试题难度的控制较为粗略。文献[6]提出了试题难度和知识点覆盖控制算法，组卷效果较好，但在题量较小时试题重复率较高。文献[7]提出基于洗牌策略的随机抽取算法，不依赖于题型数量，即使题库数量增长，仍然可以达到很快的生成速度，但是对于试卷难度控制力不强。

基于上述问题，本文结合通信电路电子电路课程，采用php+MySQL开发设计了基于B/S的在线作业与试卷生成系统，并且提出了一种基于难度和知识点改进的随机组卷方法，实现快速、有效的组卷目标。

1 设计思想

自动组卷需要兼顾多方面的因素，以满足实际教学需求。一份好的作业能涵盖的知识点全、难度中等，而且尽量避免每位学生作业题目的重复性，有效抑制学生之间相互抄袭现象。考试组卷不仅要求考察内容全面，更注重难度合理，使学生的成绩接近于正态分布[8]。

为了解决传统随机算法存在的问题，考虑采用缩小搜寻的范围和生成不重复随机数序列的方法来解决。此外，在线作业与试卷生成系统具有学生根据教师要求生成作业的功能，为了防止作业的抄袭现象，引入洗牌策略在一定程度上避免不同学生之间作业重复的现象。在组卷时运用此策略可使试卷题目的排列顺序不同，从而降低作弊的可能性。

将题目的知识点和难易程度作为组卷过程中两个最为重要的因素，同时用洗牌策略控制试题出现频度，将试卷作为整体研究对象，组卷过程可表示为式(1)。

Pa=Q(z1(D，K，P，T)，z2(D，K，P，T)，…，zN(D，K，P，T)，Q2(D,K))

(1)

式(1)中，Pa表示组卷，Q表示成功组卷的所有动作，z1、z2等表示只考虑难度(D)、知识点(K)、频度(P)、题型(T)因素的组卷过程，Q2表示对某一题型的组卷进行知识点和难易的平衡，下标N表示章节数量或者章节中的小节数量。

1.1 题库参数设计

题库是选择组卷算法及能否实现高效组卷的关键因素，一个好的题库结构在一定程度上可以提高算法的执行效率。将整个题库按照不同的题型分为4个试题库表，分别为选择题、填空题、简答题、计算题，这样既可以缩小算法的搜索范围，也更加便于数据库的管理。

一份作业、试卷中包含了不同知识点、不同题型的若干试题，因此每个试题库包含了不同章节、难度的试题，按照“卷内分块”的思想[9]，每个试题库表S可表示为式(2)。

S=(s1,s2,…,sn)n=1,2，…

(2)

式(2)中，s1,…，sn表示试题，n表示试题数量。

试题库中的每个试题除了本身的题干、答案，还根据自动组卷的要求定义多种属性，每道试题sj属性可表示为式(3)。

sj=(IDj,Cj,Kj,Dj,mj,fj)

(3)

IDj表示试题的编号，是每个试题的唯一标示，Cj表示试题所属的章节，Kj表示这个试题所属的小节，Dj表示该试题的难度系数，mj表示难度等级，fj表示该试题的分值。其中试题的难度系数与难度等级关系，如图1所示。

难度等级12345难度系数0～0.20.2～0.40.4～0.60.6～0.80.8～1难度描述易较易中等较难难

1.2 知识点划分

考试是对课程涵盖所有知识点的考察，考卷中可依据章节区分知识点，作业是对一个章节知识点的检测，因此依据章节中每个小节区分具体的知识点。因为知识点是按照章节或者小节进行区分，所以知识点的优先级是相等的，不加以区分。

1.3 难度判断

该系统具有作业生成和组卷两大功能，作业生成的主要目标是检测学生知识掌握情况，对难度系数没有苛刻的要求，只要保持在某一范围内即可，作业的平均难度系数G表示为公式(4)。

(4)

考试的目的是衡量大多数学生的学习情况，对难度系数的要求较高，所以按照正态概率分布的思想来计算难度系数。不同难易等级将正态分布分隔成5块，其中“容易”和“难”所占的面积约为2.5%，“较易”与“较难”各占13.5%，“中等”占68%[10]，概率分布，如图2所示。

图2 难度等级概率分布图

在估计难易程度时按照统计学的均值思想，分别为5个等级赋予不同的估计系数，其系数如式(5)。

(5)

式(5)中，Ym表示第m等级的估计系数，Xk表示第k等级所占面积比例。计算得到图中从右往左估计系数为0.987，0.917，0.51，0.0925，0.012，难度系数计算如式(6)。

(6)

1.4 不重复随机数的产生

针对传统随机抽取法存在反复选取无效试题的问题，采用不重复随机序列产生算法，即将已被选中的试题号用最后一个有效的试题号覆盖，使得选题过程一直在能够抽取合适试题的范围内选择，具体步骤，如图3所示。

图3 不重复随机序列生成图

第一步，将根据条件遍历数据库后得到题号1-5存入数组，并使用洗牌算法打乱题号顺序如图3(a)、(b)；第二步，产生一个随机数2作为数组的下标，选取图3(b)中的试题号1，将该题号存入题号数组后，用数组中最后一个有效的题号4覆盖已选中的数组元素1，并且将产生随机数的范围减小1；第三步，重复第二步，直到产生的题号数量达到要求。这个算法的优点是不需要反复判断，也不会因为删除数组元素而执行大量移动操作，只是进行数组元素赋值操作，将算法的复杂度降低到O(n)。

2 算法实现

2.1 算法描述

本算法优先考虑出卷人的要求，在满足基本条件的情况下，通过式(4)、(5)分别对生成的作业和试卷进行难度系数计算，如果满足要求执行下一个模块的组题，否则进行难度均衡。以选择题为例，算法的具体步骤如下。

(1) 定义一个数组Y，存放出题人要求各题型的题量数，根据出卷人给出的要求获得所需要的选择题数量为Y[0]，选择题题库中题目所属的章节数共为nc或者章节中的小节数为nc，则需要处理的子集数为nc。为了保证覆盖所有的知识点，从每个集合中抽取的题目数N可以计算，如式(7)。

(7)

(2) 定义一个二维数组temp_i，用来存放经过数据库语句得到的每个知识点的试题题号与其对应的难度等级。首先获取各个章节的单选题数量，采用洗牌算法将顺序的题号进行打乱后存放到数组tihaolist_i。洗牌算法如下：

void Shuffle()

{

for(intm=length[temp_i];m>=1;m--)

{

DoSwap(tihaolist_i[i],tihaolist_i[rand()%(m+1)]);

}

}

(3) 题号重新排序后，采用不重复的随机数序列产生算法，用rand()函数产生第一个随机数，从tihaolist_i数组取出对应随机数下标的题号，存放到finallist数组，并将temp数组中被选中的题号与数组最后有效题号进行交换，然后将随机数产生范围减1，同时将所需的题目数减1，直到选到等数量的题。核心代码如下：

k=0;

for(j=n;j

{

finalist[k]=tihaolist_i[rand()%j];

k=k+1;

}

(4) 在finallist数组中选取选择题所需的题量Y[0]，同样采用不重复随机序列的产生方法，将最终结果存入exam数组。

(5) 在获取选择题所有的题号后，根据不同的情况，作业的组成采用式(4)进行难度系数计算，因为作业不需要精确地控制难度，所以只要难度系数维持在0.3-0.7之间即可；而试卷对于难度的要求较高，采用式(6)进行难度评测，如果难度系数与难度阈值之差的绝对值在0.05之间则跳转至步骤(8)，否则进行难度均衡。

(6) 如果难度系数低(高)于难度阈值，从与其相同知识点的temp_i数组中选择难度系数高(低)于难度阈值的题目，转至步骤(5)重新进行难度评测，直到难度符合用户要求，并将其题目存入exam数组，跳转至步骤(8)，如果执行3次难度均衡后仍达不到要求跳转到(7)。

(7) 输出提示，组卷失败。

(8) 将exam数组中试题号对应的题目显示到网页上，完成组卷，结束。

2.2 算法流程图

算法流程，如图4所示。

图4 算法流程图

3 算法应用及结果分析

3.1 实验条件

该系统基于《通信电子电路》课程采用PHP+Mysql进行开发，题库系统所包含的总题量约为500道。按照题型分为4张表，分别是选择题表、填空题表、简答题表以及计算题表4个表，共约500道题，在此题库下对算法生成作业和试卷两方面性能进行测试。

实验1：生成作业的要求为第七章节选择题2题，填空题2题，简答题1题，计算题2题，如图5所示。

实验2：组卷的要求选择题8题，填空题7题，简答题4题，计算题5题，难度系数为0.5，如图6所示。

根据出题人要求，在操作系统Windows 10，CPU为intel core i5，2G内存环境下测试，经过20次的实验，得到结果如表1、表2所示。

表1 组卷成功次数对比

表2 组卷耗时对比 (单位：s)

比较改进随机算法与传统随机算法下得到的作业生成结果，试题重复率结果，如表3所示。

图5 生成作业结果图

表3 试题重复率

3.2 结果与分析

1) 算法的组卷效率

从表1可以看到，改进随机组卷算法的组卷成功率较高。表2的数据表明，改进的随机算法组卷速度明显比传统的随机法组卷的速度快，对比作业生成与考卷，明显可以看到在题库较大的情况下，改进随机组卷算法的优势更加明显。所以采用不重复随机序列算法不仅组卷效率有很大的提高，并且组卷成功率也有所提升

2) 算法的有效性

从图5可以看到，根据出题人要求生成作业，其涵盖了第七章的知识点，没有重复的知识点，而且分布也较为合理。由表3可见，运用洗牌算法后，试题的重复率有所降低，使不同学生的作业有所区别。此外，在组卷时运用洗牌算法，可以达到试卷试题顺序不同的效果，从而在一定程度上避免学生作弊。

3) 算法复杂度分析

改进的随机组卷算法采用了洗牌算法和不重复随机序列生成算法，洗牌算法的复杂度为O(n)，虽然相对传统算法而言增加了复杂度，但是从一定程度上进行了试题频度控制。不重复随机序列生成算法的复杂度仅为O(n)，相对于一般的随机序列生成法，不用反复在无效的试题选取范围内选择，并且相对于采用删除试题号来避免的方式，大大减少了执行时间，而且复杂度上由O()降低到O(n)。

图6 部分组卷结果图

4 总结

在线作业与试卷生成系统的性能主要取决于组卷算法，性能优良的组卷算法不仅要确保成功组题，同时需要兼顾数据运算速度，即组题效率。传统随机算法，组题的成功率较低，而且在时间和空间上开销较大，更适合小型题库。本文针对传统随机算法的不足，采用不重复随机序列大大提高了组题的效率与成功率的同时，全面考虑知识点、难度控制，组题结果更加符合教学实际。此外，在改善了随机算法在较大题库情况下的性能。