（计算机软件与理论专业论文）基于网络知识资源语义化的电子试卷自动生成系统研究.pdf

皋十纠络知识资源语义化的i u 了试卷臼动生成系统研究 基于网络知识资源语义化的电子试卷自动生成系统研究 摘要 w e b 作为一个巨大的信息空间，已经成为人们获取学习资源的 重要途径之一。当前，w e b 上涌现的大量程序设计题库( 或称之为 在线答题系统，o n l i n e - j u d g e ) 为程序设计学习者带来了丰富的学 习资源。这些题库向初学者提供h t m l 形式的程序设计题，它们大 多要求做题者使用编程语言编写一个命令行的程序来解决问题。做 题者向答题系统提交这个程序的源代码时，题库会给出一个答题代 码正确性的判别。但是这些题库在提供初学者练习的时候，并没有 给予太多的学习指引只是告诉做题者答题代码是否正确，这样造成 很多初学者感觉在练习时无从入手。 究其原因可能有如下几点：1 ) 大部分题库没有针对知识点的 难度分析和对所用到的知识点的统计，初学者很难判断哪些题目适 合自己练习。2 ) 当初学者在做题过程中遇到困难时，题库无法提 供有效的提示。3 ) 网上题库虽然拥有丰富的题目资源，却没有提 供选题功能，程序设计课程教师或竞赛教练无法通过题库来方便地 选择所需要的训练题。 针对这些问题，本文通过把网上的题目资源语义化的方法，让 计算机把有难度的程序设计题分解成一些小题使初学者更容易上 皋f 删络知识资源语义化的l u 了试卷自动生成系统研究 手。同时，本文还通过大量实验数据和前人的理论得出了一种适合 于程序设计题的难度分析方法，并且开发了一个利用这种方法的基 于语义化的试卷自动生成系统。 本文的目标是研究出一种成熟的自动化程度高的程序设计出 题出卷系统，能够使出题者方便的对网上现存题目或原创题目进行 语义化，并且拆分成合适学习的小题，同时还能根据试题的难度来 自动的选题生成试卷。 本文的研究重点之一在于使用本体语言把网上的程序设计题 语义化，使之成为计算机可以理解并且根据一定规则能够自动或半 自动分解的题目。本文的另一项重要工作在于把本体语言描述的分 解后的题目转为能够被普通人所理解的自然语言描述，这里主要应 用了自然语言生成技术，使本体描述的题目内容能够直接生成自然 语言。除了分解题目，本文还论述了一种适合程序设计题的难度评 估系统，改进了传统的纸上试题试卷的难度评估用在程序设计领域 中的不足。通过这个评估系统，可以实现适合程序设计题的自动选 题和出卷。本文在最后部分给出了原型系统在多次校内程序设计训 练的实验结果，并对结果进行了一定的分析，验证本文所论述的理 论和系统的可行性与正确性。 本文的研究成果例如从本体生成自然语言和题目难度分析等 不仅能应用在本课题所论述的程序设计领域，通过一些改进还可以 用在很多其他领域，比如网上购物系统中的货物描述的自然语言生 皋十州络知识资源语义化的i 【l 了试卷自动生成系统研究 成等。说明了本课题所研究的方法具有一定程度上的通用性。 关键字：语义化，本体，自然语言生成，试题难度评估 皋f 网络知识资源语义化的l u 了试卷自动生成系统研究 e l e c t r o n i cp a p e ra u t o m a t i cg e n e r a t l 0 n s y s t e mb a s e do ns e m a n t i co n l 玳ek n o 、入几e d g e r e s o u r c e a b s t r a c t a sah u g ei n f o r m a t i o ns p a c e ，w e bh a sb e c o m ea ni m p o r t a n tw a y f o rp e o p l et oa c q u i r el e a r n i n gi n f o r m a t i o n n o w a d a y s ，t h e r ea r em a n y o n l i n e c o m p u t e rp r o g r a m m i n gp r o b l e ma r c h i v e s f o r b e g i n n e rt o t r a i n i n g t h e yu s u a l l yp r o v i d eah t m lf o r m a tp r o b l e m ，a n dn e e d p r o b l e ms o l v e rt ou s eac o m m a n d - l i n ep r o g r a mt os o l v ei t b u tw h e n b e g i n n e rc a nh a r d l yg e ta n yh e l pi n f o r m a t i o nw h e nh ec a n t s o l v e p r o b l e m s t h i sw i l lm a k et h eb e g i n n e rf e e lv e r yh a r dt og e ts t a r t t h e r ea r em a i n l yt h r e er e a s o n sf o rt h i sp h e n o m e n o n ：1 ) m o s to f p r o b l e ma r c h i v e sa r el a c ko fd i f f i c u l t ya n a l y s i sa n dk n o w l e d g es t a t i s t i c 2 ) w h e nab e g i n n e rc a n ts o l v eap r o b l e m ，h ec a n tg e tt h ea n yh i n to n t h a t3 ) c u r r e n to n l i n ep r o b l e ma r c h i v e sd o n th e l pu s e rt oc h o o s e p r o b l e m s of o rs o m eb e g i n n e r , t h e yd o n tw h i c hp r o b l e mi st h em o s t l o 果f m 络知识资源语义化的i u 了试卷臼动生成系统研究 s u i t a b l ef o rt h e m f o rt h e s er e a s o n s ，t h i st h e s i sd e s c r i b e saw a yt oc o n v e r tt h eo n l i n e p r o b l e m t ob es e m a n t i c ，s ot h a tc o m p u t e rc a nd i v i d et h eh a r dp r o b l e m t ob es m a l l e ra n de a s i e ro n e s a l s o t h i sp a p e rd e s c r i b e san e ww a yt o a n a l y z et h ed i f f i c u l t yo fc o m p u t e rp r o g r a m m i n gp r o b l e m sb a s e do n m a n ye x p e r i m e n t a ld a t a t h em a i nf o c u so ft h i st h e s i si so nh o wt om a k et h eo n l i n e c o m p u t e rp r o g r a m m i n gp r o b l e ms e m a n t i c ，s o t h a t t h e y c a nb e u n d e r s t a n db yc o m p u t e r a n dt h e nc o m p u t e rc a nd i v i d et h ep r o b l e mt o s o m es m a l l e ra n ds i m p l e rp r o b l e mb a s e do ns o m er u l e s m o r e o v e r , a f t e rt h ep r o b l e mi s d i v i d e d ，t h en e wp r o b l e m m u s th a v et h e d e s c r i p t i o nt h a tc a nb er e a db yh u m a nb e i n g s s oa n o t h e rw o r ko ft h i s t h e s i si st oc o n v e r tt h ep r o b l e mi ns e m a n t i cf o r m a tt on a t u r el a n g u a g e d e s c r i p t i o n t h em a i nt e c h n o l o g yt h a t t h i st h e s i su s e dt og e n e r a t e n a t u r el a n g u a g ei st h en a t u r el a n g u a g eg e n e r a t i o n ( n l g ) b e s i d e s p r o b l e md i v i d i n g ，t h i st h e s i sa l s od e s c r i b e sam e t h o dt oa n a l y z et h e d i f f i c u l t yo fs i n g l ep r o b l e m s ot h a tc o m p u t e rc a nc o m b i n es u i t a b l e p r o b l e mf o rb e g i n n e r t h i ss y s t e mh a sb e e nu s e do no u ru n i v e r s i t y p r o g r a m m i n gt r a i n i n gm a n yt i m e s t h er e s u l tp r o v e st h a tt h ef e a s i b i l i t y a n dc o r r e c t n e s so ft h i st h e s i s t h er e s u l to ft h i st h e s i s ，f o re x a m p l en a t u r el a n g u a g eg e n e r a t i o n 壮十嗍络知识资源语义化的l 【l 了试卷自动牛成系统研究 a n d d i f f i c u l t y o fp r o b l e m ，n o t o n l y c a nb eu s e di nc o m p u t e r p r o g r a m m i n gd o m a i nb u ta l s oc a nb eu s e di no t h e rd o m a i na f t e rs o m e c h a n g i n g f o re x a m p l e ，t h en a t u r el a n g u a g eg e n e r a t i o nc a nb eu s e di n o nl i n es h o p p i n gs y s t e m s ot h er e s u l to ft h i st h e s i si sg e n e r a li nc e r t a i n d e g r e e k e yw o r d s ： s e m a n t i c ，o n t o l o g y , n a t u r el a n g u a g eg e n e r a t i o n ， p r o b l e md i f f i c u l t ya n a l y s i s 1 2 皋十网络知识资源语义化的也了试：卷臼动生成系统研究 _ _ _ _ _ _ - _ _ _ - _ _ - - _ _ _ _ _ _ _ _ - - _ _ _ - _ _ _ _ _ - - _ _ _ - _ 一 i i - j l l - lo - l l io ll _ - _ _ - _ - 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是 本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和 引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及 成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声 明的法律结果由本人承担。 吼鬻矿 日期：砂留年弓月1 日 桀十网络知识资源语义化的i 乜了试卷自动生成系统研究 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借 阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密口。 学位论文作者虢种 隅伽弓月 日 指导教师签名： 鞠蓼 只期：协矽3 年雩月譬日 皋十m 络知识资源语义化的i 【i 了试卷自动生成系统研究 第一章绪论 1 1 研究意义和背景 1 1 1 引言 2 0 0 9 年将由我校承办a c m 国际大学生程序设计竞赛( a c m i c p c ) 亚洲 预赛上海赛区竞赛，这是我校以及学院向国内外同行展示学术科研水平的绝好 机会。而这次竞赛能否成功举办的关键之一是网上竞赛平台的建设。此外，随 着国内外程序设计水平的不断提高，设计一套先进的训练环境来大幅提高我校 程序设计水平，争取在承办这次竞赛前再次冲入a c m 国际大学生程序设计竞 赛世界总决赛，并在总决赛上取得好成绩。根据以上的需求，当前需要设计和 实现一个基于先进技术的程序设计训练与竞赛平台【l 】。因此本文论述了一个基 于网络资源语义化的试卷自动生成系统，作为程序设计训练与竞赛平台的题目 和试卷来源。本文的作者和这个系统的开发团队都是在国际程序设计竞赛上屡 次获奖的选手，并且退役后担任校程序设计竞赛的助理教练，这个系统的许多 实验数据都是经过多次国际国内比赛获得的第一手资料，此外本文还参考了国 内外其它专家在这个领域的研究成果，结合自己的实验数据，提出了一些适合 程序设计题目的选题和难度评定方法。 1 1 2 网上程序设计题库 如同传统的考试，在程序设计竞赛训练中，做题是关键环节之一，一套高 质量的训练试题对程序设计训i 练有极大的帮助。而程序设计学习的过程中，做 题也是提高水平的有效途径。但是本文所说的题目和传统的笔试的题目不同， 是提出一个实际问题然后让做题者用一个命令行程序来解决问题，比如最简单 的程序设计题是a + b ，也就是要求做题者编写程序读入两个数，把这两个数 相加的结果输出。而网上题库中比较著名的是西班牙v a ll a d o li d 大学的u v a ， 1 6 耩十网络知识资源语义化的l u 了试卷( j 动生成系统研究 其网址是：b 羔主巳；么么垒堡：望! 垒：笪。在这个题库中截止本文成文时有2 2 5 3 道题目， 有6 9 1 9 7 位来自全世界各地的程序设计爱好者使用这个题库，其题目数和用户 数还在不断的增加。类似的题库网站还有不少比如北京大学的p k u o n li n e j u d g e ，浙江大学的z j uo n li n e j u d g e ，这些题库上的题目是程序设 计训练和学习的丰富资源。而从程序设计题的本质来说，它是一种知识资源， 因为题目本身是知识的载体，每一道题目都是训练程序设计中的某几项知识。 哪怕是最简单的程序设计题，比如上文所提到的a + b 都会有知识。a + b 用到的知识如下： 1 ) 整数的定义。 2 ) 输入语句。 3 ) 加法运算。 4 ) 输出语句。 以上这些都是概念级知识点( 概念级知识点是指和编程语言无关的，抽象级别 上的知识点，相对应的是语言级知识点) ，还未涉及到具体的编程语言，如果 涉及到具体编程语言，比如c + + 或j a v a ，就能列出更多的知识点。出此可以把 题目中蕴含的知识总结成一个个的知识点，如上文中a + b 就可以得出4 个 概念级的知识点，如何采集和整理知识点将在下文中详细论述。此外，本文所 论述的试卷也并非传统的纸上试卷，而是一种电子试卷。电子试卷的内容是上 文所提到的程序设计试题的集合，而电子试卷的格式是以能够和计算机交互的 文件形式存储的，比如x m l 。而本文下面所提到的试题和试卷都是指代用来存 储程序设计试题的电子试题和试卷。 如上文所述，网上有丰富的题库资源，那么利用网上的题库资源进行程序 设计训练是一个简单高效的方法，因为网上的题目量大而丰富，并且覆盖的知 识点广泛。但是在如此丰富的题目资源中，如何选择合适的题目来进行训练是 每个程序设计竞赛教练和教师所面临的问题。 1 1 3 传统试卷生成方法的不足 无论是程序设计竞赛还是训练，其题目以及整体试卷质量的高低直接关系 桀二州络欠u 识资源语义化的i 【l 了试卷白动生成系统研究 到竞赛成功与否和训练是否达到效果。以往出题出卷工作基本都是由出题者人 工完成的，一般出卷方式有两种，一种是程序设计竞赛用的试卷，由程序设计 方面的专家为这场比赛专门原创的题目组成，但是由于出题者的背景知识的偏 向和对参加竞赛或训练选手的水平估计不充分，往往有可能使题目的难度过难 或过易，或者试卷整体所用知识点偏向性严重而影响了竞赛的公j 下性和训练的 效果；另一种是平时训练以及每月的月赛使用的试卷，这种试卷由于需求数量 比较大，每次都采用原创的试题，显然工作量很大也很困难，因此常规训练以 及月赛需要从网上现有的题库中抽取一定的题目来比赛。每次程序设计竞赛训 练都会有一定针对性和目的，比如某次训练需要集中训练动态规划算法。当前 大多数训练的选题工作都是由教练根据这次训练的目的来手动选题，这样的选 题出卷方式，给出题者带来很大的不便，他必须从网上数以千计的题目中选择 合适的有针对性的题目，这样工作量很大，而且出的试卷带有很大的主观性。 综上所述，需要一套科学合理并且最好自动化的选题系统来使程序设计竞赛训 练和选题更加科学和高效。 但是现有的传统纸上试卷的自动选题方法如果用到程序设计题上来也是 不合适的，包括一些现存的在计算机考试中的选题和出卷方法【2 】也很难直接 适用于程序设计竞赛选题和出卷。程序设计试题有自己的特点，主要体现在题 型和难度的评估上。程序设计题作为大题的形式，每次竞赛或考试只有6 1 0 道题，但是必须全部答对测试数据才能给分，而不像传统考试中的大题，答对 部分便能得分。这里答对所有意思是：程序设计题的解题程序输入题目的输入 测试数据后，输出的结果必须完全和题目给出的标准输出数据一致，这就类似 软件测试中的黑盒测试方法( b l a c kb o xt e s t i n g ) 【3 1 。比如a + b 这题，题 目给出的输入测试数据可以如图1 1 所示。 图1 1a + b 的输入数据 图1 1 中有3 组测试数据，每组一行包括两个数字。要求解题程序能够把上面 皋f 嘲络知识资源语义化的i u 了试卷自动生成系统研究 3 组数据中的2 个数字相加的结果输出，而标准输出数据可以如图1 2 所示。 图1 2 a + b 的输出数据 如果解题程序的输出如图1 2 ，则得到这题的分数。否则，如果解题程序由于 整型溢出问题把第3 组数据算错了，则这题将不得分而不是传统题目中的答对 三分之一数据而得三分之一的分数。 这样在选题出卷中必须尤其谨慎并采用合适的方法，如果使用传统的难度 评估和选题方法很有可能让做题者“颗粒无收”。这部分内容将在第5 章中会 有详细论述。 另外，大多数现存的程序设计竞赛的练习卷中，题目和题目l 日j 是没有联系 的，也就是说如果做题者做不出某题的话，换一题就相当于另起炉灶重新读题 做题。如果能够在生成的一张练习卷中所有的题目都有一定的联系，而且这种 联系能够帮助做题者解题和学习的话，就能让练习卷起到引导做题者的作用。 当作题者某题做不出的时候，可以在其它题目上得到提示进而做出自己本来做 不出的题目同时学到知识，以达到更好的学习效果。 1 1 4 电子试卷自动生成的应用背景 如上文所述，需要进行题目问有联系的试卷生成，那一种比较直接的方法 便是选用现有题库中的部分本身就有联系题目进行生成。这里说的联系主要可 以有两种关系：一种联系是题目之间解法相似；另一种联系是个问题是另一 个问题的子问题。前一种联系是横肉联系，也就是做题者通过另一道比较简单 的题目来学习一种解题方法，然后解决当前比较难的问题。而后一种联系是用 来引导做题者先解决子问题后再解决总的问题。对于第一种联系，从题库中寻 找相似解法的题目，只要计算机能理解题目的主要解法和知识点并且能够判别 难度即可实现，然而这种方法的缺陷在于题库中并不定有合适知识点和难度 的题目。但是第二种联系在题库中寻找就更加困难了，因为一道程序设计题可 1 9 雉于纠络戈u 识资源语义化的i 匕了试卷自动生成系统研究 能包含很多子问题，要寻找到包含这些子问题并且不包含其它问题的题目( 因 为有其它问题的话，可能会增加做题者的难度) 。除非题库内题目有一定数量 的题目，否则这很难做到。因此，如果能用一定的方法把道题分解成一些单独 的子问题，这样就可以生成符合要求的试卷了。但是要完全实现分解任何题目 有一定的难度，因此本文会就一些特定的子问题研究一些比较实用的方法来分 解题目。除了分解试题以外，本文还将介绍一种方法来进行试卷组合以适应练 习，竞赛和考试的需求。 1 2 研究问题及解决方法 1 2 1 网络知识资源的语义化研究 从上文的论述可以看出，电子试卷自动生成的主要问题有三个：题目内容 的计算机可理解表示方法，拆分题目和题目的生成，以及组合试卷的方法。首 先，题目内容如果能用计算机可理解的方式来表示的话，就能自动根据题目的 内容来抽取和组合成试卷，这个就是题目的语义化。其次，拆分方法主要需要 解决的内容是如何拆分题目，拆题的依据是什么，然后又以什么方法来组合成 试卷。最后，题目的生成问题主要在于题目拆分后的内容如何自动生成人们可 理解的题目描述。 对于第一个问题，本文的方法是采用语义化【4 】的方法来把题目转化为计算 机可理解的表示形式。由于程序设计题语义化后，将会部署在网上以语义题库 的形式发布，因此本文根据当前流行的语义网的标准，把程序设计题以本体 ( o n t o l o g y ) 【5 】的形式来表现，以提高题目的兼容性和可扩展性。 对于第二个问题主要解决方法是知识词典和方法库，这两个系统是本课题 组的另外两个项目的工作，下一节将对它们做一个简单介绍。同时本文还提出 了一种方法来进行试题自动挑选并生成各种目的的试卷。 对于第三个问题，主要解决方法是自然语言的生成法( n l g ) 1 6 】也就是在 有基于语义化的拆分方法后，再从本体的实例利用n l g 的部分理论来自动生 成合适的自然语言描述。这旱需要说明的是，一道程序设计题一般包括自然语 2 0 皋于网络知识资源语义化的i u 了试卷自动生成系统研究 言描述的题目描述，输入输出描述。用来给做题者说明题目的内容以及题目的 输入格式如何。比如上文例子中的a + b 这题，1 1 3 节中给出了他的输入 输出形式，那么在题目的输入输出描述中将会有类似以下的文字来给做题者说 明，如图1 3 所示。 图1 - 3 a + b 的输入输出描述 有了如图1 3 的输入输出描述，做题者才能写出解题程序的输入输出部分。 而分解后生成的新题目也必须有这些自然语言的输入输出描述，因此需要有一 种方法来自动生成新题目的自然语言输入输出描述。 l 。2 2 电子试题和试卷之问的关系 首先，试卷是由试题组成的，也就是 兑试题是生成试卷的基础。试卷的内 容就是以试题组成的，试题的质量和难度高低完全取决于各个试题的质量与难 度。因此本系统首先需要解决的便是试题的问题，也就是试题的分解，以及分 解出的题目的自动生成，l ，2 3 节将论述这个问题。 其次，试题的选择是由试卷的总体目标决定的，也就是说在出卷时，一般 都是先制定试卷的目标，然后决定难度等，也就是根据出卷的目标来选择题目。 也就是说，试题和试卷的关系是相辅相成的题库的知识点决定了试卷的选择范 围，而试卷则根据自己的要求从题库中选择合适的题目，因此本文前半部分将 论述有关试题生成的内容，后半部分将论述试卷的生成以及题目难度评论的问 题。 堆十州络知识资源语义化的i u 了试卷自动生成系统研究 1 2 3 利用知识词典的电子试题分解 电子试题的分解其关键在于如何让计算机理解题目，当计算机可以理解题 目后，就能利用一定的方法进行自动或半自动的分解了。而如何让题目被计算 机所理解的过程即是语义化的过程【4 】。知识点是语义化的核心问题，语义化的 主要目的就是赋予题目以知识点，同时这些知识点又是计算机可理解的。如何 使知识点被计算机理解，这是本课题组另一个项目知识词典的工作。这个知识 词典完成后，将会包含一个相对完整的知识点体系，这些知识点之间存在各种 各样的联系，并且以本体模型【7 】来描述，使之能被计算机所理解。有了这样一 个知识词典后，本系统的主要工作就在于如何赋予题目以知识点。主要是如何 从现有的网上题库的题目中提取知识点，当得到了题目的知识点后，便可以利 用知识词典建立这些知识点之间的联系，并赋予题目以知识点。于是题目语义 化的主要部分知识点便有了，接下来就是对题目的输入输出进行语义的描述。 出于分解题目不单单是把题目的知识点分解出来，而且分解出来的题目必须由 自己的测试数据，输入输出和题目描述，这样才能成为一道完整的题目，否则 光有知识点的堆砌并不能成为题目。因此，如何把分解出来的知识点整合成新 的题目是分解题目的难点之一。本文根据程序设计题的输入输出特点，建立了 输入输出各个元素之间的关系的语义化描述，于是计算机也能形式化的理解题 目的输入输出格式，并进行格式的自然语言生成，这样分解出来的题目输入输 出描述有了。此外，对建立了输入输出各个元素之间的关系的语义化描述后， 还能让计算机理解测试数据，并根据一定规则分解原题的测试数据并整合到新 题目中去。本文第3 章将集中讲述如何采集题目的知识点，第4 章将讨论输入 输出的描述结构以及生成自然语言的方法。 1 2 4 电子试题的自动生成 如1 2 2 节所论述的试题的自动生成中，所要解决的主要问题是如何使分 解后的新题目生成人可读的自然语言描述。这里采用的主要方法是：建立输入 输出各个元素之问的关系的语义化描述后，把以语义化的描述通过一定的方 攘十网络欠u 识资源语义化的i u 了试卷白动生成系统研究 法，转换成自然语言的题目输入输出描述。在本文所论述的原型系统中，语义 化描述主要采用w 曲本体语言( w 曲o n t o l o g yl a n g u a g e ，o w l s 1 ) 的形式。 自然语言生成技术主要有两种实现方法【9 】，一种是基于模板的生成，另一 种是基于规则分析的生成。其中基于模板的生成实现简单效率高，但它不能生 成非常复杂的文本。基于规则分析的生成实现起来比较复杂效率低，但是它可 以生成比较丰富的语意。本系统生成的信息主要由2 部分组成，一部分是本体 中的实例信息，主要是本体的实例及其关系，出于本体的复杂性，很难使用模 板来描述，因此使用规则分析的方法来生成。而另一部份是文档的上下文信息， 主要是有关输入输出内容基础信息的介绍，他们结构简单有章可循，因此可以 使用基于模板的生成。本系统以程序设计题目的输入输出o w l 实例描述作为 输入。因此，在进行单个实例的自然语言生成时，使用规则分析的方法来生成。 在总体的文档生成时，使用基于模板的上下文生成规则，最后生成自然语言的 描述。 1 2 5 个性化选题服务 无法给初学者提供个性化的选题服务也是各种现存网上题库所存在的问 题，但是这个问题并不是本文研究的范围，本课题组另一个子项目：个人知识 档案库会解决这个问题。而本系统有一个重要的功能就是提供给个人知识档案 子系统以个性化选题的服务。个性化选题是指对于拥有不同的知识背景的做题 者提供给他不同的题目，以做到个性化的教学。个人知识档案子系统将会给本 出卷系统提供一个做题者的需要练习的知识点集合，然后本系统将根据这个集 合推荐合适其学习的题目，并把题目根据难易程度编成一个题目序列提供给做 题者以供其练习。有关个性化选题方法的内容将在下面第五章中介绍。 1 2 6 电子试卷的自动生成 如前文所述，本系统能够提供自动语义化和分解试题，但是试题最终要以 试卷的形式提供给做题者。因此，除了能够生成题目以外，本系统的主要功能 攮寸二叫络知识资源语义化的l 【i 了试卷自动生成系统t 0 d f 就是选题和生成试卷。从知识点来看，它描述了一道题目内部知识的结构与联 系，因此用来分解题目是很合适的。而选题和生成试卷则需要用到不同题目之 间的联系，因此必须使用方法库，方法库是本项目组另一个子项目的内容。方 法库的作用在于找出题目或题目的一种解题方法之间的联系，以及他们的相似 度。这样就能把题库中的所有题目之间的联系组成一张图，根据这张图上的联 系试卷生成系统依照一定的方法以及题目的难度系数，把所需要的题目使用广 度优先搜索【3 5 】后其他方法找到并组成试卷，。本文将结合以及改进传统的选题 出卷方法，并根据程序设计题本身的特点和知识点分析得出一种适宜于程序设 计题的难度评判方法。这部分内容将在第五章详细论述。 试卷自动生成系统已在我校a c m 协会活动中多次使用并得到了一定的效 果和非常有用的实验数据，给系统的改进提供了极大的帮助。并且也对系统的 可行性作了一个有效的评估，在大多数情况下，题目的拆分非常有用，但是有 一小部分题目其拆分方法仍然有待改进。总体来说，这套系统将对初学者学习 程序设计有极大的帮助，而对于程序设计训练来说也能在一定程度上减轻教练 选题的负担。 1 3 论文主要工作 研究本体论以及语义w e b 的相关知识。学习和探索语义化和本体的建 模方法。 使用本体来描述程序设计题所包含的知识点之间的联系以及电子试卷 所需的语义信息，提出了一种题目知识点的采集方法。 采用本体描述语言o w l 描述程序设计题的输入输出描述的模型，使该 模型能够让计算机理解。 基于知识库进行试题分解的研究，并研究出一些通用的方法来分解某些 特定的子问题。 对于分解出来的基于本体描述的试题实现自动生成其自然语言的描述， 并研究从试题描述本体生成自然语言的方法。 制作试卷自动生成器和出题器的人机交互平台，并使其能表达丰富的语 2 4 ) ) ) ) ) ) l 2 3 4 5 6ll，l，kl 幕于网络知识资源语义化的i u 了试卷臼动生成系统研究 义信息。 ( 7 )与程序设计训练与竞赛平台整合，并实现每次月赛的试卷自动生成。 1 4 论文的组织结构 本文分七个章节，前两章是介绍性的章节，主要对本文的技术路线以及所 论述的系统进行一个概述，第三、四、五章节是根据分解的步骤来详细论述题 目分解的过程，第六章主要是实验结果和实例，第七章是结束语。 有关三、四、五章的排列顺序可用图1 4 来表示。 图1 4 文章章节内容概括 如图1 4 所示，本系统分解题目和组成试卷的过程一共分3 步，可以概括 为语义化及分解，分解后的题目描述生成，分解后题目重组成试卷。而三，四， 五章的内容则分别对应这三部分。其中题目描述的语义化和描述的自然语言生 成联系非常紧密，因此放在第四章中论述。 1 5 本章小结 本章主要对论文进行一个概述，把论文的主要工作以及研究路线作了一个 简要的说明，为下文进一步详细论述打基础。 桀十川络知识资源语义化的l u 了试卷臼动生成系统研究 第二章相关技术及其研究与应用 2 1 当前网上知识资源及其语义化 在本文标题中所提到的网络知识资源o 】是网上题库资源，虽然题库中的题 目本身并不直接向人们传授知识，但是每道题目都会考察一定的程序设计知 识，而做题者做题的目的也是练习或学习相应的知识。因此题目归根到底也是 知识的集合，只不过其形式和一些直接教授知识点的资源如网上的学习资料有 所不同。因此题库中的题目也是一种知识资源的一种表现形式，但是这罩的知 识资源并没有语义化而是使用的h t m l 的形式，也就是其内容无法被计算机所 理解只是对人可读，而本文的主要工作之一便是把这些知识语义化。 当今网上这样的资源非常之丰富，仅仅是u v a 题库，截止本文成文时， 这个题库中共有2 2 5 3 道题目，而且这个题库还是动态更新的，不断有新的题 目加入。但是多次比赛干n i ) l l 练的实验数据显示，这个题库的题目仍然有一定的 难度。对于初学者来说并不适合。因此，本文所要丌发的系统虽然目标是能够 把网上题库的大部分题目进行有效的语义化，但是第一步的原型系统将以另一 个更为适合初学者的题库为例。经过整理后，题库中共有8 l 道题目，同时这 些题目所用到的知识点已经建立了一个知识词典。本文利用知识库对题库进行 语义化，使这些知识资源从只能人可读变为计算机可理解。 2 2 语义网和o w l 语言 当今信息化时代，互联网已经越来越成为人们生活的重要部分之一。现在 互联网上的主要信息都是提供给人阅读的，而在下一代互联网一一语义网 ( s e m a n t i c w e b ) 1 1 】中互联网上的信息不但能给人阅读，还可以提供给计算机 理解。语义网的方法是研究开发能够将信息表现成计算机可以处理的形式的语 言【4 】。这晕最常用的语言就是o w l ，w e b 本体语言o w l ( w e bo n t o l o g y l a n g u a g e ) 是w 3 c 1 2 1 推荐的本体描述语言，由d a m l 1 3 1 和o i l 1 4 1 所结合演变 2 6 皋十网络知识资源语义化的i u 了试卷自动生成系统研究 而来，是用束定义和实例化本体的。o w l ( w e bo n t o l o g yl a n g u a g e ) 适用的 应用中，不仅仅需要提供给用户可读的文档内容，而且希望能够处理文档的内 容信息。o w l 能够被用于清晰地表达词汇表中的词条( t e r m ) 的含义以及这 些词条之间的关系【1 5 】。而这种对词条和它们之间的关系的表达就称作本体 ( o n t o l o g y ) 。o w l 相对x m l 、r d f 和r d f s c h e m a 拥有更多的机制来表达 语义，从而o w l 超越了x m l 、r d f 和r d f s c h e m a 仅仅能够表达网上机器 可读的文档内容的能力。【1 6 j 但是在语义网的发展过程中伴随产生了一个问题：给人阅读的信息和给计 算机理解的信息其中可能存在不一致的问题。举例来泌，对于计算机理解，比 较重要的一点就是对于程序输入的定义，然而在人所理解的程序输入定义如何 和计算机的理解不一致的话，就会导致程序输入有问题。比如计算机理解的输 入数据应该是个整数，而用户在说明中看到的却是英文字母，那么很有可能程 序便无法运行。 对于普通人来说，由于o w l 专为计算机理解所设计的，因此它并不便于 普通人理解。对于这个问题，当前还没有太多的办法来解决，主要难点在于自 然语言的理解1 7 】。因此，当前语义网络的学者们试图通过其他方法来建立计 算机可理解的本体与自然语言之间的桥梁。其中研究得比较多的一种方法是语 义注释( a n n o t a t i o n ) i s 】。例如，b e n j a m i n s 等人在2 0 0 5 年论述了一种半自动 的文档语义注释工具来连接自然语言的文档和本体【1 9 1 ，而h e n r i k 在2 0 0 7 年研 究出了一种基于p d f 的比较先进的语义注释方法【1 7 1 。但是在大多数语义的方 法中，文档的来源是人写的文本，因此，它很难保持动态更新，比如本体做了 改动后无法自动的更新文本。同时，对于一个现有本体的新个体( i n d i v i d u a l ) 每次都要重新撰写自然语言的文档也是非常耗时的。为了克服这些缺点，需要 一种从本体自动转化为自然语言文档的方法。当前还没有一种通用的方法来完 全解决这个问题，但是有一些学者在特定领域中对这个方面有不少研究成果， 比如m i a k t 2 0 1 ，t a l k i n go w l 2 1 】等等。他们的原理很相近，能够基于一个现 存本体的个体( i n d i v i d u a l ) 生成自然语言的报告。但是这些方法用在本文的 系统中并不完全合适，因此需要对之进行改进。 2 7 皋十网络则识资源语义化的i u 了试卷自动生成系统研究 2 3 自然语言生成分析 自然语言生成( n a t u r a ll a n g u a g eg e n e r a t i o n ，n l g ) 是从一种具有意义的表 示( m e a n i n gr e p r e s e n t a t i o n ) 中生成文本【7 1 。它是人工智能和计算机语言学的 交叉领域，它主要用来使计算机能够产生人类可读的自然语言文本。一般来说， 自然语言生成系统以一种非自然语言的具有意义的表示作为输入，然后系统根 据语法规则以及这个系统的应用背景和领域知识来自动得生成文档，报告，帮 助信息等。自然语言生成是当前受到广泛关注和应用的领域，它给人工智能和 人机交互学带来了新的课题。从长远来看，自然语言生成将在人机交互中扮演 重要角色并在不久的将来使计算机能够在交流方面更加智能化。【4 l 当前，已经有大量的能够实用的自然语言生成系统，比如参考文献f 2 2 】中 的基于模板的e m a i l 答复系统，这样的系统已经在w e b 中得到越来越广泛的 应用了。虽然由于用词和语言的不同，本体描述语言和自然语言的用词又很大 的差别【2 3 1 。而随着自然语言生成技术的发展，在一定的领域中从本体语言直 接生成自然语言的文档成为了可能。在参考文献 2 4 】中，对网上的现存本体进 行了一个统计，得出了本体可以作为自然语言生成资源的结论。而当前大多数 自然语言生成系统都是基于一定的应用领域的【2 5 】，这样可以给生成的自然语 言带来一定的限制，方便建立领域词典。 本文在一些其他学者的研究基础上，通过总结和改进，提出了一种适合于 程序设计输入输出描述的从本体生成自然语言的方法，并且把这种方法应用到 一个基于这个本体的有关描述命令行程序输入输出的系统中，也就是前文所提 到的本文的实验系统程序设计试卷自动生成系统中的试题描述生成部分。 由于程序设计基础的题目都是基于命令行的程序，而本系统的目的就是为这些 程序自动生成符合其实际情况的输入和输出描述。因为训练用题的数量比较巨 大，如果由人手工来写程序的输入输出很花时问，更重要的是由于人手工写的 文本很有可能会产生与计算机所理解的输入输出格式有不一致性，因此，自动 生成符合其实际情况的输入和输出描述在题目生成这部分中是一项很重要的 工作。 皋十列络知识资源语义化的i 【l 了试卷自动生成系统研究 2 4 知识词典与方法库 如第一章所论述的，知识词典与方法库是本系统所依赖的两大组件，他们 分别提供了题目的知识和方法上的支持，下面将分两节论述他们的在本文所论 述的系统中的主要作用。 2 4 1 知识词典 图灵奖( t u r i n g a w a r d ) 获得者e d w a r df e i g e n b a u m 曾在他的得奖演说一 一“h o wt h ew h a tb e c o m e sh o w ” 2 6 】中指出了软件开发过程中的关键问题之一， 即软件开发中，缺少的并不是技术，而是领域知识( d o m a i nk n o w l e d g e ) 。而 本文所论述的试卷自动生成系统中的领域知识的来源正是基于程序设计基础 知识的知识词典。 知识词典并不是一个静态的只提供查询功能的知识点数据库，而是能够根 据外部的需求提供有关知识点的智能服务的词典。知识词典的最大作用是为题 目进行知识点的标注，也就是通过知识词典的支持语义化的赋予题目以知识 点。最基本的支持方法是通过代码来获取知识点，知识词典将会通过程序的代 码分析来得出代码中包含哪些基本的语言级知识点。得到语言级的知识点后， 知识词典还能够通过这些语言级知识点之间的联系来分析出一些高级的概念 级知识点。这里需要说明的是在知识词典中，语言级知识点是那些与具体程序 设计语言比如c + + ，j a v a 等有直接联系的知识点，如c + + 的输入语句c i n 这个 知识点直接和语言挂钩。而概念级的知识点则是比较高级的与具体程序设计语 言脱离的知识点。比如“标准输入”这个知识点，并不与具体的程序设计语言 挂钩，而是泛指任何程序设计语言的标准输入这个知识。除了分析代码，还有 通过测试数据等方式来得到知识点，但是这些方法比较复杂也需要人工干预， 在下面相关的章节中会详细介绍这方面内容。 知识词典除了提供知识点的标注服务外，还会在进行题目分解时提供知识 点上的支持。 2 9 堆于纠络知识资源语义化的i u 了试卷自动生成系统研究 2 4 2 方法库 方法库提供的主要是解题方法所包含的知识点以及他们之间的联系。 首先，方法库可以通过知识词典的支持来整理出每一种解题方法所包含的 知识点组合，这样就可以通过给定的知识点来判别所用的方法。本系统将利用 到方法库的这个服务来分解试题，其主要作用在于对题目的知识点进行拆分 后，必须知道哪些知识点的组合是可以生成题目的。因为并不是所有的知识点 组合都能给出合适的题目。本文将在第三章中论述如何结合知识词典和方法库