改进的APRIORI算法在试卷系统数据挖掘中的应用

黄艺坤

（福建师范大学协和学院 福建 350117）

0 引言

试卷系统有利于高校建立课程题库，现在各个高校都在倡导题库建设，通过试卷系统就可以把题库信息采集在数据库里，要查询历史题库只要打开后台就可以查到相关试卷，考试也只要通过自动组卷和随机排序组成相同难度，不同序列的题目给考生，避免了学生作弊。

很多试卷系统在自动组卷时，往往只考虑考试范围而忽略了考试难度，因此每次组卷时，试卷的难度很难把控。本文通过对Apriori算法进行改进，利用计算机容量大、计算速度快等优点，考虑各种因素和关联，实现数据分析和数据挖掘，通过改进，可以随机组成更科学、更有难度梯度的试卷，这样也有利于课程的建设和发展。

1 数据挖掘技术

1.1 数据挖掘技术概述

数据挖掘是对存在大量数据的数据仓库进行数据分析，通过分析找出数据与数据之间的关联关系，从而挖出更有价值的信息。数据准备、数据挖掘和结果表达与解释是数据挖掘的主要三个步骤。数据准备是把需要进行挖掘的数据从数据库中抽出，并整合成数据集；规律寻找是使用特定的算法把数据中存在的某种规律找出；规律表示是用用户看得懂的方法表示出数据之间的规律，这个规律即是有价值的线索。普遍认为数据挖掘是数据库中发现有价值信息的一个重要环节。它一般分为以下几个阶段：选择数据集、数据预处理、数据形式转变、实施数据挖掘以提取模式和关系、结果表达和解释。

1.2 Apriori算法

Apriori算法是一种数据挖掘关联规则中的典型算法。该算法在生成频繁项集时会有频繁的数据库扫描操作，并且在由低维频繁项集连接生成高维候选项集时，如果频繁项集维数过大，笛卡尔积后就会产生大量的候选项集，从而影响算法的效率。针对上述2个方面对Apriori算法进行改进，并将改进后的算法应用在试卷分析系统中。经过系统测试，改进后的算法具有较高的效率和较强的稳定性。

2 组卷方法

2.1 Apriori在组卷中的应用

为了使试题在自动抽取过程中能够使试题在知识点分布上更均衡、更广泛，同时使试题的难度系数有一定梯度抽取，本文采用数据挖掘中的关联规则法对数据进行挖掘分析，在分析中采用了改进型的Apriori算法，使挖掘效率更好，数据更准确。

在Apriori使用过程中，系统先对全局数据集进行检查，如在答题库中，把考生作答时同一章节的考题同时作对或同时做错的题型记录到高频集，如果优等生同时做错的题目和差等生同时做对的题目分别放在两个高频集里，在自动组卷之后，可以通过高频集来判断试卷的质量，同一份试卷里，高频集出现的越多，则试卷质量越差，这样在自动组卷过程中，可以利用高频集来评价。Aprior筛选高频集的方法是先把筛选出的高频集并记录在N1集合，再把N1作为参考集合对数据库进行挖掘，找出M2集合，再由M2产生N2，以此类推，直到找出所有的频繁项集，Apriori算法如下：

（1）设置相应的最小支持度阈值Minimum_Threshold

（2）在数据集 DATASET中找出高频集N1=FIND_ONE_ITEM（DATASET）；

（3）FOR（X =2；NX-1≠Φ；X＋＋）{

MX=APRIORI_GEN（NX-1，Minimum_Threshold）；

（4）FOR_EACH TRANSACTION Y∈D

{ MY=SUBSET（MX，Y）；

FOR_EACH CANDIDATE c∈MY

m.COUNT＋＋；}

（5）NX=｛m∈MX｜ m.COUNT>=Minimum_Threshold｝

}

（6）RETURN N=∪XNX；

2.2 改进Apriori算法

通过对Apriori算法进行研究，发现虽然该算法和其他算法比起来在查找最优解上具有很强的优势，但在实际操作中每次生成单个N集合都要对数据库进行循环筛查数据库一次，这样是会给服务器的运行带来压力，运行效率低等问题，针对以上问题，本文对Apriori算法进行了改良。

在数据挖掘中，我们还可以把差生（小于60分的考生）同时作对的题目或优等生（大于80分的考生）同时做错的题目作为高频集，记录为MK（K=1）或LK（K=1），通过把高频集M和L作为参考集使用改进型Apriori算法进行数据挖掘，可以分析出题库中，差生容易掌握的题型和优等生中不容易掌握的题型，这些题型对于数据分析中具有重要作用，通过挖掘出来的数据，我们可以重新对这些题型的难易系数加以评级，对学生能掌握的知识点和不能掌握的知识点进行总结分析，这对今后的教学质量评估具有重要意义.

针对Apriori算法存在的问题，本文提出了改良型Apriori算法，改良后对数据集进行遍历扫描时，去除一些非同源高频集，增强了挖掘效率。改良的算法还针对自动组卷组成的试卷进行优化，通过高频集筛选出优秀的试卷。经过改良后的算法如下：

（1）设置相应的最小支持度阈值Minimum_Threshold

（2）在数据集 DATASET中找出高频集N1=FIND_ONE_ITEM（DATASET）；

（3）FOR（X =2；NX-1≠Φ；X＋＋）{

MX=APRIORI_GEN（NX-1，Minimum_Threshold）；

（4）FOR_EACH TRANSACTION Y∈D{

MY=SUBSET（MX，Y）；

（5）IF GET_JUDGE（MY，"约束条件"）THEN

（6）{ DELETE MY；

Continue；}

（7）FOR_EACH CANDIDATE c∈MY

（8）m.Count+=GETSCORE（c，Y）；}

（9）NX=｛m∈MX｜ m.COUNT>=Minimum_Threshold｝}

（10）RETURN N=∪XNX；

改良后的Apriori算法在对数据集操作中，在挖掘数据时，删除非高频集数据即把不在约束条件范围内，不用再次查找的有效数据删除，不断减少数据量，挖掘的目标范围也逐渐缩小，服务器的运行速度变快。改良后的算法会把抽取的数据和高频集数据进行比较，通过 GETSCORE函数判断数据的吻合程度然后对高频集进行加权处理，不同的学校和不同的教学方案对此都有不同要求，如非很好`或很差的试卷返回分值1；优等卷中包含差生同时作对的试题，那么函数返回 0；优等卷中包含优等生同时做错的题目，那么函数返回 2；在劣等卷中含差等生同时作对的题目，那么函数返回 0；在劣等卷中含有优等生同时作错的题目，那么函数返回 1，以此类推，最后通过判断阈值来生成最优试卷。

3 结束语

本文研究了数据挖掘技术在试卷系统自动组卷中的应用。数据挖掘技术除了用在自动组卷上，还可以用在学生成绩分析上，由于难度系数的设置是由出题者设置的，考生所学知识点与试题所设置的难度系数不一定吻合，因此，本文还可以尝试使用数据挖掘的关联规则法，把考生答题库和题库两个数据表作为原始数据，对某道题考生在答题过程中对错概率进行挖掘分析，如某道题考生出现的错误率超过标准值那么教师就得知学生掌握知识点程度，在下次命题或者教学中就会做出相应的改变。

[1] 王金龙.全局和局部相结合的数据挖掘算法及应用研究[博士学位论文].浙江：浙江大学，2007.

[2] 黄玥.高校无纸化考试系统新探索.科技创新导报，2012，21：56.

[3] 薛乐，于建军.浅谈高校在线考试系统的设计与实现.科技资讯，2012，26：219.

[4] William J.Tastle.Data Mining Applications Using Artificial Adaptive Systems.Springer Science.2013.70-103.

[5] 吕健.试论计算机自动组卷的常用算法.电脑知识与技术，2011，08：1802-1803.