Apriori算法在无纸化考试系统中的应用和改进

黄艺坤

传统的考试从古至今一直以“笔试”为主,考试过程都需要人工来完成各项工作.传统考试的出题、改卷、试卷管理、分数登记等环节不仅需要安排大量工作人员,还要花很多时间和劳务费,除此之外,考务工作也是考试过程中一项烦琐的工作.随着信息化发展,传统考试的形式出现了越来越多的问题,缺点显而易见,无纸化考试系统正是在这种环境下显得很有优势.

高校的无纸化考试系统对学校课程建设、题库建设都有着重要意义,通过无纸化考试系统数据的采集和功能设置,即可完成试卷组装.在试卷自动组装过程中,通常只考虑了知识点范围,无法顾及试题的难易程度,因此组卷后,试卷总体难度系数无法准确把握.本文通过对无纸化考试系统数据仓库进行分析,使用关联规则的Apriori算法进行研究和改进,在挖掘中通过删除无关集合突出高频集合使挖掘中快速找出有价值数据,使得组卷效率高,知识分布更科学,为高校教育与考试管理提供更好的服务.

1 数据挖掘技术

1.1 数据挖掘技术概述

数据挖掘是对数据仓库中的海量数据进行数据提取、分类、转换、分析和建模处理,提取出隐藏在数据中具有意义的信息和知识的过程.数据挖掘技术是当今数据库领域研究中一个新兴的领域,融合了数理统计、智能技术以及数据库等多方面知识.数据挖掘的三个主要步骤分别为数据准备、数据挖掘、结果表达与解释[1].数据准备可利用高性能的T-SQL语句在数据源中把需要挖掘的数据抽出形成新的数据集,系统对已提取的数据进行二次分析,如检查重复数据、拼写错误、补齐数据等等,最终形成符合数据挖掘需求的模式;数据挖掘的一个重要过程就是在数据库中发现有价值的信息,通过定义业务问题,使用一种挖掘算法进行数据处理的过程,最后对是否存在冗余或者存在无关信息等进行评估,数据挖掘结果最终使用的是客户,因此还要把结果转化为客户易懂方式.

1.2 Apriori算法

Apriori算法是一种数据挖掘关联规则[2]中的典型算法.该算法通过多次迭代来统计数据库中的频繁项集,通过频繁项集产生强关联规则.在生成频繁项集[3]时经常会对数据仓库进行频繁迭代操作,尤其在低维度频繁项集到高纬度项集时,会因频繁项集的维数高导致笛卡尔积后生成许多候选项集,导致查找效率低下.针对以上提出的问题,笔者对Apriori算法进行改进,最后将新的算法在无纸化考试系统中使用.

2 组卷方法

2.1 组卷策略

自动组卷功能是无纸化考试系统的核心功能,通过自动组卷程序要求系统生成科学性、随机性的试题.传统无纸化考试系统的组卷方式有以下两种,一是专业教师在系统后台选择相应科目的考试题型,根据考试范围选择相应的考试题目组成试卷,这种方式组卷对机器的压力比较小,但每位学生试卷题目都一样,学生作弊的可能性也比较大;另一种方式是考试时对题库试题进行自动抽取,通过事先设置的难易系数随机生成试卷,这种方式每个学生所做的试题可能都不一样,难以作弊,但对机器的负荷比较大.

每个学校无纸化考试系统的自动组卷形式都不一样,无论用哪种办法,最主要是如何研究出更科学、更高效的自动组卷方式.

2.2 Apriori在组卷中的应用

为了使试题在自动组卷中能够让知识点分布更加均衡、更加科学,笔者采用关联规则中的Apriori算法对考试系统数据仓库进行挖掘.首先在数据仓库中可把优等生都不得分和差等生都得分的题目放在频繁项集里,无纸化系统自动组卷之后把频繁项集作为一个评价标准,如频繁项集越多则该份试卷越差.挖掘工作中利用N-项集来生成(N+1)-项集,产生候选项集CN后,利用CN找频繁项集LN,以此类推直至找出所有的频繁项集[4],APRIORI常用算法如下:

(1)设置相应的最小支持度阈值Minimum_Threshold

(2)找出数据集中的高频集L1=FIND_FREQUENT_1-ITEMSETS(D)

(3)循环处理L-项目集对应的链表,并获得最大频繁项目集

FOR(N=2;LN-1≠Φ;N++)

{ CN=APRIORI_GEN(LN-1,Minimum_Threshold);

(4)FOR_EACH TRANSACTION Y∈D

CY=SUBSET(CN,Y);

FOR_EACH CANDIDATE c∈CY

c.COUNT++;}

(5)KN={c∈CN| c.COUNT＞=Minimum_Threshold}

}

(6)RETURN L=∪NLN;

2.3 Apriori算法改进

通过对Apriori算法进行研究比较,发现在CN候选项集查找频繁项集LN时,候选项集需要对数据库扫描N次,数据库越大扫描所用的时间也越大,机器所承受的压力也越大,显然随着无纸化系统数据的增加,该算法所表现出来的工作效率就越来越低.要解决以上问题的方法有两种,一是缩小需要扫描数据库的规模,二是候选项集在查找频繁项集LN时只扫描数据库中的部分数据.针对这些问题,笔者提出了Apriori算法改进.

系统后台在输入题库时,可根据试题基本信息对试题的难易系数进行初步评价,如把试题评价成一级、二级、三级,其中三级试题最难,那么搜索与优等生相关的频繁项集时只要在三级试题的数据库中搜索,搜索与差等生相关的频繁项集时只要在一级试题的数据库中搜索,这样就大大缩小搜索范围.另外,在生成频繁项集过程中,如果某项事务不包含N-项集,那么该事务也不可能包含任何频繁(N+1)-项集[5],把这样的事务找出来并删除即可缩小数据仓库大小.经过挖掘可以得知学生对知识点的掌握程度以及对试题的初步评价重新进行评价调整,这对教学质量把控以及质量评估有着重要意义.经过以上分析,文章对Apriori算法提出了改进设计,改进后的算法如下:

(1)设置相应的最小支持度阈值Minimum_Threshold

(2)在数据集DATASET中找出高频集N1=FIND_ONE_ITEM(DATASET);

(3)FOR(N=2;LN-1≠Φ;N++)

{CN=APRIORI_GEN(LN-1,Minimum_Threshold);

(4)FOR_EACH TRANSACTION Y∈D{

(5)FOR each(N-1)-SUBSET S OF C{

IF s∉LN-1Then

Delete Y;

}

(6)IF(|Y|＜N)THEN{

delete Y; }

CY=SUBSET(CK,Y);

}

(7)FOR_EACH CANDIDATE c∈MY

(8)m.Count+=GETSCORE(c,Y);

}

(9) NX={m∈MX| m.COUNT＞=Minimum_Threshold}

}

(10)RETURN N=∪XNX;

因任何频繁项集的全部非空子集也是频繁项集,非频繁项集的超集也是非频繁项集,同时支持频繁项集LN的任意一个事物也至少支持LN-1中的N个N-1项集[6].经过算法改进,当对数据仓库进行挖掘时,先确定挖掘数据范围和最小支持阈值,通过不断删除与生成频繁项集条件不符合的事务,使数据挖掘在迭代过程中逐渐减少迭代规模,从而减少了系统的负载.通过GETSCORE函数来获取数据的正确性并对高频集合数据进行加权,对不同的试卷类型给予系数校对,最终通过系数权加值来判断和获取目标试卷.

为了测试算法工作情况,笔者对某学校的无纸化考试系统数据库进行测试,测试工作在CPU为I3 3.4 GHz,内存4 G的Windows 7操作系统,配置了VC++和SQL2005的环境下进行,数据量共有6 600条数据,把数据分别分为1 500,3 000,4 500,6 000,7 500,使用DBminer2工具合成数据,设置事务平均长度为15,项集的平均长度为4,使用原来的Apriori算法和改进后的Apriori算法对数据进行测试,发现随着数据规模变大,改进后的算法执行效率不会大幅度降低,几乎呈线性增长(见图1).这体现了改进后的算法具有良好的稳定性.

3 结束语

本文针对现有Apriori算法的瓶颈问题进行分析,通过减少事务、压缩数据、缩减比较和迭代次数的方法从而增加了算法的运行效率.本文提出的算法除了使用在无纸化考试系统的组卷,还可以使用在对学生成绩进行分析和统计等其他方面.数据挖掘是一个新兴学科,通过多年的研究,目前也已经运用在各个领域.笔者的研究结论可以促进高校传统教学方法的改革,可以更科学地指导教学.

图1 Apriori算法改进前后效率对比图

参考文献:

[1]李亮.视频点播系统中的数据挖掘技术应用[D].江苏:扬州大学,2009.

[2]王月行,马垣,胡志宇.基于概念格的关联规则挖掘方法[J].计算机工程与设计,2009,30(22):5062-5064.

[3]张文静,马冬来,么炜.基于改进Apriori算法的决策推导过程[J].河北农业大学学报,2013,36(2):122-124.

[4]徐嘉莉,石琳,付平.改进的Apriori算法在基于J2EE架构的网络考试系统中的应用[J].成都大学学报:自然科学版,2007,26(03):254-256.

[5]刘兴涛,石冰,解英文.挖掘关联规则中Apriori算法的一种改进[J].山东大学学报:理学版,2008,43(11):67-71.

[6]陈安娜.Apriori优化算法在临床数据挖掘中的应用分析[J].长春师范学院学报,2013,32(02):45-48.