基于馬爾科夫模型的漢語語句相似度計算

郜炎峰，林燕芬，王忠建

(哈爾濱商業(yè)大學 計算機與信息工程學院，哈爾濱 150028)

基于馬爾科夫模型的漢語語句相似度計算

郜炎峰，林燕芬，王忠建

(哈爾濱商業(yè)大學 計算機與信息工程學院，哈爾濱 150028)

語句相似度計算在自然語言處理領域是一項非常重要的實用技術，基于馬爾科夫模型的漢語語句相似度計算方法通過對語句進行分詞處理、構建特征詞向量以及權重值向量的方式實現了語句相似度計算.該方法以關系向量模型為基礎，通過深入研究漢語語句的特征，利用前后相鄰詞的共現對權重值向量進行加權處理，以調整不同特征詞的權重.方法重點考慮了關鍵詞詞形的相似度，結合了句長、詞序等表面信息的相似度，并考慮了同義詞的情況.最后采用兩種不同的方案與關系向量模型進行了對比實驗，結果表明方法可以更好的處理長度差很大的兩個語句的相似度計算問題，尤其在檢索相關新聞標題時準確率較高.

馬爾科夫；語句相似度；相鄰詞；詞形

在如今的信息時代，隨著信息科技的不斷發(fā)展，中國網絡規(guī)模，網民數量正在以每年兩位數的方式增長[1]，網絡上每天都會產生海量的數據，而且這些以圖片、視頻、文本等形式存在的信息以指數級的方式不斷增長，其中文本數據占了70%以上[2]，如何從這些海量的數據中獲取有效的信息已經成為自然語言處理的重中之重.在自然語言處理中，語句相似度計算具有非常重要的地位，它是文本信息處理的基礎.

1 語句相似度計算

1.1 研究概況

語句相似度計算在信息檢索、機器翻譯、自動文摘和問答系統(tǒng)等領域具有廣泛的應用.從研究的粒度大小來看，漢語語句相似度計算是以詞語的相似度研究為基礎，同時又是文本相似度計算的基礎.從剖析方向來看，語句相似度的研究方向主要有兩個：一個是將語句的深層次的語義作為重點研究語句相似度；另一個是以關鍵詞、詞性、句長、句型結構等語句表面特征作為語句相似度的研究重點.

國外的語句相似度研究理論和技術都比較成熟，但是研究內容主要是針對英語、日語等其他語言的語句相似度計算，很少涉及漢語語句相似度計算的內容.

在國內，漢語語句的相似度研究起步相對較晚，也取得了一定的成果，例如：張培穎[3]綜合考慮了詞形、詞序、長度、結構、距離和語義這6個方面的信息，給予不同特征不同的權重，提出了多特征融合的語句相似度計算方法.吳全娥，熊海靈[4]綜合考慮詞形、詞匯語義和句法三個方面的信息計算語句的相似度.文獻[5-7]是有關知網的語句相似度計算方法.雖然研究成果豐碩，但是漢語的博大精深導致其研究難度要高于日語和英語，因此漢語語句相似度計算的研究仍然有很長的一段路要走.

1.2 存在的問題

目前漢語語句的相似度計算存在如下一些問題：

1)重點考慮句法結構分析的方法

這類方法主要考慮語句結構和詞語之間的依存關系，忽略詞語之間的語義關系，句法分析技術不成熟，實際應用中準確率并不高.

2)重點考慮語義分析的方法

過度依賴語義詞典大小的影響，實用性小于基于關鍵詞詞形信息的語句相似度計算方法.

3)重點考慮關鍵詞詞形信息的方法

一些常見的此類方法，需要建立大規(guī)模語料庫，耗費大量的人力、物力，容易產生數據稀疏的問題，忽略句法結構和語義等深層信息.

DekangLin認為任何事物之間的相似度都是由它們的共性和個性決定，本文重點考慮關鍵詞詞形信息，對影響漢語語句共性和個性的因素做了深入研究，并將其中一些影響因素融入到漢語語句的相似度計算中，提出了基于馬爾科夫模型的漢語語句相似度計算方法.

2 語句特征分析

2.1 詞語的劃分

根據漢語相關知識可知，漢語語句都是由關鍵成分和修飾成分組成.一般情況下，主語和賓語是名詞或代詞，謂語是形容詞或動詞.其他所有詞性的詞均為修飾成分.語句相似度計算方法都是按照詞性對關鍵詞進行提取，把動詞、名詞、形容詞、代詞作為關鍵詞.

2.2 語句分析

語句相似度計算方法都是建立在關鍵詞的基礎上，語句的其他特征很多，很難做到所有特征都被作為衡量因素，同時特征之間也存在相互牽制的作用，下面僅對語句相似度計算中相對比較重要的兩個特征作簡單介紹.

在句長方面，本文中的句長是指語句中詞語的個數，漢語語句中詞的個數越多，蘊含的信息量越大，而句長是由語句中詞的個數決定.當其他條件一致時，長度越接近的兩個語句越相似.

在詞序方面，漢語語句的意思與詞序或多或少會有一定的聯(lián)系，詞序的變動可以使整個語句或詞組具有不同的意義，例如：“我對他好”與“他對我好”，這兩句話的關鍵詞與語句長度完全一樣，但是詞序不同，在不考慮詞序的情況下，會錯誤的把這類語句的相似度視為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的長度更短，本文創(chuàng)建的語句長度的相似度計算公式如式(1).

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

(1)

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

(2)

其中:p表示公共詞向量中的公共詞的個數，Rord(Ti,Tj)代表逆序數.

易證0≤OrdSim(Ti,Tj)≤1，這種詞序相似度計算的優(yōu)點是當一個語句的局部整體在另一個語句中出現時，能夠增加兩個語句的相似度，而且實現快捷.

在關鍵詞相似度計算方面，本文創(chuàng)建的關鍵詞相似度計算公式，如式(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的漢語分詞系統(tǒng)和人工分詞相結合的方式進行分詞處理.

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.

兩種方案對基于關系向量模型的方法進行了一定的優(yōu)化，更加平衡了兩個關鍵詞向量對語句相似度的影響，同時也在一定程度上縮小了兩個語句長度差對相似度的影響.

4 實驗與分析

本實驗從不同的新聞網站采集了131條國際新聞標題作為一個測試集，由于新聞標題言簡意賅，除去標點符號之后，基本都是關鍵詞，給實驗的進行帶來一定的方便.

對該測試集中的相關新聞標題中的同義詞進行替換，將替換后的測試集插入mysql數據庫中，用c3p0數據庫連接池以及dbutil數據庫連接工具連接數據庫，編程工具采用Eclipse.用中科院ICTCLAS漢語分詞系統(tǒng)(又名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%.實驗結果表明本文新提出的兩種相似度計算方案明顯優(yōu)于關系向量模型的相似度計算方法.

通過對錯誤的實驗數據以及計算公式進行分析，發(fā)現基于關系向量模型的相似度計算方法在計算兩個語句相似度時，對語句長度差的考慮嚴重不足.兩個新方案能夠較為準確的衡量兩個語句的影響因素，因此準確率也較高.本實驗采用了較小的語料庫即可說明新方法的優(yōu)越性，避免了大規(guī)模語料庫的構建.

另外，本實驗涉及的計算方法都是計算關鍵詞較多的語句的相似度，但是對非關鍵詞較多的語句相似度進行處理時，其準確率可能會受到影響.例如：“無論如何，我都要請你吃飯.”與“我要請你吃飯.”兩個語句關鍵詞完全一樣，關鍵詞向量長度、詞序也相同，可能會誤認為相似度為1，高估了兩個語句的相似度.此外，還有標點符號的不同，可能導致兩個語句的意思有差異.

5 結 語

本文提出的基于馬爾科夫模型的語句相似度計算方法充分考慮了相鄰詞語之間的共現作用，適當的衡量了語句長度對相似度的影響.同時，也表明以詞序為代表的其他一些語句特征在計算新聞標題相似度時影響甚微，在一定應用領域，并不是語句特征考慮的越多就準確率越高.雖然新方法的準確率得到了提高，但是不足之處是新方法只針對關鍵詞較多，且非關鍵詞較少的語句相似度計算較為準確，對非關鍵詞較多的語句的相似度計算還有待進一步研究.

[1] 中國互聯(lián)網絡信息中心.第33次中國互聯(lián)網絡發(fā)展狀況統(tǒng)計[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]. 計算機系統(tǒng)應用, 2010, 19(11): 110-114.

[5] 李迎凱,徐小良. 一種改進的基于知網的句子相似度計算方法[J]. 電子科技, 2012, 25(7): 69-71.

[6] 李 進. 基于知網的句子相似度計算的研究[J]. 電腦知識與技術, 2012, 29(8): 7073-7075.

[7] 董振東, 董 強, 郝長伶. 知網的理論發(fā)現[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