基于語義擴展的句子相似度算法

冶忠林，賈真＊，楊燕，尹紅風(fēng)

（1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756；2.DOCOMO Innovations公司，帕羅奧圖 美國 94304）

0 引言

句子相似度計算是自然語言處理領(lǐng)域中比較基礎(chǔ)而重要的研究課題，它在現(xiàn)實中有廣泛的應(yīng)用。在信息檢索領(lǐng)域，句子相似度計算方法用來對檢索結(jié)果進行排序。在問答系統(tǒng)領(lǐng)域，需要使用相似度方法對用戶所提問題和系統(tǒng)知識庫中的問題進行比較，找到問題的最佳匹配從而返回最佳答案。在機器翻譯領(lǐng)域，通過計算句子的相似度來匹配相似的句子，找出相似的翻譯。

Palakorn等 總結(jié)了三類計算句子相似度的算法，對當(dāng)前主要的算法進行了分類，同時分析了各種方法的原理并將它們進行了對比。漢語和英語句子的相似度計算有很大的差別，因為英語是基于語法的句子，而漢語是基于語義的句子，因此，在計算句子相似度時，英語句子相似度是從句子的依存關(guān)系、詞語距離方面考慮兩個長字符串的匹配程度，而漢語句子是從組成句子的詞性、詞義及整個句子的語義角度考慮。在國外，計算句子相似度主要有基于距離及其擴展算法的相似度模糊匹配［3］、MCWPA字符串快速比較算法［4］、最長公共子序列算法［5］等，這些算法都是基于字符串的比較和處理。比如，最長公共子序列算法就是通過求兩個英語句子中公共的子串來計算相似度。在國內(nèi)，漢語言自然語言句子的相似度研究也取得了很多成果。例如，Yin［6］在向量空間模型的基礎(chǔ)上提出了一種同時考慮句子結(jié)構(gòu)和語義信息的關(guān)系向量模型。吳佐衍等［7］利用概念層次網(wǎng)絡(luò)理論詞匯層面聯(lián)想的概念表述體系來計算詞語之間的相似度。李彬等［8］提出了基于語義依存關(guān)系的漢語句子相似度計算方法。此方法基于董強和董振東先生創(chuàng)建的《知網(wǎng)》知識資源，首先采用哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院信息檢索研究室所做的依存句法分析器建立句子依存樹，然后利用依存結(jié)構(gòu)計算有效搭配對之間的相似程度。該方法測試結(jié)果的準(zhǔn)確率嚴重依賴于所生成的句法依存樹，在分析句子較長、動詞較多的網(wǎng)絡(luò)文章時，正確率常常比較低。李茹等［9］提出了基于漢語框架網(wǎng)語義資源，通過多框架語義分析、框架的重要度度量、框架的相似匹配、框架間相似度計算等關(guān)鍵步驟來實現(xiàn)句子語義的相似度度量。張奇等［10］通過回歸方法將uni－gram、bi-gram、tri-gram幾種相似度結(jié)果綜合起來，提出了一種新的句子相似度度量方法并應(yīng)用于文本自動摘要中。

本文提出了一種基于語義擴展的句子相似度計算方法。首先，利用現(xiàn)有的搜索引擎技術(shù)，對句子進行語義擴展得到與句子相關(guān)的長文本；其次，使用特征提取獲得長文本的特征項及分布概率，將句子轉(zhuǎn)化為具有與句子含有相同語義的特征項組；再次，取兩個特征項的交集，利用其分布概率建立向量空間模型，求得向量的夾角的余弦值即為相似度值。因此，本文提出的方法將句子相似度的計算從詞形、詞序、詞義、依存關(guān)系的理解轉(zhuǎn)移到對句子語義間的相似度計算，從而減少在相似度計算時對句子語義的歧義理解。

1 基于語義擴展的句子相似度算法介紹

1.1 算法原理

現(xiàn)有的計算句子相似度的方法僅僅從詞形、詞序、句子結(jié)構(gòu)、依存關(guān)系等方面考慮句子表面的信息，沒有嘗試去理解句子的隱含語義。比如，基于空間向量的句子相似度算法把詞當(dāng)作一個維度，于是，一個句子的每個詞以及詞的權(quán)重就構(gòu)成了一個n維空間圖，那么求兩個句子的相似度，也就是求兩個空間圖的接近度。

本文放棄了對句子的詞形、詞序、句子結(jié)構(gòu)、依存關(guān)系的分析，而考慮句子所隱含的語義特征，類似于知網(wǎng)中的義原，即利用搜索引擎，對句子進行知識擴展，挖掘出更多與句子相關(guān)的知識文本，如此，一條較短的句子擴展為一個較長的文本，進而將句子之間的相似度計算轉(zhuǎn)化為文本之間的相似度計算。相較于短句子，長文本具有大量的信息可以利用，更加有利于計算相似度。然后使用潛在狄利克雷分配（Latent Dirichlet Allocation，LDA）模型，對擴展后的文本進行特征提取，獲得該文本的主要內(nèi)容，即特征詞以及特征詞在主題空間上的概率分布，最后將特征詞轉(zhuǎn)化為向量空間模型，計算取交集后兩個共同部分的向量之間的夾角的余弦值，該值即為兩個句子的相似度。

本文中的相似度計算算法主要由以下三個步驟組成：

（1）知識擴展：基于搜索引擎的句子內(nèi)容擴展；

（2）特征提?。夯贚DA的特征提??；

（3）向量空間模型建立：將特征項轉(zhuǎn)化為向量模型。

1.1.1 知識擴展

知識擴展是對句子語義的深度理解，對一個句子單獨地進行語義理解具有很高的難度，但是如果將一個句子的語義轉(zhuǎn)化為文本，可有效地利用現(xiàn)有的知識挖掘算法對該文本進行特征提取，這有助于對句子語義進行分析。由于搜索引擎返回的頁面與所要查詢的問題高度相關(guān)，所以在搜索引擎中，由頁面排序算法可知，排名越靠前的網(wǎng)頁標(biāo)題和摘要信息與查詢語句越相關(guān)。

本文首先利用搜索引擎下載與句子相關(guān)的前100個頁面的標(biāo)題和摘要，然后組成一個長文本，之后去除大文本中的干擾詞和噪音信息。其中干擾詞包括停用詞和搜索引擎中經(jīng)常出現(xiàn)的詞語，比如“問答”、“搜索”、“了解”等詞語。噪音信息包括組成網(wǎng)頁的HTML語言、CSS視圖層、JAVASCRIPT等。

例如，對于句子T1＝｛“西紅柿是什么顏色”｝，利用搜索引擎進行知識擴展得到大文本，然后去干擾詞、噪音、分詞處理后結(jié)果如表1所示。

表1 知識擴展返回的大文本Table 1 Long text after knowledge extension

1.1.2 特征提取

特征提取就是對知識擴展后的大文本提取特征。本文使用LDA進行特征提取。

對于句子T1＝｛“西紅柿是什么顏色”｝和T2＝｛“番茄是什么顏色”｝，知識擴展后，獲得大文本，之后進行特征提取，根據(jù)經(jīng)驗值，設(shè)置主題個數(shù)為1，取分布概率最高的5個特征項作為句子的特征項。如表2所示：

表2 LDA模型特征項提取Table 2 Features extraction by LDA model

通過LDA特征提取之后，句子可用表2中的特征項表示，即句子的語義可以用特征項表示。因此，兩個句子的相似度可以通過特征項的相似度來表示。

1.1.3 空間向量模型建立

空間向量中，文檔中的每個詞可以當(dāng)作一個維度，而詞的頻率作為該維度的值，即向量，于是文檔中的每個詞和詞頻就構(gòu)成了一個多維空間圖。求兩個文檔的相似度就是求兩個空間圖的接近度，即距離。在信息檢索中，常用的計算距離的方式有余弦相似度計算、相關(guān)系數(shù)、Dice、Jaccard等。本文使用余弦相似度求兩個文本的相似度。

當(dāng)獲取了特征項組一和特征項組二（表2所示）之后，需要做交集運算，找出兩個特征組向量的共同部分。因為該共同部分雖然特征項相同，但是相同特征項的分布概率卻不同，因此取交集運算后得到兩個向量長度相同但分布概率不同的向量IP1和IP2。之后計算這兩個向量的夾角的余弦值。

例如 表2中，IP1＝｛0.143 6，0.114 9，0.023 7，0.017 1，0.008 8｝，IP2＝｛0.123 9，0.100 8，0.049 9，0.017 4，0.008 8｝，則S（T1，T2）＝S（IP1，IP2）＝cosθ，其中θ為IP1和IP2的夾角。綜上，利用空間向量模型，可以將兩個句子的相似度計算轉(zhuǎn)化為句子特征項向量的夾角余弦值的計算。

1.2 算法定義

為了便于說明算法，此處對文章中所用到的概念作如下定義。

定義1 句子向量：對于一個句子s使用分詞系統(tǒng)，可得到該句子的分詞結(jié)果，該結(jié)果有一個或多個詞w構(gòu)成，得到的所有詞wi構(gòu)成的句子向量叫作句子Si的向量表示，即：Si＝｛w1，w2，…，wn｝。

例如 s1：劉德華出演過哪些電影。s2：劉德華的電影有哪些。經(jīng)過西南交通大學(xué)漢語分詞系統(tǒng)分詞之后，s1：劉德華／nr出演／v過／uguo哪些／ry電影／n。s2：劉德華／nr的／ude1電影／n有／vyou哪些／ry。那么，s1和s2的向量形式為：

S1＝｛劉德華，出演，過，哪些，電影｝，S2＝｛劉德華，的，電影，有，哪些｝。

定義2 句子向量長度：對于Si，如果可用向量的形式表示，那么Si中單詞的數(shù)量為句子Si的向量長度，即句子Si的向量長度可表示為len（Si）。

例如 對于定義1中的兩個句子s1和s2，有：len（S1）＝5，len（S2）＝5。

定義3 擴展向量表：對于已經(jīng)分詞的句子s1和s2，并且len（S1）＞0，len（S2）＞0，利用搜索引擎的知識擴展和理解功能，將句子向量表輸入到搜索引擎，可獲得相關(guān)的知識，去除停用詞、干擾詞，然后使用主題模型進行建模學(xué)習(xí)，可獲得與句子s1和s2的相關(guān)詞wi與詞wi概率分布pi。同時，詞wi的向量組成稱為擴展向量表Ri，詞的概率分布pi組成的向量表稱為詞的概率分布向量表Pi。即：Ri＝｛w1，w2，…，wn｝，Pi＝｛p1，p2，…，pn｝。

例如 對于定義1中的兩個句子s1和s2，利用所有引擎進行擴展，然后使用LDA模型進行建模，最終得到5個推薦詞，且在主題空間中分布概率最高，則R1＝｛劉德華，電影，演，出演，拍｝，R2＝｛劉德華，電影，演，片，出演｝，P1＝｛0.168 8，0.144 6，0.062 1，0.051 6，0.019 6｝，P2＝｛0.170 8，0.142 1，0.020 0，0.0118，0.009 8｝。

定義4 交集向量表：已知擴展向量表R1和R2，如果R1和R2有相同的單詞wi，并且len（R1）＞0，len（R2）＞0，那么，求得向量R1和R2的交集的結(jié)果稱為兩個句子的交集向量表IR，因為IR中的每個詞有2個不同的分布概率，所以與之相對應(yīng)的分布概率記為IP1和IP2。即：

IR＝R1∩R2＝｛w1，w2，…，wn｝，IP1＝｛p11，p12，…，p1n｝，IP2＝｛p21，p22，…，p2n｝。

例如 對于定義3中的兩個擴展向量表R1和R2，有IR＝R1∩R2＝｛劉德華，電影，演｝，其中IP1＝｛0.168 8，0.144 6，0.062 1｝，IP2＝｛0.170 8，0.142 1，0.020 0｝。

該節(jié)中，對計算句子相似度的相關(guān)概念及下小節(jié)中要出現(xiàn)的數(shù)學(xué)符號做出了定義，比如句子s、句子向量表Si、擴展向量表Ri、交集向量表IR、概率分布向量表Pi以及IP1和IP2等。

1.3 算法過程

語義擴展的句子相似度算法利用搜索引擎，擴展句子的語義信息，然后使用LDA模型，獲得主題空間上分布概率較高的某些詞wi，同時獲得詞的分布概率pi，隨后獲取兩個句子的交集向量表IR、概率分布向量表Pi以及IP1和IP2，最后使用IP1和IP2建立向量空間模型，計算向量IP1和向量IP2的夾角的余弦。

在向量空間模型中，計算兩個語句s1，s2的相似度Sim（s1，s2）時，常用向量之間的夾角的余弦值表示，所以在該小節(jié)中，計算語句s1，s2的相似度Sim（s1，s2）可認為是計算向量IP1和向量IP2的夾角的余弦值。具體公式如下：

當(dāng)len（IR）＝0時，Sim（s1，s2）＝0。

當(dāng)len（IR）＝len（R1）＝len（R2）時，Sim（s1，s2）＝1。

其中，θ表示向量IP1與向量IP2之間的夾角，p1n為向量IP1中的每一個概率值，p2n為向量IP2中的每一個概率值，k為交集向量表IR中詞的個數(shù)。

算法偽代碼如下：

在1.2中S1＝｛劉德華，出演，過，哪些，電影｝，S2＝｛劉德華，的，電影，有，哪些｝，R1＝｛劉德華，電影，演，出演，拍｝，R2＝｛劉德華，電影，演，片，出演｝，P1＝｛0.168 8，0.144 6，0.062 1，0.051 6，0.019 6｝，P2＝｛0.170 8，0.142 1，0.020 0，0.011 8，0.009 8｝，IR＝R1∩R2＝｛劉德華，電影，演｝，其中IP1＝｛0.168 8，0.144 6，0.062 1｝，IP2＝｛0.170 8，0.142 1，0.020 0｝。則使用公式1計算句子s1與句子s2之間的相似度為：

從上面分析中可以看出，本文提出的方法利用搜索引擎，擴展句子的語義信息，類似于知網(wǎng)中的義原，所以當(dāng)兩個句子高度相似時，其擴展后的語義也高度相似，如果當(dāng)兩個句子高度不相似時，其擴展后的語義則相差很大。綜上，考慮句子語義擴展的相似度算法可以準(zhǔn)確地計算出兩個句子之間的相似度，并且可以解決其他句子相似度算法中兩個毫無相關(guān)的句子相似度很高的現(xiàn)象。另外，本文提出的方法只對兩個擴展向量表中的交集向量表IR進行相似度計算，所以能在一定程度上降低運算的時間復(fù)雜度。

2 實驗結(jié)果分析

在該小節(jié)，使用2個實驗進行算法效果對比。實驗一是本文提出的方法與文獻［11］提出句子相似度計算方法做比較，同時給出其他常用的相似度計算方法的值。在實驗一中，測試了3組句子，每組句子有1個源句子和5個相似的句子構(gòu)成且與源句子的相似度依次遞減。實驗二使用Li和David［12］提出的實驗方法進行比較，從當(dāng)前的網(wǎng)絡(luò)新聞中收集了教育、科技、健康、軍事、旅游等10大類新聞文本組成10個測試樣本集，每個測試樣本集約50個句子，共500個句子。我們從10個測試樣本集中隨意抽取1條目標(biāo)語句，然后人工的找出與目標(biāo)句子語義比較相近的3個測試句子組成一組，即共10組句子，每組1個目標(biāo)句子，3個測試句子，共40條句子。

2.1 實驗一

為了和其他算法進行對比，本文計算了基于語義和詞序的句子相似度值、基于詞語共現(xiàn)模型的相似度值、基于詞類串句子相似度值。

方法1：本文方法。

方法2：基于本文知識擴展的方法，但是使用TF-IDF模型獲取大文本的特征詞和特征詞的詞頻。

方法3基于詞語共現(xiàn)模型的句子相似度計算方法

方法4：基于詞類串的漢語句子結(jié)構(gòu)相似度計算方法［14］。

方式5：基于語義和詞序的句子相似度計算方法［15］。

關(guān)于以上5種方法的句子相似度結(jié)果如表3所示。

表3 句子相似度計算結(jié)果對照表Table 3 Result comparison in different sentence similarity computing method

從表3中看以得出，當(dāng)兩個句子相似度很高時，基于本文的方法1和方法2，可以得到一個較高的相似度值，當(dāng)兩個句子相似度很低時，本文的方法計算所得的相似度值符合常識。方法3、4在實驗一中，也具有較好的實驗結(jié)果，方法5中當(dāng)兩個句子相似時，效果較好，但是當(dāng)兩個句子不相似時，卻出現(xiàn)相似度值比較高的情況。

2.2 實驗二

實驗二中，有10個測試樣本集和10組句子，每組句子有1個目標(biāo)句子和3個測試句子組成。10個樣本測試集的文本類別和10組句子的文本類別是相對應(yīng)的。使用本文提出的方法，使用1個目標(biāo)句子在其對應(yīng)類別的樣本測試集中計算句子相似度，取相似度最高的3條句子，然后和10組句子中的測試句子相比較。如果通過本文計算相似度方法得到的句子與人工方式找到的測試語句相同，則認為本文的方法有效。表4是采用不同的句子相似度算法獲取相似度最高的3條句子，然后和人工選出的3條句子對比后的準(zhǔn)確率，共有10個樣本集，因此測試句子和人工選出的句子共有30條。

表4 實驗二結(jié)果Table 4 Second experiment’s result

從表4可以發(fā)現(xiàn)，在近500條的句子的測試過程中，基于句子語義擴展的算法其準(zhǔn)確率達到0.87，基于詞語共現(xiàn)模型的相似度算法的準(zhǔn)確率為0.63，而基于語義和詞序相似度算法準(zhǔn)確率卻比較低。主要原因是，在實驗二中，目標(biāo)語句與3條相似語句之間語義很接近，所以在語句的詞語構(gòu)成上，詞語共現(xiàn)的頻率就會提高，因此基于詞語共現(xiàn)的相似度算法在該類數(shù)據(jù)集上表現(xiàn)較好。而基于語義和詞序的相似度算法，由于詞語相似度計算的準(zhǔn)確率受限，所以句子相似度值準(zhǔn)確率較差?；诰渥诱Z義擴展的方法，通過搜索引擎進行語義理解，找出與句子含有相同語義的更多特征詞組，所以能夠獲得符合常識的相似度計算結(jié)果。

3 結(jié)束語

本文提出了一種基于語義擴展的句子相似度算法，將句子相似度的計算從詞形、詞序、詞的語義、依存關(guān)系的理解轉(zhuǎn)移到對句子語義的理解上，依托強大的搜索引擎的頁面推薦功能，能夠?qū)⒑唵蔚木渥舆M行語義擴展，從而解決句子特征詞稀疏問題，提升句子相似度計算的準(zhǔn)確性。實驗表明，與基于詞語共現(xiàn)模型、語義和詞序的相似度方法、詞類串的漢語句子結(jié)構(gòu)相似度計算方法相比，本文的方法對相似度很高的句子可有效地找出其中的關(guān)聯(lián)，計算出準(zhǔn)確的相似度，對于相似度很低的句子，由于其隱含的語義相差很大，所以本文計算出來的相似度值很低，因此，基于句子語義擴展的方法計算所得的值符合常識判斷。

［1］ Zhang H，Yu Z，Shen L，et al.Naxi Sentence Similarity Calculation Based on Improved Chunking Edit-distance［J］.International Journal of Wireless and Mobile Computing，2014，7（1）：48-53.

［2］ Palakor A，Hu X H，Shen X J.The Evaluation of Sentence Similarity Measures［C］／／Proceedings of the 10th International Conference on Data Warehousing and Knowledge Discovery，Stroudsburg：Association for Computational Linguistics，2008：305-316.

［3］ Liu X，Zhou Y，Zheng R.Sentence Similarity Based on Dynamic Time Warping［C］／／Semantic Computing，2007.ICSC 2007.International Conference on.Irvine：IEEE，2007：250-256.

［4］ Chan T P，Callison-Burch C，Van Durme B.Reranking Bilingually Extracted Paraphrases Using Monolingual Distributional Similarity［C］／／Proceedings of the GEMS 2011 Workshop on GEometrical Models of Natural Language Semantics.New York：Association for Computational Linguistics，2011：33-42.

［5］ Li L，Hu X，Hu B Y，et al.Measuring Sentence Similarity from Different Aspects［C］／／Machine Learning and Cybernetics，2009 International Conference on.Baoding：IEEE，2009，4：2244-2249.

［6］ Yin Y M，Zhang D Z.Sentence Similarity Computing Based on Reation Vector Model.Computer Engineering and Applications［J］，2014，50（2）：198-203.

［7］ 吳佐衍，王宇.基于 HNC理論和依存句法的句子相似度計算［J］.計算機工程與應(yīng)用，2014，50（3）：97-103.

［8］ 李彬，劉挺，秦兵，等.基于語義依存的漢語句子相似度計算［J］.計算機應(yīng)用研究，2013，20（12）：15-17.

［9］ 李茹，王智強，李雙紅，等.基于框架語義分析的漢語句子相似度計算［J］.計算機研究與發(fā)展，2013，50（8）：1728-1736.

［10］ 張奇，黃萱菁，吳立德.一種新的句子相似度度量及其在文本自動摘要中的應(yīng)用［J］.中文信息學(xué)報，2004，19（2）：93-99.

［11］ 陳海燕.基于搜索引擎的詞匯語義相似度計算方法［J］.計算機科學(xué)，2015，42（1）：261-267.

［12］ Li Y H，David M.Sentence Similarity Based on Semantic Nets and Corpus Statistics［J］.IEEE Transactions on Knowledge and Data Engineering，2006：1138-1150.

［13］ Ahsaee M G，Naghibzadeh M，Naeini S E Y.Semantic Similarity Assessment of Words Using Weighted Word Net［J］.International Journal of Machine Learning and Cybernetics，2014，5（3）：479-490.

［14］ Huang X，Zhang J，Chen H，et al.Research on Text Similarity Algorithm Based on Sentence Semantic Clustering［J］.Journal of Computational Information Systems，2014，10（8）：3163-3170.

［15］ O’Shea K.An Approach to Conversational Agent Design Using Semantic Sentence Similarity［J］.Applied Intelligence，2012，37（4）：558-568.