基于VSM模型的文本相似度的比较

..毕业设计〔论文题目：基于VSM模型的文本相似性的比较姓名XXXXX学号AAAAA所在学院BBBBB专业班级CCCCC指导教师DDDDD日期摘要在互联网迅速发展的时代,网络上的信息数量越来越多,种类也比较纷杂。虽然能在我们查询相关信息是提供大量选择,但是靠人工浏览的方式在浩瀚的信息库中找到自己最需要最相关的信息,无疑给用户带来了麻烦,而且效率也十分低下。为了解决这一个问题,关于判断文本相似度的技术应运而生,目前广泛运用于计算机,电信等行业。本文着重阐述了计算文本相似度的过程中会遇到的难题,以及解决这些难题需要用到的相应算法,最后利用VSM模型进行简单的设计与运用,完成基于web的相似网页检测程序关键字：文本相似度；相似网页检测；VSM模型ABSTRACTWiththeInternetdevelopingrapidly,therearemoreandmoreInformationontheInternet,andthevarietiesofInformationisbecomingmorecomplex.AlthoughwehaveabiggerchancetousetheInformation,itisverydifficultandinefficientforuserstofindtheInformationwhichtheyaremostneededintheInformationDatabase.Tosolvethisproblem,therelevanttechnologyisinventedandnowwidelyusedinComputerandTelecomfield.Thispassageismainlydemonstratedtheproblemswemaymeetwhenwecalculatethetextsimilarityandtherelevantalgorithmsolvingtheproblemsabove.Intheend,weuseVSMmodeltodesignandcompletetheProject-SimilarWebdetectionBasedOnWebKeyWords：textsimilarity;similarwebdetection;VSMmodel目录TOC\o"1-4"\h\z\u摘要-1-ABSTRACT-2-目录-3-第一章绪论-6-1.1选题背景-6-1.2研究意义-6-1.3国内外研究现状-6-国外文本相似度研究状况-6-国内文本相似度研究情况-7-1.4开发语言-8-1.5本文的主要工作和论文结构-8-主要工作-8-论文结构-9-第二章系统原理介绍-10-2.1原理概述-10-2.2系统相关知识点简介-10-向量空间模型-10-中文分词技术-11-统计方法-12-算法-13-数据降维-16-相似度计算方法-16-2.3系统实现思想-17-第三章系统分析与设计-19-3.1系统需求分析-19-3.2系统功能概述-19-系统流程-19-功能模块介绍-20-3.3系统性能要求-21-第四章系统实现-22-4.1系统运行环境-22-4.2核心相关代码分析-22-分词类的介绍-22-核心代码解析-23-第五章系统测试-29-5.1文章分词测试-29-5.2获取关键字测试-29-5.3抓取网页内容测试-30-5.4计算文本相似度-30-第六章总结与展望-31-6.1总结-31-6.2展望-31-致谢-33-参考文献-34-附录Ⅰ中文-35-附录Ⅱ译文-39-第一章绪论1.1选题背景随着internet的迅猛发展,人们的生活越来越离不开网络。www<worldwideweb>技术以其使用直观、高效、简单等优点逐步成为Internet上最为重要的信息发布与交互方式,据美国因特网监制公司Netcraft发布的数据表明,截止20XX2月底,全球互联网网站数量超过1.6亿,达162662053,较前一个月增加了450万。网页数量也达到百亿级别。1.2研究意义由于WWW的迅猛发展,越来越多的信息可供用户在网上查询,但是信息膨胀和丰富的同时,加大了用户寻求自己最需要信息的负担,特别是目前用户对查询信息提出了新的需求,除了需要高效率,高准确性等要求外,用户有时需要在互联网上搜索与一篇文档〔例如txt文件、word文档等或一张图片最相关、最相似的信息,这就给目前的技术提出了新的挑战,而与文本相似度有关的算法应运而生。同时,我国学术论文抄袭现象频频发生,非法复制等文档侵权问题也比较严重。在如今的高校中,学生的论文抄袭、作业抄袭现象更是屡见不鲜。学生日益对自己的作业马虎了事,随便抄抄了事。尤其是对于有些枯燥的专业课程通常要进行实验并撰写电子实验报告,这就给不想动手动脑的同学以可乘之机。这种现象长此发展下去,不仅老师不能把握学生专业课程学习的情况,而且学生学习的积极性也会严重下降,抄袭的风气将影响到整个高校的学术氛围。那么文本进行相似度检测应用就成了眼下一个现实的需求。1.3国内外研究现状1.3.1国外文本相似度基本研究状况目前,国内外有很多学者在研究文本相似度计算问题并且已经有很多文本相似度模型被提出并得到广泛应用,如字符串相似度,文档结构相似度以及统计相似度等模型。字符串相似度模型将文档构成的基本单位视为字符串,通过将一个字符串转换为另一个字符串的替换、插入和删除操作次数或最大匹配字符串来计算相似度,如Levenshtein距离和Likelt方法。Nirenberg等也提出了两种串匹配的方法,即更规范的"切块+匹配+重组"方法和整句级匹配的方法。这两种方法所采用的相似度衡量机制都是词组合法。该系统的相似度计算采用罚分制,两个句子匹配所得到的总罚分值由句子中每个对应单词对的比较所得的罚分组合而成。文档结构相似度模型通过文档结构上的相似程度来计算文档的相似度,如：Lambros等提出同时依据句子的表层结构和内容计算相似度的方法。在计算相似度时,系统使用了两级动态规划技术,应用动态规划算法允许在两个长度不同的句子之间计算语句相似度。统计相似度模型：如GerardSalton和McGill于早期提出的向量空间模型,他的思想是把文档简化为以特征项的权重为分量的向量表示,通过词频统计与向量降维处理来计算相似度。基于向量的文本相似度计算方法是目前主流的文本相似度计算方法,该方法将要比较相似度的文本根据文本中的词语将文本映射为n维空间向量,然后通过比较向量间的关系来确定文本间的相似度,其中最常见的方式是计算空间向量间的余弦值,但传统向量空间模型就利用文本而不是用词来表示词语之间的关系。现在研究的主流方向就是基于空间向量模型。除了以上的模型以后还有一些其他方法被提出和发展。如：挪威Agdcr大学的VladimirOleshchuk等人提出基于本体的文本相似度比较方法,将本体论引入了文本相似度计算,它能计算文本的语义相似度。此外还有学者在研究句子间相似度的计算,如哥伦比亚大学的CarbonellJ.等人的最大边缘相关的MMR方法。1.3.2国内文本相似度研究情况在国内,国内学者盘谦红、王炬提出利用属性论计算文本相似度,建立了文本属性重心剖分模型,通过坐标点与坐标点的距离计算关键字与关键字的相关性,通过坐标点与单纯形的关系计算关键词与文本的相关度。张焕炯、王国胜、钟义信〔2001提出了基于汉明距离的文本相似度计算,该方法提出了汉明码的概念。与其他的文本相似度计算公式相比较,因为该方法只是利用模2加等运算,其方便性是不言而喻的,他完全避开了诸如在欧式空间中求相似度的大量乘法运算,因此,可以较大的提高速度。其次,它跳出了传统的借用空间的理念,而是用码字的方式来表征文本信息的特征,可以不仅限于关键字等孤立的信息,这为联合的描述文本的信息提供了可能。1.4开发语言JAVA语言。JAVA是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由SunMicrosystems公司于1995年5月推出的Java程序设计语言和Java平台〔即JavaEE,JavaME,JavaSE的总称。Java自面世后就非常流行,发展迅速,对C++语言形成了有力冲击。Java技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动和互联网,同时拥有全球最大的开发者专业社群。选择JAVA作为开发语言,一方面是因为自己对这种语言比较熟知,另一方面是因为它的确有着一些优于其他语言的特点：<1>Java是简单的Java与C++极为相似,但却简单得多。高级编程语言的所有特性中,不是绝对需要的都已删去了。例如,Java没有算符过载、标题文件、预处理、指针运算、结构、联合、多维数组、模板及隐式类型变换。<2>Java是编译型的当运行Java程序时,它首先被编译成字节代码。字节代码非常类似于机器指令,所以Java程序非常高效。然而,字节代码并不专对一种特定的机器,所以Java程序无需重新编译便可在众多不同的计算机上执行。<3>Java是可移植的Java程序是一次编译,处处运行。所以Java的移植却很容易,而且不需要进行重新编译。<4>Java是健全的Java程序不可能造成计算机崩溃。Java系统仔细检测对内存的每次访问,确认它是合法的,而且不致引起任何问题。不过,即使Java程序也可能有错误。如果出现某种出乎意料之事,程序不会崩溃,而把该例外抛弃。1.5本文的主要工作和论文结构1.5.1主要工作本文先介绍空间向量模型以及中文分词的相关基本知识,在此基础上,利用Java语言对某篇TXT文档进行分词、词频统计、选出关键词、调用Baidu搜索网页相关内容、下载网页页面、网页去标签获取主题内容、计算余弦值得出相似度,通过上述过程完成基于WEB的相似网页检测。本文的研究内容体现在以下四个方面：<1>VSM空间向量模型<2>中文分词策略<3>HTML解析策略<4>计算文本相似度1.5.2论文结构本文共分为六个章节,具体章节内容安排如下：第一章：绪论,介绍了选题背景和研究意义,然后粗略的讲述了国内外相关研究情况,最后介绍了本文的研究内容和文章结构。第二章：系统原理介绍,主要介绍了系统需要用到的相关知识点,例如向量空间模型、中文分词技术、相似度的计算方式、下载网页内容并进行解析等。第三章：系统分析与设计,主要阐述了基于WEB相似检测的需求和项目设计的思想和流程。第四章：系统实现,系统的核心代码和算法抽取出来进行详细的讲解和阐述。第五章：系统测试,抽取一个TXT文件进行测试,查看结果是否符合预期要求。第六章：总结与展望,总结做毕业设计过程的经验,吸取教训,展望未来的生活。最后是参考文献和致谢。第二章系统原理介绍2.1原理概述本系统是基于向量空间模型〔VSM来设计的。我们将一篇文档都看成一个向量,每个词作为向量的一个维度,而词的频率看成其值〔有向,即向量,这样每篇文章的词及其频率就构成了一个i维空间图,两个文档的相似度就是两个空间图的接近程度,即它们之间夹角的大小,我们通过计算余弦系数来体现。计算机不会像人一样自动识别文档里的每个词,所以要对文档进行分词处理,然后统计词频,最后根据余弦系数计算公式得出相似度比较结果。2.2系统相关知识点简介2.2.1向量空间模型VSM模型〔VSM：VectorSpaceModel即向量空间模型,由Salton等人于20世纪70年代提出,并成功地应用于著名的SMART文本检索系统。向量空间模型的基本思想为将文本简化为特征向量表示,将相似度计算问题简化为空间向量的运算,由此使得问题的复杂性大大降低。该方法根据文本中的词语将文本映射为n维空间向量,通过计算空间向量的余弦值来确定文本的相似度,即利用空间的相似性来解决文本上的相似性,直观易懂。通过向量空间模型,文本数据就转换成了计算机可以处理的结构化数据,两个文档之间的相似性问题转变成了两个向量之间的相似性问题。我们可以这样来理解一下向量空间模型。对于每篇文档来说,它都是由很多词条组成的。对此,我们可以对文档〔Document和其所包含的词条〔Term之间的关系进行一个研究。我们可以将一篇文档看成一个向量D〔term1,term2,……,termn。这样,假设某两篇文档中都出现了term1和term2,就可以用一个二维的坐标来表示文档和词条之间的关系,如图2-1所示。从图中可看出,文档1中Term1共出现3次,Term2出现1次；而文档2中Term2出现3次,Term1出现1次。所以,可以用向量D1〔3,1、D2〔1,3来表示这两篇文档。以此类推,一个搜索引擎的索引库,可以看成是一个由词条组成的N维向量空间。每一篇文档均为其中的一个向量。在这种情况下,文档之间就出现了特定的关系。例如,当两篇文档内容相近时,它们的词条也就差不多。因此,从逻辑上看,它们可能就会在这个向量空间中处于一种很"接近"的位置。此时,"接近"真实含义指的是这两个向量之间的夹角比较小。Term1Term2文档1文档2图2-1文档和词条的向量空间Term1Term2文档1文档2图2-1文档和词条的向量空间2.2.2中文分词技术众所周知,中文是世界上最复杂的语言之一。那么要对文本进行相似度计算,首先就要进行分词处理。分词,即将一段文本拆分成多个词。现有的分词方式主要有单字分词、二分法、词典分词。单字分词,顾名思义即在对中文文本进行分词时,以字为单位进行切分。按这种方式建立索引,则索引中所有的词条的集合就是中文汉字库的一个子集合。字索引比较灵活,但需要复杂的单字匹配算法,以及大量的CPU运算。二分法,即将每两个字当作一个词语进行切分,然后建立索引。它明显的减少了每个词条后位置信息的长度。如Lucene的CJKAnalyzer就是对中文采取二分的方式进行分词。本系统采用IKAnalyzer分词器进行分词,也相当于使用词典分词,是目前来讲分词比较准确的一种方法,即通过构造一个常用词词典来对遇到的文本进行词语的切分。中国科学院计算技术所研究的ICTCLAS在中文分词领域是较为先进的分词系统,其分词词典也是世界公认的精准。使用词典分词法在文本中匹配单词时用到一些常用的算法：正向最大匹配算法：从左到右将待分词文本中的几个连续字符与词库匹配,如果匹配上,则切分出一个词。逆向最大匹配算法：从被处理文档的末端开始匹配扫描,每次取最末端的2i个字符〔i字字串作为匹配字段,若匹配失败,则去掉匹配字段最前面的一个字,继续匹配。其采用的分词词典是逆序词典,对文档进行处理时先要进行倒排处理,生成逆序文档。有的时候,需多种方式对文本进行切分,当它们切分的结果相同,表示这个词就是真正需要的词。2.2.3TF统计方法TF的全称TermFrequency,也就是词条频率。用数学方法来描述即某个词语出现的次数除以该文档中的词条总数。常用于情报检索与文本挖掘,用以评估一个词对于一个文档的重要程度。如今在信息科学领域,比较经典的词频统计方法有基于匹配的词频统计算法和基于树结构的词频统计算法。对于单关键词匹配算法国内外都有了深入的研究,比较著名的匹配算法有BF<BruteForce>算法、KMP<Knuth-Morris-Pratt>算法、BM<Boyer-Moore>算法等。<1>BF算法BF算法亦称蛮力算法。其基本思想是：首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M]为止；若S[1]和T[1]不等,则T向右移动一个字符的位置,再依次进行比较。如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],则匹配成功；否则失败。<2>KMP算法KMP算法是由高德纳〔DonaldErvinKnuth和VaughanPratt在1977年合作发明的。其基本思想为：假设在模式匹配的进程中,执行T[i]和W[j]的匹配检查。若T[i]=W[j],则继续检查T[i+1]和W[j+1]是否匹配。若T[i]<>W[j],则分成两种情况：若j=1,则模式串右移一位,检查T[i+1]和W[1]是否匹配；若1<j<=m,则模式串右移j-next<j>位,检查T[i]和W[next<j>]是否匹配。重复此过程直到j=m或i=n结束。<3>BM算法BM算法由BobBoyer和JStrotherMoore在1977年提出,它是一个非常有效的字符串匹配算法。它的基本思想是：假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中,若发现不匹配,则下次应从主串的i+dist<si>位置开始重新进行新一轮的匹配,其效果相当于把模式和主串向右滑过一段距离distance〔si,即跳过distance〔si个字符而无需进行比较。基于匹配的词频统计方法,不可避免的是要对待处理的文档进行多次扫描。当待处理文档数据量比较大时,这无疑是要付出更高的时间和空间代价。针对这个问题,有学者又提出了基于树结构的词频统计算法。其基本思想是：首先根据已有的关键词集合构建一棵查找树,然后利用这个查找树对文档进行扫描,从而进行关键词的统计。进行词频统计时,非常好的是每当从文档中读取一个词与查找树比较时,只需对文档扫描一遍,则可统计出所有关键词的信息。这种方法减少了一些不必要的匹配过程,大大提高了统计效率。2.2.4TF-IDF算法TF-IDF简介TF-IDF〔termfrequency–inversedocumentfrequency是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式常被搜寻引擎应用,作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外,因特网上的搜寻引擎还会使用基于连结分析的评级方法,以确定文件在搜寻结果中出现的顺序。在一份给定的文件里,词频<termfrequency,TF>指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被归一化〔分子一般小于分母区别于IDF,以防止它偏向长的文件。〔同一个词语在长文件里可能会比短文件有更高的词频,而不管该词语重要与否。逆向文件频率<inversedocumentfrequency,IDF>是一个词语普遍重要性的度量。某一特定词语的IDF,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取对数得到。某一特定文件内的高词语频率,以及该词语在整个文件集合中的低文件频率,可以产生出高权重的TF-IDF。因此,TF-IDF倾向于过滤掉常见的词语,保留重要的词语。TF-IDF主要思想如果某个词或短语在一篇文章中出现的频率TF高,并且在其他文章中很少出现,则认为此词或者短语具有很好的类别区分能力,适合用来分类。TFIDF实际上是：TF*IDF,TF词频<TermFrequency>,IDF反文档频率<InverseDocumentFrequency>。TF表示词条在文档d中出现的频率〔另一说：TF词频<TermFrequency>指的是某一个给定的词语在该文件中出现的次数。IDF的主要思想是：如果包含词条t的文档越少,也就是n越小,IDF越大,则说明词条t具有很好的类别区分能力。如果某一类文档C中包含词条t的文档数为m,而其它类包含t的文档总数为k,显然所有包含t的文档数n=m+k,当m大的时候,n也大,按照IDF公式得到的IDF的值会小,就说明该词条t类别区分能力不强。〔另一说：IDF反文档频率<InverseDocumentFrequency>是指果包含词条的文档越少,IDF越大,则说明词条具有很好的类别区分能力。但是实际上,如果一个词条在一个类的文档中频繁出现,则说明该词条能够很好代表这个类的文本的特征,这样的词条应该给它们赋予较高的权重,并选来作为该类文本的特征词以区别与其它类文档。这就是IDF的不足之处.在一份给定的文件里,词频〔termfrequency,TF指的是某一个给定的词语在该文件中出现的频率。这个数字是对词数<termcount>的归一化,以防止它偏向长的文件。〔同一个词语在长文件里可能会比短文件有更高的词数,而不管该词语重要与否。对于在某一特定文件里的词语来说,它的重要性可表示为：以上式子中是该词在文件中的出现次数,而分母则是在文件中所有字词的出现次数之和。逆向文件频率〔inversedocumentfrequency,IDF是一个词语普遍重要性的度量。某一特定词语的IDF,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取对数得到：其中|D|：语料库中的文件总数：包含词语的文件数目〔即的文件数目如果该词语不在语料库中,就会导致被除数为零,因此一般情况下使用然后某一特定文件内的高词语频率,以及该词语在整个文件集合中的低文件频率,可以产生出高权重的TF-IDF。因此,TF-IDF倾向于过滤掉常见的词语,保留重要的词语。TF-IDF算法示例有很多不同的数学公式可以用来计算TF-IDF。这边的例子以上述的数学公式来计算。词频<TF>是一词语出现的次数除以该文件的总词语数。假如一篇文件的总词语数是100个,而词语"母牛"出现了3次,那么"母牛"一词在该文件中的词频就是3/100=0.03。一个计算文件频率<DF>的方法是测定有多少份文件出现过"母牛"一词,然后除以文件集里包含的文件总数。所以,如果"母牛"一词在1,000份文件出现过,而文件总数是10,000,000份的话,其逆向文件频率就是log<10,000,000/1,000>=4。最后的TF-IDF的分数为0.03*4=0.12。根据关键字k1,k2,k3进行搜索结果的相关性就变成TF1*IDF1+TF2*IDF2+TF3*IDF3。比如document1的term总量为1000,k1,k2,k3在document1出现的次数是100,200,50。包含了k1,k2,k3的docuement总量分别是1000,10000,5000。documentset的总量为10000。TF1=100/1000=0.1TF2=200/1000=0.2TF3=50/1000=0.05IDF1=log<10000/1000>=log<10>=2.3IDF2=log<10000/100000>=log<1>=0；IDF3=log<10000/5000>=log<2>=0.69这样关键字k1,k2,k3与docuement1的相关性=0.1*2.3+0.2*0+0.05*0.69=0.2645其中k1比k3的比重在document1要大,k2的比重是0.在某个一共有一千词的网页中"原子能"、"的"和"应用"分别出现了2次、35次和5次,那么它们的词频就分别是0.002、0.035和0.005。我们将这三个数相加,其和0.042就是相应网页和查询"原子能的应用"相关性的一个简单的度量。概括地讲,如果一个查询包含关键词w1,w2,...,wN,它们在一篇特定网页中的词频分别是:TF1,TF2,...,TFN。〔TF:termfrequency>。那么,这个查询和该网页的相关性就是:TF1+TF2+...+TFN。TF-IDF算法深度剖析在上面的例子中,词"的"站了总词频的80%以上,而它对确定网页的主题几乎没有用。我们称这种词叫"应删除词"〔Stopwords>,也就是说在度量相关性是不应考虑它们的频率。在汉语中,应删除词还有"是"、"和"、"中"、"地"、"得"等等几十个。忽略这些应删除词后,上述网页的相似度就变成了0.007,其中"原子能"贡献了0.002,"应用"贡献了0.005。细心的读者可能还会发现另一个小的漏洞。在汉语中,"应用"是个很通用的词,而"原子能"是个很专业的词,后者在相关性排名中比前者重要。因此我们需要给汉语中的每一个词给一个权重,这个权重的设定必须满足下面两个条件：<1>一个词预测主题能力越强,权重就越大,反之,权重就越小。我们在网页中看到"原子能"这个词,或多或少地能了解网页的主题。我们看到"应用"一次,对主题基本上还是一无所知。因此,"原子能"的权重就应该比应用大。<2>应删除词的权重应该是零。我们很容易发现,如果一个关键词只在很少的网页中出现,我们通过它就容易锁定搜索目标,它的权重也就应该大。反之如果一个词在大量网页中出现,我们看到它仍然不很清楚要找什么内容,因此它应该小。概括地讲,假定一个关键词w在Dw个网页中出现过,那么Dw越大,w的权重越小,反之亦然。在信息检索中,使用最多的权重是"逆文本频率指数"〔Inversedocumentfrequency缩写为IDF,它的公式为log〔D/Dw其中D是全部网页数。比如,我们假定中文网页数是D＝10亿,应删除词"的"在所有的网页中都出现,即Dw＝10亿,那么它的IDF＝log<10亿/10亿=log<1>=0。假如专用词"原子能"在两百万个网页中出现,即Dw＝100万,则它的权重IDF＝log<500>=6.2。又假定通用词"应用",出现在五亿个网页中,它的权重IDF=log<2>则只有0.7。也就只说,在网页中找到一个"原子能"的比配相当于找到九个"应用"的匹配。利用IDF,上述相关性计算个公式就由词频的简单求和变成了加权求和,即TF1*IDF1+TF2*IDF2+...+TFN*IDFN。在上面的例子中,该网页和"原子能的应用"的相关性为0.0161,其中"原子能"贡献了0.0126,而"应用"只贡献了0.0035。这个比例和我们的直觉比较一致了。2.2.5数据降维数据降维,是词频统计中所要考虑的一个因素。当文档中的词条数目很多,即向量的维度较高,那么为了提高效率,我们需要降低维度,即去除一些无关紧要的词语,减少词语的数量。而且采取降维的策略在一定程度上,还可以提高精度。文本特征向量降维主要有如下的两类：<1>特征选择：是指代去除那些不能表示信息或者表示的信息量很小的词<从广义上说：不存在不能表示信息或者意义的词,否则它就没有了存在的必要,自然这个词就无法存在>,以提高文本相似度计算的效率并且减少复杂度,基本上可以被分为如下几种方法：①根据单词的IDF值来进行判断：当单词的IDF值小于一个阈值或者大于另一个阈值的时候都要去除；②根据单词的文本频度TF值来判断：当单词的TF值小于或者大于某个给定的阙值也要去除；③根据X2统计量进行判断：其值越大,单词与文本之间的独立性越小,相关性越大,所以要去除X2小的词；·④根据互信息MI来进行判断：<MI>越大,两个单词之问的关系就越强。其中第一种方法效果较好。<2>特征重构：是通过合并或转化特征项来构造新的特征项,以达到降维的目的,一些文献中使用的奇异值分解方法就是这种思想的一种实现。2.2.6相似度计算方法基于向量空间模型,我们将两篇文档理解为两个向量,将它们之间的相似度理解为这两个向量在空间上的接近程度,即它们之间的夹角。我们通过计算余弦系数来比较两篇文章的相似度,余弦系数计算方法为,向量内积/各个向量的模的乘积,如图2-2所示。图2-2两个向量余弦值的计算其中,、分别为待比较的两个文本的特征向量,、分别为向量的第i维,n为特征向量的维数。余弦计算的好处是其值正好是一个介于0到1的数,如果向量一致就是1,如果正交就是0,符合相似度百分比的特性。为了让过程更加的简洁明了,下面举例说明：假设共有十个词：W1,W2,,W10,而共有三篇文章,d1,d2,d3。统计出文章的词频表,如图2-3所示。文档W1W2W3W4W5W6W7W8W9W10d112579d23468d3101112131415图2-3词频表的统计结果假设计算d1和d2的文本相似度,根据图2-2公式可得结论,如图2-4所示。图2-4向量余弦值的示例计算2.3系统实现思想我们将两篇文档当作两个向量,通过计算相似度来宏观的表现它们的接近程度。本系统主要按如下的思路进行：根据2.2节相关技术的介绍,本系统采用向量空间模型,主要流程可以细分为如下模块进行,分词处理,词频统计,选择关键字调用百度搜索查询,下载网页并解析,相似度计算。注释：分词处理主要利用IKAnalyzer分词器〔下面统一简称为IK分词器IKAnalyzer是一个开源的,基于java语言开发的轻量级的中文分词工具包。从20XX12月推出1.0版开始,IKAnalyzer已经推出了4个大版本。最初,它是以开源项目Luence为应用主体的,结合词典分词和文法分析算法的中文分词组件。从3.0版本开始,IK发展为面向Java的公用分词组件,独立于Lucene项目,同时提供了对Lucene的默认优化实现。在2012版本中,IK实现了简单的分词歧义排除算法,标志着IK分词器从单纯的词典分词向模拟语义分词衍化。其相关特性如下：<1>采用了特有的"正向迭代最细粒度切分算法",具有60万字/秒的高速处理能力。<2>采用了多子处理器分析模式,支持：英文字母〔IP地址、Email、URL、数字〔日期,常用中文数量词,罗马数字,科学计数法,中文词汇〔姓名、地名处理等分词处理。对中英联合支持不是很好,在这方面的处理比较麻烦.需再做一次查询,同时是支持个人词条的<3>优化的词典存储,更小的内存占用。支持用户词典扩展定义<4>针对Lucene全文检索优化的查询分析器IKQueryParser；采用歧义分析算法优化查询关键字的搜索排列组合,能极大的提高Lucene检索的命中率。第三章系统分析与设计3.1系统需求分析随着计算机的普及和网络的飞速发展,互联网上以及各种电子文档的数量以空前的速度增长,人们获取知识的途径也发生了深刻的变化。面对如此巨大的知识海洋,如何快速查找相关信息变得非常重要。如果没有有效的组织和提取方式,普通用户查找自己想要的信息所用的时间可能比了解信息本身所花费的时间还长,这是人们无法容忍的。文本相似度是表示两个或多个文本之间匹配程度的一个度量参数,相似度大,说明文本相似程度高,反之文本相似度低。对于文本聚类、信息检索、问答系统、网页去重、文本分类等很多领域,文本相似度的有效计算问题是其进行信息处理的关键。论文抄袭是一种严重的造假行为。当前出现的各种学术造假、论文抄袭现象,已严重的影响到整个高校的学术氛围。大学是一个要求学生独立自主学习的地方,而现在越来越多的学生放慢自己的行为,对老师布置的作业抄抄了事。这样老师既不能对学生的学习情况得到一个真实的掌握,学生学习的积极性也慢慢下降。这牵涉到的是一个诚信问题。诚信是社会道德的一道防线,也是大学生诚信责任的一道防线。现在这道防线岌岌可危,我们应采取积极地措施加以保护。本课题就在网上搜索与已经存在的TXT文件相似的内容做了一个系统设计。系统一方面在理论方面进行了一定的探究,了解了文档相似度相关方面的知识,另一方面在实际的应用上也有一定的价值。本系统只是简单实现了基本功能,有些地方还需进一步完善优化,用户可用此系统较为方便的搜索与自己已有文档相似的网页内容,老师也可以将此作为检查学生抄袭情况的工具,尽量减少学生抄袭的念头。3.2系统功能概述3.2.1系统流程首先,用户选择一个要查询的TXT文件,确定TXT文件所在的文件夹,然后是进行文档分词,统计词频,得到一个HashMap；排序后,选择所需数量的关键词后调用Baidu搜索相关的网页并下载；整理并去掉网页标签得到纯文本内容,提取内容存入到电脑；最后计算得到两篇文章的相似度。比较各个网页与原TXT文件的相似度,相似度越接近1则表示越相近；相似度越接近0则表示内容越来越不匹配。3.2.2功能模块介绍本课题设计的基于WEB的相似网页检测主要是进行一个理论的研究,可以搜索与TXT文件相似的网页内容,每一次检测的对象都是放在同一文件夹下,然后对文档进行相似度的检测。另外,本系统对图片、表格等是不进行识别和检测的。根据实际的需求,基于WEB的相似网页检测可以分成四个功能模块,如图3-1所示。基于WEB的相似网页检测基于WEB的相似网页检测分词统计模块调用Baidu查询模块下载网页解析模块计算文本相似度模块图3-1系统模块图各模块实现的功能如下：<2>分词统计模块此模块实现文本分词,并对分词进行统计。选择TXT文件所在的文件夹,读取文件内容存为字符串,利用IK分词器将字符串〔也就是文本内容进行分词,并且统计分词出现的次数,最后计算词频。<3>调用Baidu查询模块此模块实现调用Baidu对关键词进行网络查询。其中百度的查询代码是[此处为搜索的词语]&tn=monline_4_dg"抽取搜索的网页中的百度链接所用的方法是使用正则表达式://baidu/link\\?url=\\w+<\\S+>?\"<4>下载网页进行解析模块此模块对下载的模块进行解析。下载下来的内容为HTML语言,而我们只需要的是里面的文字内容,标签以及标签中的嵌套都不是我们所需。得到的纯文本内容写入文件。<5>文本相似度计算模块此模块实现对向量的计算,得出文本相似度。文件通过上述过程都转换成了计算机可以计算的向量空间,调用计算向量的函数得到一个介于0~1的结果。通过结果可以判定两个文本的相似程度。3.3系统性能要求<1>系统设计的合理性在设计系统时要考虑实际的系统性能和硬件要求,不能忽视所处环境,也不能一味地追求新的设计方法,要保证系统实现的合理性。<2>系统的简单易用性本系统侧重于对相似度检测进行一个理论的研究,所以并不需要过于美观、应用的界面,作为用户最终需要的只是两篇文档的相似度比较结果。因此设计时本着"简单易用"的原则,方便用户操作。<3>系统的可靠性要比较的两篇文档,可能是数据量很大的文本,就要考虑到系统运行的效率,采取相应的算法加以优化,尽可能的保证系统高性能有效的运行。第四章系统实现4.1系统运行环境1、硬件环境：处理器：InterCore或更高内存：2GB2、软件环境：操作系统：WindowsXP或者Windows7语言开发工具：Eclipse4.2核心相关代码分析4.2.1分词类的介绍<1>类org.wltea.analyzer.core.IKSegmenter：说明：这是IK分词器的核心类。它是独立于Lucene的Java分词器实现。当需要在Lucene以外的环境中单独使用IK中文分词组件时,可以使用IKSegmenter。publicIKSegmenter<Readerinput,booleanuseSmart>说明：IK主分词器构造函数参数1：Readerinput,字符输入读取参数2：booleanuseSmart,是否采用智能切分策略。true使用智能切分,false使用最细粒度切分。publicIKSegmentation<Readerinput,Configurationcfg>说明：IK主分词器新构造函数参数1：Readerinput,字符输入读取参数2：Configurationcfg,分词器配置。用户可以定制自己的Configuration类,来改变词典配置。publicsynchronizedLexemenext<>throwsIOException说明：读取分词器切分出的下一个语义单元,如果返回值为null,表示分词器已经结束。返回值：Lexeme语义单元对象,即相当于Lucene的词元对象Token说明：这是IK分词器的语义单元对象,相当于Lucene中的Token词元对象。由于IK被设计为独立于Lucene的Java分词器实现,因此它需要Lexeme来代表分词的结果。publicintgetBeginPosition<>说明：获取语义单元的起始字符在文本中的位置返回值：int,语义单元相对于文本的绝对起始位置publicintgetEndPosition<>说明：获取语义单元的结束字符的下一个位置返回值：int,语义单元相对于文本的绝对终止位置的下一个字符位置publicintgetLength<>说明：获取语义单元包含字符串的长度返回值：int,语义单元长度=getEndPosition–getBeginPositionpublicStringgetLexemeText<>说明：获取语义单元包含字符串内容返回值：String,语义单元的实际内容,即分词的结果4.2.2核心代码解析privatestaticMap<String,Integer>segString<Stringcontent>{//分词Readerinput=newStringReader<content>;//智能分词关闭〔对分词的精度影响很大IKSegmenteriks=newIKSegmenter<input,true>;Lexemelexeme=null;Map<String,Integer>words=newHashMap<String,Integer><>;try{while<<lexeme=iks.next<>>!=null>{if<words.containsKey<lexeme.getLexemeText<>>>{words.put<lexeme.getLexemeText<>,words.get<lexeme.getLexemeText<>>+1>;}else{words.put<lexeme.getLexemeText<>,1>;}}}catch<IOExceptione>{e.printStackTrace<>;}returnwords;}该函数主要实现分词功能,参数是读取TXT文件后存入变量中的字符串。利用IK分词器循环对字符串进行分词,得到的分词存入到HashMap中。其中HashMap键值对中key指的是分词,value是该分词在字符串中出现的次数。privatestaticHashMap<String,Double>tf<Map<String,Integer>segWordsResult>{HashMap<String,Double>tf=newHashMap<String,Double><>;if<segWordsResult==null||segWordsResult.size<>==0>{returntf; }Doublesize=Double.valueOf<segWordsResult.size<>>;Set<String>keys=segWordsResult.keySet<>;for<Stringkey:keys>{ Integervalue=segWordsResult.get<key>; tf.put<key,Double.valueOf<value>/size>;}returntf;}该函数实现词频的统计。参数为通过分词函数得到的〔分词,出现次数键值对的HashMap。而词频的计算方式为该词出现次数/总次数,即是Double.valueOf<value>/size。publicstaticMap<String,Map<String,Double>>allTf<Stringdir>{try{ ReadFile.fileList=ReadFile.readDirs<dir>;for<StringfilePath:ReadFile.fileList>{ Stringcontent=ReadFile.readFile<filePath>; Map<String,Integer>segs=segString<content>;allSegsMap.put<filePath,segs>;allTfMap.put<filePath,tf<segs>>; } }catch<FileNotFoundExceptionffe>{ ffe.printStackTrace<>; }catch<IOExceptionio>{ io.printStackTrace<>; }returnallTfMap;}该函数实现对一个文件夹下所有的TXT文件进行词频的统计。该函数的参数是一个文件夹路径名〔注意并非文件名,遍历读取文件夹下面的文件内容后用上面所说的segString函数对文件内容进行分词然后存储到Map中。返回值是一个嵌套的Map,Map<String,Map<String,Double>>中的前一个String代表文件路径名,后一个Map中的String代表一个分词,Double即是词频。publicstaticMap<String,Integer>getMostFrequentWords<intnum,Map<String,Integer>words>{ Map<String,Integer>keywords=newLinkedHashMap<String,Integer><>;intcount=0; //词频统计 List<Map.Entry<String,Integer>>info=newArrayList<Map.Entry<String,Integer>><words.entrySet<>>; Collections.sort<info,newComparator<Map.Entry<String,Integer>><>{publicintcompare<Map.Entry<String,Integer>obj1,Map.Entry<String,Integer>obj2>{returnobj2.getValue<>-obj1.getValue<>; } }>; //高频词输出for<intj=0;j<info.size<>;j++>{ //词-->频if<info.get<j>.getKey<>.length<>>1>{if<num>count>{ keywords.put<info.get<j>.getKey<>,info.get<j>.getValue<>>; count++; }else{break; } } }returnkeywords; }该函数实现功能是获取最高词频的分词,其中需要的最高词频的分词个数可以自己选择。其中排序算法用到了Java集合中的Collections.sort方法对list排序的方法。其中一种是list中的对象实现Comparable接口,另一种是根据Collections.sort重载方法来实现,本文采取后一种方式排序。值得注意的是后一种方式需要实现comparator接口中的compare方法。publicStringparse<Stringhtml>{ StringBuildersb=newStringBuilder<>;intstatus=0;//0-->notstart1-->startedfor<inti=0;i<html.length<>;i++>{charch=html.charAt<i>;if<status==0>{if<ch=='<'>{if<html.startsWith<"script",i+1> ||html.startsWith<"SCRIPT",i+1>> status=2;elseif<html.startsWith<"style",i+1> ||html.startsWith<"STYLE",i+1>>{ status=3; }else{ status=1; } }elseif<ch=='&'>{ //finda';'within5charsintk=1;for<k=1;k<5;k++>{if<html.charAt<i+k>==';'>break; }if<k<5> i+=k;else{ sb.append<ch>; } }elseif<ch==''||ch=='\r'||ch=='\n'||ch=='\t'>{ }else{ sb.append<ch>; } }else{if<ch=='>'>{if<status==1>{ status=0; }elseif<status==2>{if<html.startsWith<"/script",i-"/script".length<>> ||html.startsWith<"/SCRIPT", i-"/SCRIPT".length<>>>{ status=0; } }elseif<status==3>{if<html.startsWith<"/style",i-"/style".length<>> ||html.startsWith<"/STYLE", i-"/STYLE".length<>>>{ status=0; } } } } }returnsb.toString<>; }此函数主要实现了HTML去掉标签的功能,为了得到我们需要的网页内容,我们需要对下载的HTML代码进行去标签处理。去除脚本语言<script>和</script>以及样式<style>和</style>间的内容。第五章系统测试5.1文章分词测试选择需要进行分词的文件,我选择的测试文件为D:\\text\\LOLtEXT,测试结果如图5-1所示。图5-1文章分词测试结果结果显示了D:\\text\\LOLtEXT文件夹下的"新建文本文档.txt"文件的分词结果,以及词频tf的统计。由于分词比较多,上图只是部分截图。5.2获取关键字测试通过以上分词以及结果统计后,我们得到了文章的所有分词,此时我们需要抽取