基于分詞的語句相似度計算的改進

邸書靈， 劉曉飛， 李 歡

(1.石家莊鐵道大學信息科學與技術(shù)學院，河北石家莊050043;2.河北聯(lián)合大學現(xiàn)代教育技術(shù)中心，河北唐山063009)

0 引言

語句相似度計算是自然語言處理領(lǐng)域中比較重要的研究課題，應用廣泛。語句相似度是指兩個語句相似的程度，即通過一定的算法從信息庫中查找與指定句子相似的句子，得到滿足用戶需求的句子。語句相似度計算主要應用于FAQ系統(tǒng)、信息檢索和翻譯等方面。

目前有很多計算語句相似度計算的算法，如詞形詞序綜合法［1-4］、語義依存樹法［5-6］、編輯距離法［1］和基于關(guān)鍵詞的TFIDF法［7］、語義詞典法［8］等，這些方法各有優(yōu)缺點而且仍在不斷發(fā)展完善。

介紹了詞形詞序綜合法的語句相似度計算算法，它將句子分割成多個短語，消除了局部的次序變化帶來的影響，該方法還可保證當一個句子的分句或短語整體發(fā)生長距離移動后，仍與原句很相似，而眾多短語中關(guān)鍵詞的直接匹配，使得詞形相似度計算更加準確。但是該方法對分詞的依賴性很高，往往分詞的質(zhì)量決定了計算結(jié)果的準確性，由于目前的分詞算法和系統(tǒng)在歧義處理和未登錄詞識別方面進展緩慢，致使分詞具有很大約束性，算法準度不高，針對基于分詞的詞形詞序綜合法相似度計算的缺點對該算法進行了改進。

1 詞形詞序綜合法

詞形詞序綜合法有三部分組成:詞形相似度、詞序相似度和句長相似度?？紤]到在兩個句子比較時，根據(jù)詞形、詞序和句長各自對整個相似度計算的貢獻，詞形相似度起主要作用，句長相似度次要作用，而詞序相似度作用最小。

1.1 詞形相似度

詞形相似度方法是通過計算兩個問句的詞形即相同詞的個數(shù)來比較相似度的［1］。首先將兩個句子分詞，用s1Arr和s2Arr兩個數(shù)組分別存放兩句子分詞后的單詞，然后在計算出兩個句子共同包含的單詞個數(shù)sum，若共有單詞出現(xiàn)次數(shù)不相同則取最小出現(xiàn)次數(shù)。Len(s1)表示s1分詞后的詞語數(shù)。詞形相似度計算公式如下

可以看出詞形相似度數(shù)值范圍為CiSmily(s1，s2)∈［0，1］。

例如:s1:“二維的數(shù)組有哪些存儲方式”，s2:“二維的數(shù)組存儲方式”。分詞后得到:s1Arr={二維，的，數(shù)組，有，哪些，存儲方式}，s2Arr={二維，的，數(shù)組，存儲方式}。CiSmily(s1，s2)=4/6≈0.667。

1.2 計算句長相似度

兩個句子長度越接近就越相似。計算句長相似度采用句子的所有單字的總數(shù)，而非分詞后詞的總數(shù)，這樣避免了，因使用分詞后的詞總數(shù)而忽略有些詞所含單字較多的情況。

句長相似度計算公式，s1L和s2L分別是句子s1和s2所含單字個數(shù)

句長相似度的數(shù)值范圍LenSimly(s1，s2)∈［0，1］。

因此，可以計算出s1:“二維的數(shù)組有哪些存儲方式”，s2:“二維的數(shù)組存儲方式”這這兩個句子的相似度為LenSimly(s1，s2)=18/21≈0.857。由于兩句長度很接近，故長度相似度較高。

1.3 計算詞序相似度

共有單詞在兩個句子中所處位置信息能很好反應句子之間的相似程度。首先計算出s1和s2中都出現(xiàn)且只出現(xiàn)一次的詞的集合onews。然后計算出onews中各個詞語依次出現(xiàn)在s2中的位置向量，計算出逆序數(shù)count。仍然使用同一個例子，可得onews={二維，的，數(shù)組，存儲方式}。s1中與onews中詞對應關(guān)系

二維的數(shù)組有哪些存儲方式

0 1 2 3 4 5

s1的位置向量為{0，1，2，5}。同理可得s2中與onews中詞對應關(guān)系

二維的數(shù)組存儲方式

0 1 2 5

s2的位置向量為{0，1，2，5}，由于0＜1，1＜2，2＜5不存在逆序，可得逆序數(shù)count=0。詞序相似度計算公式

容易得出詞序相似度的數(shù)值也在Record(s1，s2)∈［0，1］之間。

因此，s1和s2兩個句子的詞序相似度為:Record(s1，s2)=1。即onews中的詞語在兩個句子中的順序完全相同。若Record(s1，s2)=0，說明順序完全相反。

1.4 語句相似度

語句相似度

式中，λ1，λ2，λ3均為常數(shù)，且λ1+λ2+λ3=1，則Sim(s1，s2)∈［0，1］。

根據(jù)詞形、句長和詞序在相似度計算中所起作用的大小，給三個常數(shù)賦值，可設(shè)λ1遠大于另外兩個常數(shù)，λ1=0.8，λ2=0.15，λ3=0.05。

最終得到s1:“二維的數(shù)組有哪些存儲方式”，s2:“二維的數(shù)組存儲方式”兩個句子相似度Sim(s1，s2)=0.8*0.667+0.15*0.857+0.05*1≈0.712。

2 存在的問題及改進

詞形詞序綜合法因其容易理解及易于實現(xiàn)，而且其計算結(jié)果能達到人們的一半要求，在實際應用中有一定的優(yōu)勢。

但是上述相似度計算方法仍有局限性。該相似度計算方法，對分詞的依賴性很強，例如:要比較的是“哈夫曼”和“哈夫曼樹”，假如詞庫中(你也可以使用其他非基于詞典詞庫的分詞方法)有“哈夫曼樹”但是無“哈夫曼”時，第一句就會分成{哈，夫，曼}，而第二句分詞后是{哈夫曼樹}，按照上述算法，這兩句的詞形相似度為0，總的相似度僅為0.129。這顯然不符合實際。因此，需要對以上方法進行改進。

改進的方法是，增加計算兩個句子不分詞的詞形相似度計算，來平衡分詞后對相似度計算的影響。即，在式(1)中的sum為兩個句子共同包含的單字個數(shù)，若共有單字出現(xiàn)次數(shù)不相同則取最小出現(xiàn)次數(shù)。Len(s1)表示s1中的單字個數(shù)。其計算公式不變，單字詞形相似度

式(4)中的語句相似度也要更改為

式中，λ1=0.4，λ2=0.15，λ3=0.05，λ4=0.4，λ1+λ2+λ3+λ4=1。使得基于分詞和單字的詞形相似度計算所占比重相同。經(jīng)過改進后，“哈夫曼樹”和“哈夫曼”的NoCiSmily(s1，s2)=0.75，總相似度為0.429，有了較大提升。

那么，為什么不使用單字的詞形相似度計算取代基于分詞的詞形相似度計算呢?因為單字詞形相似度計算也有局限。例如:“多維數(shù)組”和“多個二維數(shù)組”，因為詞庫中有“多維數(shù)組”，所以基于單字的相似度NoCiSmily(s1，s2)≈0.667，Sim(s1，s2)≈0.653(詞序和詞長相似度計算不變)說明這兩句話相似度很高，但是很顯然我們要查“多維數(shù)組”，“多個二維數(shù)組”就離我們想要的相去較遠，因此就要降低它們的相似程度，而使用上述改進的方法CiSmily(s1，s2)=0，Sim(s1，s2)≈0.387。有效的降低了使用單字詞形相似度計算造成的較低的查準率。而且從這也可以看出，這樣符合語義的要求。

改進后的相似度計算得到的結(jié)果更準確也更合理。設(shè)置一個閾值作為問句相似的一個條件，當兩個問句的相似度高于這個閥值時，就認為這兩個問句相似。由于改進的方法是取了兩種詞形詞序相似度的折中，因此總的相似度將會趨于降低，但這并不會影響結(jié)果的準確性，只需根據(jù)實際情況適當設(shè)置閥值即可得到準確結(jié)果。而且將此方法應用于上面兩種情況下準確性會大大提高。很適合在某一領(lǐng)域的自動問答系統(tǒng)中使用。

3 實驗結(jié)果分析

本次實驗從《數(shù)據(jù)結(jié)構(gòu)》課程常用問句集中選取16個不同類別，每類有3～4句相似的句子組成，共計50句，并作為樣本句，另外依據(jù)這些樣本句人工構(gòu)造出50個與樣本句相似的句子作為測試集。對測試集中的每句話，分別設(shè)計與之相似的語句分別使用改進前和改進后兩種方法計算所有句子與其的相似度，并將相似度最大的句子和人工判斷出的正確句子做比較，若相同則認為結(jié)果正確。實驗結(jié)果如表1。

表1 實驗結(jié)果

從實驗結(jié)果可知，改進的方法的效率明顯較高，得益于綜合了兩種詞形相似度計算方法，兼顧了基于分詞和基于單字算法的優(yōu)點，因此一般說來改進前可以得到正確結(jié)果的，改進后也可以得到正確結(jié)果。但是，考慮到用戶在輸入時對于一些由多個詞復合而成的詞語，并不一定能完整輸入整個詞，可能只是輸入這個詞語的部分或部分的組合或內(nèi)部詞語詞序顛倒，將使得改進前的算法的準確率急劇下降，如:“時間和空間復雜度”和“時空復雜度”，按照改進前的算法(詞庫中有“空間復雜度”無“時空復雜度”)相似度為Sim(s1，s2)≈0.115，這顯然不對，改進后Sim(s1，s2)≈0.365，相對于改進前已經(jīng)有明顯的提升，而這也是改進后算法的優(yōu)勢之一。另外，由于改進前基于分詞的缺陷，即:過度依賴于分詞，有時會出現(xiàn)難以接受的結(jié)果，如:用s1:“動態(tài)查找表的表示方法”來搜索與之最相似的句子s2:“動態(tài)和靜態(tài)查找表有哪些表示方法”，兩者相似度(詞庫中有“靜態(tài)查找表”和“動態(tài)查找表”)為Sim(s1，s2)≈0.399;但是s1與s3:“有哪些存儲圖的方法”的相似度為Sim(s1，s2)≈0.459，這樣的結(jié)果顯然錯誤，在這點上改進后的算法明顯優(yōu)于改進前，改進后s1與s2的相似度Sim(s1，s2)≈0.524，s1與s3的相似度Sim(s1，s2)≈0.445，顯然改進后更合理?；谝陨系姆治觯膶嶒炛械贸?，若按相似度由高到低排序輸出前N(N≥2)個句子，改進后的結(jié)果更準確。

本次實驗沒有去除停用詞，若去除停用詞將會使算法的準度和性能進一步提高。

4 結(jié)語

基于詞形詞序的相似度計算改進算法分為四個部分，將四部分數(shù)值匯總就可得到兩個句子的最終相似度。相對來說，詞形詞序綜合算法易于理解和實現(xiàn)，更重要的是計算結(jié)果也可靠。由于詞形相似度計算在整個相似度計算中所占比重較大，因此本文對基于分詞的相似度計算進行了優(yōu)化，增加了單字詞形相似度計算來降低過分依賴分詞帶來的不合理計算。另外，可以根據(jù)實際情況，靈活改變相似度計算中四個參數(shù)的值，來控制各部分在總的相似度中所占的比重。

［1］董自濤，包佃清，馬小虎.智能問答系統(tǒng)中問句相似度計算方法［J］.武漢理工大學學報:信息與管理工程版，2010，32(1):31-34.

［2］王常亮，滕至陽.語句相似度計算在FAQ中的應用［J］.計算機時代，2006(2):24-25.

［3］楊思春.一種改進的句子相似度計算模型［J］.電子科技大學學報，2006，35(6):956-959.

［4］李玉紅，柴林燕，張琪.結(jié)合分詞技術(shù)與語句相似度的主觀題自動判分算法［J］.計算機工程與設(shè)計，2010，31(11):2663-2666.

［5］車萬翔，劉挺，秦兵，等.基于改進編輯距離的中文相似句子檢索［J］.高技術(shù)通訊，2004(7):15-19.

［6］李彬，劉挺，秦兵，等.基于語義依存的漢語句子相似度計算［J］.計算機應用研，2002(12):15-17.

［7］秦兵，劉挺，王洋，等.基于常問問題集的中文問答系統(tǒng)研究［J］.哈爾濱工業(yè)大學學報，2003，35(10):1179-1182.

［8］李素建.基于語義計算的語句相關(guān)度研究［J］.計算機工程與應用，2002(7):75-76.