毕业设计双选系统的设计与实现
计算机科学与技术隋旭宗
指导教师沙芸副教授
摘要随着互联网的不断发展，各类信息管理系统已成为数字化校园建设的一部分。毕业设计双选是教学的重要环节，也是毕业设计质量提高的基本保证。目前，毕业设计双选的大部分工作仍需要人工完成。本文通过对当前选题流程及特点分析，设计并实现一个毕业设计双选系统，以完善教学体系，促进数字化校园的建设。
本系统的目的是：简化毕业设计选题申报流程，借助B/S方式，使师生能够不受时间、地域的限制，完成毕业设计双选，并由指导教师向学生提供任务书。本系统的特点是：实现了题目及题目申报表的相似度计算。此功能借助Lucene完成分词操作，经过词频统计后，生成文档向量。系统实现了余弦相似度、Dice和Jaccard三种相似度计算方法。通过对不同算法的相似度比对结果进行评估，确定了相似度的阈值，并对这些结果进行讨论。
本系统为B/S结构，使用https://www.doczj.com/doc/d418728721.html,技术开发，拥有良好的用户体验。相似度比对能够快速有效地给出参考结果，减少了教师出题过程中因检索题目相似度而消耗的时间。
关键词毕业设计双选，文档向量，词频统计，文本相似度计算
1 绪论
1.1 研究背景和研究意义
毕业设计是高校教学任务的重要实践环节，是评估学生学位资格的依据之一。目前大多数院校仍沿用传统的选题方式，存在很大弊端。大部分学生不能从题目中了解到更多有效信息，很难评估题目的工作量和难易度。学生盲目选题，开题阶段不能顺利进行，教师需要修改甚至变更题目，给教师和学生增添了许多工作量。
随着毕业生人数逐年增加，毕业设计的题目数量也在增长[1]，人工分配学生可能产生错误。此外，教师通过人工筛查的方式不易得知题目是否重复，产生许多雷同或是相同的任务内容在所难免。规范毕业设计的管理流程，提高选题效率，不仅有助于改善毕业设计质量，还可以节约人力、物力成本。设计并实现一个B/S结构的毕业设计选题系统[2]，可以减轻教师的工作量，推动毕业设计工作进行。
数字化校园[3]最早是由麻省理工学院于上世纪70年代提出的。目前，西方发达国家的许多高校已经完成了数字化校园的建设工作。在毕业设计选题方面，英国的诺丁汉大学已经拥有了自己的毕业设计双向选择信息服务系统[4]，欧美国家的一般大学均实现了在线选题，同时可以进行在线评审、讨论[5]等。
1.2 需要解决的问题
针对学校当前的选题流程，设计并实现一个具有以下功能的毕业设计双选系统：
（1）教师出题，包括题目上传、查重及申报书相似度比对，给出相似度比对结果；
（2）学生选题，按需求查看题目（申报书）信息及下载任务书；
（3）师生双选，并由教师上传任务书及任务书相似度比对，给出相似度比对结果。针对毕业设计的题目和申报书中的内容，比对题目历史信息及申报书相似度；
（4）综合比较各种文本相似度的计算方法，选择区分度更好的，应用在申报书的相似度比对中，对题目、内容进行查重。
要完成以上功能，需要解决以下三个关键问题：
（1）段落主题是文本相似度比对的基本前提，设计并实现一种提取段落主题的方法；
（2）申报书之间的相似度主要通过段落相似度来计算，设计并实现一种主题段落相似度比对的计算方法； （3）对系统结构和相似度算法的优化。
2 毕业设计双选系统总体设计
2.1 总体结构
毕业设计双选系统的主要用户有：教师、学生、系统管理员。针对各个用户的特点，将系统功能进行划分，如图2.1所示：
2.2 E-R 图
本系统涉及的实体、属性以及相互之间的关系如图2.2所示：
毕业设计双选系统
题目 申报
题
目查重 申报书 维护
双选信 息管理
申报书管理
任务书 下载
课题 双选
任务书 上传
双
选管理
学生信息查询
系统参 数配置
选题信 息导出
高级权 限操作
当
前学年
选题数上限
数据可见性
图2.1 毕业设计双选系统模块划分图
2.3 动态模型
系统正常使用时，按照其涉及的主要事件及发生的先后顺序，脚本如下： □教师登录后，将申报书信息在页面上填写完毕。 □题目申报成功后，形成申报书，并交由教师审核。 □教师审核通过，此题目有效，学生可以看到此题目。
□学生登录后，向系统提交查询请求，如：按难易度降序排序。系统将查询结果显示给学生。 □学生提交选题申请，教师可以看到学生申请。 □教师通过学生信息，选择学生，如：张三。 □教师上传任务书，系统显示上传结果。 □学生提交下载任务书请求。
□系统与学生建立连接，将任务书发送至学生。 根据以上脚本，绘制事件追踪图如图2.3所示：
题目
题目信息
1
配置信息
修改人 修改
学生
选题
选题结果
申报书 教师
1 m n 双选
p q m
m n
图2.2 毕业设计双选系统实体及其联系图
3 文本相似度计算
查重作为毕业设计双选系统的重要功能之一，需要系统能够有效识别重复信息，给出两篇源文档的相似度比对结果。以词频为特征项，建立向量空间模型[6]，计算特征向量[7]的相似度，是解决此类问题的一种常用手段。
3.1 基于词频的相似度比较
本节以词频作为特征项T ，对一些相似度计算的方法进行比较分析。流程如图3.1所示，其中文档分析器使用的是Lucene 。
教师
题目申报类
题目双选类
学生
任务书类
填写申报信息 题目申报书 通过审核
完成题目申报 查询题目请求
申报书 选题申请
学生选题情况 选定学生 上传任务书
文件上传结果 下载任务书请求
任务书
图2.3 事件追踪图
待测文档
成分分析
特征项提取
语料库
文档分析器
提取器
信息过滤
输出结果
图3.1 相似度比较流程图
3.2 欧氏距离
欧氏距离通常指的是，两个点在n 维空间中的真实距离。在二维和三维空间中，欧氏距离就是两个点之间的实际距离。假设空间中存在两个点D 0、D 1，如图3.2所示，那么它们之间的欧氏距离为：
()()
2
011,i
i
i
Dist D D d x y ==
-∑ （3-1）
其中x i 和y i 表示这两个点各个特征项的权重。保持D 0和D 1的夹角大小不变，延长D 0至D'0，记Dist (D'0,D 1)=d 2，显然有d 1≠d 2。由此可见，特征项的权重大小会对欧氏距离造成直接影响，容易使相似度比较结果存在较大偏差。在继续对欧氏距离进行讨论前，先对余弦相似度进行分析。
3.3 余弦相似度
用词频构建一个简单的向量空间模型，结合余弦相似度[8]来进行文档相似度的比较。假设有两篇文档D 1和D 2，抽取出这两篇文档中包含的10个关键词w i （i =1,2,...,10）。经过对文档进行统计，得到这些词的词频如下：
w 1 w 2 w 3 w 4 w 5 w 6 w 7 w 8 w 9 w 10 D 1 4 2 9 3 1 D 2
1
1
5
2
4
1
1
则D 1={4,2,0,0,0,9,3,0,1,0}，D 2={0,1,1,5,2,4,0,1,0,1}。然后利用公式（3-2）计算它们的余弦相似度：
()()
12
122212
,i
i
i
i i
i
i
a b D D Similarity D D D D a b
?==
??∑∑∑ （3-2）
其中，a i 和b i 为对应关键词w i （i =1,2,...,10）的词频。上面所得结果的意义在于，余弦值越接近1，表明它们的夹角越接近0°。通过这个角度可以判断两个向量的相似度（如图3.3所示）。
y
x
z y
x
z
D 0
D 1
D'0
θ
d 1 d 2
图3.2 欧氏距离示意图
D 0
D 1
D'0
θ
Dice 系数和其十分相似，如式（3-3）：
()()()
12122
2
2
212
22,i i i
i i
i
i
a b D D Dice D D a b
D D ?=
=
++∑∑∑ （3-3）
比较欧氏距离和向量的夹角余弦，它们都可以用来进行个体间相似度的分析，但是在实际情况中，需要根据不同的数据模型，评估二者的性能。在空间中的两点，距离一定时，它们的夹角余弦值不一定相同。对进行文档的相似度比较时，空间向量很可能在高维空间中。欧氏距离更依赖个体的数值特征，而对维度不够敏感，容易导致度量标准不统一。而余弦相似度有效地避免了这个问题，不会受到指标刻度的影响，且所得结果的绝对值会落于[0,1]之间，比较这个数值的大小，可以得到向量之间的差异。
3.4 Jaccard 相似度
狭义的Jaccard 相似度描述为：两个集合A 和B 中，交集元素个数在并集元素个数中所占的比例，其可以表示为：
(,)A B J A B A
B
=
（3-4）
根据上式所得的相似度结果在[0,1]之间。其缺点是，仅靠元素是否存在来进行计算，而元素的其它属性则会被丢弃。
广义的Jaccard 相似度，可以用下式表示：
()
()
12
122
2
22
1212
(,)i
i
i
i
i i i i
i
i
a b D D E D D D D D D a
b a b *==+-+-*∑∑∑∑ （3-5）
其中，a i 和b i 为对应关键词w i （i =1,2,...,10）的词频。
与狭义的Jaccard 相似度不同的是，元素的取值可以是实数。从公式中可以看出它和余弦相似度有一些共同点，该方法也可以用来计算基于词频的文档相似度。
3.5 TF-IDF 算法
单纯使用词频来进行文档相似度比较存在一定的缺陷。这种方式没有考虑文档中词语的总数对结果的影响。x
y z D 0
D 1
D 2
θ2
θ1 x
y
z
图3.3 余弦相似度示意图
D 0
D 1
D 2
θ2
θ1
假如一个词w 在一篇100个词的文档D 1中出现了10次，在一篇1000个词的文档D 2中出现了20次，在只考虑词频的情况下，D 2可能对结果的影响更大一些，显然这是不合理的。
TF-IDF [5][9]算法即Term frequency -Inverse document frequency 算法。其中TF （词频）指一个词语在一个文档中出现的次数越多，说明这个词能够表现这个文档含义的可能性越大。IDF （逆文档频率）指的是如果一个词在某个文档集合中出现的次数很多，那么这个词对其中某些文档的贡献度就越小，因此可以通过IDF 来衡量区分文本的好坏程度。
3.6 实验及结论
本节以三组实验，验证Lucene 的分词效果，并对余弦相似度、Dice 、Jaccard 计算方法进行分析比较。
实验1 验证Lucene 分词效果。以两篇题目申报书为实验数据，其部分内容相似度极高。申报书比对结果如图3.4所示，可以看出相似度高的部分，其被标记内容达到85%以上；相似度低的部分其内容，其被标记内容少且分散。全分词器的分词效果良好，可以有效识别重复内容。
实验2 三种相似度计算方法的准确度。以毕业设计双选系统中的实际数据来对比余弦相似度、Dice 、Jaccard 计算方法。为了使数据更加清晰，以()1,2,3,...,10i T i =表示10篇数据库中的申报书。
将以上题目的基本信息与“基于句子结构分析的文本自动摘要算法的设计与实现”的基本信息进行比较。计算相似度时，分别利用余弦相似度（Cosine ）、Dice 系数、Jaccard 系数来得出结果，并给出真实相似度（S t ）。如表4-1所示：
图3.4 详细比对结果
表4-1 各相似度算法的计算结果及实际相似度
选题背景相似度选题意义相似度学生主要工作相似度
T i
Cosine Dice Jaccard S t Cosine Dice Jaccard S t Cosine Dice Jaccard S t
T10.0293 0.0293 0.0149 0.0239 0.0073 0.0066 0.0033 0.0025 0.1040 0.0897 0.0469 0.0645
T20.0719 0.0710 0.0368 0.0599 0.0157 0.0147 0.0074 0.0142 0.1782 0.1646 0.0897 0.1290
T30.1100 0.1053 0.0556 0.1100 0.0318 0.0299 0.0152 0.0286 0.1685 0.1672 0.0912 0.0645
T40.0000 0.0000 0.0000 0.0000 0.0118 0.0118 0.0059 0.0000 0.1555 0.1385 0.0744 0.0774
T50.4101 0.4100 0.2579 0.3853 0.2571 0.2567 0.1472 0.0286 0.2083 0.1943 0.1076 0.1548
T60.0482 0.0481 0.0246 0.0550 0.0309 0.0259 0.0131 0.0000 0.2048 0.1682 0.0918 0.1161
T70.4689 0.4688 0.3061 0.4037 0.0424 0.0278 0.0141 0.0571 0.1977 0.1919 0.1061 0.0516
T80.0455 0.0452 0.0231 0.0275 0.0674 0.0408 0.0208 0.0428 0.1640 0.1614 0.0878 0.1161
T90.4969 0.4944 0.3284 0.4587 0.2587 0.2338 0.1324 0.1714 0.3749 0.3645 0.2228 0.2323
T100.0981 0.0933 0.0490 0.0550 0.0543 0.0505 0.0259 0.1429 0.2605 0.2528 0.1447 0.1806 从结果中可以看出，利用Cosine和Dice得出的结果差异不大，而Jaccard得出的结果会减少50%左右，且部分结果会有较大的偏差。通过人实际估算的相似度通常比Jaccard得出的相似度要高，而比另外两种方式低。
实验3三种相似度计算方法的耗时。选取一定数量的文档，统一与某文档进行相似度比对。从分词开始计算时间，至得到计算结果结束。实验中所用的计算机处理器为Intel(R) Core(TM) i7-2670QM 2.20GHz，内存8.00GB。
表4-2 各相似度算法耗时
文档数量Cosine耗时(ms) Dice耗时(ms) Jaccard耗时(ms) 128 799 830 806
512 3262 3332 3311
1024 6318 6695 6596 对比三种计算方法耗时，结果相差不大。在文档数量较多时，余弦相似度计算方法会略快于其它算法。
4 总结与展望
本文通过对学校当前毕业设计双选情况的分析，对比国内外各高校在选题方面的不同，结合实际，设计了B/S 结构的毕业设计双选系统。
本系统基本可以实现题目申报、申报书管理、学生选题、师生双选、任务书上传等核心功能。使用本系统，教师申报的题目信息全部存储于数据库中，更加安全可靠，同时也有利于信息整合。学生通过本选题平台，能够获取的信息更加丰富，一定程度上避免了因对选题内容不了解而误选的尴尬。选题方式的灵活性更是传统选题方
法所不能及的。此外，在功能上还增加了双选信息的统计、导出，进一步简化了双选流程；查重模块的实现可省去教师人工比对相似度的工作。将本系统应用于学校中，可以有效促进数字化校园的建设。
在查重部分，简要介绍了目前广泛应用的文本相似度比对技术。实现了余弦相似度、Dice、Jaccard计算方法，验证了利用这些方法可以完成查重，并对它们的准确性、效率进行了比较。从结果上看，相似度比对基本能够满足查重需求。
本系统在功能上还可以有进一步的提升：
（1）提供学籍信息和注册信息的接口，使用户信息直接导入；
（2）结合JQuery，将部分页面的部分功能配合JavaScript实现，提升用户体验；
（3）使用带词性标注的分词方法，提高分词准确度。将此方法应用于段落主题提取，使用基于主题句的相似度比对，会有更好查重的效果；
（4）使用P/Invoke技术，将旧平台中好的相似度计算方法移植到系统中。
参考文献
[1] 吴海燕.基于WEB的毕业设计选题系统的设计与实现[D]:[硕士学位论文].内蒙古大学,2013.
[2] 李瑞.基于.NET的毕业设计选题系统的设计与实现[D]:[硕士学位论文].吉林:吉林大学,2012.
[3] 柏依彤.基于校园网的高校毕业设计选题系统的建模与设计[D]:[硕士学位论文].电子科技大学,2011.
[4] 胡巧婕.基于B/S的昌吉电大毕业设计选题系统的研究与设计[D]:[硕士学位论文].电子科技大学,2012.
[5] 柏依彤.基于.NET的高职论文选题系统的设计与实现[D]:[硕士学位论文].山东:山东大学,2013.
[6] 王秀红.文本相似度计算核函数的构造及其在分布式信息检索中的应用研究[D]:[博士学位论文].江苏:江
苏大学,2012.
[7] 韩晨靖.基于标题特征词密度聚类以及相似度计算的热点发现研究[D]:[硕士学位论文].电子科技大学,
2013.
[8] 桓乐乐.基于马尔科夫模型词序因子的文本相似度研究[D]:[硕士学位论文].湖北:湖北工业大学,2012.
[9] 唐勇.互联网舆情监控系统的设计与实现[D]:[硕士学位论文].北京:北京邮电大学,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. 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 the task book. The feature of this system is: implement the similarity calculation based on topic and reports. This function using Lucene to complete segmentation operation, after term frequency statistics, build the text vector. This system implement the cosine similarity, Dice and Jaccard. According to the similarity comparison results of different algorithms, determined the similarity threshold, and discussed.
This system is the B/S structure, use the https://www.doczj.com/doc/d418728721.html, technology to develop this system, own a good user experience. Reducing the time of retrieval topic by teachers, because the similarity comparison can gives reference results, rapidly and effectively.
Key words graduation project double-channel choosing, text vector, term frequency statistics, text similarity computing