基于马尔科夫模型的汉语语句相似度计算

郜炎峰，林燕芬，王忠建

(哈尔滨商业大学 计算机与信息工程学院，哈尔滨 150028)

基于马尔科夫模型的汉语语句相似度计算

郜炎峰，林燕芬，王忠建

(哈尔滨商业大学 计算机与信息工程学院，哈尔滨 150028)

语句相似度计算在自然语言处理领域是一项非常重要的实用技术，基于马尔科夫模型的汉语语句相似度计算方法通过对语句进行分词处理、构建特征词向量以及权重值向量的方式实现了语句相似度计算.该方法以关系向量模型为基础，通过深入研究汉语语句的特征，利用前后相邻词的共现对权重值向量进行加权处理，以调整不同特征词的权重.方法重点考虑了关键词词形的相似度，结合了句长、词序等表面信息的相似度，并考虑了同义词的情况.最后采用两种不同的方案与关系向量模型进行了对比实验，结果表明方法可以更好的处理长度差很大的两个语句的相似度计算问题，尤其在检索相关新闻标题时准确率较高.

马尔科夫；语句相似度；相邻词；词形

在如今的信息时代，随着信息科技的不断发展，中国网络规模，网民数量正在以每年两位数的方式增长[1]，网络上每天都会产生海量的数据，而且这些以图片、视频、文本等形式存在的信息以指数级的方式不断增长，其中文本数据占了70%以上[2]，如何从这些海量的数据中获取有效的信息已经成为自然语言处理的重中之重.在自然语言处理中，语句相似度计算具有非常重要的地位，它是文本信息处理的基础.

1 语句相似度计算

1.1 研究概况

语句相似度计算在信息检索、机器翻译、自动文摘和问答系统等领域具有广泛的应用.从研究的粒度大小来看，汉语语句相似度计算是以词语的相似度研究为基础，同时又是文本相似度计算的基础.从剖析方向来看，语句相似度的研究方向主要有两个：一个是将语句的深层次的语义作为重点研究语句相似度；另一个是以关键词、词性、句长、句型结构等语句表面特征作为语句相似度的研究重点.

国外的语句相似度研究理论和技术都比较成熟，但是研究内容主要是针对英语、日语等其他语言的语句相似度计算，很少涉及汉语语句相似度计算的内容.

在国内，汉语语句的相似度研究起步相对较晚，也取得了一定的成果，例如：张培颖[3]综合考虑了词形、词序、长度、结构、距离和语义这6个方面的信息，给予不同特征不同的权重，提出了多特征融合的语句相似度计算方法.吴全娥，熊海灵[4]综合考虑词形、词汇语义和句法三个方面的信息计算语句的相似度.文献[5-7]是有关知网的语句相似度计算方法.虽然研究成果丰硕，但是汉语的博大精深导致其研究难度要高于日语和英语，因此汉语语句相似度计算的研究仍然有很长的一段路要走.

1.2 存在的问题

目前汉语语句的相似度计算存在如下一些问题：

1)重点考虑句法结构分析的方法

这类方法主要考虑语句结构和词语之间的依存关系，忽略词语之间的语义关系，句法分析技术不成熟，实际应用中准确率并不高.

2)重点考虑语义分析的方法

过度依赖语义词典大小的影响，实用性小于基于关键词词形信息的语句相似度计算方法.

3)重点考虑关键词词形信息的方法

一些常见的此类方法，需要建立大规模语料库，耗费大量的人力、物力，容易产生数据稀疏的问题，忽略句法结构和语义等深层信息.

DekangLin认为任何事物之间的相似度都是由它们的共性和个性决定，本文重点考虑关键词词形信息，对影响汉语语句共性和个性的因素做了深入研究，并将其中一些影响因素融入到汉语语句的相似度计算中，提出了基于马尔科夫模型的汉语语句相似度计算方法.

2 语句特征分析

2.1 词语的划分

根据汉语相关知识可知，汉语语句都是由关键成分和修饰成分组成.一般情况下，主语和宾语是名词或代词，谓语是形容词或动词.其他所有词性的词均为修饰成分.语句相似度计算方法都是按照词性对关键词进行提取，把动词、名词、形容词、代词作为关键词.

2.2 语句分析

语句相似度计算方法都是建立在关键词的基础上，语句的其他特征很多，很难做到所有特征都被作为衡量因素，同时特征之间也存在相互牵制的作用，下面仅对语句相似度计算中相对比较重要的两个特征作简单介绍.

在句长方面，本文中的句长是指语句中词语的个数，汉语语句中词的个数越多，蕴含的信息量越大，而句长是由语句中词的个数决定.当其他条件一致时，长度越接近的两个语句越相似.

在词序方面，汉语语句的意思与词序或多或少会有一定的联系，词序的变动可以使整个语句或词组具有不同的意义，例如：“我对他好”与“他对我好”，这两句话的关键词与语句长度完全一样，但是词序不同，在不考虑词序的情况下，会错误的把这类语句的相似度视为1.

3 汉语语句相似度计算

3.1 特征融合基础

3.1.1 相关概念

定义1 给定一个语句Ti，经过分词处理后，得到的词语按顺序构成一个向量，表示形式Ti={m1,m2,m3,…,mn}，其中mi代表一个词.该向量只包含关键词.

定义2 给定一个汉语语句Ti的向量表示形式Ti={m1,m2,m3,…,mn}，Ti中词的个数称为Ti的向量长度，该向量是由关键词构成，向量长度表示为Len(Ti).

定义3 给定一个汉语语句Ti向量表示形式Ti={m1,m2,m3,…,mn}，该语句的向量长度n，其中每一个词初始的权重值为1/n，这些权重值构成的向量称为权重值向量，表示形式Tvi={1/n,1/n,…,1/n}.

定义4 给定两个语句Ti和Tj，Ti的向量长度较短，对于Ti={m1,m2,m3,…,mn}中的每一个词mi，如果mi或其同义词在向量Tj={m1,m2,m3,…,mn}中也存在(如果一个词语只在其中一个语句中重复出现，不累计计算，在两个语句同时出现则累计计算)，则Ti中所有在Tj中存在的词构成的向量，称为公共词向量，表示为Ei,j={e1,e2,…,ep}，其中1≤p≤n.

定义5 给定两个语句Ti和Tj，公共词向量中的每一个词对应的权重值向量中的权重值构成的向量，称为公共值向量，语句Ti的公共值向量表示为Evi={v1,v2,…,vp}，语句Tj的公共值向量表示为Evj={v1,v2,…,vp}.

假如现对Ti和Tj两个语句进行相似度处理，Ti的向量长度较小，对公共词向量中每一个词ei，让ei在Ti中的前一个词与ei在Tj中的前一个词作比较，如果它们是相同的词或同义词就把该词在Ti和Tj的权重值向量中相应的权重值增加α倍，同时将公共值向量中相应的权重值也增加α倍，如果它们不是相同的词或同义词，则权重值不变.对于ei在Ti和Tj中的后一个词做同样的处理，α的取值可以通过实验获得.

3.1.2 相关公式

假如语句Ti的长度更短，本文创建的语句长度的相似度计算公式如式(1).

LenSim(Ti,Tj)=2Len(Ti)Len(Ti)+Len(Tj)

(1)

在词序相似度计算方面，本文采用的词序相似度计算公式[8]，如式(2)所示.

(2)

其中:p表示公共词向量中的公共词的个数，Rord(Ti,Tj)代表逆序数.

易证0≤OrdSim(Ti,Tj)≤1，这种词序相似度计算的优点是当一个语句的局部整体在另一个语句中出现时，能够增加两个语句的相似度，而且实现快捷.

在关键词相似度计算方面，本文创建的关键词相似度计算公式，如式(3)所示.

G(Ti,Tj)=∑p1k=1vk+∑p1l=1vl∑n1i=1vi+∑n2j=1vj

(3)

其中: 公共词向量Ei,j的长度为p1， 语句Ti的向量长度Len(Ti)为n1，语句Tj的关键词向量长度Len(Tj)为n2，vk表示公共值向量Evi中第k项的值，0

3.2 汉语语句相似度计算实现过程

3.2.1 方法描述

输入：两个汉语语句Ti和Tj

输出：语句相似度Sim(Ti,Tj)

方法：

1)输入两个汉语语句Ti、Tj，假如Ti的向量长度较小，利用中科院ICTCLAS的汉语分词系统和人工分词相结合的方式进行分词处理.

2)对分词后的语句Ti、Tj提取关键词，构造Ti和Tj的关键词向量，根据这两个向量计算这两个语句的公共词向量Ei,j.

3)根据公共词向量，计算Ti的权重值向量Tvi，Tj的权重值向量Tvj.

4)根据公共词向量和权重值向量，计算Ti的公共值向量Evi，Tj的公共值向量Evj.

5)根据公式(1)，计算Ti和Tj的语句长度相似度.

6)根据公式(2)，计算Ti和Tj的词序相似度.

7)根据公式(3)计算关键词的相似度.

8)采用以下方案1和方案2中的语句相似度计算公式计算Ti和Tj的语句相似度.

3.2.2 计算方案

以下分别采用两种不同方案对语句Ti和Tj的相似度进行计算.

1)不考虑词序的相似度计算方案

该方案是以基于关系向量模型的相似度计算方法为基础，公式表示如式(4).

Sim(Ti,Tj)=G(Ti,Tj)×LenSim(Ti,Tj)

(4)

2)考虑词序的相似度计算方案

公式如式(5)所示.

Sim(Ti,Tj)=λ1G(Ti,Tj)+λ2LenSim(Ti,Tj)+λ3OrdSim(Ti,Tj)

(5)

其中:λ1代表关键词相似的权重，λ2代表语句长度相似的权重，λ3代表词序相似的权重，0≤λ1≤1，0≤λ2≤1，0≤λ3≤1，λ1+λ2+λ3=1，为了突出关键词的重要性，给λ1较大的权重值.当两个语句的关键词、句长、词序完全相同时，这两个语句的相似度为1.

两种方案对基于关系向量模型的方法进行了一定的优化，更加平衡了两个关键词向量对语句相似度的影响，同时也在一定程度上缩小了两个语句长度差对相似度的影响.

4 实验与分析

本实验从不同的新闻网站采集了131条国际新闻标题作为一个测试集，由于新闻标题言简意赅，除去标点符号之后，基本都是关键词，给实验的进行带来一定的方便.

对该测试集中的相关新闻标题中的同义词进行替换，将替换后的测试集插入mysql数据库中，用c3p0数据库连接池以及dbutil数据库连接工具连接数据库，编程工具采用Eclipse.用中科院ICTCLAS汉语分词系统(又名NLPIR)和人工分词相结合的方式进行分词处理.

本实验分别采用关系向量模型的相似度计算方法[9]和本文提出的两种相似度计算方案进行相似度计算的比较实验，从中检索出相关新闻的组数，每组两个新闻标题.设定检索组数分别为50组和45组时，计算结果如表1、2所示.

表1 相似度计算结果的比较(50组)

表2 相似度计算结果的比较(45组)

从表1、2可以看出当设定检索50组相关新闻标题时，关系向量模型的方法正确率为78.0%，方案1和方案2分别为88.0%和90.0%，当设定检索组数为45时，关系向量模型的方法正确率为80.0%，方案1和方案2正确率分别为93.3%和93.3%.实验结果表明本文新提出的两种相似度计算方案明显优于关系向量模型的相似度计算方法.

通过对错误的实验数据以及计算公式进行分析，发现基于关系向量模型的相似度计算方法在计算两个语句相似度时，对语句长度差的考虑严重不足.两个新方案能够较为准确的衡量两个语句的影响因素，因此准确率也较高.本实验采用了较小的语料库即可说明新方法的优越性，避免了大规模语料库的构建.

另外，本实验涉及的计算方法都是计算关键词较多的语句的相似度，但是对非关键词较多的语句相似度进行处理时，其准确率可能会受到影响.例如：“无论如何，我都要请你吃饭.”与“我要请你吃饭.”两个语句关键词完全一样，关键词向量长度、词序也相同，可能会误认为相似度为1，高估了两个语句的相似度.此外，还有标点符号的不同，可能导致两个语句的意思有差异.

5 结 语

本文提出的基于马尔科夫模型的语句相似度计算方法充分考虑了相邻词语之间的共现作用，适当的衡量了语句长度对相似度的影响.同时，也表明以词序为代表的其他一些语句特征在计算新闻标题相似度时影响甚微，在一定应用领域，并不是语句特征考虑的越多就准确率越高.虽然新方法的准确率得到了提高，但是不足之处是新方法只针对关键词较多，且非关键词较少的语句相似度计算较为准确，对非关键词较多的语句的相似度计算还有待进一步研究.

[1] 中国互联网络信息中心.第33次中国互联网络发展状况统计[EB/OL]. http://www.cmiic.cn/hlwfzyj/hlwxzbg/hlwtjb1403/P020140305346585959798.pdf,2014-01-16.

[2] 夏 天. 中文信息相似度计算理论与方法[M]. 郑州: 河南科学技术出版社, 2009.

[3] 张培颖. 多特征融合的语句相似度计算模型[J]. 计算机工程与应用, 2010,46(26):136-137.

[4] 吴全娥,熊海灵. 一种综合多特征的句子相似度计算方法[J]. 计算机系统应用, 2010, 19(11): 110-114.

[5] 李迎凯,徐小良. 一种改进的基于知网的句子相似度计算方法[J]. 电子科技, 2012, 25(7): 69-71.

[6] 李 进. 基于知网的句子相似度计算的研究[J]. 电脑知识与技术, 2012, 29(8): 7073-7075.

[7] 董振东, 董 强, 郝长伶. 知网的理论发现[J]. 中文信息学报,2007, 21(4): 3-9.

[8] 吕学强, 任飞亮, 黄志丹, 等. 句子相似模型和最相似语句查找算法[J]. 东北大学学报:自然科学版, 2003, 24(6): 531-534.

[9] 殷耀明, 张东站. 基于关系向量模型的句子相似度计算[J]. 计算机工程与应用, 2014, 50(2): 198-203.

Chinese sentence similarity computation based on Markov

GAO Yan-feng, LIN Yan-fen, WANG Zhong-jian

(School of Computer and Information Engineering, Harbin University of Commerce, Harbin 150028, China)

Sentence similarity computation is a very important practical technology in the field of natural language processing. Chinese sentence similarity computation based on Markoff was realized by using word segmentation processing, constructing characteristic word vector and weight value vector. The method was based on the relation vector model. In order to adjust the weight of the different characters, the characteristics of Chinese sentences and the weight of neighboring words appearing together were studied in this paper. The keywords morphological similarity was the key factor. The surface information of sentence length, word order similarity and the synonyms are all taken into account. Finally, two kinds of different schemes are used to compare with the relation vector model. The experimental results showed that the method could better handle the similarity of two sentences with a large difference in the length; especially the accuracy rate was higher in the retrieval of relevant news headlines.

Markov; sentence similarity; adjacent word; morphology

2016-03-11.

黑龙江省自然科学基金(F201243)；黑龙江省教育厅科研项目(12511127)

郜炎峰(1990-)，男，硕士，研究方向：自然语言处理.

O177

A

1672-0946(2017)01-0073-04