基于词性和关键词的短文本相似度计算方法

赵明月

(河南大学计算机与信息工程学院，河南 开封 475004)

0 引言

文本相似度的度量就是衡量两个文本之间语义相似的程度，是自然语言处理中一个非常重要的任务。

早期的文本相似度研究多侧重于长文本，比如文档或段落等[15]。然而近年来，由于微博平台上大量短文本的出现，对短文本相似度度量的研究吸引了很多研究者进行了深入而广泛的关注。例如pilehvar等[12]通过寻找文本的语义指纹，进而比较两个语义指纹的差异性来判断文本的相似度，Yazdani等[13]利用维基百科生成一个概念网络，通过计算由概念网络中生成的文本各自的语义概念的相似度，来计算文本间的相似度。其中 Matt等[14]人提出的 Word Mover’s Distance（WMD）算法，为求解两条微博的相似度开辟了新思路，取得了较好的效果。

WMD是一种新的计算文本文档距离方法，是将Earth Mover’s Distance(EMD)和词嵌入结合起来，用来度量两个文档之间的语义相似距离。WMD算法是在EMD算法基础上改进得来的，这个方法第一次用运输距离的思想解决了自然语言中如何对文本内容进行归类的问题。

虽然WMD算法使用EMD和词嵌入在文本内容相似度衡量方面取得了较好的效果，但是WMD算法中所有的单词用相同的权重，其忽略了关键词在语义相似度衡量上的重要性,未考虑到词性不同的单词对语义相似度衡量的影响。因此本文针对WMD不考虑单词权重问题，做出如下改进。

首先，使用TextRank[7]算法将句子中的关键词提取出来，然后使用Natural Language Toolkit(NLTK)将句子中单词标注词性，最后根据提出权重分配算法求解不同词性的单词和关键词的最优权重。使用文献[14]中的数据进行实验表明，本文所提的方法在微博情感倾向应用中，性能优于原始的WMD方法。

1 WMD算法的简介

WMD算法是在对EMD(Earth Mover’s Distance)算法基础上进行改进得到的新算法。首先简单介绍EMD算法，EMD是一个找到运输问题最优解的算法，假定有P和Q两个地方，需要将货物从P运输到Q。两地之间的距离定义为dij且为恒定值；从P运输到Q的物品重量定义为fij，它是运输的惟一变量并限制fij≥0。这样得到运输完所有物品的总工作量是：

从公式⑴得到P的总容量为Wp和Q的总容量为WQ，则有，所以运输总量等于P和Q的最小值

其中WMD的度量是依靠Word2Vec模型生成的高质量和大规模的数据集中的word embedding工具实现的。因为自然语言是由词来组成的，所以Word2Vec是将每一个词表示成一定纬度的向量，如果这个词在第三个位置出现，那么就将第三个位置的值设为1，其余设为0，这样的话就可以对所有样本进行神经网络的训练直到收敛。收敛之后会得到权重，然后将这些权重作为每一个词的向量，需要注意的是，在Word2Vec中使用了哈夫曼树，这样的话就可以根据上下文来推测这个词的概率。

WMD的图解如图1所示。

图1 WMD图解

首先将去除停用词的这些文字插入到Word2Vec空间里，这些文字会表示在向量空间上，称之为Word Embeeding。从图1可以看出，从文档1到文档2的距离就是将文档1所有非停用词移动到文档2中词语的最小距离的累加。

对于文档1和文档2，首先用nBOW将文档P和Q中去除停用词的单词用向量表示，并用计算该词的权重，其中ci表示词语ci在文档中出现的次数。

在Word2Vec向量空间中，语义相似的词与词之间的距离可以用欧式距离来计算，即：

这里的C(i,j)是一个词运输到另一个词所花费的代价。

在得到每一个单词到单词之间的距离之后，就可以得到整个文档P到文档Q之间的距离：

将累积cost最小化，有以下公式⑷：

subject to:

图2 距离计算图解

从图2中可以看出，将Illinois转换为Chicago，比Japan转换为Chicago的代价小，因为在向量空间中，向量（Illinois）比向量（Japan）的距离小，因此能计算出哪两个文档之间距离较近。

WMD在实际运用中也存在一些缺点，例如在得到词向量时，WMD算法只是单纯的对所有词随机赋予一个权重，并不考虑词在句子中的重要与否，这样可能会造成对句子的分类错误。在原先的WMD算法中，若是随机赋予权重，可能会将这两句话归为意思相近的一类，但是实际却恰恰相反。本文对句子中的所有词进行重新的梳理，将不同词性的词分门别类的赋予权重，这样在使用WMD求解语义相似度的过程中可以将意思更为接近的句子归为一类，提高求解相似度的准确率。

2 基于词性的WMD算法改进

随着社交媒体的发展，每天的新文本内容有了爆炸式的增长，但是，这些文本内容与传统的文本内容（新闻，小说等）有很大区别，其主要特点是，风格随意，单词简写，文法接近于口语化表达。这些特点也大大影响了自然语言处理的效率。近年来，各类自然语言处理工具的准确率下降的事件多次被提及，例如Stanford tagger[3](针对社交文本的词性标注结果分析)准确率从97%下降到87%，词性也称为词类，是词汇在文章中最基本的语法特征，一方面，文章中许多单词，即便是同一个单词，在不同的语境中也有不同的意思；另一方面，文章中的关键词也可以对文章进行高度概括，所以，这些词性和关键词成为了语义分类的关键因素。

2.1 词性的分类及方法

在词性分类中，现在有以下三种模型比较流行[4]。第一种是布朗语料库，这种模型纯粹是靠手工的方式来获得大量的语料库，然后对这些语料库取样本，并且还要靠用户来对存在的错误进行勘正。第二种是隐马尔可夫模型，在二十世纪八十年代，欧洲的研究人员通过计算单词出现的可能性来得到下一个单词的词性。第三种是动态编程的方法，1987年，Steven DeRose[5]和Ken Church[6]独立开发了动态规划算法，在很短的时间内解决同样的问题。他们的方法类似于其他领域已知的Viterbi算法。DeRose使用了一个对的表格，而Church则使用了一个三元组表格和一个估算在Brown语料库中罕见或不存在的三元值的方法（三重概率的实际测量将需要更大的语料库）。本文根据实际情况，使用了第三种模型来处理这些问题，依托Python中现有的NTLK包中POS_TAG功能，对每条用户所发的微博内容进行单独提取，例子如表1所示。

表2 对文本内容的词语进行分类

如表1所示，首先对于给定的文本内容进行分割，然后使用NTLK工具对其去除停用词的所有单词进行词性标准，从而得到给定文本内容中名词、形容、动词和副词的分类。

2.2 TextRank算法简介和关键词提取

TextRank[7]算法是在PageRank[8]基础进行改进，在PageRank最初是用在搜索引擎上，用于搜索网页的算法其基本思想是投票，在对某一个网页进行排名时，首先要看有多少网页链接到这个网页，这个值称为PR值，计算PR值的公式如下：

其中，S(Vi)是网页i的中重要性（PR值）。d是阻尼系数，一般设置为0.85。In(Vi)是存在指向网页i的链接的网页集合。Out(Vj)是网页j中的链接存在的链接指向的网页的集合。|Out(Vj)|是集合中元素的个数。由于PageRank算法构成的是一个无向图，所以在PageRank算法中加入每个点的权重，就可以得到TextRank算法，其公式如下：

相比PageRank算法，TextRank算法中多了一个W作为权重值，用来表示两个节点之间的边连接有不同的重要程度。这样将文章中不同重要程度的词按照大小排列起来，得到备选关键词。

在本文中，经过实验对比，发现选取前三个关键词时效果最好，所以将前三个关键词存入文档备用。

2.3 权重算法的学习

对于2.1和2.2所提取出的关键词和词性不同的词语，将这些词语赋予新的权重，为了找到最合适的权重算法使得准确率最高，在本文中使用梯度下降算法[9]来对权重进行迭代更新。

在使用梯度算法之前，首先要对梯度进行求解，对于每一个自变量求偏导数并将其偏导数作为变量方向的坐标，梯度下降算法的公式如下：

h(θ)是要拟合的函数，J(θ)损失函数，θ是参数，要迭代求解的值。其中m是训练集的记录条数，i是参数的个数。

由于本文中数据量过多，对比批量梯度下降和随机梯度下降两种算法，发现采取随机梯度下降方法来对权重进行求解效果更好。因此，公式可以改写为：

其中，（xi,yi）是训练集中的一个样本。这样的好处是可以通过随机选取训练集中的样本来对权重进行求解，从而得到局部最优解，由此可得每个样本的损失函数，对θ求偏导得到对应梯度，来更新θ。

为了求得局部最优解，在对函数f(x)进行求导的时候必须先选择一个初始点并计算该点的梯度值，假定梯度的符号为∇,所以对任意函数f(x,y)的梯度为：

由于本文中使用的凸函数，所以按照梯度的负方向来更新参数。假设第n次迭代后的值为xn,可得公式：

其中，α为学习率，这个值表示每次迭代变化的幅度。这个值需要人为设定，如果设定的学习率过大或过小，对于求得的局部最优解会产生较大的影响。

在随机梯度下降中，假设有两个点a(n)和a(n+1)，从a(n)出发，到a(n+1)截止，学习率为α，可得：

其中，

因此，参数推导过程如下：

参数θ的迭代方程可表示为：

算法：权重最优化算法

输入：变量X，训练样本G

输出：变量Y，变量θ

初始化：随机设置α

1.For i=1 to N Do:

2.改变θ，更新

3.For i=1 to M Do:

3 实验及其结果分析

3.1 实验过程

为验证上述改进算法的有效性，本文通过使用文献[14]中的Twitter数据作为原始数据集D1。对所得的数据进行分类，提取各种所需的单词。

也许是去年效益好的缘由，今年的园里栽了不少美人娇花，园林的负责人说，美人蕉花是鸡冠花好几倍，难怪前些年那片土慌着。给人一种园好企业兴的感觉。

为了对比实验结果，本文在改进算法和未改进算法中使用了同一测试集，将D1的前百分之八十作为训练集，后百分之二十作为测试集。

3.2 实验结果分析

本章实验中，为了对实验结果进行衡量，选取正确率、精确率、召回率和F1值作为性能评价指标。我们将获得转发的目标微博记为正例，反之则记为反例。

正确率(Accuracy)：反应模型对整个样本数据的判定能力。即对于测试集，能将正例判定为正例，将反例判定为反例的能力。

精确率(Precision)：分类器将样本数据正确分类为正例的个数，占全部分类为正例的个数的比例。

召回率(Recall)：分类器将样本数据正确分类为正例的个数，占整个数据集中所有正例的个数的比例。

F1值：对精确率和召回率综合考虑得到的另一个评价指标即：

对这两种方法进行比较，结果如表2所示。

表2 两种算法的实验结果比较

只加词性不同的词和只加形容之间的正确率，如图3所示。

图3 词性不同的词和形容之间存在时正确率

图4 所有权重都存在时正确率

表2实验结果显示，在采取相同的数据集中，本文改进的WMD算法较原始的WMD算法有较为明显的提升。

对上述实验结果进行总结，得出以下结论。

传统的WMD对于词语权重这方面并没有较大的涉及，只是随机的分配给词语权重，并未考虑到在句子中，不同词性的词语会对句子的意思产生较大的影响。

在传统的WMD算法中并未考虑到否定词对于整体句子情感走向的影响，只是单纯的将否定词与其他词语简单的赋予权重。

综上所述，本文提出的改进WMD的算法可以较好地提高对于相似文本的分类，这对于自然语言处理和舆情控制等方面有较好的帮助。

4 结束语

自然语言处理中的语言分类是一个较为热门的领域，在当今社会，这个领域可以较好地帮助人们节省大量时间，例如处理垃圾邮件，对流行程度进行预测等。本文对于传统的WMD算法进行分析和整理，对其中不足之处提出改进，但本文所改进的算法仍有一些不足之处，例如在进行赋予词权重时并未对算法进行优化，所需要的时间太长。下一步工作将继续优化赋值操作，进一步减小算法耗时，提升算法运行的效率。

参考文献(References):

[1]Yang C,Wen J.Text Categorization Based on a Similarity Approach[J].InternationalJournalofComputational Intelligence Systems,2007.29(6):1-1

[2]Kusner M J,Sun Y,Kolkin N I,et al.From word embeddings to document distances[C]//International ConferenceonInternationalConferenceonMachine Learning.JMLR.org,2015:957-966

[3]Gupta V,Joshi N,Mathur I.POS tagger for Urdu using Stochastic approaches[C]//International Conference on Information and Communication Technology for Competitive Strategies.ACM,2016:56

[4]张一哲.汉语词类划分与词性标注方法的研究[D].南京师范大学硕士学位论文,2011.

[5]Aly,G.(n.d.).Tagging text with Stanford POS Tagger in Java Applications|Galal Aly.Retrieved from http://www.galalaly.me/index.php/2011/05/tagging-text-withstanford-pos-tagger-in-java-applications/

[6]Surhone L M,Tennoe M T,Henssonow S F.Steven DeRose[J].2010.

[7]Dredze M,Jansen A,Coppersmith G,et al.NLP on Spoken Documents without ASR[C]//Conference on EmpiricalMethodsin NaturalLanguage Processing,EMNLP 2010,9-11 October 2010,Mit Stata Center,Massachusetts,Usa,A MeetingofSigdat,A Special Interest Group of the ACL.DBLP,2010:460-470

[8]Haveliwala T H.Topic-sensitive PageRank:a contextsensitiverankingalgorithm forWebsearch[M].IEEE Educational Activities Department,2003.

[9]Mihalcea R,Tarau P.TextRank:Bringing Order into Texts[C]// Conference on EmpiricalMethods in Natural LanguageProcessing,EMNLP 2004,A Meetingof Sigdat,A Special Interest Group of the Acl,Held in Conjunction with ACL 2004,25-26 July 2004,Barcelona,Spain.DBLP,2004:404-411

[10]Burges C,Shaked T,Renshaw E,et al.Learning to rank using gradientdescent[C]//InternationalConference on Machine Learning.ACM,2005:89-96

[11]Mohler M,Mihalcea R.Text-to-text semantic similarity for automatic short answer grading[C]//Conference ofthe European Chapterofthe Association for Computational Linguistics.Association for Computational Linguistics,2009:567-575

[12]Pilehvar M T,Jurgens D,Navigli R.Align,Disambiguate and Walk: A Unified Approach for Measuring Semantic Similarity[C]//Meeting of the Association for Computational Linguistics,2013.

[13]Yazdani M,Popescu-Belis A.Computing text semantic relatedness using the contents and links of a hypertext encyclopedia:extended abstract[J].Artificial Intelligence,2013.194(194):176-202

[14]Kusner M J,Sun Y,Kolkin N I,et al.From word embeddings to document distances[C]//International Conference on International Conference on Machine Learning.JMLR.org,2015:957-966

[15]Chua T S,Leong M K,Myaeng S H,et al.Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval[J].1992,105(4):1227-1230