夹了比嗨盗
范文一：文本相似度计算
文本相似度计算系统
摘 要
在中文信息处理中，文本相似度的计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域，是一个非常基础而关键的问题，长期以来一直是人们研究的热点和难点。本次毕设的设计目标就是用两种方法来实现文本相似度的计算。
本文采用传统的设计方法，第一种是余弦算法。余弦算法是一种易于理解且结果易于观察的算法。通过余弦算法可以快捷的计算出文本间相似度，并通过余弦算法的结果(0、1之间)判断出相似度的大小。由于余弦计算是在空间向量模型的基础上，所以说要想用余弦算法来完成本次系统，那么必须要将文本转化成空间向量模型。而完成空间向量模型的转换则要用到加权。在空间向量模型实现之前，必须要进行文本的去停用词处理和特征选择的处理。第二种算法是BM25算法，本文将采用最基础的循环来完成，目的是观察余弦算法中使用倒排索引效率是否提高有多大提高。
本次文本相似度计算系统的主要工作是去除停用词、文本特征选择、加权，在加权之后用余弦算法计算文本的相似度。在文本特征选择之后用BM25计算相似度。由于为了使系统的效率提高，在程序设计中应用了大量的容器知识以及内积、倒排算法。
关键词:文本相似度;余弦;BM25;容器
1
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
2
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) .............................................. 错误～未定义书签。64.1 研究设计中的关键问题 ...................................................... 错误～未定义书签。6
3
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
4
1绪论
随着计算机的广泛应用和Intemet的普及，各类信息都在急速地膨胀。信息量的增长给人们带来了方便，同时也带来了信息过量的问题。面对海量信息，人们越来越希望能够在数据分析的基础上进行科学研究、商业决策和企业管理，带来经济效益或社会效益。在现实世界中，文本是最重要的信息载体。因此对文本文档的处理和分析成为当今数据挖掘和信息检索技术的热点之一。处理和研究文本文档的技术有很多，其中重要的一个技术就是文本相似度，它在文本聚类、Web智能检索、问答系统、网页去重、自然语言处理等很多领域中有着重要的应用，文本相似度是这些应用的关键。
本次目标就是做出文本相似度的计算工具，用两种算法来计算文本间的相似度。
1(1开发背景:
文本相似度有着比较广泛的应用，典型的应用有:(1)信息智能检索:搜索引擎对用户输入关键字的反应是列出所有与该关键字相匹配的网页。这些网页的数量之大，往往要以十万百万来计量，而且对于某一关键字检索出来的网页有可能对应于不同的主题。这些各种主题的网页有些没有相关性，有些内容很相似。这种各类主题杂乱在一起的搜索结果和冗余页面给用户找到自己感兴趣的信息带来极大的不便。如果利用文本相似度技术，对搜索结果进行进一步的处理，在搜索结果中将相似度很高的信息分为不同类别，或者去掉相似度很高的重复的信
5
息，为用户提供一个清晰的导航。这将大大的有利于用户发现自己感兴趣的信息，提高信息检索的质量。(2)自动问答系统:在这种系统中，问题是多种多样，且非常巨大的，有些问题是非常相似的，如果用人工来回答，将耗费大量的时间和人力，如果在这种系统中应用文本相似度技术，将相似度很高的问题归为一类，使系统对这类问题自动做出答复，将节省大量的时间。(3)文本查重:在某些领域，考虑到隐私性和独创性，要求文本不能重复出现，那么应用文本相似度技术，对这类文本进行相似度的计算，就可以看出哪些文本多次出现。因此，研究文本相似度的算法具有重要的实际价值。
1(2课题研究意义
文本相似度计算系统是自然语言处理的一部分，可以计算一个文本中不同词条的相似度，可以计算俩个文本间的相似度也可以进行批处理，对多个文本之间进行两两计算，并输出文本间相似度的最后结果。
文本相似度除了简单的计算相似度外，还可以在其基础上进一步发展，成为其他的功能软件。其中最主要的体现就是检索工具与信息挖掘，例如:语义检索、招聘信息检索等。在这些软件中，文本相似度计算系统起到了决定性的作用。
文本相似度计算系统中的去除停用词功能、文本特征选择以及加权功能还可以单个的拿出，作为单独的一个程序或者成为其他系统的一部分。 1(3本课题要解决的问题
文本相似度计算系统包括去除停用词、文本特征选择、加权、余弦算法、BM25算法。
在去除停用词中，主要的问题就是选词范围和set容器的使用。由于给出的词语前面是有词性的，所以在选词的时候要注意将词性去掉。这样才能得到准确的结果。虽然去除停用词这一功能十分的简单。但是由于它是第一个功能，所以一定要保持它的正确性。
文本的特征选择目的是选出那些重要但是又不是每行都有的词，并且输出该词语的特征量。所以在特征选择这一项，我在程序中做了三个模块，选出那些特征为一的特殊词语，并且删除。由于BM25计算方法是在特征选择之后进行的，所以在这一部分还特别为BM25就算出了不为一的文本等。
加权是在文本特征选择之后，是为余弦做准备。通过加权可以得到文本的空
6
间向量模型，由于该结果为全数字，所以要十分的主要加权的准确性。
余弦算法作为该程序的两个算法之一，是该程序的灵魂所在，在余弦算法中除了VC基本知识、容器之外还用到了倒排索引和内积。余弦算法也是该程序的难点之一。
BM25算法是一种很陌生的算法，很多人都可能是第一次听过，BM25算法具有准确这一特点，是一种十分专业的算法。BM25算法中只用到了循环，目的是验证倒排索引、内积等方法可以提高多少效率。
2研究方法
2(1根据研究的侧重点阐述相关的研究方法
目前较为常用的相似度计算方法有许多，例如本次程序要用到的余弦相似度就算方法和BM25相似度计算方法。除此之外内积相似度计算方法，SMART相似度计算方法、Pivoted Normalisation相似度计算方法、Log-linear相似度计算方法等。但是由于相似度的用途、方法等原因，很多方法都是不常见的。
余弦算法作为大家熟知的计算方法而被广泛的应用。在本次程序中，主要的流程就是将语料去除停用词，之后进行文本的特征选择，将特征项为一的和特征项与文本数相同的去掉。接下来进行文本加权，将语料变为一个空间向量模型。最后通过内积与倒排索引按照余弦公式最终计算出文本间的相似度大小。
BM25算法是一种严谨的计算方法，在此次项目中，进行特征选择之后就可以开始进行计算了。BM25比余弦好的地方在于其不用经过加权形成空间向量模型，但是它在公式中也有一部类似加权的计算步骤。
2(2历史以及研究现状
目前，国内外很多学者在研究文本相似度计算问题，并提出了一些解决方案和技术，在这些技术中，Salton等人(1975)提出的向量空间模型(VSM)是最常用的方法。
Salton等人(1975)的观点是，向量空间模型VSM的基本思想是把文档简化为以特征项的权重为分量的向量表示，它假设词与词间不相关，用向量来表示文本，
7
从而简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备了可计算性。这种机制通过为文档中的索引项分配权重来实现。权重应该能体现关键词的重要程度，是对整个文档的描述能力，和区别其他文档的区分能力的量化。特征项的权重计算一般利用统计的方法获得，通常使用词频来表示。基于向量的文本相似度计算方法是最常用的文本相似度计算方法，该方法将要比较相似度的文本根据文本中的词语将文本映射为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)等人的观点，对文
8
本进行处理。但是，这些方法需要分析整个文档语料库去构造一个好的本体模型，而且文本处理的好坏取决于构造本体模型的良好程度。在语料分析中，一些项在文本中很少出现，因为他们的出现频率很低，而往往被忽视。然而，根据信息理论，这些少见的项却对文本处理来说是有价值的。忽视他们在构建本体模型的时候可能会影响文本处理的性能。这些基于本体的方法也没有完全能和LSI抗衡。
3关键问题及分析(一)(余弦) 3.1 研究设计中的关键问题
余弦:关键问题是先要明确余弦的相关定义，理解公式每个地方代表了什么，之后理解相关定义的内容，最后结合C++中的容器知识解决问题。
去除停用词
预处理:在计算余弦算法之前，必须要有预处理的过程，其中包括去除停用词和特征选择。去除停用词主要就是按照停用词表中的词语将语料中不常见的符号，标点级乱码去掉。在去除停用词中除了用到基本的输入输出流，还用到了set容器。set容器重要作用在本次去除停用词过程中存储“哈工大停用词表”，在用循环输入“三类语料”，如果在set容器中就去掉，不在就输出。set容器是容器中最常用也是最基础的知识，下面具体介绍了set容器的基本操作。 set容器:定义一个元素为整数的集合a，可以用set 插入元素:a.insert(1); 删除元素(如果存在):a.erase(1); 判断元素是否属于集合:if (a.find(1) != a.end()) 特征选择: 特征选择的目的:特征选择也属于预处理中的一部分，其最终的目的是将文本中只在一行出现的词语和在每行都出现的词语去掉。 特征选择的实现方法: 在特征选择中用到了set、map、multimap三中容器。 首先用set容器来存放去停用词后的文本。在这里set起到的功能与去除停 9 用词中功能是一样的。 map是STL的一个关联容器，它提供一对一(其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值)的数据处理能力，由于这个特性map内部的实现自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能。由于map容器排序的特性，得到得特征排序的很乱的，所以用到了multimap。Multimap所起到的作用就是一个排序的作用，他使得最终结果按特征选择的值来排序，为后面的去除做一个准备。 在进行文本的特征选择之后要像去除停用词一样去除特征为1的和特征数等于文本行数的特征。因为特征为1的表示特征过小，只在一行出现，对文本的影响不大。而特征数过大的与文本行数相等的说明每一行都出现了，不具有代表行。 加权:由于用余弦来计算相似度，所以引入了空间模型的概念。 G.Salton提出的向量空间模型(VSM)有较好的计算性和可操作性，是近年来应用较多且效果较好的一种模型，向量空间模型最早成功应用于信息检索领域，后来又在文本分类领域得到了广泛的运用。向量空间模型的假设是，一份文档所属的类别仅与某些特定的词或词组在该文档中出现的频数有关，而与这些单词或词组在该文档中出现的位置或顺序无关。也就是说，如果将构成文本的各种词义单位(如单词i、词组)统称为“词项”，以及词频在文本中出现的频数称为“词频”，那么一份文档中蕴含的各个词项的词频信息足以用来对其进行正确的分类。在向量空间模型中的文本被形式化为n维空间中的向量: 其中为第i个 特征的权重。 向量空间模型:向量空间模型重简单方面说就是一个完全由向量所组成的文本，由于余弦算法是按照向量的夹角来计算的，所以必须通过加权来计算出每个词语的权重。 NIDF(q),log加权公式: 其中N为文本的总行数，n为出现该词语的总行in(q)i 数。 10 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<> for(map<> { 11 for(map { write } 这样就将文件成一个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<><><><> 12 为30，20，20，10，那么该文本的向量表示为D(30，20，20，10)。在向量空间 模型中，两个文本D1和D2之间的内容相关度Sim(D1，D2)常用向量之间夹角的 余弦值表示，公式为: 其中，W1k、W2k分别表示文本D1和D2第K个特征项的权值，1<><=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++中的容器来书写程序描述这个算法。对于一个给定的 13 算法，我们主要的精力是研究如何用程序来实现这个算法，我个人觉得这个有些南辕北辙的味道，我们应该从最深处理解算法的精髓，能写出算法的人是大师，而用程序实现算法的人只是一个程序员，由于个人的原因，本人的数学功底有些差，但是我会再以后的道路上努力弥补自己的不足，完善自我。 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等提出的，基于概率检 14 索的框架(probabilistic retrieval framework)发展。BM25是一个bag-of-words的检索函数，综合了特征在文本中的词频、以及在语料中的文档频度、平衡了文档的长度等特征。这个函数有很多变种，其中应用最普遍的计算方法，如公式(5.2)所示: n(5.2) f(q,D),(k，1)i1score(D,Q),IDF(q),,iD||,i1f(q,D)，k,(1,b，b,)i1avgdl {q,...,q}QQQ1nn其中是用来计算的检索的query的向量=，代表向量的关键词 D,{w...w}1,MDMD的个数;是语料中的一个样本向量，代表向量特征个数;f(q,D)q|D|iiDD是检索词的在样本中的出现的次数;表示文档的长度(指文档 avgdlQ中词语的个数，包括重复的词语);是中的query检索到的全部样本的平 IDF(q)kkibb11均长度。和是自由参数，通常情况下，取值为2.0，取值为0.75。 qi是文档频度的倒数，是检索词的权重，计算如公式(5.3)所示: (5.3) N,n(q)，0.5iIDF(q),log in(q)，0.5i n(q)qiiN其中是整个数据集上的文档总数，是指包含检索词的文档数。在实 IDF(q)i际计算中，值有可能是负数，使得的BM25值也有可能是负数，由于 IDF(q)qqiiiBM25公式中偏重于未出现检索词和出现索引词的样本数的比重， qi对于DF值较高的索引词，未出现索引词的文档个数有小于DF值，取log之IDF(q)i后的值变为负值。在本文的实验中去掉了BM25值为负数的样本。 4.3本章小结 BM25算法计算相比余弦算法过程要简单的多，但是我只是运用了一个循环的方法，目的是看用“倒排”的效率，结果“不看不知道,一看下一跳”。结果不是差了一点半点啊。使用“倒排”的效率大大提高。 关于BM25算法的结果，个人表示没有余弦好理解，因为他的结果是无规律且大小相差很多，非专业人员(我)无法用BM25来看出相似度到底有多少，而余弦的结果是0~1之间的，可以一目了然的看到两篇文本的相似度是多少。 15 通过了BM25的实现，使我的数学有了提高，而且更加深入的了解到了如何编算法，以前总感觉算法是很难实现的，但是现在感觉已将给了公式，这样逻辑就很明了了。相信下次我会编的更好。 16 5系统设计及实现 本章从系统的实现过程，各模块的功能、各模块间的关系、界面设计及测试等几个方面阐释了系统的具体实现。 5.1设计实现的策略和关键技术描述 文本相似度计算 特去文加征除档权选停载模择用入块 模词模 块模块 块 BM25显相余示似弦模度算算块导 法法出模 模模块 块 块 在上边的讲解里提出了关于本程序的相关模块，在这一节里将对每个模块进行详细讲解，并对其实现方法进行描述。通过设计方案可以确定出本程序主要分为如下模块:文档载入模块、去除停用词模块、加权模块、特征选择模块、余弦算法模块、BM25算法模块、相似度显示模块，相似度导出模块。 5.2分模块详述系统各部分的实现方法 5.2.1文档载入模块 获取文件的信息可包括两个方面，一个是获取原文本文档(三类语料.txt)中的翻译信息，一个是获取停用词表(哈工大停用词表.txt)中的信息。下面分别对获取文本文档中的原文信息和获取停用词表中的信息进行详细的介绍。 17 1)获取文本文档(三类语料.txt)中的翻译信息 文本文件(txt)文件的格式相对比较简单，本程序用C++语言读取文本文件的方法读取原文的信息。用了C++语言中的getline方法读取文件信息，之后用C++语言中的istringstream函数进行分词操作。原文格式如下: 2)获取文本文档(哈工大停用词表.txt)中的翻译信息 获取停用的操作相对来说简单了些，因为每个停用词独占一行，用C++语言的读一行文件的操作即可，此处就不做详述了。 5.2.2去除停用词模块 去除停用词的目的是去除停用词表中的词语，因为一个刚刚分好词的文本会有许多不重要的词或符号。去除停用词的操作是一个非常常见的教科书程序，而且在我的印象中还做过相关课设，去除停用词的方法主要就是一个循环，但是由于这次要去除的词是在一个文本中，所以要用到一个set容器。 5.2.3特征选择模块 特征选择模块的最终目的一共有两个，一个是输出每个词的特征，即在文本中有多少行含有该词。另一个目的就是去除特征为一的词语和特征等于该文本的总行数的词语，因为程序的最终目的是比较相似度，特征为一的就表示该词不是一个由代表性的词语，而特征数与总行数相等则说明了有无该词对相似度的结果是没有影响的。所以我们对原文做了如下特征选择的操作，去除每篇文章都出现的单词或者有且仅有只在一篇文章中出现的单词。 5.2.4加权模块 对权值的解释: 权值就是指这个指标在整个分析过程中所占的重要程度，比如 你买辆车 你对车的属性有几方面认识——假定只有3个方面 质量 价格 舒适程度 18 你认为 这个质量对你最重要 你赋权值为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。 DD12用向量空间模型表示文本和文本，两个向量的余弦计算，如公式(5.1)所示: 19 k (weight(d,t)weight,(d,t)),ii12(5.1) dd,i,012cos(D,D),,12nm||d||||,d||1222weight(d,t),weight(d,t),,ij12ii,0,0 DDD121其中k表示样本和样本两个向量的共现特征的个数，n、m分别表示向量D2和的向量的维数。 此处求的的余弦的相似度在0~1之间。 5.2.6 BM25计算模块 BM25是一个bag-of-words的检索函数，综合了特征在文本中的词频、以及在语料中的文档频度、平衡了文档的长度等特征。这个函数有很多变种，其中应用最普遍的计算方法，如公式(5.2)所示: n(5.2) f(q,D),(k，1)i1score(D,Q),IDF(q),,iD||,i1f(q,D)，k,(1,b，b,)i1avgdl n{q,...,q}QQQ其中是用来计算的检索的query的向量=，代表向量的关键词1n D,{w...w}DMD的个数;是语料中的一个样本向量，代表向量特征个数;1,M f(q,D)q|D|DD是检索词的在样本中的出现的次数;表示文档的长度(指文档ii avgdlQ中词语的个数，包括重复的词语);是中的query检索到的全部样本的平 IDF(q)kkbb均长度。和是自由参数，通常情况下，取值为2.0，取值为0.75。i11 q是文档频度的倒数，是检索词的权重。 i (5.3) N,n(q)，0.5iIDF(q),login(q)，0.5i n(q)qiiN其中是整个数据集上的文档总数，是指包含检索词的文档数。 本模块利用BM25算法对输入的文章进行比对，并将生成的相似度结果显示在ClistCtrl控件上。 20 5.2.7相似度显示模块 本模块的主要作用是将两篇文档的余弦(BM25)的相似度结果显示在ClistCtrl控件中，使用户能方便快速的看到两篇文章的余弦(BM25)相似度对比的结果。 5.2.8相似度导出模块 本模块主要做的是，将两篇文章的余弦相似度的结果保存在文本文档中。保存格式如下图所示: 以第二行为例: 1:2 0.0219334表示第一篇文章和第二篇文章的相似度之比0.0219334。 5.3程序流程 本系统的主要流程如下图所示: 21 开始 打开文件 去停用词 加权 特征选择 算法 N N BM25 余弦 Y Y 余弦算法 BM25算法 显示相似度结果 结束 图1.1 系统总的流程图 22 5.4界面设计 本程序的主要功能是文本相似度的计算，为了方便用户操作，本系统将所有用户需要的功能都放在了程序的显著位置即界面的上方，并以按钮的形式和用户交换。下图为用户的主界面部分: 图1.2 主界面图 当用户按下“打开语料”按钮时系统将弹出Windows文件管理工具菜单如图所示: 打开三类语料操作 23 图中选择打开的是文本文档(*.txt)。选择三类语料这个文本文件，之后点击“打开”按钮。 打开停用词的操作 上步操作打开了“三类语料”，之后点击“打开停用词”按钮，系统同样会弹出Windows文件管理工具菜单，如图所示: 选择停用词的操作 24 选择“哈工大停用词表.txt”，点击“打开”按钮。界面如下图所示: 待输入算法前的界面 之后就可以选择计算文本相似度的算法了，如果选择想选择余弦算法的话，点击“余弦”按钮。之后系统会在后台计算余弦的相似度，并在下半部分的表格中显示出来。显示结果如下图所示: 显示余弦相似度的界面 第一列的序号代表比较的次序，第二列表示的对比行一所在的行数，第三列表示的对比行二所在的行数，第四列表示二、三列所表示的文件的余弦相似度。 25 同样，如果想选择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正常运行的条件下测试的。 26 5.6实例测试(表格) 表1.2 系统测试表 序号 测试项 验证过程 预期结果 实际结果 结论 打开Windows文件管理打开语料库，并将语打开语料库，并将语打开语料库 1 工具菜单，并打开三类语料的内容存入到内存料的内容存入到内存通过 (txt) 料(*.txt) 中 中 打开Windows文件管理打开停用词表，并将打开停用词表，并将打开停用词表2 工具菜单，并打开哈工大停用词表中的内容存停用词表中的内容存通过 (txt) 停用词表(*.txt) 入到内存中 入到内存中 根据停用词表中的停根据停用词表中的停 点击用户界面上的去停用词，去除语料中的用词，去除语料中的3 去停用词 通过 用词的按钮 停用词，并生成一个停用词，并生成一个 去除停用词后的词表 去除停用词后的词表 在去除停用词之后的在去除停用词之后的 点击用户界面上的“特征文本基础上选择出特文本基础上选择出特4 特征一 通过 一”按钮 征为1的词语，输出征为1的词语，输出 文本 文本 在去除停用词之后的在去除停用词之后的 点击用户界面上的“特征文本基础上选择出特文本基础上选择出特5 特征不为一 通过 不为一”按钮 征不为1的词语，输征不为1的词语，输 出文本 出文本 根据去除停用词后的根据去除停用词后的 点击用户界面上的“去特文本和特征为1的文文本和特征为1的文6 去特征选择 通过 征选择”按钮 本输出一个去除特征本输出一个去除特征 为1之后的文本 为1之后的文本 在去除特征为1之后在去除特征为1之后点击用户界面上的“加7 加权功能 的文本基础上进行加的文本基础上进行加通过 权”按钮 权获得空间向量模型 权获得空间向量模型 将语料按照余弦算法将语料按照余弦算法 进行处理，并生成两进行处理，并生成两点击用户界面上的“余8 余弦算法 两比较的余弦相似度两比较的余弦相似度通过 弦”按钮 结果，并显示在用户结果，并显示在用户 页面的表格控件中 页面的表格控件中 9 BM25算法 点击用户界面上的将语料按照BM25算法将语料按照BM25算法通过 27 “BM25”按钮 进行处理，并生成两进行处理，并生成两 两比较的文本相似度两比较的文本相似度 结果，并显示在用户结果，并显示在用户 页面的表格控件中 页面的表格控件中 5.7性能分析 本系统体积较小，要求配置较低，运行平台为日常普通的Windows操作系统，不会因为系统的缺陷对软件造成影响。本系统功能基本符合要求，有一定的容错能力(对用户的非法操作有一定的提醒和检查功能)，方便用户操作，易操作性强。 6 结论与展望 28 参考文献 [1] 任哲. MFC Windows 应用程序设计(第二版).清华大学出版社，2007-9 [2] 谭浩强. C程序设计(第三版).清华大学出版社，2005-7 [3] 陈松乔 任胜兵 王国军. 现代软件工程. 清华大学出版社，2004-6 吴爱民 数据结构(C语言版).清华大学出版社，2007-4 [4] 严蔚敏 [5] 刘腾红. Windows 程序设计技术. 清华大学出版社，2004-10 余安萍. VC++深入详解. 电子工业出版社，2006-1 [6] 孙鑫 [7] 孙浩. Visual C++范例大全 机械工业出版社，2009-3 [8] 杨友东 汪深深. Visual C++程序设计全程指南. 电子工业出版社，2009-4 致 谢 29 相似度计算方面 Jaccard 相似度：集合之间的Jaccard 相似度等于交集大小与并集大小的比例。适合的应用包括文档文本相似度以及顾客购物习惯的相似度计算等。 Shingling ：k-shingle 是指文档中连续出现的任意k 个字符。如果将文档表示成其k-shingle 集合，那么就可以基于集合之间的Jaccard 相似度来计算文档之间的文本相似度。有时，将shingle 哈希成更短的位串非常有用，可以基于这些哈希值的集合来表示文档。 最小哈希：集合上的最小哈希函数基于全集上的排序转换来定义。给定任意一个排列转换，集合的最小哈希值为在排列转换次序下出现的第一个集合元素。 最小哈希签名：可以选出多个排列转换，然后在每个排列转换下计算集合的最小哈希值，这些最小哈希值序列构成集合的最小哈希签名。给定两个集合，产生相同哈希值的排列转换所占的期望比率正好等于集合之间的Jaccard 相似度。 高效最小哈希：由于实际不可能产生随机的排列转换，因此通常会通过下列方法模拟一个排列转换：选择一个随机哈希函数，利用该函数对集合中所有的元素进行哈希操作，其中得到的最小值看成是集合的最小哈希值。 签名的局部敏感哈希：该技术可以允许我们避免计算所有集合对或其最小哈希签名对之间的相似度。给定集合的签名，我们可以将它们划分成行条，然后仅仅计算至少有一个行条相等的集合对之间的相似度。通过合理选择行条大小，可以消除不满足相似度阈值的大部分集合对之间的比较。 向量空间距离方面 欧式距离：n 维空间下的欧式距离，是两个点在各维上差值的平方和的算数平方根。适合欧式空间的另一个距离是曼哈顿距离，指两个点各维度的差的绝对值之和。 Jaccard 距离：1减去Jaccard 相似度也是一个距离测度。 余弦距离：向量空间下两个向量的夹角大小。 编辑距离：该距离测度应用于字符串，指的是通过需要的插入、删除操作将一个字符串处理成另一个字符串的操作次数。编辑距离还可以通过两个字符串长度之和减去两者最长公共子序列长度的两倍来计算。 海明距离：应用于向量空间。两个向量之间的海明距离计算的是它们之间不相同的位置个数。 索引辅助方面 字符索引：如果将集合表示成字符串，且需要达到的相似度阈值接近1。那么就可以将每个字符串按照其头部的一小部分字母建立索引。需要索引的前缀的长度大概等于整个字符串的长度乘以给定的最大的Jaccard 距离。 位置索引：我们不仅可以给出索引字符串前缀中的字符，也可以索引其在前缀中的位置。如果两个字符串共有的一个字符并不出现在双方的第一个位置，那么我们就知道要么存在某些前面的字 符出现在并集但不出现在交集中，那么在两个字符串中存在一个更前面的公共字符。这样的话，我们就可以减少需要比较的字符串对数目。 后缀索引：我们不仅可以索引字符串前缀中的字符及其位置，还可以索引当前字符后缀的长度，即字符串中该字符之后的位置数量。由于相同字符但是后缀长度不同意味着有额外的字符必须出现在并集但不出现在交集中，因此上述结构能够进一步减少需要比较的字符串数目。 总结 以上的一些概念和方法可以配合使用，可以基本满足许多场景下的相似度计算。相似度计算又可以为相关推荐做基础。怎么做好词的粒度切分，怎么划定阈值，选择何种距离测算，如何优化实现方法还是要下很多功夫的。 两个例子 Levenshtein 其实是编辑距离，下面计算编辑距离的方法是把两个String 串里的字/词当成一个矩阵来比较和计算。 [java] view plaincopy 1. package zbf.search.recommend; 2. 3. public class LevenshteinDis { 4. 5. public static void main(String[] args) { 6. // 要比较的两个字符串 7. String str1 = " 相似度计算方法" ; 8. String str2 = " 文本相似项发现" ; 9. levenshtein(str1, str2); 10. } 11. 12. public static void levenshtein(String str1, String str2) { 13. 14. int len1 = str1.length(); 15. int len2 = str2.length(); 16. 17. int [][] dif = new int [len1 + 1][len2 + 1]; 18. 19. for (int a = 0; a <= len1;="" a++)=""> 20. dif[a][0] = a; 21. } 22. for (int a = 0; a <= len2;="" a++)=""> 23. dif[0][a] = a; 24. } 25. 26. int temp; 27. for (int i = 1; i <= len1;="" i++)=""> 28. for (int j = 1; j <= len2;="" j++)=""> 29. if (str1.charAt(i - 1) == str2.charAt(j - 1)) { 30. temp = 0; 31. } else { 32. temp = 1; 33. } 34. // 取三个值中最小的 35. dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1, 36. dif[i - 1][j] + 1); 37. } 38. } 39. System.out.println(" 字符串\"" + str1 + "\"与\"" + str2 + "\"的比较 " ); 40. System.out.println(" 差异步骤：" + dif[len1][len2]); 41. // 计算相似度 42. float similarity = 1 - (float ) dif[len1][len2] 43. / Math.max(str1.length(), str2.length()); 44. System.out.println(" 相似度：" + similarity); 45. } 46. 47. private static int min(int ... is) { 48. int min = Integer.MAX_VALUE; 49. for (int i : is) { 50. if (min > i) { 51. min = i; 52. } 53. } 54. return min; 55. } 56. 57. } 下面是余弦距离计算的例子： [java] view plaincopy 1. 2. public static double getSimilarity(String doc1, String doc2) { 3. if (doc1 != null && doc1.trim().length() > 0 && doc2 != null 4. && doc2.trim().length() > 0) { 5. 6. Map ; 7. 8. //将两个字符串中的中文字符以及出现的总数封装到，AlgorithmMap 中 9. for (int i = 0; i < doc1.length();="" i++)=""> 10. char d1 = doc1.charAt(i); 11. if (isHanZi(d1)){ 12. int charIndex = getGB2312Id(d1); 13. if (charIndex != -1){ 14. int [] fq = AlgorithmMap.get(charIndex); 15. if (fq != null && fq.length == 2){ 16. fq[0]++; 17. }else { 18. fq = new int [2]; 19. fq[0] = 1; 20. fq[1] = 0; 21. AlgorithmMap.put(charIndex, fq); 22. } 23. } 24. } 25. } 26. 27. for (int i = 0; i < doc2.length();="" i++)=""> 28. char d2 = doc2.charAt(i); 29. if (isHanZi(d2)){ 30. int charIndex = getGB2312Id(d2); 31. if (charIndex != -1){ 32. int [] fq = AlgorithmMap.get(charIndex); 33. if (fq != null && fq.length == 2){ 34. fq[1]++; 35. }else { 36. fq = new int [2]; 37. fq[0] = 0; 38. fq[1] = 1; 39. AlgorithmMap.put(charIndex, fq); 40. } 41. } 42. } 43. } 44. 45. Iterator 46. double sqdoc1 = 0; 47. double sqdoc2 = 0; 48. double denominator = 0; 49. while (iterator.hasNext()){ 50. int [] c = AlgorithmMap.get(iterator.next()); 51. denominator += c[0]*c[1]; 52. sqdoc1 += c[0]*c[0]; 53. sqdoc2 += c[1]*c[1]; 54. } 55. 56. return denominator / Math.sqrt(sqdoc1*sqdoc2); 57. } else { 58. throw new NullPointerException( 59. " the Document is null or have not cahrs!!"); 60. } 61. } 62. 63. public static boolean isHanZi(char ch) { 64. // 判断是否汉字 65. return (ch >= 0x4E00 && ch <=> 66. 67. } 68. 69. /** 70. * 根据输入的Unicode 字符，获取它的GB2312编码或者ascii 编码， 71. * 72. * @param ch 73. * 输入的GB2312中文字符或者ASCII 字符(128个) 74. * @return ch在GB2312中的位置，-1表示该字符不认识 75. */ 76. public static short getGB2312Id(char ch) { 77. try { 78. byte [] buffer = Character.toString(ch).getBytes("GB2312" ); 79. if (buffer.length != 2) { 80. // 正常情况下buffer 应该是两个字节，否则说明ch 不属于GB2312编码， 故返回'?' ，此时说明不认识该字符 81. return -1; 82. } 83. int b0 = (int ) (buffer[0] & 0x0FF ) - 161; // 编码从A1开始，因此减 去0xA1=161 84. int b1 = (int ) (buffer[1] & 0x0FF ) - 161; // 第一个字符和最后一个 字符没有汉字，因此每个区只收16*6-2=94个汉字 85. return (short ) (b0 * 94 + b1); 86. } catch (UnsupportedEncodingException e) { 87. e.printStackTrace(); 88. } 89. return -1; 90. } 91. } 92. 93. 1，2 1，21，2 ，，诚夏青松孙昌年郑 ( 1, ，230039; 安徽大学 计算机科学与技术学院安徽 合肥 2, ，230039)教育部计算智能与信号处理重点实验室安徽 合肥 , : TFIDF 、、，摘 要传统基于 的向量空间模型的文本相似度计算存在高维数据稀疏缺乏语义和维度未归一等问题基于其 ,TFDF ，。 I上的语义扩展的 向量空间模型中部分解决了语义问题但是其基于词典的词语相似度计算限制了其应用范围 ( Latent Drchet ocaton，LD) ，LDA iilAlliA提出了一种基于潜在狄利克雷分配的文本相似度计算方法模型可以在没有词典的 ,，，JS( JensenShannon) 情况下解决上述所有问题通过吉比斯抽样方法将文本建模到主题空间然后使用 距离来计算文本相 。F 。似度通过聚类实验表明该方法取得了较高的 值 : ; ; ; ; 关键词向量空间模型文本相似度自然语言处理潜在狄里克雷分配主题模型 ,,, : TP31: A: 1673 629X( 2013) 01 0217 04中图分类号文献标识码文章编号 , doi: 10, 3969 / j, issn, 1673 629X, 2013, 01, 053 Chinese Text Similarity Computing Based on LDA 1，2 1，2 1，2 ,,SUN Chang nian，ZHENG Cheng ，XIA Qing song ( 1, School of Computer Science and Technology ，Anhui University ，Hefei 230039，China; 2, Key Lab, of Intelligent Computing , Signal Processing ，M ini, of Edu, ，Anhui Univ ,， Hefei 230039，China) , Abstract: Text similarity calculation based on traditional TFIDF vector spacme odel exists high dimensional sparse data，lack of semantic ,and dimension normalization，the TFIDF vector spacme odel based on its semantic extension is to solve the partial problem of semantic， but its w ord similarity computation based on dictionary limits its application scope, Proposed a text similarity computing method based on potential Dirichlet distribution ( Latent Dirichlet Allocation，LDA) ，LDA model can solve all thesep roblems in no dictionary ，through the , Gibbs sampling method，the textm odeling to subject space，and then use JS ( Jensen Shannon) distance computing text similarity ,T he custerng experment resuts show that ths method can acheve hgh F vaue, liiliiil Key words: vectors pace model; text similarity ; natural language processing ; latent Dirichlet allocation; topic model ，，文本集中的词项数目大小一般在几万维而矩阵中的 0 引言，列数目则为文本集中的文本数量因而有着非常高的 , TFIDF 基于 的向量空间模型文本相似度计算方 ，法是使用最广泛的文本相似度计算方法这种方法以 ，。维度并且是极度稀疏的最终导致了非常低效的计算 词在文本中出现的频率以及在文本集中出现的该词的 基于词项语义来考察文本相似度的方法在文本表示模，频率来表征词的权重通过计算向量之间的余弦相似 ，( 型上多 数沿 用了词频向量模型利 用 外 部 词 典 如 。， 度来计算文本的相似度忽略了文本中词项的含义WordNet、HowNet、) 同义词词林等的引入来计算词项 ,1 : 4,，因而也就无法分辨出同义词与多义词而同义词与多 ，之间的相似度度量这种引入外部词典的方法需 。，义词对于计算文档相似度具有重要的意义此外对 ，要设计复杂的数据结构来提高计算效率增加了系统 ，于大多数文本数据集而言词项的数目和文本数目通 ，设计的复杂度而且又无法解决词典中未登录词的语 ，，常都很大而采用词频向量模型必须将文本表示为词 ，义问题而且这种方法很难移植到没有语义词典的应 ，项数目与文本数目大致相当的矩阵矩阵中的行数位 ，，用中方法的鲁棒性较差再者没有针对文本表示的高 ，维模型进行降维处理也缺乏衡量文本间相似度的定 ，义导致基于词项语义相似度的文本计算方法局限性 、。较大难以扩展 ,,,, : 2012 04 16; : 2012 07 21收稿日期修回日期，针对上述方法存在的缺陷文中使用主题模型中 : ( 06060716 ) ; 基金项目安徽省自然科学基金安徽大学研究生学术 LDA ，的 模型对文本进行建模该方法利用文本的统计 ( Q090047)YH 创新研究，，特性能有效降低文本表示维度同时又能解决同义词 ,: ( 1985 ) ，，，作者简介孙昌年男硕士研究生研究领域为文本数据挖 ; ，，、。郑 诚副教授研究领域为数据挖掘语义网 掘 ，，和多义词问题并且无需引用外部词典的相似度计算个单词的主题进行采样一旦每个单词的主题确定下 ，，，。，方法这种方法绕开了外部词典的引入因而避免了词来参数就可以在统计频次后计算出来因此参数估 ,10,。典中未登录词无法得到语义的问题 ，计问题变为计算单词序列下主题序列的条件概率 :其公式如下 ? ? 1 相关工作 =p( zk | z ， w) ，i i 自然语言处理中的主题模型起源于隐性语义索引 ? ? t + n ,5,β p( w，z k，，i tk( Latent Semantc ndexng，LS) 。LS iIiII并不是概率模 = + ) α?( n m，， ki V ? ?t + nβ，，， 型因此也算不上是主题模型但基于其 主 要 思 想p( w，z )? k，，i t ，i = t 1 Hofmann ( Probabstc Latent ilii提出了概率隐性语义索引，zi ; ，i 其中表示第 个单词对应的主题变量表示 i ,6,Semantic Indexing，pLSI) ，pLSI 模型被看做是一个真 t i ; n; k t 剔除其中的第 项表示主题 出现词项 的次数β k t。Blei 正意义上的主题模型此后 等人提出隐性狄里 k ,7,m k irichlet ; nt D表示文本 出现主题 的是词项 的 先验 m ( Latent Drchet Aocaton，LDA) iillli克雷分配进一步完 ; rchet 。k Diil次数α是主题 的 先验一旦获得每个单 k 。善了主题模型文中计算文本相似度的方法主要是基 ，:词的主题标号需要的参数计算公式可由下式获得LDA 。于 模型 t + nLDA β模型通过类似于词聚类的办法将相似词聚 k t=φ k，t V t ，类为一个个主题使得主题以及主题之间具有语义上 + nβ? k t = t 1 ，的意思对于在同一个主题中的词项一般具有近义词 k + n α m k ，， 特性而在不同主题中的同一个词则具有多义词特性= m，k K k + nα从而在文本相似度计算机的过程中免去了计算词项之 ? m k = t 1 ，间的相似度而利用文本的主题分布可以计算文本之 ; k t 其中 φ表示主题 中词项 的概率表示文 k，t m，k ，， 间的相似度而且其计算在不需要外部词典的情况下m k 。，本 中主题 的概率因此主要知道了每个单词的 ，其计算结果也具有语义效果比起基于外部词典的方 ，主题标号那么就可以通过简单计数的方式对参数进 。LDA 法算法更具鲁棒性基于 的主题模型是一种生 。行估计，1 LDA 。成模型图 是使用板图的方法对 模型的表示 2 LDA 基于 的文本相似度 2, 1 —— 文本词向量转换为文本主题向量 Gibbs ，基于 抽样的参数推理方法较容易实现对 ，其中的不必要的计算省去得到下面的计算主题空间 ，,11,，的算法该算法参考了文献中的算法不同之处 —。在于省去了对主题词空间的计算过程 :算法描述如下 1 LDA 图 的模型图表示 ，M、N 图中方框表示循环右上角的 表示循环次 ?，，， 数阴影区域代表观测变量文中表示文本中的单词Phi_Gibbs( ,w, ，，，k ) α β ，。空心节点表示隐含变量箭头表示依赖关系α 是 θ 的 { × ，K V ，K ，V 超参数β 是 的参数集合是主题个数是词项 ( k)( t)= = = = nnnn0 ; m m k k ，，M ，M 个数θ 表示某文本的主题概率分布共 个为文 ++ = for ( d 1; d , m; d )，w ，z w 。本个数为单词为 的主题标号 { LDA ，在 模型中最重要的两组参数分别是各主题 ++= for( w 1; w , n; w ) m 。下的词项概率分布和各文档的主题概率分布参数估 {: 计可以看成是生成过程的逆过程即在已知文本集 = zk , Mult( 1 / 抽样主题标记 m，n ( ) ，，即生成的结果的情况下通过参数估计得到参数 ;K) ( k)( t)。，:值根据图模型可以得到一篇文本的概率值为 ++++ ++ ++ n; n; n ; n ; m m k k N } } = p( w | ，) p( | ) ( p( z| ) p( w| z，αβθ αθWhile( 1 ) ??n n n ?n = 1 z n{ ) ) d βθ++= for ( d 1; d , m; d ) LDA ， 在实际的应用中需要对 模型进行参数估计,8, { 、其参数估计方法主要有变分贝叶斯推理期望传播,9, ++= for( w 1; w , Nm; w ) Collapsed Gibbs Sampling，Gibbs 和 等方法首先对每 抽样主题标记。文档数为标准裁剪数据集复旦文本分类数据集裁剪( t), ? + n 200 ，TanCrop β后每个类别包含 篇文章数据集裁剪后每 k， i t( t)= + k , p( zk | z ，w) ( n)α i i k， i k V 150 。 个类别包含 篇文章 ( t)+ nβ? k， i t ? = t 1 ,F实验采用 度量值来衡量文中提出的文本相似 ( k)( t)ni 。，nj ，度设 是类别 的文本数目是聚类 的文本数目 i j n++ ++ ++ ++ ; n ; n ; n ; m m k k ni P( i，j) j ，是聚类 中隶属于 的文本数目则查准率 和 ij } R( i，j) :} 查全率 可分别定义为 f ( )I收敛或者达到迭代次数 nn ij ij= = P( i，j) ，R( i，j) { nn ji ( k)F :度量值定义为 + nα m k=计算主题分布参数集 m，k K n × × 2 P( i，j) R( i，j) i ( k)+ = nF max(α) k? ? m = k 1 j + n P( i，j) R( i，j)i }n 。F 其中 是文本集合中总的文本数目通常 度量} ，。值越大聚类效果越好 } 3, 2 实验结果 Gibbs ，经过 抽样算法之后就可以将文本的词向 ，FudanNLP 在对数据简单处理后使用 平台提供 。量空间映射为文本的主题向量空间接下来就可以将 。的分词技术对文本进行分词以及去除停用词预处理 。该结果作为文本相似度计算的输入了 。，之后的文本用词向量代替预处理之后将文本集做 LDA ，LDA 处理处理中先验超参数 α 和 β 的经验取值 2, 2 计算文本相似度= = 50 / K ，0, 01。K 为 α β 的取值对于不同文本集而由于文本的主题分布是文本向量空间的单纯形映 。言 取值不是固定的通过实验的方式来确定主题数 ，，射所以在文本的主题表示情况下计算两个文本的相 K 的 。 似度可以通过计算与之对应的主题概率分布来实现 。F ，取值确定的标准为聚类结果 值最高的主题数目，KL( Kullback由于主题是词向量的混合分布因而使用 ,11,Leibler) ，KL , + + – 距离作为相似度度量标准距离如下 K Means ，其中的聚类算法为 算法使用开源工具 ,+ +lingPipe KMeans 。2 中的 实现图 显示了不同主题 :所示 F 。数量对于聚类 值影响 T 2 200 F ，p 从图 中可以看出在主题为 时 值最高因 j = D( p，q) pln KL?j ,+ + 200。KMeans此在后续的比较中选择主题为 通过 qj = 1 j ,, TFIDF TF 算法对比了基于 的向量空间模型以及在 = = pqD( p，q) 0。j ，，当对于所有的 当 时但是 j j KLIDF 基础上加入基于词典语义的向量空间模型的方 KL ，D( p，q) D( q，p) 距离并不是对称的即 ? 因此KLKL，3 。法实验对比结果如图 所示 ，常常使用其对称版本, 3 TF IDF 从图 中可以看出文中的方法比基本的 ++= D( p，q) D( p，p( 1 ) q) ( 1 λλλ λKL, IF IDF 相似度方法以及基于词典计算语义相似度的 + , ) D( q，p ( 1 ) q) λλλKL, , 。扩展方法的聚类效果要好 1 = = D( p，q) D( q，p) 。，容易证明 当 λ 时上述λλ 2 , JS( JensenShannon) :公式转变为 距离 4 结束语 + + 1 p qp q+ = D( p，q) ,D( p， ) D( q， ) , JSKLKLLDA 文中提出了基于 主题模型来建模文档并使 222 ,2,JS JS,0，1 ,，文献指出 距离的区间为文中以 JS 。用 距离来计算文档相似度的方法由于在文本建 。距离公式为标准来度量文本之间的相似度 ，模以及计算相似度的过程中没有使用任何外部词典 相似度计算的效果完全是根据不同文本集自身的特 ，。，性因而文中的计算方法其鲁棒性相对较好另外由 3 实验LDA ，于在使用 建模的过程中对于文本向量的维度压 3, 1 实验数据及度量标准，缩比相当大这给后来的相似度计算和聚类计算带来 :文中的实验数据是两个常用的文本分类数据集 。了相对大的计算效率的提升实验表明了文中方法的 、复旦文本分类数据集谭松波中文文本分类数据集。有效性 TanCorpV1, 0。TanCorp 两个数据集特别是 的数据分 ,3,，，，, 汪 敏肖诗斌王弘蔚等一种改进的 《》,J,, 基于知网的词语相似度计算中文 ,，2008，22( 5) : 84 90,信息学报 ，，, 黄承慧印 鉴侯 昉一种结合词项语 ,4,,TFIDF 义信息和 方法的文本相似度量方 ,,J,, ，2011( 5) : 857 法计算机学报 866, Deerwester S，Dumais T，Landauer G，et ,5,a, ndexng by atent semantc anaysslIilili ,J,, Journa of the Amercan Socety of nforma- liiI ,tion Science，1990，41( 6) : 391 ,6,407,H ofmann T, Probabilistic latent semantic in- dexing,C,/ / Proceedings of the , Twenty second Annua nternatona SGR lIilII 2 图 不同主题数量对聚类效果的影响Confer- ence, ,s, , ,: ,s, n, ,，1999, l Blei D，Ng A，Jordan M, Latent Dirichlet ,7, Aocaton,M,/ / Advances in Neura nfor- llilI mation Processing Systems1 4, Cambridge， MA: MT Press，2002,I Mnka T，Lafferty J, Expectaton propagaton iii ,8, for the generative aspect model,C,/ / Pro- ceedng of UAI 2002, Edmonton，Aberta，il , Canada: ,s, n, ,，2002: 352 359, Heinrich G, Parameter estimation for text a- ,9, nalysis,R,, Darmstadt，Germany: ,s, n, ,， 3 图 三种方法的效果比较 2009, ,10, SteyversM , Probabilistic Topic Models,M,/ / Latent Semantic Analysis: A Road to Meaning, Mahwah: Lawrence Erlbaum As- ,sociates，2007: 424 440, :参考文献 ,11, Duda R O，Hart P E，Stork D G, PatternC lassification,M,, ,1, Hotho A，Staab S，Stumme G, Wordnet mproves text document 李 i ，, 2nd ed, : ，2003,clustering,C,/ / Proceeding of the Semantic Web Workshop at 宏东姚天翔译北京机械工业出版社 , SIGIR2003，26th Annual International ACM SIGIR Confer- ,12, Lin J, Dvergence measures based on Shannon entropyi ,ence, Toronto，Canada: ,s, n, ,，2003: 541 550, ,J,,IEEE Transactions on Information Theory，1991，37 , ( 14 ) : 145 ,2, ，, 《》李 峰李 芳中文词语语义相似度计算基于知网 ,2000,J,, ，2007，21( 3) : 99 105,中文信息学报 ,151, 檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪 ( 216 )上接第 页 Navgaton and Contro Conf, ,P ortand OR: ,s, n, ,，1999,iill,8,, ，，飞行计划冲突预探测算法研究吴舜歆彭 炜李瑞芳 Prandini M，Lygeros J，Nilim A，et al, Randomized Algorithms ,,J,, ，2006，27( 3) : 430 432, ，计算机工程与设计陈晓波宋 ,3,for Probabilistic Aircraft Conflict Detection,C,/ / Conference ，, 万忠杨红雨具有多航路点的多机中期冲突探 测算法 ,9,,on Decision and ControlCDC, ,s, l, ,: ,s, n, ,，,,J,, ，2010，31( 12) : 2807 2810,计算机工程与设计 1999,Er zberger H，Paielli R A, Concept for Next ,4, ,10,，，, 查牧言冯子亮罗世谦适用于多航路的概率型中期冲突Generation Air ,,J,, ，2010，30( 5) : 1046 1049,探测方法计算机应用 Traffic Control System ,J,, AirTraffic Control Quarterly， ,2002，10( 4) : 355 378, ,11,, ,J,, 崔德光空中交通管制自动化中的冲突概率分析清华 ,，2000，40( 11) : 119 122,大学学报 ,5,Pae R A，Erzberger , Confct probabty estmaton forilliHliiliii,12,，, 崔德光王哲鹏空中交通管制自动化系统中飞行冲突概 free flight,J,, Journal of Guidance，Control and Dynamics， ,J,, ，2001，22 ( 5 ) :率解析算法的应用计算机工程与设计 ,1997，20( 3) : 588 596, ,46 49, ，, 罗世谦冯子亮一种高效的中期冲突探测随机化算法 ,6,,,13,，，, ,M,, : ,J,, ，2010，27( 3) : 56 57, ，方保镕周继东李医民矩阵论北京清华大学出版 计算机应用与软件李俊菊宋万 ，2004,，，, ,J,, 社 忠梁海军等中期冲突探测算法的研究与 设计计 ,7,,，2010，31( 20) : 4493 4494,算机工程与设计 原理参考：http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html Java代码 /** * */ package?com.text; import?java.io.IOException; import?java.io.StringReader; import?java.util.HashMap; import?java.util.Map; import?org.apache.commons.collections.MapUtils; import?org.apache.commons.lang3.tuple.MutablePair; import?org.apache.commons.lang3.tuple.Pair; import?org.wltea.analyzer.core.IKSegmenter; import?org.wltea.analyzer.core.Lexeme; /** *?@author?Riching * *?@date?2013-8-10 */ public?class?IKMainTest?{ /** *?@param?args *?@throws?IOException */ public?static?void?main(String[]?args)?throws?IOException?{ String?str1?=?"我喜欢看电视，不喜欢看电影。"; String?str2?=?"我不喜欢看电视，也不喜欢看电影。"; Map Map Map<> for?(String?key?:?tf1.keySet())?{ MutablePair tfs.put(key,?pair); } for?(String?key?:?tf2.keySet())?{ MutablePair if?(null?==?pair)?{ pair?=?new?MutablePair }?else?{ pair.setRight(tf2.get(key)); } } double?d?=?caclIDF(tfs); System.out.println(d); } public?static?Map Map IKSegmenter?ikSegmenter?=?new?IKSegmenter(new?StringReader(str),?true); Lexeme?lexeme?=?null; while?((lexeme?=?ikSegmenter.next())?!=?null)?{ String?key?=?lexeme.getLexemeText(); Integer?count?=?map.get(key); if?(null?==?count)?{ count?=?1; }?else?{ count?=?count?+?1; } map.put(key,?count); } return?map; } public?static?double?caclIDF(Map<> double?d?=?0; if?(MapUtils.isEmpty(tf))?{ return?d; } double?denominator?=?0; double?sqdoc1?=?0; double?sqdoc2?=?0; Pair for?(String?key?:?tf.keySet())?{ count?=?tf.get(key); denominator?+=?count.getLeft()?*?count.getRight(); sqdoc1?+=?count.getLeft()?*?count.getLeft(); sqdoc2?+=?count.getRight()?*?count.getRight(); } d?=?denominator?/?(Math.sqrt(sqdoc1)?*?Math.sqrt(sqdoc2)); return?d; } } 在向量空间模型中，文本泛指各种机器可读的记录。用D （Document ）表示，特征项（Term ，用t 表示）是指出现在文档D 中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D(T1，T2，…，Tn) ，其中Tk 是特征项，1<><=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=""><><=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<><> 在自动归类中，我们可以利用类似的方法来计算待归类文档和某类目的相关度。例如文本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 范文二：文本相似度的计算方法
public class CosineSimilarAlgorithm {范文三：基于LDA的中文文本相似度计算
范文四：使用余弦相似性原理计算文本的相似度
范文五：文本相似度算法
