（计算机科学与技术专业论文）基于领域知识的试题分类及相似试题检测的研究.pdf

中文摘要 摘要 计算机技术和网络技术的不断发展，使得一些无纸化且随机选题的练习和考 试方式越来越多地应用于各种计算机考试系统中，这种应用的实现离不开电子试 题库。通常在电子试题库中，试题以手工方式录入，且一次录入就可长期使用， 然而随着试题不断地大量地补充，试题库管理的两个十分突出的问题：试题分类 和检测试题是否重复也就随之而来，传统的人工分类和检测已经无法胜任这项艰 巨的工作了。因此，如何有效地分类和去除重复或相似的试题是试题库管理中亟 待解决的问题。 针对上述问题，本论文综合考虑了领域知识的特点和试题的特点，将文本分 类技术和句子相似度计算技术引入到试题库管理中，提出了基于领域知识的试题 分类和相似试题检测的方法。主要研究内容如下： 首先，分析试题库中试题，提出试题区域性特点。试题是对知识进行测试评 估的最简单、最有效的方式，试题要考核的知识所属的知识点就是试题所属的类 别，即试题的区域性，它保证了试题分类的可行性。 其次，提出基于领域知识的试题分类方法。将领域知识和文本分类算法引入 到试题分类中，利用领域知识和试题的特点，再加上改进的k n n 分类器，实现试 题的分类。 再次，提出基于领域知识的相似试题检测方法。本论文考虑到领域知识对试 题相似度计算的影响，同时又考虑到试题本身的句子性特点，将领域知识和句子 相似度进行融合，实现相似试题检测。 最后，设计并实现试题分类和相似试题检测系统。本论文以计算机操作系 统课程的知识和资源为研究对象，同时充分考虑到领域专家的参与，由浅入深 地设计并实现试题分类和相似试题检测系统。 关键词：相似试题检测；试题分类：试题库：领域知识 英文摘要 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g y , s o m ep r a c t i c e sa n d t e s t sw h i c hu s en op a p e ra n ds e l e c tq u e s t i o n sr a n d o m l ya r em o r ea n dm o r eu s e di na l l k i n d so fc o m p u t e re x a m i n a t i o n ss y s t e m ，w h i c ha r er e a l i z e db ye l e c t r o nt e s tq u e s t i o n s l i b r a r y g e n e r a l l yt e s tq u e s t i o n sa r er e c o r d e dm a n u a l l y o n c ea t e s tq u e s t i o ni sr e c o r d e d ， i tc a l lb eu s e df o ral o n gt e r m h o w e v e r , t e s tq u e s t i o nc l a s s i f i c a t i o na n dr e p e a t e d q u e s t i o n sd e t e c t i o nc o m ea l o n gw i t ht h ec o n t i n u a la n dl a r g ei n c r e a s eo ft h et e s t q u e s t i o n si nt h em a n a g e m e n to ft e s tq u e s t i o n sl i b r a r y t r a d i t i o n a lc l a s s i f i c a t i o na n d d e t e c t i o nb yh u m a n sc a l ln o tc o m p l e t et h i sa r d u o u st a s k t h e r e f o r e ，h o wt oc l a s s i f ya n d w i p eo f ft h er e p e a t e do rs i m i l a rt e s tq u e s t i o n se f f e c t i v e l yi sas e r i o u si s s u ei nt h e m a n a g e m e n to f t e s tq u e s t i o n sl i b r a r y f o rt h ea b o v ep r o b l e m s ，c o n s i d e r e dt h ec h a r a c t e r i s t i c so ft h ed o m a i nk n o w l e d g ea n d t e s tq u e s t i o n s ，t h i sp a p e rb r i n g st h ed o c u m e n tc l a s s i f i c a t i o nt e c h n o l o g ya n dt h es e n t e n c e s i m i l a r i t yc o m p u t i n gt e c h n o l o g yi n t ot h em a n a g e m e n to ft h et e s tq u e s t i o n sl i b r a r yt o p r o p o s et h et e s tq u e s t i o nc l a s s i f i c a t i o na n ds i m i l a rt e s tq u e s t i o n sd e t e c t i o nb a s e do n d o m a i nk n o w l e d g e t h em a j o rr e s e a r c hc o n t e n ti si nt h ef o l l o w i n g ： f i r s t , p r o p o s er e g i o n a l i t yc h a r a c t e r i s t i co ft h et e s tq u e s t i o nb ya n a l y z i n gt h et e s t q u e s t i o n sl i b r a r y t h et e s tq u e s t i o ni st h es i m p l e s ta n dm o s te f f e c t i v ew a yo ft e s t e v a l u a t i o n k n o w l e d g et h a ti st h ep a r to ft h et e s tq u e s t i o nb e l o n g st ot h ek n o w l e d g e p o i n tw h i c hi st h et y p eo ft h et e s tq u e s t i o n r e g i o n a l i t yc h a r a c t e r i s t i ce n s u r e st h e f e a s i b i l i t yo ft e s tq u e s t i o nc l a s s i f i c a t i o n s e c o n d ，i n t r o d u c ed o m a i nk n o w l e d g ea n dt e x tc l a s s i f i c a t i o na l g o r i t h m st ot e s t q u e s t i o nc l a s s i f i c a t i o n t h i sp a p e rp r o p o s e st h em e t h o do ft e s tq u e s t i o nc l a s s i f i c a t i o n b a s e do nd o m a i nk n o w l e d g e ，a n da c h i e v e st h ec l a s s i f i c a t i o no ft e s tq u e s t i o nu s i n gt h e c h a r a c t e r i s t i c so fd o m a i nk n o w l e d g ea n dq u e s t i o nc o u p l e dw i t hi m p r o v e dk n n c l a s s i f i e r t h i r d ，p r o p o s es i m i l a rt e s tq u e s t i o n sd e t e c t i o nb a s e d o nd o m a i nk n o w l e d g ei nt h i s p a p e r c o n s i d e r i n gt h a td o m a i nk n o w l e d g ea f f e c t sc a l c u l a t i o no fs i m i l a r i t ya n dt a k i n g i n t oa c c o u n tt h ec h a r a c t e r i s t i c so ft h et e s t q u e s t i o n , t h i sp a p e rc o m b i n e sd o m a i n k n o w l e d g ea n dt h es e n t e n c es i m i l a r i t yc o m p u t i n gt oa c h i e v es i m i l a rt e s tq u e s t i o n s d e t e c t i o n 英文摘要 l a s t ，d e s i g na n da c h i e v et e s tq u e s t i o nc l a s s i f i c a t i o na n ds i m i l a rt e s tq u e s t i o n s d e t e c t i o nb yt a k i n gt h e ”c o m p u t e ro p e r a t i n gs y s t e m c o u r s ea so b j e c t i v e ，a n d m e a n w h i l ec o n s i d e rt h ep a r t i c i p a t i o no fd o m a i ne x p e r t sf u l l y k e yw o r d s ：s i m i l a rt e s tq u e s t i o n sd e t e c t i o n ；t e s tq u e s t i o nc l a s s i f i c a t i o n ； t e s tq u e s t i o nl i b r a r y ；d o m a i nk n o w l e d g e 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文竺基王锺缝翅丝的达壁坌羞拯揎型达壁捡测的婴窒：。除 论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已 经公开发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密( 请在以上方框内打“ ) 论文作者签名：煮秘导师签妾： 日期：沸 翻勋日 基于领域知识的试题分类及相似试题检测的研究 第1 章绪论 1 1 研究背景 随着计算机和网络技术的发展，网络考试( 在线考试) 系统成为了近年来计 算机技术研究的一个热门领域 。网络考试系统在智能组卷、标准化测试和结果的 统计分析等方面较传统的考试方式具有一定的优越性。同时，数据库技术的普及 以及国家对教、学的重视，许多院校也相继建设了校园网，这就为网上教学、网 上作业、网络考试系统的建立提供了一个必要的环境。 试题库与计算机技术相结合产生了电子试题库【2 】( 本论文简称试题库) 。试题 库的出现，不仅弥补了传统教学的部分缺陷，而且将计算机在教学领域中的应用 推向了一个新的阶段。在国外许多国家，试题库系统已经广泛应用于教学领域， 而且收到了显著的成效。 试题库管理在在线考试系统中有着十分重要的意义和价值，良好的试题库管 理系统可以为考试系统提供有效的、丰富的试题数据，还可以为师生的教、学活 动提供一种新的教学平台。然而，网络带来的信息资源的共享以及信息数据量的 爆炸性增长使得传统的手工信息处理方法变得不切实际，因此需要采用自动化程 度更高、效率更好的信息处理方法，帮助人们更高效地进行文本处型3 1 。 随之试题从网络和实际中大量地获取，试题库管理的两个十分突出的问题： 试题分类和检测试题是否重复也就随之而来。传统的纯人工分类和检测费时又费 力，随着从各处获取的试题数量的剧增，其分类和检测效率更低。举个例子来说， 假设试题库中有1 0 0 道试题，现在要加入1 0 道试题，那么为了判断这1 0 道试题 是否已经存在，人工检查的话最多要做1 0 0 0 次比较，这个工作量看似人工可以胜 任，但是如果要添入1 0 0 道、1 0 0 0 道试题呢? 从上面的例子可以看出，人力已经 不能胜任这项工作了，快速高效的计算机分类技术和检测技术将是解决试题分类 和检测问题的有效途径。 第1 章绪论 1 2 研究目的及意义 1 2 1 研究目的 试题库的产生为网络教学和在线考试带来了方便。然而试题库在管理上却一 直存在着许多问题。网络的迅猛发展以及学校和学校之间，学校与社会之间的信 息交流与合作，使得试题资源相当丰富而且非常容易获得。如何对获得的海量试 题进行有效地管理已经得到了社会和专家的密切关注。 试题库管理中两个十分突出的问题就是试题分类和试题相似性检测。试题分 类是根据试题待考核知识的信息将新获取的试题一一划分到相应的类别( 知识点) 下，类别的划分是由领域专家确定的。试题相似性检测是对获得的试题，检测庞 大的试题库中是否已经存在了相同的试题，或者已经存在了具有很高相似度的试 题。传统的人工分类和检测费时费力，而且主观性太强，随着试题数量的剧增， 其效率更低，难度更高。在试题库管理中引入快速高效的计算机分类技术和句子 相似度计算技术，将是解决上述问题的有效途径。 本论文以计算机操作系统课程的领域资源为研究数据，以文本分类技术 和句子相似度计算为理论基础，探讨基于领域知识的试题分类和相似试题检测的 试题库管理方法和技术。利用文本分类算法的思想，根据领域知识的特点和试题 本身的特性，构建适合于试题库管理的分类算法，由计算机快速完成试题分类； 通过引入句子相似度计算，同时考虑领域知识的特点和试题本身的特性，构建适 合于试题库管理的相似性检测算法，由计算机快速完成相似试题检测。总之本论 文以实现自动化或半自动化的试题分类和相似试题检测为目的，研究有助于人们 方便、快速以及高效的进行试题库管理的方法和技术。 1 2 2 研究意义 试题库是在线考试系统的基础，为试题的存储、分类、相似性检测等提供了 平台。然而，现存的海量试题却给试题库管理带来了新的挑战。对于特定领域的 试题库，根据领域专家提供的知识点信息，将试题分类到相应知识点下，是智能 化和个性化测试基本要求，也是试题基本的、有效的组织形式。重复存在的试题， 不仅给试题库造成额外的空间开销，同时给知识地考核带来负面影响。一份考核 基于领域知识的试题分类及相似试题检测的研究 试卷中存在相同或相似的试题，不仅造成知识测评的不准确，更会让用户对网络 教学失去信心。 知识可分为通用知识和领域知识。通用知识具有比较强的二义性，而领域知 识则具有比较强的针对性【4 】。领域知识在逻辑上的紧密相关性称为领域内聚性；在 一定时间内领域知识不会发生剧烈的变化称为领域稳定性。领域知识的上述特点， 为特定领域或专业的试题分类技术和相似检测技术提供了一定的理论依据。 文本分类技术多应用于文档分类、邮件过滤、智能搜索引擎等多个方面，而 应用于试题分类方面的研究甚少【5 】。而且，现有的文本分类技术的研究对象主要是 大型文本，对于适用于试题这种只有数十字的小型文本分类技术研究甚少。因而， 本论文尝试把计算机文本分类技术应用于试题分类中，根据领域知识的特点和试 题本身的特性，设计并实现一个基于领域知识的试题分类系统，由计算机快速完 成试题分类。 在自然语言处理领域，尤其是在中文信息处理领域，句子相似度计算一直是 一个基础研究课题。它的研究状况直接决定着其他一些相关领域的研究进展【6 1 。句 子相似度计算在自然语言处理的很多领域都有着重要的作用，例如基于实例的机 器翻译系统f 7 】、文档自动文摘系统【8 】、基于常见问题集的机器问答系统1 9 及信息 检索、信息过滤等。本论文尝试将句子相似度计算引入到相似试题检测中，设计 并实现一个基于领域知识的相似试题检测系统。实现半自动化相似试题检测，以 节省人力资源。 试题分类和相似试题检测的研究将会为试题库管理带来方便，为教师或领域 专家极大地减轻人工试题处理的负担，有利于网络教学推广和发展，因此本论文 具有研究的理论价值和实际的应用价值。 1 3 研究现状 ( 1 ) 文本分类研究现状 文本分类的研究在国外开展比较早。1 9 5 7 年i b m 公司的h p l u h n 在自动分类领 域最先进行了开创性的研究，提出基于词频统计思想的文本自动分类【1 0 】。1 9 6 0 年 m a r o n 和k u h n 发表了与文本分类有关的第一篇文章o nr e l e v a n c e ，p r o b a b i l i s t i e 第1 章绪论 i n d e x i n ga n di n f o r m a t i o nr e t r i e v a l 1 1 】，正式宣告了自动文本分类技术的诞生。1 9 6 3 年b o r k o 等人提出了利用因子分析法进行文献的自动分类【1 2 1 。随后，众多学者在这 一领域进行了卓有成效的研究。 2 0 世纪6 0 年代至8 0 年代，文本分类主要采用传统的知识工程技术，根据专家 提供的知识形成规则，手动建立分类器。h a y e s 等设计的c o n s t r u e 【1 3 】是其中典型 的代表。基于知识工程的分类系统的分类效果较好，但它无法移植，而且需要大 量专家的参与。基于机器学习的自动文本分类起步于2 0 世纪9 0 年代，首先由计算 机对经人工正确分类的训练文本集进行学习，获得类别的特征信息，然后根据算 法生成分类器。这种分类方法适应性强，方便移植【1 4 】【嘲。 国内在文本分类技术的研究上起步比较晚，由于中文与英文存在较大的差异， 因此不能照搬国外的研究成果。国内文本分类的研究大体上经历了可行性探讨、 辅助分类、自动分类三个发展阶段。早期对中文文本的分类研究较少，采用的技 术也主要是把英文文本分类技术应用到中文文本分类中。自2 0 世纪9 0 年代后期才 着重于对中文文本分类的研究。 ( 2 ) 句子相似度计算研究现状 句子相似度计算方法的研究一直受到国内外研究学者的青睐【1 6 】。在国外，例 如哥伦比亚大学的g o l d s d e i n 等利用最大边缘相关的方法( m a x i m a lm a r g i n a l r e l e v a n c e ) b 7 】进行句子相似度计算。c h r i sh d i n g 等采用隐含语义索g l ( l a t e n t s e m a n t i ci n d e x i n 曲的方法【1 8 】进行句子相似度计算。l a m b r o s 等提出同时依据句子的 表层结构和内容计算句子相似度【1 9 】等。 国内，对于句子相似度计算主要是以字或词为处理单元，通过计算相同词语 所占的比重确定句子间的相似程度。有些方法是在此基础上结合句子结构信息进 行相似度计算。如穗志方、俞士汶提出的基于骨架依存树的语句相似度计算模型 【2 0 】；基于知网和同义词词林，李素建等提出了语句相关性的定量计算模 型【2 1 ；金博等在词汇语义相似度的基础上，通过为词性不同的词赋予不同的权重 来综合评定句子的相似度【2 2 】；吕学强等通过考虑词形相似度和词序相似度两个因 素，提出了句子相似模型和最相似句子的查找算法例等。 由于汉语语言的复杂性和不确定性，完全句法分析目前仍是不太可能。本论 基于领域知识的试题分类及相似试题检测的研究 文考虑到句子结构分析难以在短时间内有很大提高，所以将如何更好的利用句子 中词汇本身的信息作为提高句子相似度精度的入手点。 1 4 研究内容与论文结构 本论文主要包括六部分内容，各章节安排如下： 第一章绪论。本章主要阐述论文题目的研究背景、研究目的、研究意义以及 相关技术的研究现状，分析目前存在的相关问题，最后列出本文的主要研究内容。 第二章相关技术介绍。本章重点论述论文中使用到相关技术和理论，包括知 识点理论，文本表示技术，文本分类技术和句子相似度计算方法等。 第三章基于领域知识的试题分类。本章首先分析了领域知识的特点，针对本 系统的环境对领域知识进行组织。接着详细阐述语料库训练过程，尤其是试题库 训练过程。最后详细说明了基于领域知识的试题分类算法和改进的州分类器的 计算过程。 第四章基于领域知识的相似试题检测。本章首先通过实例分析了相似试题检 测的必要性和重要性。接着通过对试题库和句子相似度计算理论的分析，给出了 相似试题检测的理论和算法。最后结合本论文的系统给出相似试题检测算法的实 际应用方案。 第五章试题分类和相似试题检测系统设计与实现。本章首先简单介绍了系统 的设计目标及开发平台和工具。接着重点论述了系统设计的整体框架，通过数据 流图和实例详细说明了各子模块的设计以及其中数据走向和结构组成。最后通过 系统运行界面说明各模块的实现情况。 第六章系统测试及总结。本章利用测试数据，给出系统测试结果和错误分析。 在此基础上对论文期间所做的工作进行总结，提出有待于进一步研究的相关问题。 第2 章相关技术的研究 第2 章相关技术介绍 2 1 知识点理论 近几年来，“知识点 概念被广泛应用于教学研究、教学实践以及教学系统 的设计当中，但是目前“知识点 的定义却没有统一、明确。“知识点 的定义 不明确尽管不会妨碍对其使用，但是在教学活动过程中可能会影响到人们发现它 所反映的认知规律。关于“知识点 ，本论文参考文献【2 5 】使用如下定义：知识点 ( k n o w l e d g ep o i n t ) 是指在教学活动过程当中教学信息的基本的组织单元和传递单 元。它包括词、句、概念、定义、定理、定律、公式、规律、观点、范例和结论 等。知识点可分为原子知识点和复合知识点。原子知识点是不能再分割的知识点， 是知识的最小单元。复合知识点是由多个知识点( n - i 以是原子知识点，也可以是 复合知识点) 组合而成的知识点。保证知识内容的局部完整性是知识点提取的基 本原则，其大小可随需要而定，可能相差很悬殊。 知识点之间存在着复杂的关系，主要包括层次关系、前驱关系和关联关系。 其形式化定义如下【2 4 】： ：= l i ：= ， ：= ， ：= ， 层次关系指知识点可以由若干知识点组合而成，各知识点之间形成树型结构。 知识点的层次关系是按照横向结构与纵向结构对知识划分得到的。横向结构是指 知识点之间的一种并列关系，各知识点间互为兄弟。纵向结构是指各知识点间形 成的父子关系，由几个知识点组成的复合知识点称为父知识点。父知识点是子知 识点的综述，子知识点从不同的侧面，不同的角度，不同的范畴对其父知识点进 行阐述。 知识点的前驱关系指知识点在学习过程中的一种必然的先后关系。在学习某 一知识点之前必须先学习相关的另一知识点，这两者之间就为前驱关系。 知识点的关联关系指作为一种知识体系，概念原理之间存在着相互制约、相 基于领域知识的试题分类及相似试题检测的研究 互影响的关系。关联关系揭示了知识点之间存在着复杂的网状结构，指出知识是 由一组相互作用、相互联结的结点组成。 2 2 文本表示 电子文本( 以下简称文本) 大部分是没有固定的结构，甚至根本没有结构的， 而且其内容大都通过自然语言来描述，计算机无法直接理解其语义并对其进行处 理，因此需要对文本进行预处理，抽取能表达文本主题内容的特征，并将这些特 征用结构化的形式保存起来，形成文本的中间表示形式这就是文本表示文档表示 ( d o c u m e n tr e p r e s e n t a t i o n ) 2 6 1 。本论文在系统设计时采用s a l t o n 等人提出的向量 空间模型对领域文本进行表示。 2 2 1 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，简称s v m ) 是由美国的s a l t o n 等人于 2 0 世纪6 0 年代提出，并成功地应用于s m a r t 系统中f 2 7 1 2 8 1 。向量空间模型的基本思 想是使用词袋法( b a g - o f - w o r d ) 表示文本，每个特征项对应特征空间的一维，文 本d 可用以下形式描述为d = ( w l ，w l ，w 2 ，w 2 ，w i ，w i ，w n ，w n ) 。其 中w i 是能表示文本内容的特征项，w i 是特征项w i 在文本d 中的对应权重1 2 9 。 向量空间模型中有以下几个常用概念： 文本( d o c u m e n t ) ：泛指一般的文献或文献中的片断( 段落、句子组等) ，一般指 一篇文章。在本论文中，文本与文档是不加区别的。 特征项( t e r m ) ：文本的内容常可以用它所包含的基本语言单位( 字、词或短语 等) 来表示，这些基本的语言单位统称为文本的特征项( 本论文中也称为特征词) ， 即文本d 可以用特征项集( t e r ml i s t ) 表示为d = - ( w l ，w 2 ，w i ，w n ) ，其 中w i 是特征项。 特征项的权重( w e i g h t ) ：对于含有1 1 个特征项的文本d = ( w l ，w 2 ，w i ， w n ) ，常用一定的权重w i 表示特征项w i 在文本d 中的重要程度，即d = ( w i ，w i ， w 2 ，w 2 ，w i ，w i ，w n ，w o ) ，简记为：d = ( w l ，w 2 ，eo $ w i ，w n ) 。 文本相似度( s i m i l a r i t y ) ：对于两个文本d l 和d 2 之间的内容相关度的度量被称 为文本相似度。文本d l = ( w 1 l ，w 1 2 ，w l i ，w l n ) 和d e = ( w 2 l ，w 2 2 ， 第2 章相关技术的研究 w 2 i ，w 2 n ) 的相似度的计算公式为： s i m i l a r i t y ( d i ，d 2 ) = ( 2 1 ) 向量空间模型是一种简单，有效的文本表示模型而且已经在信息检索、文本 分类等相关领域得到了广泛而成功的应用。本文也是以该模型为基础进行研究的。 2 2 2t f io f 加权算法 t f i d f 加权算法向量空间模型中最常用的特征项权重计算方法，是由s a l t o n 等人提出并用于信息检索领域【2 8 】 3 0 1 ，后来被应用于文本分类、文本聚类等数据挖 掘之中。t f i d f 计算公式如下： 形。d = 厂d l g ( 生) ( 2 2 ) 刀f 其中、表示特征项t 在文档d 中的权重；丘d 表示t 在d 中出现的频率；n 表示训练文档总数，n t 表示出现特征项t 的文档数目。从式( 2 2 ) 可以看出：特征 项在文本中出现次数越多，就越重要，其权重就越大；特征项在越多的文本中出 现，就越不重要，其权重就越小。 考虑到文本长度对特征项权值的影响，还需要对式( 2 2 ) 做归一化处理【3 1 1 ， 将各项的权重规范n o 1 】之间： w , d = 其中，m 表示特征项集合的大小，整个分母为归一化因子。 ( 2 3 ) 2 3k n n 文本分类算法 文本分类的任务是在给定的类别体系下，根据文本的内容由机器自动地确定 与文本相关联的类别，系统的输入是待分类的文本，而输出是与待分类文本相关 联的类别。 目前比较著名的文本分类算法有：k 最近邻算法( kn e a r e s tn e i g h b o r s ，简称 基于领域知识的试题分类及相似试题检测的研究 k n n ) 3 2 】、支持向量机算法( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 3 3 1 1 3 4 1 、最大熵 模型法( m a x i m u me n t r o p y ) 【3 5 1 、神经网络法( n n c t ) 3 6 1 等。 2 3 1k n n 分类算法 i 心眦文本分类算法在文本分类中得到了广泛地应用，它是一个简单、有效、 非参数的分类算法。本论文选择l 心附分类算法作为试题分类研究的基础是因为它 能够表现出较高的精确性和稳定性【3 2 1 1 3 7 1 3 8 1 ；它是在r e u t e r s 语料上取得较好结果的 文本分类算法之一。 k n n 分类算法是一种基于统计的模式识别方法，其思想是：对于一篇待分类 文档d ，在训练集中找到k 个最相近的邻居，使用这k 个邻居的类别为d 的候选 类别，d 与k 个邻居之间的文本相似度为候选类别的权重，然后根据k n n 决策规 则得到d 的最终归属类别。目前较常用的k n n 决策规则如下【3 9 】： p ( d ，c ，) = s i m i l a r i t y ( d ，d ，) j ，( 皿，c ，) - b i ( 2 4 ) d i e k n n 其中，p ( d ，c j ) 表示待分文档d 属于类别c j 的权重；d i 表示k n n 训练集中 一篇文本的特征向量表示；s i m i l a r i t y ( d ，d i ) 表示d 与训练文本d i 的相似度，根 据式( 2 1 ) 计算得出；y ( d i ，c j ) o ，1 ，( 当d i 属于c j 时取1 ，否则取o ) ；b j 为预先测定的c j 的阈值。 2 3 2 分类器性能评价 在文本分类领域一般使用召回率( r e c a l l ) 和准确率( p r e c i s i o n ) 来衡量分类器 的性能 5 1 1 。召回率( 又称查全率) 是指一个文档应该属于某一类别而分类器也确 实将其分到该类别的概率。准确率是指一个文档被分类器分类到某一类别而且这 个分类是正确的概率。对于分类系统中的类别，一般使用二值列联表( t w o w a y c o n t i n g e n c yt a b l e ) 来确定准确率与召回率【5 1 1 ： 表2 1 二值列联表 t a b l e2 1t w o - w a yc o n t i n g e n c yt a b l e 第2 章相关技术的研究 表2 1 中，a 表示人工分类中属于该类的文档被分类器分到该类中的文档数目。 b 表示人工分类中不属于该类的文档却被分类器分到该类中的文档数目。c 表示原 本属于该类却被分到了其它类中的文档数。d 表示不属于此类的但也没有被分到此 类中的文档数。 准确率和召回率的计算公式如下： 准确率( p r e 虻i s i o n ) = j 与( 2 5 ) 召回率( r e 爿m u ) = 旦 ( 2 6 ) 准确率和召回率反映了分类质量的两个不同方面，必须综合考虑，不可偏废。 因此，存在一种新的评估指标f 1 值5 1 1 ，f 1 值是对分类器性能的综合评价指标。 其计算公式如下： n ：絮黧臻擎 ( 2 7 ) r i = 一 ，- 一 准确率+ 召回率 pv 2 4 句子相似度计算 句子相似度是一个主观性比较强的概念，在信息理论、哲学、语义学中被广 泛地讨论，然而脱离具体的应用背景去讨论句子相似度，很难得到一个统一的定 义删。 d c k a n gl i n 曾给出一个与应用领域无关的相似度的非形式化定义：句子a 与 b 的相似度一方面与它们的共性相关，共性越多，相似度越高；另一方面与它们的 区别相关，区别越大，相似度越低；当a 与b 完全相同时，相似度达到最大值【4 1 1 。 然而，在实际应用中，要根据具体的应用背景寻找合适的句子相似度的定义， 这是因为在不同的应用中，相似度的含义是有差别的。虽然没有通用的相似度定 义，但是在实践中也形成了一些划分方法【4 2 1 。 在句子相似度计算中，按照对语句的分析深度来看，主要存在两种类型的计 算方法： ( 1 ) 对句子进行完全的句法与语义分析。对被比较的两个句子进行深层的句法 分析，找出依存关系，并在依存分析的基础上进行句子相似度计算。例如基于词 基于领域知识的试题分类及相似试题检测的研究 义的句子相似度计算。 基于词义的句子相似度计算方法需要一定的知识资源为基础【4 3 】，如同义词词 林、h o w n e t 5 2 】等。设句子a 与b ，a 的特征词为a l ，a 2 ，a i ，a m ，b 的特征词为b l ，b 2 ，b j ，b n ，记特征词a i 、b j 的相似度为s ( a i ，b j ) ， 则句子a 与b 的相似度为： r a 口，b ， s i m ( 彳，b ) = ( 址+ 上l 一) 2( 2 8 ) m 刀 其中a i = m a x ( s ( a i ，b 1 ) ，s ( a i ，b 2 ) ，s ( a i ，b n ) ) ，b j = m a x ( s ( b j ，a 0 ，s ( b j ，a 2 ) ，s ( b j ，a n ) ) 。 该计算方法充分考虑到每一个词的深层信息，将表面不同，而深层意义相同的词 挖掘出来。但是由于知识词典等资源的不全面和一些未登录词的缺失，也给计算 带来了一定程度的影响。 ( 2 ) 基于向量空间模型的方法。该方法是把句子看成词的线性序列( 即把句子 表示成由关键字构成的向量) ，不对句子进行语法分析和语义分析等，其相似度计 算是利用句子的表层信息。由于不进行任何的结构和语义分析，该方法在相似度 计算时不能考虑句子的整体结构的相似性。例如，基于关键词的句子相似度计算。 基于关键字的句子相似度计算【4 3 】：任给两个句子s l 和s 2 ，它们所有的关键字 构成的向量空间为驴 x l ，x 2 ，x l i ) ，其中x i 为特征词( 1 i n ) 。句子s l 的向量v t = w i ，w 2 ，w 。 ，其中w i 为特征词x i 在句子s l 中出现的次数。句子 s 2 的向量v 2 = 1 l rl ，l i t 2 ，1 l r n ) ，其中1 l r i 为特征词x i 在句子s 2 中出现的次数。 则句子s l 、s 2 的相似度为： s i m ( s l ，s 2 ) = 矗 w ，q ， f ；l ( 2 9 ) 该计算方法只是简单地利用了句子的表面信息，对于一些内容相关性较小的 语料其效果较好。但是，没有考虑到词本身的词义信息以及句子的句法信息，因 此计算方法存在一定的局限性。 第3 章基于领域知识的试题分类 第3 章基于领域知识的试题分类 试题分类的最终目的是在已有的知识点体系下，按待分类试题所包含的知识 点信息，将其划分到相应的知识点类别下。本论文中试题分类算法的基本思想是： 在领域专家构建的领域词典的基础上，利用试题中所包含的领域知识的信息，通 过使用改进的k n n 文本分类算法，实现试题的自动分类。其关键技术是试题内领 域知识的提取和使用以及k n n 文本分类算法的改进和使用。 试题是用来对某一领域知识进行考核的文本，因此试题中包含着丰富的领域 知识的信息。试题所包含的领域知识是试题能够被分类的基础，同时也是试题的 特性之一；试题本身又可以看成是一个小型文本，所以试题分类的问题可以通过 借鉴文本分类技术予以解决，这是试题的又一特性。基于试题的以上两个特性本 论文提出了基于领域知识的试题分类算法。 3 1 领域知识的组织模型 领域知识【4 4 1 ，即属于某一领域范围内的特定知识，这里的“领域”范围根据 使用者的需求来确定，它可以是一个学科领域，也可以是某几个学科领域的结合， 还也可以是某个领域中的一个小范围【4 5 】。领域知识的范围根据实际的需求和实际 的应用来确定。 试题分类中的一个关键问题就是领域知识的组织和表示，良好的知识表示形 式，不仅可以合理有效的将领域知识组织起来，还可以帮助学习者建立良好的知 识结构，提高学习效率。领域知识表示的目的就是要揭示出领域知识中的各种元 素及其相互之间的关系，尤其是知识的上下位关系，并用形式化的方法描述并表 示出领域知识及其相互之间的关系。 3 1 1 领域知识的特点 书籍、电子文档以及领域专家等是领域知识的主要载体。在教学领域，领域 知识往往以课程知识的形式传承，例如以书籍的形式传播，以教师授课的形式传 授等。本论文中的领域知识是指教学领域中某一学科的课程知识，本论文的设计 就是建立在计算机操作系统课程知识的基础上。 基于领域知识的试题分类及相似试题检测的研究 课程知识往往以知识点作为处理单元，即把学习内容划分成若干知识点，并 建立知识点之间的关联关系。知识点是领域专家或教学专家根据一定的教学策略、 教学经验、教学目的和教学对象等进行确定的，其粒度相差可能很悬殊，例如， 一章可以划分为一个大知识点，该章下的每一小节可以划分为它的子知识点，对 每一节的内容又可以划分为若干个更小的知识点。此外，知识对象的划分粒度直 接影响到对知识对象的可重用性。一般来说，知识对象划分越细，其可重用性就 越高，但是知识点的粒度太小又势必造成其重组的困难。因此知识划分的一般原 则是：保持知识对象的局部完整性，有利于组织教学步骤和遵循一定的教学 规律。知识点之间的复杂关系，如父子关系、前驱关系、关联关系等，使得领域 知识形成一个知识网络系统。 综上所述领域知识( 课程知识) 表现出了以下几个特点【蛔： ( 1 ) 有公认的概念集：任何知识都可以用概念来概括和表示。概念在领域内有 公认的语义。例如“进程管理 表示与进程相关的一些知识。 ( 2 ) 存在最基本的结构：知识由知识点组成，知识点可以由更小的知识点组合 而成。 ( 3 ) 具有层次性：领域知识都具有层次性，按其层次性可将领域知识组成知识 树。层次性主要由知识点之间的父子关系体现。 ( 4 ) 关系复杂性：领域知识之间的关系是复杂的但是有序的。 3 1 2 领域知识的组织模型 通常在教学领域，课程知识是以知识点的形式进行组织的，知识点是组织课 程知识组织的基本单位。一般而言，课程知识按照知识点的层次关系构成树型结 构【4 7 1 ，其结构如图3 1 所示。 第3 章基于领域知识的试题分类 图3 1 知识的树型结构 f i g 3 1t h et r e es t r u c t u r eo f k n o w l e d g e 图3 1 中，知识树具有以下特性： ( 1 ) 层次越高，其整体性越强，即所包含的内容( 知识) 越多： ( 2 ) 层次越低，其部分性越强，即所表述的内容越具体，所说明的只是知识的 一个具体的方面。 把教学内容按照层次概念组织起来，上层知识是对下层知识的归纳和总结， 下层知识是对上层知识的细化和描述。常见的层次划分方式是采用章、节、知识 点进行逐步递进，其所包含的知识内容逐渐变小，但细化程度逐渐加深。课程知 识的层次结构主体是父子关系，由教材的分层目录，构成一棵完整的课程知识树。 知识点之间除了父子关系之外，还存在其他复杂的关系，如相关关系、前驱 关系等。按父子关系将课程、章、节、知识点组织形成一棵知识树，在此基础上 加入相关关系和前驱关系等其它复杂关系，使得领域知识形成一个有向知识图， 也就是知识网络【4 8 】。 本论文将领域知识资源划分为逻辑资源( l o g i c a lr e s o u r c e ) 和物理资源 ( p h y s i c a lr e s o u r c e ) 。逻辑资源是指知识点资源，即领域知识的形式化描述；物理 资源是指教学资源，如书籍、教案、电子文档以及测试试题等。 领域知识组织模型的实质就是研究知识点的属性特征和各知识点之间的相互 基于领域知识的试题分类及相似试题榆删的研究 关系。领域知识的教学以知识点的教学为基础，每一个知识点都是一个教学单位 同时也是一个教学目标。本论文中领域知识的组织模型如图3 2 所示。 图3 2 领域知识的组织模型 f i g3 2 t h e d o m a i nk n o w e e d g e o r g a n i z a t i o n m o d