毕业设计双选系统的设计与实现北京石油化工学院

1、毕业设计双选系统的设计与实现计算机科学与技术 隋旭宗指导教师 沙芸 副教授摘 要 随着互联网的不断发展，各类信息管理系统已成为数字化校园建设的一部分。毕业设计双选是教学的重要环节，也是毕业设计质量提高的基本保证。目前，毕业设计双选的大部分工作仍需要人工完成。本文通过对当前选题流程及特点分析，设计并实现一个毕业设计双选系统，以完善教学体系，促进数字化校园的建设。本系统的目的是：简化毕业设计选题申报流程，借助B/S方式，使师生能够不受时间、地域的限制，完成毕业设计双选，并由指导教师向学生提供任务书。本系统的特点是：实现了题目及题目申报表的相似度计算。此功能借助Lucene完成分词操作，经过词频统计

2、后，生成文档向量。系统实现了余弦相似度、Dice和Jaccard三种相似度计算方法。通过对不同算法的相似度比对结果进行评估，确定了相似度的阈值，并对这些结果进行讨论。本系统为B/S结构，使用ASP.NET技术开发，拥有良好的用户体验。相似度比对能够快速有效地给出参考结果，减少了教师出题过程中因检索题目相似度而消耗的时间。关键词 毕业设计双选，文档向量，词频统计，文本相似度计算1 绪论1.1 研究背景和研究意义毕业设计是高校教学任务的重要实践环节，是评估学生学位资格的依据之一。目前大多数院校仍沿用传统的选题方式，存在很大弊端。大部分学生不能从题目中了解到更多有效信息，很难评估题目的工作量和难易度

3、。学生盲目选题，开题阶段不能顺利进行，教师需要修改甚至变更题目，给教师和学生增添了许多工作量。随着毕业生人数逐年增加，毕业设计的题目数量也在增长1，人工分配学生可能产生错误。此外，教师通过人工筛查的方式不易得知题目是否重复，产生许多雷同或是相同的任务内容在所难免。规范毕业设计的管理流程，提高选题效率，不仅有助于改善毕业设计质量，还可以节约人力、物力成本。设计并实现一个B/S结构的毕业设计选题系统2，可以减轻教师的工作量，推动毕业设计工作进行。数字化校园3最早是由麻省理工学院于上世纪70年代提出的。目前，西方发达国家的许多高校已经完成了数字化校园的建设工作。在毕业设计选题方面，英国的诺丁汉大学已

4、经拥有了自己的毕业设计双向选择信息服务系统4，欧美国家的一般大学均实现了在线选题，同时可以进行在线评审、讨论5等。1.2 需要解决的问题针对学校当前的选题流程，设计并实现一个具有以下功能的毕业设计双选系统：（1）教师出题，包括题目上传、查重及申报书相似度比对，给出相似度比对结果；（2）学生选题，按需求查看题目（申报书）信息及下载任务书；（3）师生双选，并由教师上传任务书及任务书相似度比对，给出相似度比对结果。针对毕业设计的题目和申报书中的内容，比对题目历史信息及申报书相似度；（4）综合比较各种文本相似度的计算方法，选择区分度更好的，应用在申报书的相似度比对中，对题目、内容进行查重。要完成以上功

5、能，需要解决以下三个关键问题：（1）段落主题是文本相似度比对的基本前提，设计并实现一种提取段落主题的方法；（2）申报书之间的相似度主要通过段落相似度来计算，设计并实现一种主题段落相似度比对的计算方法；（3）对系统结构和相似度算法的优化。2 毕业设计双选系统总体设计2.1 总体结构 毕业设计双选系统的主要用户有：教师、学生、系统管理员。针对各个用户的特点，将系统功能进行划分，如图2.1所示：毕业设计双选系统题目申报题目查重申报书维护双选信息管理申报书管理任务书下载课题双选任务书上传双选管理学生信息查询系统参数配置选题信息导出高级权限操作当前学年选题数上限数据可见性图2.1 毕业设计双选系统模块划

6、分图2.2 E-R图本系统涉及的实体、属性以及相互之间的关系如图2.2所示：题目题目信息1配置信息修改人修改学生选题选题结果申报书教师1mn双选pqmmn图2.2 毕业设计双选系统实体及其联系图2.3 动态模型系统正常使用时，按照其涉及的主要事件及发生的先后顺序，脚本如下：教师登录后，将申报书信息在页面上填写完毕。题目申报成功后，形成申报书，并交由教师审核。教师审核通过，此题目有效，学生可以看到此题目。学生登录后，向系统提交查询请求，如：按难易度降序排序。系统将查询结果显示给学生。学生提交选题申请，教师可以看到学生申请。教师通过学生信息，选择学生，如：张三。教师上传任务书，系统显示上传结果。学

7、生提交下载任务书请求。系统与学生建立连接，将任务书发送至学生。根据以上脚本，绘制事件追踪图如图2.3所示：教师题目申报类题目双选类学生任务书类填写申报信息题目申报书通过审核完成题目申报查询题目请求申报书选题申请学生选题情况选定学生上传任务书文件上传结果下载任务书请求任务书图2.3 事件追踪图3 文本相似度计算查重作为毕业设计双选系统的重要功能之一，需要系统能够有效识别重复信息，给出两篇源文档的相似度比对结果。以词频为特征项，建立向量空间模型6，计算特征向量7的相似度，是解决此类问题的一种常用手段。3.1 基于词频的相似度比较本节以词频作为特征项T，对一些相似度计算的方法进行比较分析。流程如图3

8、.1所示，其中文档分析器使用的是Lucene。待测文档成分分析特征项提取语料库文档分析器提取器信息过滤输出结果图3.1 相似度比较流程图3.2 欧氏距离 欧氏距离通常指的是，两个点在n维空间中的真实距离。在二维和三维空间中，欧氏距离就是两个点之间的实际距离。假设空间中存在两个点D0、D1，如图3.2所示，那么它们之间的欧氏距离为：（3-1）yxzyxzD0D1D'0d1d2图3.2 欧氏距离示意图D0D1D'0 其中xi和yi表示这两个点各个特征项的权重。保持D0和D1的夹角大小不变，延长D0至D'0，记Dist(D'0,D1)=d2，显然有d1d2。由此可见，

9、特征项的权重大小会对欧氏距离造成直接影响，容易使相似度比较结果存在较大偏差。在继续对欧氏距离进行讨论前，先对余弦相似度进行分析。3.3 余弦相似度 用词频构建一个简单的向量空间模型，结合余弦相似度8来进行文档相似度的比较。假设有两篇文档D1和D2，抽取出这两篇文档中包含的10个关键词wi（i=1,2,.,10）。经过对文档进行统计，得到这些词的词频如下：w1w2w3w4w5w6w7w8w9w10D142931D21152411则D1=4,2,0,0,0,9,3,0,1,0，D2=0,1,1,5,2,4,0,1,0,1。然后利用公式（3-2）计算它们的余弦相似度：（3-2）其中，ai和bi为对应

10、关键词wi（i=1,2,.,10）的词频。上面所得结果的意义在于，余弦值越接近1，表明它们的夹角越接近0°。通过这个角度可以判断两个向量的相似度（如图3.3所示）。xyzD0D1D221xyz图3.3 余弦相似度示意图D0D1D221Dice系数和其十分相似，如式（3-3）：（3-3）比较欧氏距离和向量的夹角余弦，它们都可以用来进行个体间相似度的分析，但是在实际情况中，需要根据不同的数据模型，评估二者的性能。在空间中的两点，距离一定时，它们的夹角余弦值不一定相同。对进行文档的相似度比较时，空间向量很可能在高维空间中。欧氏距离更依赖个体的数值特征，而对维度不够敏感，容易导致度量标准不统

11、一。而余弦相似度有效地避免了这个问题，不会受到指标刻度的影响，且所得结果的绝对值会落于0,1之间，比较这个数值的大小，可以得到向量之间的差异。3.4 Jaccard相似度狭义的Jaccard相似度描述为：两个集合A和B中，交集元素个数在并集元素个数中所占的比例，其可以表示为： （3-4） 根据上式所得的相似度结果在0,1之间。其缺点是，仅靠元素是否存在来进行计算，而元素的其它属性则会被丢弃。广义的Jaccard相似度，可以用下式表示：（3-5） 其中，ai和bi为对应关键词wi（i=1,2,.,10）的词频。与狭义的Jaccard相似度不同的是，元素的取值可以是实数。从公式中可以看出它和余弦相

12、似度有一些共同点，该方法也可以用来计算基于词频的文档相似度。3.5 TF-IDF算法单纯使用词频来进行文档相似度比较存在一定的缺陷。这种方式没有考虑文档中词语的总数对结果的影响。假如一个词w在一篇100个词的文档D1中出现了10次，在一篇1000个词的文档D2中出现了20次，在只考虑词频的情况下，D2可能对结果的影响更大一些，显然这是不合理的。TF-IDF59算法即Term frequency-Inverse document frequency算法。其中TF（词频）指一个词语在一个文档中出现的次数越多，说明这个词能够表现这个文档含义的可能性越大。IDF（逆文档频率）指的是如果一个词在某个文档

13、集合中出现的次数很多，那么这个词对其中某些文档的贡献度就越小，因此可以通过IDF来衡量区分文本的好坏程度。3.6 实验及结论本节以三组实验，验证Lucene的分词效果，并对余弦相似度、Dice、Jaccard计算方法进行分析比较。 实验1 验证Lucene分词效果。以两篇题目申报书为实验数据，其部分内容相似度极高。申报书比对结果如图3.4所示，可以看出相似度高的部分，其被标记内容达到85%以上；相似度低的部分其内容，其被标记内容少且分散。全分词器的分词效果良好，可以有效识别重复内容。图3.4 详细比对结果实验2 三种相似度计算方法的准确度。以毕业设计双选系统中的实际数据来对比余弦相似度、Dic

14、e、Jaccard计算方法。为了使数据更加清晰，以表示10篇数据库中的申报书。将以上题目的基本信息与“基于句子结构分析的文本自动摘要算法的设计与实现”的基本信息进行比较。计算相似度时，分别利用余弦相似度（Cosine）、Dice系数、Jaccard系数来得出结果，并给出真实相似度（St）。如表4-1所示：表4-1 各相似度算法的计算结果及实际相似度Ti选题背景相似度选题意义相似度学生主要工作相似度CosineDiceJaccardStCosineDiceJaccardStCosineDiceJaccardStT10.02930.02930.01490.02390.00730.00660.003

15、30.00250.10400.08970.04690.0645T20.07190.07100.03680.05990.01570.01470.00740.01420.17820.16460.08970.1290T30.11000.10530.05560.11000.03180.02990.01520.02860.16850.16720.09120.0645T40.00000.00000.00000.00000.01180.01180.00590.00000.15550.13850.07440.0774T50.41010.41000.25790.38530.25710.25670.14720.0

16、2860.20830.19430.10760.1548T60.04820.04810.02460.05500.03090.02590.01310.00000.20480.16820.09180.1161T70.46890.46880.30610.40370.04240.02780.01410.05710.19770.19190.10610.0516T80.04550.04520.02310.02750.06740.04080.02080.04280.16400.16140.08780.1161T90.49690.49440.32840.45870.25870.23380.13240.17140

17、.37490.36450.22280.2323T100.09810.09330.04900.05500.05430.05050.02590.14290.26050.25280.14470.1806从结果中可以看出，利用Cosine和Dice得出的结果差异不大，而Jaccard得出的结果会减少50%左右，且部分结果会有较大的偏差。通过人实际估算的相似度通常比Jaccard得出的相似度要高，而比另外两种方式低。实验3 三种相似度计算方法的耗时。选取一定数量的文档，统一与某文档进行相似度比对。从分词开始计算时间，至得到计算结果结束。实验中所用的计算机处理器为Intel(R) Core(TM) i7-

18、2670QM 2.20GHz，内存8.00GB。表4-2 各相似度算法耗时文档数量Cosine耗时(ms)Dice耗时(ms)Jaccard耗时(ms)1287998308065123262333233111024631866956596对比三种计算方法耗时，结果相差不大。在文档数量较多时，余弦相似度计算方法会略快于其它算法。4 总结与展望本文通过对学校当前毕业设计双选情况的分析，对比国内外各高校在选题方面的不同，结合实际，设计了B/S结构的毕业设计双选系统。本系统基本可以实现题目申报、申报书管理、学生选题、师生双选、任务书上传等核心功能。使用本系统，教师申报的题目信息全部存储于数据库中，更加

19、安全可靠，同时也有利于信息整合。学生通过本选题平台，能够获取的信息更加丰富，一定程度上避免了因对选题内容不了解而误选的尴尬。选题方式的灵活性更是传统选题方法所不能及的。此外，在功能上还增加了双选信息的统计、导出，进一步简化了双选流程；查重模块的实现可省去教师人工比对相似度的工作。将本系统应用于学校中，可以有效促进数字化校园的建设。在查重部分，简要介绍了目前广泛应用的文本相似度比对技术。实现了余弦相似度、Dice、Jaccard计算方法，验证了利用这些方法可以完成查重，并对它们的准确性、效率进行了比较。从结果上看，相似度比对基本能够满足查重需求。本系统在功能上还可以有进一步的提升：（1）提供学籍

20、信息和注册信息的接口，使用户信息直接导入；（2）结合JQuery，将部分页面的部分功能配合JavaScript实现，提升用户体验；（3）使用带词性标注的分词方法，提高分词准确度。将此方法应用于段落主题提取，使用基于主题句的相似度比对，会有更好查重的效果；（4）使用P/Invoke技术，将旧平台中好的相似度计算方法移植到系统中。参 考 文 献1 吴海燕.基于WEB的毕业设计选题系统的设计与实现D:硕士学位论文.内蒙古大学,2013.2 李瑞.基于.NET的毕业设计选题系统的设计与实现D:硕士学位论文.吉林:吉林大学,2012.3 柏依彤.基于校园网的高校毕业设计选题系统的建模与设计D:硕士学位论

21、文.电子科技大学,2011.4 胡巧婕.基于B/S的昌吉电大毕业设计选题系统的研究与设计D:硕士学位论文.电子科技大学,2012.5 柏依彤.基于.NET的高职论文选题系统的设计与实现D:硕士学位论文.山东:山东大学,2013.6 王秀红.文本相似度计算核函数的构造及其在分布式信息检索中的应用研究D:博士学位论文.江苏:江 苏大学,2012.7 韩晨靖.基于标题特征词密度聚类以及相似度计算的热点发现研究D:硕士学位论文.电子科技大学, 2013.8 桓乐乐.基于马尔科夫模型词序因子的文本相似度研究D:硕士学位论文.湖北:湖北工业大学,2012.9 唐勇.互联网舆情监控系统的设计与实现D:硕士学

22、位论文.北京:北京邮电大学,2013.Abstract With the rapid development and popularization of the Internet, all kinds of MIS has become a part of digital campus construction. Graduation project is an important link of teaching system, but also guarantee the quality improvement. At present, most work need to manually

23、. This thesis through the analysis current selection of process and characteristics, design and implement a system, to perfect the teaching system, promote the construction of digital campus.The purpose of this system is: using B/S mode, simplify the topics of graduation design process to declare, so that teachers and students can not affected by time and geographical restrictions, completed the graduation design of doubly, and teachers provide students with th