句子相似度計算模型的改進(jìn)

摘要：智能搜索需維護(hù)一個動態(tài)的問題與答案的數(shù)據(jù)庫。一方面涉及到關(guān)鍵詞的提取、邏輯組合等知識。另一方面，由于用戶的用詞和系統(tǒng)中存儲的關(guān)鍵詞在表達(dá)方式上可能不完全一樣，精確的關(guān)鍵詞匹配法必將導(dǎo)致很多問題找不到答案，或者找不準(zhǔn)答案。智能搜索的關(guān)鍵性技術(shù)之一是句子相似度計算，該文從詞型、詞序、詞長和不同特征加不同權(quán)值兩方面對句子相似度進(jìn)行優(yōu)化改進(jìn)，對于智能搜索性能的提高有著顯著的作用。

關(guān)鍵詞：智能搜索；詞形相似度；語句長度相似度；詞序相似度

中圖分類號：TP181文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)36-2817-02

1 基于詞型、詞序、詞長的句子相似度的改進(jìn)

句子語句相似度由詞形相似度、語句長度相似度、詞序相似度決定的，并在此基礎(chǔ)上提出基于此三個特征的新的句子相似度計算模型。其中詞形相似度起主要作用，語句長度相似度起次要作用， 詞序相似度的作用最小。下面分別加以說明與分析。

1.1 詞形相似度

語言（文中以漢字為例）中的一個語句S(Sentence)是L中的單字和特殊符號（以下簡稱單字）的一個有序集合。S的長度即是S中單字的個數(shù)，此處用Length(S)表示。SameWC(S1，S2)表示語句S1，S2Y中相同單字的個數(shù)，當(dāng)一個單字在S1，S2中出現(xiàn)的次數(shù)不同時，以出現(xiàn)次數(shù)少的計數(shù)。語句S1，S2的詞形相似度WordSimilar(X，Y)由下面公式?jīng)Q定：

WordSimilar(X，Y)=SameWC(X，Y)Max(Length(X)， Length(Y))

容易得出WordSimilar(X，Y)∈[0，1]，其意義是兩個語句相同的字?jǐn)?shù)越多， 兩個語句越相似。

例如：S1= 正態(tài)分布的含義是什么？ S2= 什么是正態(tài)分布？

則WordSimilar(S1，S2)=8/11≈0.73。

1.2 語句長度相似度

Length(S1)，Length(S2)分別表示語句S1和語句S2的長度， 即兩個語句中的單字的個數(shù)。語句長度相似度LenghtSimilar(S1，S2)由以下公式?jīng)Q定，

容易得出LenghtSimilar(S1，S2)∈[0，1]，其意義是兩個語句的長度越接近， 兩個語句越相似。

如上例中Length(S1)=11，Length(S2)=8則LenghtSimilar(S1，S2) ≈0.84。

1.3 詞序相似度

OrderOccur(S1，S2)表示在S1，S2中都出現(xiàn)且都只出現(xiàn)一次的單字的集合。PFirst(S1，S2)表示OrderOccur(S1，S2)中的單字在S1中的位置序號構(gòu)成的向量， PSecond(S1，S2)表示PFirst(S1，S2)中的分量按對應(yīng)單詞在S2中的次序排列生成的向量。

例如S1= 正態(tài)分布的含義是什么？ S2= 什么是正態(tài)分布？

則OrderOccur(S1，S2) = {“正”，“態(tài)”，“分”，“布”，“的”，“含”，“義”，“是”“什”，“么”，“?”}，S1中單字與序號的對應(yīng)關(guān)系為：

則PFirst(S1，S2)=(0，2，3，7，8，9，10)，由各分量對應(yīng)的單詞在S2中的順序為：

PSecond(S1，S2)=(8，9，7，0，1，2，3，10)， ReWord(S1，S2)表示PSecond(S1，S2)各相鄰分量的逆序數(shù)。上例中：8<9， 9<7， 7<0， 0<1， 1<2，2<3， 3<10， 得ReWord(S1，S2)=2。語句S1，S2的詞序相似度由公式以下公式?jīng)Q定，

容易得出：OrderSimilar(S1，S2)∈[0，1]。

從而可以得到OrderSimilar(S1，S2)=1-2/(8-1) ≈0.71

這樣定義詞序相似度的優(yōu)點是： 當(dāng)一個分句或短語整體發(fā)生長距離移動后， 仍與原來的語句很相似。實現(xiàn)快捷， 算法復(fù)雜度為O(m)，其中m=| OrderOccur(S1，S2)|。

由以上三部分可以得到語句相似度公式如下：

Similar(S1，S2)= α* WordSimilar(S1，S2)+β*LenghtSimilar(S1，S2)+ γ*OrderSimilar(S1，S2)

其中α，β，γ是常數(shù)，且滿足α+β+γ=1，顯然Similar(S1，S2) ∈[0，1]。

在語句相似度中我們應(yīng)該能夠理解詞形相似度起著主要作用， 語句長度相似度和詞序相似度起著次要的作用， 因此α，β，γ取值時應(yīng)該有α>>β，γ。若取α=0.8，β=0.15，γ=0.05，則上例中的Similar(S1，S2)為：0.8×0.73+0.15×0.84+0.05×0.71=0.75。由此在檢索應(yīng)用中可設(shè)置一個閥值作為相似的一個條件，當(dāng)兩個語句的相似度高于這個閥值時， 就可以認(rèn)為這兩個語句相似。利用語句相似度可以提高檢索的效率和準(zhǔn)確性。

2 不同特征加不同權(quán)值優(yōu)化模型

上一小節(jié)我們提出基于詞型、詞序、詞長等角度的句子相似度計算改進(jìn)算法。在本節(jié)中我們通過對句子的深入分析，在分別對基于詞特征，詞義特征的句子相似度計算的基礎(chǔ)上，提出一種基于句子相似度平面計算模型。該方法通過對不同的特征加不同的權(quán)值來調(diào)節(jié)各個特征對相似度計算的貢獻(xiàn)，從而使計算結(jié)果達(dá)到優(yōu)化。該方法與其他方法相比，描述句子的信息更加全面，從而使句子相似度計算更加準(zhǔn)確。完整的表達(dá)一個句子的信息，不但依賴于組成句子的詞匯的信息，而且還包含詞匯之間的關(guān)系。本節(jié)將從句子結(jié)構(gòu)信息和組成句子的詞匯信息進(jìn)行研究，力求將句子的內(nèi)部信息盡可能準(zhǔn)確的刻畫出來，以便更精確的進(jìn)行句子相似度計算。

2.1 基于關(guān)鍵詞特征的句子相似度計算

基于關(guān)鍵詞特征的句子相似度計算[1]，就是通過利用兩個句子中所有有效詞(去掉停用詞)來構(gòu)成向量空間，然后計算兩個句子的向量，利用這兩個向量夾角的余弦值作為句子相似度。任給兩個句子S1和S2，它們的所有有效詞構(gòu)成的向量空間為V=(X1，X2，…，Xn)，其中Xn為有效詞。句子S1的向量V1={ω1， ω2，…，ωn}，其中ωn為有效詞Xn在句子S1中出現(xiàn)的次數(shù)。句子S2的向量V2={ψ1， ψ2，…，ψn}，其中ψn為有效詞Xi在句子S2中出現(xiàn)的次數(shù)。則兩個句子的相似度為：

這種方法只是簡單的利用了詞表面信息，對于一些內(nèi)容相關(guān)性較小的語料效果較好。但是這種方法沒有考慮詞本身的詞義信息以及句子的句法信息，因此具有一定的局限性。

2.2 基于詞義距離的句子相似度計算

基于詞義距離的句子相似度計算[2-7] ，需要一定的詞義知識資源作為基礎(chǔ)。計算句子之間的詞義相似度，要確定句子中的詞在這個句子中所表達(dá)的詞義。具體方法如下：

設(shè)2個句子M 和N，M包含的詞為M1、M2、…Mm，N包含的詞為N1、N2、Nn，則詞Mi(1≤i≤m)和Ni(1≤j≤n)之間的相似度可用Similar(Mi，Nj)表示。這樣就得到兩個句子中任意2個詞的相似度，M 和N句子之間的語義相似度Similar(M，N)為

式中：

ai=max(Similar(Mi，N1)，Similar(Mi，N2)，…，Similar(Mi，Nn))

bi= max(Similar(Ni，M1)，Similar(Ni，M2)，…，Similar(Ni，Mn))

在相似度計算時，該種方法充分考慮了句子中每個詞的深層信息，使表面不同，深層意義相同的詞被挖掘出來，而基于關(guān)鍵詞特征的相似度計算就不可識別。但由于詞典的不全面和一些未登錄詞的詞義代碼的缺失，也給計算帶來了誤差。

2.3 改進(jìn)的句子相似度平面計算模型

一個對象可以從線性，平面等角度來描述，對應(yīng)于空間描述即為一維，二維等。當(dāng)然維數(shù)越高，對象的描述信息越全面準(zhǔn)確。如果按照詞序列表示句子，是一維線性空間；如果句子中的每個向量按照義元來表達(dá)，相當(dāng)于二維空間。兩種形式相比較，從二維的角度描述句子類似于全息照片，可以使句子包含的信息更準(zhǔn)確，更全面的表示出來。

由2.1與2.2兩部分的分析可知：基于關(guān)鍵詞特征的方法體現(xiàn)了句子表面的信息；基于詞義距離的相似度方法體現(xiàn)了組成句子的每個詞深層的語義信息。我們的目標(biāo)是，將句子的關(guān)鍵詞特征、詞義特征，揚(yáng)長避短，互為補(bǔ)充，共同描述一個句子，從而根據(jù)這些特征計算句子和句子之間的相似度，獲得較高的準(zhǔn)確率。這里就涉及到如何確定這些特征的權(quán)重問題，在自然語言處理中，許多問題根據(jù)經(jīng)驗值來確定，但我們這里將根據(jù)問題建立數(shù)學(xué)模型，引入線性回歸算法進(jìn)行簡單的求解，從而使目標(biāo)函數(shù)在一定范圍內(nèi)達(dá)到最優(yōu)。對于線性回歸算法如下：

通過以上論述，我們從兩個個側(cè)面對句子所包含的信息進(jìn)行刻畫，即：詞特征（KW），詞義特征（SE），并將這些特征融合起來進(jìn)行句子相似度的計算，從而得到一個較準(zhǔn)確的相似度計算方法。

由此我們可以得到平面計算模型的句子相似度計算公式如下：

1) 公式一是兩個相似度相乘后開平方，Similar(S1，S2)=

2) 公式二是將兩個相似度分別乘系數(shù)后相加（其中α+β=1），Similar(S1，S2)= αSimilar1*βSimilar2

其中Similar表示S1和S2兩個基于詞特征的相似度值，Similar2表示S1和S2兩個基于詞義特征的相似度值，在此我們的目標(biāo)函數(shù)是尋找一組可能的參數(shù)組合{α，β}，使得相似度的計算更加準(zhǔn)確，其中α+β=1。為了計算α和β，我們首先限定α和β參數(shù)取值范圍為(0，1)，那么我們怎么樣去求α和β的值呢？我們主要通過回歸分析（其主要用途是預(yù)測，即給出自變量的某些取值，求出相應(yīng)的點估計和區(qū)間估計）來求α和β的值，具體計算過程如下：

假定自變量Similar1和Similar2是普通變量，因變量Similar是隨機(jī)變量，并設(shè)X= Similar1、Y= Similar2、Z= Similar，對于X，Y的一組值 (X1，Y1)，(X2，Y2)，…， (Xn，Yn)，做獨(dú)立實驗，得到隨機(jī)變量 相應(yīng)的觀測值Z1，Z2，，…，Zn，這樣就得到n對數(shù)據(jù)，(X1，Y1，Z1)， (X2，Y2，Z2)， (Xn，Yn，Zn)，稱為一組容量為n的樣本，將n對數(shù)據(jù)描在xoyz空間上，稱為散點圖。散點圖直觀地給出了n個點所呈現(xiàn)的趨勢。對于自動評分和人工評分間的關(guān)系，我們將利用二元線性回歸，假定對X 的每個值，有Z=αX+βY。

其中，α和β是與X，Y無關(guān)的常數(shù)，稱為Z=αX+βY回歸方程；α和β為回歸系數(shù)。我們的目的是用樣本來估計α和β的值，得估計值α'和β'。 稱Z'=α'X+β’Y為經(jīng)驗回歸方程。利用該回歸方程就可以進(jìn)行預(yù)測。我們用最小二乘法求此回歸方程。根據(jù)一組樣本值(X1，Y1)，(X2，Y2)，…， (Xn，Yn)，然后利用最小二乘法[2] α和β的值。

第一個公式適合綜合兩個“與”關(guān)系的因素。而第二個公式更適合于綜合兩個“或”關(guān)系的因素。這里選擇后者。因為兩個相似度是互補(bǔ)的關(guān)系，相對比較獨(dú)立。即只要其中一個相似度較高我們就認(rèn)為兩個句子相似度很高。而不是一定要兩者都很高才認(rèn)為兩個句子的相似度很高。而且選擇后者可以通過改變α和β動態(tài)調(diào)節(jié)兩個相似度的比重。當(dāng)然每個相似度都有自己的優(yōu)點和缺點。只有適當(dāng)?shù)亟M合才能充分發(fā)揮它們各自優(yōu)勢，從而獲得最佳的系統(tǒng)性能。

參考文獻(xiàn)：

[1] 趙妍妍，秦兵，劉挺，等.基于多特征融合的句子相似度計算[D].哈爾濱工業(yè)大學(xué)計算機(jī)學(xué)院，2005.

[2] 徐萃薇，孫繩武.算方法引論[M].2版.北京:高等教育出版社，2004.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”