涉及地名的句子相似度計算方法的改進

黃　洪，豐　旭

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

涉及地名的句子相似度計算方法的改進

黃洪，豐旭

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

摘要：在計算涉及地名的句子相似度時，地名有著特別的重要性.如果不恰當地對地名進行處理，不體現出地名對于句子的重要性以及地名間的差異性，會導致相似度計算結果不甚合理.提出了一種改進的句子相似度計算方法.該方法在計算地名詞語相似度時利用了地名在地理樹中的層次關系以及從百度地圖API獲得的經緯度坐標，在計算非地名詞語相似度時則利用了HowNet知識庫，通過對地名詞語和非地名詞語賦予不同的權重來體現地名的重要性，并計算出句子的整體語義相似度，再結合句子結構的相似度計算出句子的綜合相似度.實驗表明：改進后的新方法對于計算涉及地名的句子相似度可以取得更理想的結果.

關鍵詞：句子相似度；地名；地理樹；經緯度

An improved calculation method for sentence similarity with

place names involved

HUANG Hong, FENG Xu

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:Place names are of special importance when the similarity of sentences involving place names is calculated. The calculation results will not be reasonable if an algorithm improperly deal with place names. This paper proposes an improved method of Chinese sentence similarity calculation. This method uses the latitude and longitude coordinates obtained by Baidu map API and the hierarchical relationship in geographical tree when the similarity of place names is calculated. The HowNet is used to calculate the similarity between non-place names words. Then it gives different weights to place name words and non-place name words in order to obtain the semantic similarity of sentences. Finally the similarity of two Chinese sentences is calculated combining the sentences’ semantic similarity with structure similarity. Experiments show that this improved method can achieve better results for the calculation of the sentence similarity involving place names.

Key words:sentence similarity; place names; geographical tree; coordinates

相似度計算一直是人工智能和自然語言處理領域的一個研究熱點[1]，句子相似度計算在自然語言處理的很多領域都有著十分廣泛的應用，如：問答系統、文本分類等，句子相似度主要是指兩個句子在語法、語義和語用等方面的相似程度.在理解涉及地名的句子時，地名往往具有特別的重要性.由于地名間的天然關系，在計算涉及地名的句子相似度時，也需要對地名進行特殊處理.我們在研究旅游問答系統時發現：地名間的相似度是反映句子相似度的一個重要因素.但是，在現有的句子相似度研究中，還沒有考慮到地名的特殊性和重要性.目前，中文句子相似度的計算方法大致可以分為以下幾類：第一類為基于特征詞的方法，該方法從兩個句子中分別提取特征詞，通過它們的特征詞間的相似度來反映兩個句子的相似度，程志強等[2]提出建立領域特征集，利用向量空間模型的方法計算句子相似度.第二類為基于語義詞典的方法，通過詞語相似度來反映句子相似度的，而詞語相似度的計算需要依賴于比較完備的大型語義詞典，秦兵等[3]提出利用HowNet知識庫對兩個句子中所有詞語兩兩之間進行相似度計算，將相似度最高的兩個詞語作為最優匹配對，最后將所有最優匹配的詞語對的相似度進行加權平均得到句子語義相似度.第三類為基于句法結構的方法，通過對兩個句子進行句法結構分析來計算兩個句子在句法結構上的相似性，HU Jinzhu等[4]認為通過兩個句子的詞性序列獲得最優匹配的相同詞性序列后，利用句子的詞性相似度和詞形相似度來反映句子結構相似度.

在計算涉及地名的句子的相似度時，三類方法沒有很好地對地名進行處理，例如：對于“南京有哪些好玩的地方”和“杭州有哪些好玩的地方”兩個句子，三類方法的計算結果都為1.0，實際上“南京”和“杭州”在地理位置上比較接近，文化環境較為相似，因此兩個句子具有一定的相似性，但是并不完全相同，計算結果為1.0是不符合主觀判斷的.導致這種情況的原因主要有以下幾種：第一類方法只考慮了詞語在句中出現的頻率，沒有考慮詞語的語義信息；第二類方法雖然考慮了語義信息，但是在HowNet常識知識庫中地名的收集不夠全面，并且沒有對地名進行明確的區分，使得已存在HowNet知識庫中的大部分地名間的相似度都為1.0，而不存在HowNet知識庫中的大部分地名間的相似度為0.0；第三類方法只考慮了句子結構的相似度，沒有考慮詞語語義信息，只要結構相同，兩個句子相似度就相同.因此針對地名構建了一個以中國為根節點的地理樹，同時獲取所有地名的經緯度坐標作為對此地理樹的一個補充，最后提出了一種新的涉及地名的句子相似度計算方法.該方法通過句子的詞類信息將句子分成地名詞語集合和非地名詞語集合，分別計算兩個句子對應集合間的相似度，同時賦予地名詞語和非地名詞語不同的權重，獲得句子整體語義相似度，再結合句子的結構相似度，最終得到句子的整體相似度.實驗結果表明，該方法在計算涉及地名的句子相似度時更符合人們的主觀判斷.

1涉及地名的句子相似度算法的改進

考慮到地名在句中的重要性和特殊性，將地名術語和非地名術語分離出來，分別計算地名詞語相似度和非地名詞語相似度，同時考慮到句子結構對于句子相似度存在一定的影響，將句子結構相似度融入到句子相似度中.主要做了以下幾個方面的工作.

1.1地名詞語相似度計算

在自然語言處理的很多應用中，經常會出現許多地名術語.如果利用基于HowNet的方法計算地名術語相似度，由于HowNet知識庫中存放的地名太少，且沒有具體區分，使得許多尚未記錄在HowNet知識庫中的地名間的相似度為0.0，而已存在HowNet知識庫中的地名間的相似度大部分為1.0，這樣的結果是不符合人的主觀判斷的；如果利用傳統的基于字符串匹配的方法計算這些術語的相似度則得到的結果大多為0.0，但是實際上，這些地名術語在地理位置、文化環境上都是存在一定相似性的.利用《中國地名錄》以及由數據堂提供的“全國地名地物詞典”等資料構建了一個地理樹，以中國為根節點，利用地名間的下屬關系將每個地名表示成樹中的節點，部分地理樹如圖1所示.

圖1　地理樹部分結構圖Fig.1　The part of geography tree structure

在計算兩個地名間的相似度時，由于考慮到地理樹中子節點是父節點的一個分支，兩節點間距離、公共節點深度以及兩節點深度差三個要素對兩地名節點間的相似度計算存在著重要的影響，地名gi和地名gj在地理樹中的相似度計算式為

(1)

式中：deep(gi∩gj)為地名gi和地名gj在地理樹中的最近公共父節點距離根節點的路徑長度；deep(gi)為地名gi在地理樹中距離根節點的路徑長度，假設初始根節點的路徑長度deep(中國)為1.

利用地理樹的層次關系計算兩地名間的相似度在一定程度上能達到較好的效果，但是對于計算同一父節點下的所有地名中任意兩地名間的相似度結果都相同，因此，在研究了相關地理信息系統GIS[5]后，考慮引入地名的經緯度坐標作為地理樹的一個重要補充.地名的經緯度坐標通常可以通過一些定位查詢軟件[6]進行獲取，百度地圖API[7]是一套為開發者免費提供的基于百度地圖的應用程序接口，提供基本地圖展現、搜索、定位、路線規劃、LBS云存儲與檢索等功能.通過利用百度地圖API的接口獲得每一個地名的經緯度，最后將經緯度作為地名gi和gj的向量坐標，利用余弦值來表示兩個地名在經緯度上的相似度，計算式為

(2)

式中：xi為地名gi的經度值；yi為地名gi的緯度值.

利用上述對地名術語相似度計算有著重要影響的兩個因素：地理樹層次關系以及地名經緯度坐標，得到計算地名術語整體相似度的公式為

Sim(gi,gj)=αSimg(gi,gj)+βSiml(gi,gj)

(3)

式中α和β為調節參數，α+β=1.經多次實驗發現，當α=0.6，β=0.4時計算結果能夠體現地名間的差異性，也較為符合人們主觀判斷.

如果待比較的句子中獲得的地名在地理樹中存在歧義，例如“海底世界有哪些好玩的東西”經過分詞后會得到一個地名“海底世界”，但是句中并沒有其他地名明確指出這是哪個地名下的“海底世界”，那么這個“海底世界”可能是杭州的“海底世界”，也可能是南京的“海底世界”，或者其他地方的“海底世界”，即“海底世界”無法在地理樹中獲得一個惟一的值.考慮到人們主觀上通常詢問的都是兩個較為相近的地名之間的比較，例如：“海底世界”和“杭州海洋公園”，主觀上人們會認為詢問的是“杭州海底世界”和“杭州海洋公園”的比較，因此可以通過以下方法來計算地名不惟一時兩個待比較的地名gi和gj的相似度：

1) 當gi惟一，gj不惟一時，即gi在地理樹中獲得相對應的地名Gi，gj在地理樹中獲得若干個相對應的地名{G1j，…，Gtj}，通過式(3)將Gi和{G1j，…，Gtj}中的每一個地名進行相似度計算，取相似度值最大的兩個地名的相似度作為gi和gj的相似度并用于句子的相似度計算.

2) 當gi不惟一，gj也不惟一時，取gi在地理樹中對應的歧義地名集合{G1i，…，Gni}，gj在地理樹中對應的歧義地名集合{G1j，…，Gtj}，通過式(3)將{G1i，…，Gni}中的每一個地名和{G1j，…，Gtj}中的每一個地名兩兩進行相似度計算，取最大值作為gi和gj的相似度值并用于句子相似度的計算.

1.2非地名詞語相似度計算

國內外對詞語相似度的計算方法大致可以分為兩類：基于統計的方法和基于語義詞典的方法.基于統計的方法是通過計算兩個詞語所處的上下文環境的相似度來度量兩個詞語的相似度的，王石等[8]通過利用詞語的搭配詞作為其上下文來計算詞語的相似度，該方法建立在大規模語料庫的基礎上，屬于經驗主義方法.基于語義詞典的方法是利用已有的語義詞典中概念的上下位關系，通過計算兩個概念在樹狀層次體系中的距離來得到詞語相似度，屬于理性主義方法，例如：基于WordNet語義詞典，AHSAEEMG等[9]和KIMTANIDK等[10]通過計算兩個概念節點之間的最短路徑來計算詞語間的相似度；基于HowNet的語義詞典結構，劉群等[11]、江敏等[12]、王小林等[13]和崔淑潔等[14]提出了通過義原樹中的上下位關系計算相似度的方法；基于同義詞詞林，YUZhengtao等[15]和田久樂等[16]提出了利用樹形圖中的節點間路徑距離獲得相似度的方法.

直接使用劉群等[11]提出的利用HowNet計算詞語相似度的方法，計算詞語相似度公式為

(4)

式中：W1和W2為兩個詞語；C1i為詞語W1中的某個義項；C2j為詞語W2中的某個義項，詞語相似度是利用兩個詞語的所有義項之間相似度的最大值來表示的.

1.3句子結構相似度計算

句子結構相似度反映了兩個句子在整體結構上的相似程度，是影響句子相似度的一個重要因素.王榮波等[17]利用詞類信息經過正向匹配和反向匹配后獲得兩個句子結構的詞類最優匹配序列，從而得到句子的結構相似度；LANYanling等[18]將兩個句子的詞性信息組成詞性矩陣，利用對應詞間距獲得結構相似度.在計算句子結構相似度時只考慮句長相似度和詞序相似度.句長相似度反映了句子在整體長度上的相似程度，計算公式為

(5)

式中：S為長句；T為短句；Len(S)為長句S分詞后詞語的個數；Len(T)為短句T分詞后詞語的個數.詞序相似度反映了兩個句子的相同詞語在順序關系上的相似程度，計算公式為

(6)

式中：假設兩個句子的相同詞語在長句S中的順序為正序，則RevOrd為相同詞語序列在短句S中的逆序數；MaxRevOrd為相同詞語序列的最大逆序數.

1.4實現語句相似度改進算法的具體步驟

定義1相似度矩陣：兩個句子對應集合中所有詞語兩兩配對進行詞語相似度計算，將計算結果存放到矩陣中，矩陣初始化為0.

首先，假設兩個句子S和T分詞后對應的詞類序列為SPOS和TPOS.

SPOS：S0，S1，S2，…，Si，…，Sn-1

TPOS：T0，T1，T2，…，Tj，…，Tm-1

式中：Si表示句子S中下標為i的詞語的詞類，Tj表示句子T中下標為j的詞語的詞類.

算法具體步驟如下：

1) 根據詞類信息存放詞語，去除修飾性地名術語：遍歷句子T中每個詞類Tj，判斷Tj是否屬于地名詞類ns：如果不屬于ns，則將該詞類Tj對應的詞語存放到非地名集合中；如果屬于ns，則判斷該詞類的下一個詞類Tj+1是否屬于ns：如果Tj+1不屬于ns，則將Tj對應的詞語存放到地名集合中，如果Tj+1屬于ns，則判斷Tj+1對應的地名是否是Tj對應的地名的下屬，如果不是其下屬，則將Tj對應的詞語存放到地名集合中，如果是其下屬，則返回繼續遍歷下一個詞類Tj+1.同理，對句子S進行相同的步驟.

2) 對地名詞語進行相似度計算：經過步驟1)將句子分詞后的詞語分別存放到了地名集合和非地名集合中，利用公式(3)計算得到兩個句子對應地名集合中每個地名術語之間兩兩配對的相似度矩陣，從相似度矩陣中獲得地名術語的最佳配對結果.

3) 對非地名詞語進行相似度計算：利用公式(4)得到兩個句子對應非地名集合中每個詞語之間兩兩配對的相似度矩陣，從中獲得詞語的最佳配對結果.

4) 經過上述三個步驟后，對于兩個句子S和T，可以得到地名術語的最佳配對結果和非地名詞語的最佳配對結果，由這些最佳配對結果可以獲得句子整體的語義相似度，計算公式為

(7)

式中：n為兩個句子的地名集合中獲得的最佳配對地名的對數；gi1為配對地名中句子S的地名；gi2為配對地名中句子T的地名；m為兩個句子的非地名集合中獲得的最佳配對詞語的對數；Wj1為配對詞語中句子S的詞語；Wj2為配對詞語中句子T的詞語；w1為賦予地名詞語的權重；w2為賦予非地名詞語的權重，w1+w2=1.經過多次實驗發現，當w1=0.7，w2=0.3時獲得的相似度值能夠體現兩個句子在語義上的相似程度，較為符合人們的主觀判斷.

5) 根據式(5，6)計算句子的句長相似度和詞序相似度，獲得句子的結構相似度，計算公式為

Simstru(S,T)=w3SimLen(S,T)+w4SimOrd(S,T)

(8)

式中：w3為句子長度相似的權重；w4為句子詞序相似的權重，w3+w4=1.經過多次實驗發現，當w3=0.6，w4=0.4時獲得的相似度值能夠體現兩個句子在結構上的相似程度，也較為符合人們的主觀判斷.

6) 將句子整體的語義相似度與句子結構相似度相結合，得到句子整體相似度，計算公式為

Sim(S,T)=λ1Simsem(S,T)+λ2Simstru(S,T)

(9)

式中：λ1為句子語義相似度的權重；λ2為句子結構相似度的權重，λ1+λ2=1.經過實驗對比分析發現，當λ1=0.9，λ2=0.1時計算結果較為符合人們的主觀判斷.

2實驗及結果分析

在實驗中，使用中科院的分詞系統ICTCLAS2011對句子進行分詞和詞性標注處理，中科院的分詞系統ICTCLAS2011所使用的漢語詞性標注集將詞類分為22個一類、66個二類和11個三類，由于該分詞系統對于地名的識別還不是十分完整，筆者將整理出來的地理樹知識作為參考資料存放到系統的用戶導入文件中，以便于在分詞時能夠更好的識別出地名.由于目前還沒有可用于中文句子相似度測試的標準化測試集，鑒于本實驗重點研究的是地名對于語句相似度的影響，而旅游領域問答系統的問句通常會涉及到地名，因此實驗例句使用除地名不同外其他詞語都基本相同的旅游領域的典型句子.本次實驗還邀請了35名學歷本科以上、身心健康的同學對這些實驗例句進行主觀評分，分數取值為0到1之間的任意小數，分數越接近0說明相似度越低，分數越接近1說明相似度越高，最后將所有同學的主觀數據進行加權平均，得到的結果存放在表1的“主觀”一列中，作為標準數據用于和其他四種方法的計算結果進行比較.方法1是基于特征詞的方法[2]，方法2是基于HowNet語義詞典的方法[3]，方法3是基于句法結構的方法[4]，方法4是筆者的方法.由于篇幅有限，部分實驗結果如表1所示.

表1　部分句子相似度計算實驗結果

表1給出了兩組實驗例句，從表1中可以看出：相似句A5、A6和A8在方法1下與源句A的相似度計算結果都為1.0，但是實際上，“吳山廣場”和“上城區”只是同屬于杭州，“蘇州寒山寺”和“北京天壇”與“上城區”沒有關系，只是距離遠近的區別，兩個地方距離越近，城市文化和氣候差異就越小.由此可以看出：相似句A5和源句A的相似度應該高于相似句A6和源句A的相似度，相似句A8和源句A的相似度應該最低，而且這些相似句和源句A都不相同，因此實驗結果是不符合主觀判斷的.相似句B1、B3和B4在方法2下與源句B的相似度計算結果都為1.0，但是三個相似句與源句B都不是完全相同的，相似句B1比較的是“寒山寺”和“靈隱寺”，相似句B3比較的是“杭州”和“南京”，相似句B4比較的是“蘇州”、“杭州”和“揚州”，所以相似句B4和源句B的相似度應該高于相似句B1、B3和源句B的相似度，因為B4中會包含源句B的“蘇州”和“杭州”的比較，故實驗結果是不符合主觀判斷的.相似句A2和A3在方法3下與源句A的相似度計算結果都為0.96，但是相似句A2的地名“平海路”被包含在源句A的地名“上城區”中，相似句A3的地名“杭州”包含了源句A的地名“上城區”，因此A2和A3與源句A的相似度應該是不同的，故實驗結果并不符合主觀判斷.而且在第一組實驗例句中，相似句A9與源句A最接近，相似度也應該是最高的.可見三種典型算法都有著各自的缺點，它們的計算結果不太符合主觀判斷.

但是，從方法4的計算結果中可以看出：相似句A5，A6，A8和源句A在方法4下的相似度計算結果互相比較時，A5的相似度高于A6的相似度，A8相似度是最低的，這較好地體現了方法4的地名相似度計算中的經緯度相似度計算對沒有包含關系的地名進行了距離遠近的區分.同理，相似句B3的相似度要高于相似句B2與源句B的相似度.同時，相似句A1和源句A在方法4下的計算結果不為1.0，這也反映了方法4的地名相似度計算中的地理樹相似度計算對具有包含關系的地名的區分起到了一定的作用.相似句A9和源句A的相似度不為1.0，這說明方法4還考慮到了句子結構對于句子的影響.將四個方法的計算結果和主觀判斷結果進行方差計算，得到的結果如表2所示.

表2　方差計算結果比較

從表2容易看出：方法4的計算結果在總體上是最接近主觀判斷結果的，而且在邀請的35名同學中有86%的同學都認為方法4的計算結果是四個方法中最好的.

3結論

提出了一種改進的涉及地名的句子相似度計算方法，通過構建地名地理樹和獲取地名經緯度來計算地名詞語間的相似度，在計算句子相似度時通過對地名詞語和非地名詞語賦予不同的權重來體現地名對于計算句子相似度的重要性，并考慮了句子結構的因素.實驗表明：改進后的方法在計算涉及地名的句子相似度時比傳統方法更加合理，計算結果更符合人們的主觀判斷.

參考文獻：

[1]徐彩虹，劉志，潘翔，等．一種基于實例學習的三維模型檢索匹配方法[J]．浙江工業大學學報，2012，40(3)：326-330.

[2]程志強，閔華松．一種基于向量詞序的句子相似度算法研究[J]．計算機仿真，2014，31(7)：419-424.

[3]秦兵，劉挺，王洋，等．基于常問問題集的中文問答系統研究[J]．哈爾濱工業大學學報，2003，35(10)：1179-1182.

[4]HU Jinzhu, XU Ting, SHU Jiangbo, et al. A kind of calculation method of Chinese sentence structure similarity[C]//International Conference on Advanced Computer Theory and Engineering(ICACTE). Chengdu: International Conference on IEEE，2010：344-347.

[5]劉俊萍，董飛龍，邵佳偉．GIS支持下的海塘工程信息管理[J]．浙江工業大學學報，2014，42(2)：199-203.

[6]徐志江，莊壯，孟利民．一種基于Android智能手機的車載定位查詢軟件[J]．浙江工業大學學報，2013，41(6)：655-659.

[7]百度．百度地圖API[EB/OL]．[2015-06-10]．http://developer.baidu.com/map/.

[8]王石，曹存根，裴亞軍，等．一種基于搭配的中文詞匯語義相似度計算方法[J]．中文信息學報，2013，27(1)：7-14.

[9]AHSAEE M G, NAGHIBZADEH M, NAEINI S E Y. Semantic similarity assessment of words using weighted WordNet[J]. International Journal of Machine Learning and Cybernetics，2014，5(3)：479-490.

[10]KIMTANI D K, CHOUDHURY J, CHAKRABARTY A. Improvement in word sense disambiguation by introducing enhancements in English WordNet structure[J]. International Journal on Computer Science and Engineering，2013，2(5)：435-438.

[11]劉群，李素建．基于《知網》的詞匯語義相似度計算[J]．中文計算語言學，2002，7(2)：59-76.

[12]江敏，肖詩斌，王弘蔚，等．一種改進的基于《知網》的詞語語義相似度計算[J]．中文信息學報，2008，22(5)：84-89.

[13]王小林，王義.改進的基于知網的詞語相似度算法[J]．計算機應用，2011，31(11)：3075-3077.

[14]崔淑潔．句子相似度算法研究及其在中文問答系統中的應用[D]．杭州：浙江工業大學，2014.

[15]YU Zhengtao, HU Lei, HUANG Li, et al. Similarity computation of Chinese question based on chunk[C]//Proceedings of the Fifth International Conference on Machine Learning and Cybernetics．Dalian：International Conference on IEEE，2006：17-22.

[16]田久樂，趙蔚．基于同義詞詞林的詞語相似度計算方法[J]．吉林大學學報，2010，28(6)：602-608．

[17]王榮波，池哲儒．基于詞類串的漢語句子結構相似度計算方法[J]．中文信息學報，2005，19(1)：21-29.

[18]LAN Yanling, CHEN Jianchao. Chinese sentence structures similarity computation based on POS and POS dependency[J]．Computer Engineering,2011，37(10)：47-49.

(責任編輯：陳石平)

文章編號：1006-4303(2015)06-0624-06

中圖分類號：TP391

文獻標志碼：A

作者簡介：黃洪(1964—)，男，江西豐城人，教授，研究方向為軟件開發方法、智能電子商務和自然語言處理等，E-mail：huanghong@zjut.edu.cn.

收稿日期：2015-06-12