文本相似度计算

文本相似度计算系统

摘 要

在中文信息处理中，文本相似度的计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域，是一个非常基础而关键的问题，长期以来一直是人们研究的热点和难点。本次毕设的设计目标就是用两种方法来实现文本相似度的计算。

本文采用传统的设计方法，第一种是余弦算法。余弦算法是一种易于理解且结果易于观察的算法。通过余弦算法可以快捷的计算出文本间相似度，并通过余弦算法的结果（0、1之间）判断出相似度的大小。由于余弦计算是在空间向量模型的基础上，所以说要想用余弦算法来完成本次系统，那么必须要将文本转化成空间向量模型。而完成空间向量模型的转换则要用到加权。在空间向量模型实现之前，必须要进行文本的去停用词处理和特征选择的处理。第二种算法是BM25算法，本文将采用最基础的循环来完成，目的是观察余弦算法中使用倒排索引效率是否提高有多大提高。

本次文本相似度计算系统的主要工作是去除停用词、文本特征选择、加权，在加权之后用余弦算法计算文本的相似度。在文本特征选择之后用BM25计算相似度。由于为了使系统的效率提高，在程序设计中应用了大量的容器知识以及内积、倒排算法。

关键词：文本相似度；余弦；BM25；容器

Text Similarity Algorithm Research

Abstract

In Chinese information processing，text similarity computation is widely used in the area of information retrieval，machine translation,automatic question—answering，text mining and etc．It is a very essential and important issue that people study as a hotspot and difficulty for a long time．Currently，most text similarity algorithms are based on vector space model(VSM)．However,these methods will cause problems of high dimension and sparseness．Moreover，these methods do not effectively solve natural language problems existed in text data．These natural language problems are synonym and polyseme．These problems sidturb the efficiency and accuracy of text similarity algorithms and make the performance of text similarity computation decline．

This paper uses a new thought which gets semantic simirality computation into traditional text similarity computation to prove the performance of text similarity algorithms．This paper deeply discusses the existing text similarity algorithms and samentic text computation and gives a Chinese text similarity algorithm which is based on semantic similarity．There is an online information management system which is used to manage students’graduate design papers．Those papers ale used to calculate similarity by that the algorithm to validate that algorithm．

This text similarity computing system's main job is to stop word removal, text feature selection, weighting, after weighting using cosine algorithm to calculate the similarity of the text. After the text feature selection calculation of similarity with the BM25. Because in order for the system's efficiency, knowledge application in programming a lot of containers as well as the inner product, the inversion algorithm 

KEY WORDS：Text similarity；cosine；BM25；container

目  录

1 绪论    1

1.1 开发背景    1

1.2 课题研究意义    1

1.3本课题要解决的问题    1

2 研究方法    3

2.1根据研究的侧重点阐述相关的研究方法    3

2.2历史以及研究现状    3

3关键问题及分析（一）（余弦）    6

3.1 研究设计中的关键问题    6

3.2 具体实现中采用的关键技术    6

3.2.1 容器    6

3.2.2 倒排    7

3.2.3 内积    7

3.2.4 算法    8

3.3本章小结    6

4关键问题及分析（二）（BM25）    6

4.1 研究设计中的关键问题    6

4.2 具体实现中采用的关键技术    6

4.2.1 容器    6

4.2.2 算法    7

4.3本章小结    6

5系统设计及实现    9

5.1设计实现的策略和关键技术描述    9

5.2分模块详述系统各部分的实现方法    10

5.2.1 文档载入模块    6

5.2.2 去除停用词模块    6

5.2.3 特征选择模块    6

5.2.4 加权模块    6

5.2.5 余弦计算模块    6

5.2.6 BM25计算模块    6

5.2.7 相似度显示模块    6

5.2.8 相似度导出模块    6

5.3程序流程    11

5.4界面设计    12

5.5测试环境与测试条件    12

5.6实例测试(表格)    12

5.7性能分析    12

6 结论与展望    35

参考文献    36

致  谢    37

1绪论

随着计算机的广泛应用和Intemet的普及，各类信息都在急速地膨胀。信息量的增长给人们带来了方便，同时也带来了信息过量的问题。面对海量信息，人们越来越希望能够在数据分析的基础上进行科学研究、商业决策和企业管理，带来经济效益或社会效益。在现实世界中，文本是最重要的信息载体。因此对文本文档的处理和分析成为当今数据挖掘和信息检索技术的热点之一。处理和研究文本文档的技术有很多，其中重要的一个技术就是文本相似度，它在文本聚类、Web智能检索、问答系统、网页去重、自然语言处理等很多领域中有着重要的应用，文本相似度是这些应用的关键。

本次目标就是做出文本相似度的计算工具，用两种算法来计算文本间的相似度。

1．1开发背景：

文本相似度有着比较广泛的应用，典型的应用有：(1)信息智能检索：搜索引擎对用户输入关键字的反应是列出所有与该关键字相匹配的网页。这些网页的数量之大，往往要以十万百万来计量，而且对于某一关键字检索出来的网页有可能对应于不同的主题。这些各种主题的网页有些没有相关性，有些内容很相似。这种各类主题杂乱在一起的搜索结果和冗余页面给用户找到自己感兴趣的信息带来极大的不便。如果利用文本相似度技术，对搜索结果进行进一步的处理，在搜索结果中将相似度很高的信息分为不同类别，或者去掉相似度很高的重复的信息，为用户提供一个清晰的导航。这将大大的有利于用户发现自己感兴趣的信息，提高信息检索的质量。(2)自动问答系统：在这种系统中，问题是多种多样，且非常巨大的，有些问题是非常相似的，如果用人工来回答，将耗费大量的时间和人力，如果在这种系统中应用文本相似度技术，将相似度很高的问题归为一类，使系统对这类问题自动做出答复，将节省大量的时间。(3)文本查重：在某些领域，考虑到隐私性和独创性，要求文本不能重复出现，那么应用文本相似度技术，对这类文本进行相似度的计算，就可以看出哪些文本多次出现。因此，研究文本相似度的算法具有重要的实际价值。

1．2课题研究意义

文本相似度计算系统是自然语言处理的一部分，可以计算一个文本中不同词条的相似度，可以计算俩个文本间的相似度也可以进行批处理，对多个文本之间进行两两计算，并输出文本间相似度的最后结果。

文本相似度除了简单的计算相似度外，还可以在其基础上进一步发展，成为其他的功能软件。其中最主要的体现就是检索工具与信息挖掘，例如：语义检索、招聘信息检索等。在这些软件中，文本相似度计算系统起到了决定性的作用。

文本相似度计算系统中的去除停用词功能、文本特征选择以及加权功能还可以单个的拿出，作为单独的一个程序或者成为其他系统的一部分。

1．3本课题要解决的问题

文本相似度计算系统包括去除停用词、文本特征选择、加权、余弦算法、BM25算法。

在去除停用词中，主要的问题就是选词范围和set容器的使用。由于给出的词语前面是有词性的，所以在选词的时候要注意将词性去掉。这样才能得到准确的结果。虽然去除停用词这一功能十分的简单。但是由于它是第一个功能，所以一定要保持它的正确性。

文本的特征选择目的是选出那些重要但是又不是每行都有的词，并且输出该词语的特征量。所以在特征选择这一项，我在程序中做了三个模块，选出那些特征为一的特殊词语，并且删除。由于BM25计算方法是在特征选择之后进行的，所以在这一部分还特别为BM25就算出了不为一的文本等。

加权是在文本特征选择之后，是为余弦做准备。通过加权可以得到文本的空间向量模型，由于该结果为全数字，所以要十分的主要加权的准确性。

余弦算法作为该程序的两个算法之一，是该程序的灵魂所在，在余弦算法中除了VC基本知识、容器之外还用到了倒排索引和内积。余弦算法也是该程序的难点之一。

BM25算法是一种很陌生的算法，很多人都可能是第一次听过，BM25算法具有准确这一特点，是一种十分专业的算法。BM25算法中只用到了循环，目的是验证倒排索引、内积等方法可以提高多少效率。

2研究方法

2．1根据研究的侧重点阐述相关的研究方法

目前较为常用的相似度计算方法有许多，例如本次程序要用到的余弦相似度就算方法和BM25相似度计算方法。除此之外内积相似度计算方法，SMART相似度计算方法、Pivoted Normalisation相似度计算方法、Log-linear相似度计算方法等。但是由于相似度的用途、方法等原因，很多方法都是不常见的。

余弦算法作为大家熟知的计算方法而被广泛的应用。在本次程序中，主要的流程就是将语料去除停用词，之后进行文本的特征选择，将特征项为一的和特征项与文本数相同的去掉。接下来进行文本加权，将语料变为一个空间向量模型。最后通过内积与倒排索引按照余弦公式最终计算出文本间的相似度大小。

BM25算法是一种严谨的计算方法，在此次项目中，进行特征选择之后就可以开始进行计算了。BM25比余弦好的地方在于其不用经过加权形成空间向量模型，但是它在公式中也有一部类似加权的计算步骤。

2．2历史以及研究现状

目前，国内外很多学者在研究文本相似度计算问题，并提出了一些解决方案和技术，在这些技术中，Salton等人(1975)提出的向量空间模型(VSM)是最常用的方法。

Salton等人(1975)的观点是，向量空间模型VSM的基本思想是把文档简化为以特征项的权重为分量的向量表示，它假设词与词间不相关，用向量来表示文本，从而简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备了可计算性。这种机制通过为文档中的索引项分配权重来实现。权重应该能体现关键词的重要程度，是对整个文档的描述能力，和区别其他文档的区分能力的量化。特征项的权重计算一般利用统计的方法获得，通常使用词频来表示。基于向量的文本相似度计算方法是最常用的文本相似度计算方法，该方法将要比较相似度的文本根据文本中的词语将文本映射为n维空间向量，然后通过比较向量间的关系来确定文本间的相似度，其中最为常用的方法是计算向量间的余弦系数。Frakes等人(1992)的观点是，向量空间模型的最大优点在于它在知识表示方法上的巨大优势，在该模型中，文本内容被形式化为空间中的一个点，通过向量的形式给出，把对文本内容的处理简化为向量空间中向量的运算。潘有能(2002)，鲁松(2000)等人的观点是，向量的权重计算可以通过简单的频数统计来完成，使问题的复杂性大为降低。向量空间模型的缺点在于关键词之间的线性无关的假说前提。在自然语义中，词或短语间存在十分密切的联系，很难满足假定的条件，因此对计算结果的可靠性造成一定的影响。此外，将复杂的语义关系归结为简单的向量结构，丢失了许多有价值的线索。因此，引进改进技术以获取深层语义结构是有必要的。同时权值计算是相似度计算里面关键的部分，如何定义最准确的权值也是向量空间模型要考虑的一大问题。

此外其他学者在文本相似度计算方法上也提出了不同的见解，如哥伦比亚大学的Carbonell J．等人(1998)提出的最大边缘相关的方法MMR(Maximal Marginal Relevance)方法。Lambms等人(1994)提出同时依据句子的表层结构和内容计算相似度的方法。在计算相似度时，系统使用了两级动态规划技术，应用动态规划算法允许在两个长度不同的句子之间计算语句相似度。Nirenburg等人(1993)提出了两种串匹配的方法，即更规范的“切块+匹配+重组”方法和整句级匹配的方法，这两种方法所采用的相似度衡量机制都是词组合法。该系统的相似度计算采用罚分制，两个句子匹配所得到的总罚分值由句子中每个对应单词对的比较所得的罚分组合而成。其它方法还有根据Ricardo(2005)所提到的Belkin和Croft于1992年提出的概率型。

Lee(2005)、Lipika(2006)、Ong(2006)和Blaz(2006)等人的观点是，一个类别主要是以用机器学习的方法，比如聚类分析和模糊逻辑去构造文本的本体模型，然后用这些模型，根据Navigli(2005)、Sugumaran(2005)等人的观点，对文本进行处理。但是，这些方法需要分析整个文档语料库去构造一个好的本体模型，而且文本处理的好坏取决于构造本体模型的良好程度。在语料分析中，一些项在文本中很少出现，因为他们的出现频率很低，而往往被忽视。然而，根据信息理论，这些少见的项却对文本处理来说是有价值的。忽视他们在构建本体模型的时候可能会影响文本处理的性能。这些基于本体的方法也没有完全能和LSI抗衡。

    

3关键问题及分析（一）（余弦）

3.1 研究设计中的关键问题

余弦:关键问题是先要明确余弦的相关定义，理解公式每个地方代表了什么，之后理解相关定义的内容，最后结合C++中的容器知识解决问题。

去除停用词

预处理：在计算余弦算法之前，必须要有预处理的过程，其中包括去除停用词和特征选择。去除停用词主要就是按照停用词表中的词语将语料中不常见的符号，标点级乱码去掉。在去除停用词中除了用到基本的输入输出流，还用到了set容器。set容器重要作用在本次去除停用词过程中存储“哈工大停用词表”，在用循环输入“三类语料”，如果在set容器中就去掉，不在就输出。set容器是容器中最常用也是最基础的知识，下面具体介绍了set容器的基本操作。

set容器：定义一个元素为整数的集合a，可以用set a;

基本操作：对集合a中元素的有

插入元素：a.insert(1);

删除元素（如果存在）：a.erase(1);

判断元素是否属于集合：if (a.find(1) != a.end())

特征选择：

特征选择的目的：特征选择也属于预处理中的一部分，其最终的目的是将文本中只在一行出现的词语和在每行都出现的词语去掉。

特征选择的实现方法：

在特征选择中用到了set、map、multimap三中容器。

首先用set容器来存放去停用词后的文本。在这里set起到的功能与去除停用词中功能是一样的。 map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性map内部的实现自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能。由于map容器排序的特性，得到得特征排序的很乱的，所以用到了multimap。Multimap所起到的作用就是一个排序的作用，他使得最终结果按特征选择的值来排序，为后面的去除做一个准备。

在进行文本的特征选择之后要像去除停用词一样去除特征为1的和特征数等于文本行数的特征。因为特征为1的表示特征过小，只在一行出现，对文本的影响不大。而特征数过大的与文本行数相等的说明每一行都出现了，不具有代表行。

加权：由于用余弦来计算相似度，所以引入了空间模型的概念。

G.Salton提出的向量空间模型（VSM）有较好的计算性和可操作性，是近年来应用较多且效果较好的一种模型，向量空间模型最早成功应用于信息检索领域，后来又在文本分类领域得到了广泛的运用。向量空间模型的假设是，一份文档所属的类别仅与某些特定的词或词组在该文档中出现的频数有关，而与这些单词或词组在该文档中出现的位置或顺序无关。也就是说，如果将构成文本的各种词义单位（如单词i、词组）统称为“词项”，以及词频在文本中出现的频数称为“词频”，那么一份文档中蕴含的各个词项的词频信息足以用来对其进行正确的分类。在向量空间模型中的文本被形式化为n维空间中的向量：

其中为第i个 特征的权重。

向量空间模型：向量空间模型重简单方面说就是一个完全由向量所组成的文本，由于余弦算法是按照向量的夹角来计算的，所以必须通过加权来计算出每个词语的权重。

加权公式： 其中N为文本的总行数，n为出现该词语的总行数。

3.2 具体实现中采用的关键技术

3.2.1 容器

本系统主要运用的map容器和vector容器的相关知识。下面先介绍map容器相关的知识：

map容器：Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。

下面举例说明什么是一对一的数据映射。比如一个班级中，每个学生的学号跟他的姓名就存在着一一映射的关系，这个模型用map可能轻易描述，很明显学号用int描述，姓名用字符串描述。

Vector容器的相关知识如下：vector是C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector是一个容器，它能够存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，可以动态改变大小。

3.2.2 倒排索引

倒排索引的概念：这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件

倒排的应用：倒排的目的是为了使计算的方法简便，使程序的效率提高。倒排就是用map >dp这样一个大的复合容器来将结果显示为3列。

for(map >::iterator i=dp.begin();i!=dp.end();i++)

    {

    for(map::iterator j=i->second.begin();j!=i->second.end();j++)

    {

                  write<first<<" "<first<<" "<second<<"\\n";

            

    }

这样就将文件成一个3列的输出，为后面的内积计算做了一个铺垫。

3.2.3 内积

内积（inner product），又称数量积（scalar product）、点积（dot product）他是一种矢量运算，但其结果为某一数值，并非向量。

设矢量A=[a1,a2,...an]，B=[b1,b2...bn]

则矢量A和B的内积表示为:

A·B＝a1×b1＋a2×b2＋……＋an×bn

A·B = |A| × |B| × cosθ

|A|=(a1^2+a2^2+...+an^2)^(1/2);

|B|=(b1^2+b2^2+...+bn^2)^(1/2).

其中，|A| 和 |B| 分别是向量A和B的模，是θ向量A和向量B的夹角（θ∈[0,π]）。若B为单位向量，即 |B|=1时，A·B= |A| × cosθ，表示向量A在B方向的投影长度。向量A为单位向量时同理。

3.2.4 算法

初看余弦相似度的公式，不明所以的人一定会对复杂的数学符号感到头疼，其实大可不必，下面我摘录了一个比较通俗易懂的余弦相似度的解释：

在向量空间模型中，文本泛指各种机器可读的记录。用D（Document）表示，特征项（Term，用t表示）是指出现在文档D中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D(T1，T2，…，Tn)，其中Tk是特征项，1<=k<=N。例如一篇文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为D(a，b，c，d)。对含有n个特征项的文本而言，通常会给每个特征项赋予一定的权重表示其重要程度。即D＝D(T1，W1；T2，W2；…，Tn，Wn)，简记为D＝D(W1，W2，…，Wn)，我们把它叫做文本D的向量表示。其中Wk是Tk的权重，1<=k<=N。在上面那个例子中，假设a、b、c、d的权重分别为30，20，20，10，那么该文本的向量表示为D(30，20，20，10)。在向量空间模型中，两个文本D1和D2之间的内容相关度Sim(D1，D2)常用向量之间夹角的余弦值表示，公式为：

    其中，W1k、W2k分别表示文本D1和D2第K个特征项的权值，1<=k<=N。

在自动归类中，我们可以利用类似的方法来计算待归类文档和某类目的相关度。例如文本D1的特征项为a，b，c，d，权值分别为30，20，20，10，类目C1的特征项为a，c，d，e，权值分别为40，30，20，10，则D1的向量表示为D1(30,20,20,10,0),C1的向量表示为C1（40，0，30，20，10），则根据上式计算出来的文本D1与类目C1相关度是0.86

那么0.86具体是怎么推导出来的呢？

在数学当中，n维向量是 V{v1, v2, v3, ..., vn}

他的模： |v| = sqrt ( v1*v1 + v2*v2 + ... + vn*vn )

两个向量的点击 m*n = n1*m1 + n2*m2 + ...... + nn*mn

相似度 ＝ (m*n) /(|m|*|n|)

物理意义就是两个向量的空间夹角的余弦数值

下面是代入公式的过程：

d1*c1 = 30*40 + 20*0 + 20*30 + 10*20 + 0*10 = 2000

|d1| = sqrt(30*30 +20*20 + 20*20 + 10*10 + 0*0) = sqrt(1800)

|c1| = sqrt(40*40 + 0*0 + 30*30 + 20*20 + 10*10) = sqrt(3000)

相似度 = d1*c1/(|d1|*|c1|)= 2000/sqrt(1800*3000)= 0.86066

3.3本章小结

本章主要介绍了余弦相似度的具体算法，余弦计算前去除停用词、文本特征选择、加权和如何利用c++中的容器来书写程序描述这个算法。对于一个给定的算法，我们主要的精力是研究如何用程序来实现这个算法，我个人觉得这个有些南辕北辙的味道，我们应该从最深处理解算法的精髓，能写出算法的人是大师，而用程序实现算法的人只是一个程序员，由于个人的原因，本人的数学功底有些差，但是我会再以后的道路上努力弥补自己的不足，完善自我。

4关键问题及分析（三）（BM25）

4.1 研究设计中的关键问题

本章节主要面对的问题是

1.BM25的数学公式是什么？

2.BM25公式的主要的参数是什么意思？

3.用程序实现BM25的算法用到哪些相关的知识？

4.2 具体实现中采用的关键技术

4.2.1 容器

本章主要用到了map容器和vector容器。

解释map容器：Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，在map内部所有的数据都是有序的。

Vector容器的相关知识如下：

vector是C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector是一个容器，它能够存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，可以动态改变大小。

4.2.2 算法

BM25通常用于信息检索的领域，它是一种用于排序跟搜索关键词相关的文本的一种排序的函数，最早在1970年，由S. E. Robertson等提出的，基于概率检索的框架（probabilistic retrieval framework）发展。BM25是一个bag-of-words的检索函数，综合了特征在文本中的词频、以及在语料中的文档频度、平衡了文档的长度等特征。这个函数有很多变种，其中应用最普遍的计算方法，如公式（5.2）所示：

（5.2）

其中是用来计算的检索的query的向量=，代表向量的关键词的个数；是语料中的一个样本向量，代表向量特征个数；是检索词的在样本中的出现的次数；表示文档的长度(指文档中词语的个数，包括重复的词语)；是中的query检索到的全部样本的平均长度。和是自由参数，通常情况下，取值为2.0，取值为0.75。是文档频度的倒数，是检索词的权重，计算如公式（5.3）所示：

（5.3）

其中是整个数据集上的文档总数，是指包含检索词的文档数。在实际计算中，值有可能是负数，使得的BM25值也有可能是负数，由于BM25公式中偏重于未出现检索词和出现索引词的样本数的比重，对于DF值较高的索引词，未出现索引词的文档个数有小于DF值，取log之后的值变为负值。在本文的实验中去掉了BM25值为负数的样本。

4.3本章小结

  BM25算法计算相比余弦算法过程要简单的多，但是我只是运用了一个循环的方法，目的是看用“倒排”的效率，结果“不看不知道,一看下一跳”。结果不是差了一点半点啊。使用“倒排”的效率大大提高。

  关于BM25算法的结果，个人表示没有余弦好理解，因为他的结果是无规律且大小相差很多，非专业人员（我）无法用BM25来看出相似度到底有多少，而余弦的结果是0~1之间的，可以一目了然的看到两篇文本的相似度是多少。

  通过了BM25的实现，使我的数学有了提高，而且更加深入的了解到了如何编算法，以前总感觉算法是很难实现的，但是现在感觉已将给了公式，这样逻辑就很明了了。相信下次我会编的更好。

5系统设计及实现

本章从系统的实现过程，各模块的功能、各模块间的关系、界面设计及测试等几个方面阐释了系统的具体实现。

5.1设计实现的策略和关键技术描述

在上边的讲解里提出了关于本程序的相关模块，在这一节里将对每个模块进行详细讲解，并对其实现方法进行描述。通过设计方案可以确定出本程序主要分为如下模块：文档载入模块、去除停用词模块、加权模块、特征选择模块、余弦算法模块、BM25算法模块、相似度显示模块，相似度导出模块。

5.2分模块详述系统各部分的实现方法

5.2.1文档载入模块

获取文件的信息可包括两个方面，一个是获取原文本文档（三类语料.txt）中的翻译信息，一个是获取停用词表（哈工大停用词表.txt）中的信息。下面分别对获取文本文档中的原文信息和获取停用词表中的信息进行详细的介绍。

1）获取文本文档（三类语料.txt）中的翻译信息

文本文件（txt）文件的格式相对比较简单，本程序用C++语言读取文本文件的方法读取原文的信息。用了C++语言中的getline方法读取文件信息，之后用C++语言中的istringstream函数进行分词操作。原文格式如下：

2）获取文本文档（哈工大停用词表.txt）中的翻译信息

获取停用的操作相对来说简单了些，因为每个停用词独占一行，用C++语言的读一行文件的操作即可，此处就不做详述了。

5.2.2去除停用词模块

去除停用词的目的是去除停用词表中的词语，因为一个刚刚分好词的文本会有许多不重要的词或符号。去除停用词的操作是一个非常常见的教科书程序，而且在我的印象中还做过相关课设，去除停用词的方法主要就是一个循环，但是由于这次要去除的词是在一个文本中，所以要用到一个set容器。

5.2.3特征选择模块

特征选择模块的最终目的一共有两个，一个是输出每个词的特征，即在文本中有多少行含有该词。另一个目的就是去除特征为一的词语和特征等于该文本的总行数的词语，因为程序的最终目的是比较相似度，特征为一的就表示该词不是一个由代表性的词语，而特征数与总行数相等则说明了有无该词对相似度的结果是没有影响的。所以我们对原文做了如下特征选择的操作，去除每篇文章都出现的单词或者有且仅有只在一篇文章中出现的单词。

5.2.4加权模块

对权值的解释：

权值就是指这个指标在整个分析过程中所占的重要程度，比如 你买辆车 你对车的属性有几方面认识——假定只有3个方面 质量 价格 舒适程度

你认为 这个质量对你最重要 你赋权值为0.5 价格其次重要 赋值0.3 舒适程度适当考虑 并赋值0.2 

OK 我们可以以此为标准来评判

你看中了车A 给它三方面打分质量90 价格80 舒适80

车B 质量80 价格90 舒适80 

然后 你把这些分数乘以相应的权值 可以有

A的得分90*0.5+80*0.3+80*0.2=85

B的得分80*0.5+90*0.3+80*0.2=83

故A车对你是较好的选择

权值就是这样在问题分析中起到重要作用

一般的 权值累加为1 实际上 这只是习惯 不为1 而为任意正数都没有关系 

我们在此处用了如下的加权公式：

（写公式）

下面是对公式的通俗解释（摘录自维基百科）：

有很多不同的数学公式可以用来计算TF-IDF。这边的例子以上述的数学公式来计算。词频 (TF) 是一词语出现的次数除以该文件的总词语数。假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是 0.03 (3/100)。一个计算文件频率 (DF) 的方法是测定有多少份文件出现过“母牛”一词，然后除以文件集里包含的文件总数。所以，如果“母牛”一词在1,000份文件出现过，而文件总数是10,000,000份的话，其逆向文件频率就是 4( ln(10,000,000 / 1,000) )。最后的TF-IDF的分数为0.12( 0.03 * 4)。

5.2.5余弦计算模块

此处利用了余弦公式求解了预先相似度的值，公式如下：

和向量余弦的计算方法是文本相似度计算中最常见的一种方法，标记为cosine。用向量空间模型表示文本和文本，两个向量的余弦计算，如公式（5.1）所示：

（5.1）

其中k表示样本和样本两个向量的共现特征的个数，n、m分别表示向量和的向量的维数。

此处求的的余弦的相似度在0~1之间。

5.2.6 BM25计算模块

BM25是一个bag-of-words的检索函数，综合了特征在文本中的词频、以及在语料中的文档频度、平衡了文档的长度等特征。这个函数有很多变种，其中应用最普遍的计算方法，如公式（5.2）所示：

（5.2）

其中是用来计算的检索的query的向量=，代表向量的关键词的个数；是语料中的一个样本向量，代表向量特征个数；是检索词的在样本中的出现的次数；表示文档的长度(指文档中词语的个数，包括重复的词语)；是中的query检索到的全部样本的平均长度。和是自由参数，通常情况下，取值为2.0，取值为0.75。是文档频度的倒数，是检索词的权重。

（5.3）

其中是整个数据集上的文档总数，是指包含检索词的文档数。

本模块利用BM25算法对输入的文章进行比对，并将生成的相似度结果显示在ClistCtrl控件上。

5.2.7相似度显示模块

本模块的主要作用是将两篇文档的余弦（BM25）的相似度结果显示在ClistCtrl控件中，使用户能方便快速的看到两篇文章的余弦（BM25）相似度对比的结果。

5.2.8相似度导出模块

本模块主要做的是，将两篇文章的余弦相似度的结果保存在文本文档中。保存格式如下图所示：

以第二行为例： 1：2 0.0219334表示第一篇文章和第二篇文章的相似度之比0.0219334。

5.3程序流程

本系统的主要流程如下图所示：

N

N

Y

Y

图1.1 系统总的流程图

5.4界面设计

本程序的主要功能是文本相似度的计算，为了方便用户操作，本系统将所有用户需要的功能都放在了程序的显著位置即界面的上方，并以按钮的形式和用户交换。下图为用户的主界面部分：

图1.2 主界面图

当用户按下“打开语料”按钮时系统将弹出Windows文件管理工具菜单如图所示：

打开三类语料操作

图中选择打开的是文本文档（*.txt）。选择三类语料这个文本文件，之后点击“打开”按钮。

打开停用词的操作

上步操作打开了“三类语料”，之后点击“打开停用词”按钮，系统同样会弹出Windows文件管理工具菜单，如图所示：

选择停用词的操作

选择“哈工大停用词表.txt”，点击“打开”按钮。界面如下图所示：

待输入算法前的界面

之后就可以选择计算文本相似度的算法了，如果选择想选择余弦算法的话，点击“余弦”按钮。之后系统会在后台计算余弦的相似度，并在下半部分的表格中显示出来。显示结果如下图所示：

显示余弦相似度的界面

第一列的序号代表比较的次序，第二列表示的对比行一所在的行数，第三列表示的对比行二所在的行数，第四列表示二、三列所表示的文件的余弦相似度。

同样，如果想选择BM25算法的话，可以点击“BM25”这个按钮，跟余弦算法类似，本系统同样会在后台执行BM25算法，

点击“BM25”按钮后，界面显示的效果如下图所示：

BM25算法的界面

和余弦的表示结果相似，BM25算法的显示界面的第一列的序号代表比较的次序，第二列表示的对比行一所在的行数，第三列表示的对比行二所在的行数，第四列表示二、三列所表示的文件的BM25相似度。

测试实例（测试集）的研究与选择

本系统采用黑盒法进行测试。按照程序需求说明书规定的功能和性能测试程序能否正常使用，是否能打开文本文档(*.txt)、是否可以去除停用词、是否能加权、是否能按照公式的要求计算余弦相似度和BM25相似度等功能。

5.5测试环境和测试条件

测试环境是在Windows XP系统下，开发语言采用MFC、C++语言，开发工具是Microsoft Visual C++ 6.0。

测试条件是程序环境配置好，正常运行Microsoft Visual C++ 6.0正常运行的条件下测试的。

5.6实例测试（表格）

表1.2 系统测试表

序号	测试项	验证过程	预期结果	实际结果	结论
1	打开语料库（txt）	打开Windows文件管理工具菜单，并打开三类语料（*.txt）	打开语料库，并将语料的内容存入到内存中	打开语料库，并将语料的内容存入到内存中	通过
2	打开停用词表（txt）	打开Windows文件管理工具菜单，并打开哈工大停用词表（*.txt）	打开停用词表，并将停用词表中的内容存入到内存中	打开停用词表，并将停用词表中的内容存入到内存中	通过
3	去停用词	点击用户界面上的去停用词的按钮	根据停用词表中的停用词，去除语料中的停用词，并生成一个去除停用词后的词表	根据停用词表中的停用词，去除语料中的停用词，并生成一个去除停用词后的词表	通过
4	特征一	点击用户界面上的“特征一”按钮	在去除停用词之后的文本基础上选择出特征为1的词语，输出文本	在去除停用词之后的文本基础上选择出特征为1的词语，输出文本	通过
5	特征不为一	点击用户界面上的“特征不为一”按钮	在去除停用词之后的文本基础上选择出特征不为1的词语，输出文本	在去除停用词之后的文本基础上选择出特征不为1的词语，输出文本	通过
6	去特征选择	点击用户界面上的“去特征选择”按钮	根据去除停用词后的文本和特征为1的文本输出一个去除特征为1之后的文本	根据去除停用词后的文本和特征为1的文本输出一个去除特征为1之后的文本	通过
7	加权功能	点击用户界面上的“加权”按钮	在去除特征为1之后的文本基础上进行加权获得空间向量模型	在去除特征为1之后的文本基础上进行加权获得空间向量模型	通过
8	余弦算法	点击用户界面上的“余弦”按钮	将语料按照余弦算法进行处理，并生成两两比较的余弦相似度结果，并显示在用户页面的表格控件中	将语料按照余弦算法进行处理，并生成两两比较的余弦相似度结果，并显示在用户页面的表格控件中	通过
9	BM25算法	点击用户界面上的“BM25”按钮	将语料按照BM25算法进行处理，并生成两两比较的文本相似度结果，并显示在用户页面的表格控件中	将语料按照BM25算法进行处理，并生成两两比较的文本相似度结果，并显示在用户页面的表格控件中	通过

5.7性能分析

本系统体积较小，要求配置较低，运行平台为日常普通的Windows操作系统，不会因为系统的缺陷对软件造成影响。本系统功能基本符合要求，有一定的容错能力（对用户的非法操作有一定的提醒和检查功能），方便用户操作，易操作性强。

6 结论与展望

参考文献

[1]任哲. MFC Windows 应用程序设计（第二版）.清华大学出版社，2007-9

[2]谭浩强. C程序设计（第三版）.清华大学出版社，2005-7

[3]陈松乔 任胜兵 王. 现代软件工程. 清华大学出版社，2004-6

[4]严蔚敏 吴爱民 数据结构（C语言版）.清华大学出版社，2007-4

[5]刘腾红. Windows 程序设计技术. 清华大学出版社，2004-10

[6]孙鑫 余安萍. VC++深入详解. 电子工业出版社，2006-1

[7]孙浩. Visual C++范例大全 机械工业出版社，2009-3

[8]杨友东 汪深深. Visual C++程序设计全程指南. 电子工业出版社，2009-4

 

致  谢