一種改進的基于知網的句子相似度計算方法

李迎凱，徐小良

(杭州電子科技大學計算機學院，浙江杭州 310018)

主觀題自動批改是在線考試系統中的關鍵技術。由于主觀題的答題特點呈現出復雜性，目前還沒有一種考試系統能較好地完成自動批改。主觀題的自動批改涉及到人工智能、模式識別以及自然語言理解等方面的理論知識，需要解決很多技術問題，因而成為在線考試系統中的一個技術難點［1］。

主觀題的自動批改主要是進行學生答案與標準答案語義匹配的計算，其過程如圖1所示。

圖1 主觀題自動批改過程

當前的主觀題自動評分算法中，多數使用的是對學生答案和標準答案中關鍵字匹配來計算語句相似度，如基于向量空間模型TF－IDF方法、詞性詞序相結合的方法等［2－3］。該方法僅從句子的表層結構信息進行匹配而忽略了語句語義分析，存在局限性，影響了自動批改的準確度。因此文中提出了一種新的基于知網的改進的句子相似度計算方法，通過增加候選語句篩選，獲取全局最優匹配的改進來計算句子相似度的值，不僅考慮了兩個句子中詞對之間的語義相似度和字符串編輯距離，還考慮了不同詞性詞匯對句子的影響程度不同而賦以不同的權重。該方法從兩個方面有效地提高了句子相似度計算的準確性。

1 句子相似度計算相關概念

1.1 基于詞項的句子相似度計算原理

句子相似度是指兩個句子之間的匹配符合程度，值為［0，1］之間的實數，值越大表明兩個句子越相似［4］。

基于詞項的句子相似度計算方法基本思想是通過中文分詞得到組成句子的詞語及其詞語的語法屬性和語義信息。首先運用詞語語義相似度計算方法，得到兩個句子中各個詞語之間兩兩配對的相似度矩陣，然后從中找出最佳的詞語配對結果，再由詞語的相似度得到句子的整體相似度。由于這種兩兩配對計算相似度，并求相似度和的最大值問題，比較類似于組合優化中的指派問題，傳統多采用動態規劃方法，只考慮局部最優。

1.2 《知網(How－net)》簡介

知網是以漢語和英語的詞語所代表的概念為描述對象，以揭示概念與概念之間，以及概念所具有的屬性間關系為基本內容的常識知識庫［5］。

文中正是使用知網的龐大知識庫來進行詞項語義相似度計算。

1.3 中文分詞

中文分詞［6］是把中文的漢字序列切分成有意義的詞。中文分詞技術的基本原理是針對輸入的字符串先預處理，分詞操作，輸出單詞。其模式如圖2所示。

圖2 中文分詞技術原理

中文分詞技術屬于自然語言處理技術范疇，目前，分詞方法大致有3種發展方向，即基于詞典的分詞方法、基于統計的分詞方法、基于人工智能領域的專家系統和神經網絡分詞。其中基于詞典的分詞方法較為成熟，且易于實現。文中在實現主觀題自動批改時，對自動分詞的要求較低，只需能保證系統的效率以及分詞得到的詞語與How－net知識庫的詞語一致即可。所以文中選擇基于詞典的分詞方法，其中分詞詞典是基于How－net建立的。

2 改進的句子相似度計算方法

傳統的基于詞項相似度計算需經過預處理、分詞和詞性標注、分組和詞對匹配、加權求和4個步驟。改進后的方法在預處理之后增加了候選語句篩選，去掉不參與運算的冗余信息，在一定程度上降低了后續處理的時間復雜度，同時改進方法中采用了全局最優的匹配算法，即帶權二分圖最大匹配算法。改進的句子相似度計算方法流程如圖3所示。

預處理是對待切文本進行兩次掃描。區分出漢字字符和非漢字字符，去除助詞、介詞等。

2.1 候選語句篩選

在兩組語句集合中尋找最為相似的語句，設定一個閾值，當相似度達到該閾值時，則可視為相似語句，即候選語句。選擇候選語句的依據是:若一個語句與已知語句之間相同的部分越多，就越有可能是最佳匹配的一對。經過此步驟，可以直接篩掉冗余的無關信息，在一定程度上減小了后續相似度計算的迭代規模，降低了計算時冗余信息造成的干擾。

2.2 帶權最大二分圖匹配算法

圖3 改進方法計算句子相似度步驟

候選語句經過分詞、詞性標注和按照詞性分組后，利用知網的知識庫計算出每個詞性組中任意一對詞之間的相似度值，各自構成相似矩陣，然后需要計算出每個詞性組中的最大匹配，進而得到每個詞性組的值，然后乘以對應詞性所占權重，最終可求出兩個句子的相似度值。在此過程中，關鍵部分是獲取到每個詞性組的最大相似匹配。

假設兩個句子分詞后得到的任意一個對應的詞性集合為 W1，W2，其中 W1={w11，w12，w13，…，w1m}，W2={w21，w22，w23，…，w2n}。

兩兩對應詞性集合間建立規模為m×n的相似度特征矩陣C。

即轉換為數學上組合優化中的指派問題，由于動態規劃法［7］只考慮了局部最優，因此文中采用能夠全局最優的帶權二分圖最大匹配算法求解相似矩陣，得到最大相似度路徑，從而獲得詞項之間相似度的值。

二分圖匹配:給定一個二分圖G，M為G邊集的一個子集，如果M滿足當中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。

極大匹配(Maximal Matching)是指在當前已完成的二分圖匹配下，不能再通過增加沒有完成的匹配的邊來增加完成的匹配的邊數。而最大匹配(Maximum Matching)是在全部極大匹配中有著最多邊數的那個匹配。從圖中選出這樣的邊數最多的子集這個過程便是圖的最大匹配問題。若是在一個匹配中，圖中的每一個頂點都能跟圖中的某條邊相關聯，那么該匹配便稱為完全匹配或完備匹配。

二分圖最大權完美匹配的KM(Kuhn－Munkras)算法是在一個二分圖里，求一個最大權匹配［12］。KM算法可以對任意帶權二分圖求最大權完美匹配。

樸素的KM算法的基本設計思路:KM算法，通過給每一個頂點標記一個號將求解圖的最大權匹配的問題轉換為求解圖的完備匹配的問題。

假設二分圖中X部的頂點Xi的頂標為A［i］，Y部的頂點Yi的頂標為B［i］，頂點Xi與Yi頂點之間的權值為W［i，j］。結論:對于任意一條邊(i，j)在 KM 算法執行的任何一個時刻，A［i］+B［i］≥W［i，j］成立。KM算法的正確性是基于下列定理。

如果由二分圖中的全部符合 A［i］+B［i］=W［i，j］式子的邊(i，j)構成的子圖中包含完備匹配，那么這個完備匹配就是二分圖所要求的的最大權匹配，因為如任意一個二分圖的匹配包含于相等子圖，那么其邊的權值和是等于圖的全部頂點的頂標和的;如果有些邊沒有包含于相等子圖，那么其邊的權值和是小于圖的全部頂點的頂標和的。

為能讓 A［i］+B［i］≥W［i，j］始終成立，在初始化的時候，記A［i］為所有的與Xi頂點相關聯的邊的權值的最大值，記B［i］=0。若是當前的子圖中不存在完備匹配，就需要修改頂標以便使相等子圖得到擴大，直至相等子圖具有完備匹配為止便可求出最大權匹配。

如當前相等子圖找不到完備匹配，那么是因為對于某個頂點X，找不到從它出發的一條交錯路，但卻得到了一棵葉子結點全部是X頂點的交錯樹，現在把交錯樹中X部頂點的頂標都減小一個值d，Y部頂點的頂標都增加一個值d，就可以使得至少有一條新邊進入相等子圖。原因是如果邊(i，j)的兩個點都在交錯樹中，那么 A［i］+B［i］的值并未變化，換一種說法就是，其原來屬于相等子圖，現在仍然是;如果邊(i，j)的兩個點都不在交錯樹中，那么A［i］+B［i］的值都未曾發生變化，(換一種說法就是，其原來屬于(或不屬于)相等子圖，現在仍然是);如果邊(i，j)的X頂點不在交錯樹中但Y頂點在交錯樹中，那么它的A［i］+B［i］的值有所增大，亦即，其原來不屬于相等子圖，現在仍然不屬于;如果邊(i，j)的X頂點在交錯樹中但Y頂點不在交錯樹中，那么它的 A［i］+B［i］的值有所降低，(換一種說法就是，其原來不屬于相等子圖，現在可能屬于相等子圖了，因此能使相等子圖有所擴大)。接下來就是求取 d值。想要 A［i］+B［i］≥W［i，j］保持成立，并且還要保證相等子圖至少有一條邊加入，應 該 有j］}X

這樣用樸素的方法實現KM算法時間復雜度是O(n4)，其中需要查找增廣路徑O(n)次，每一次增廣最多需要更改頂標O(n)次，因為每次更改頂標時需要枚舉邊來求d值，所以其復雜度是O(n2)。文中將KM算法的復雜度降到O(n3)，采用如下辦法:每次分配給Y部的頂點Yi一個變量slack，每當要尋找增廣路徑時把slack變量初始化為無窮大。如果遇到在尋找增廣路的過程中邊(i，j)不在相等子圖中的情況，需將slack［j］改成其原值和 A［i］+B［i］－W［i，j］之中較小的值。這樣的話，在改動頂標的時候，就取那些不在交錯樹中的所有Y頂點的slack值中的最小的那個作為d值，更改頂標之后，所有slack變量值都要減去d。

KM算法與動態規劃算法的比較:KM算法的時間復雜度比動態規劃算法較好，并且考慮了全局最優。

3 實驗條件和實驗結果分析

3.1 實驗條件

以《計算機網絡》課程為實驗素材，選取了148份主觀試題學生答案，將其錄入計算機，同時將標準答案也錄入計算機，然后分別對這148份學生答案與對應的標準答案進行文本相似度計算。評出最終得分，并對這148份考生答案進行人工批改得出實際得分。

3.2 實驗結果

文中相似度計算的實驗結果如表1所示。

表1 文本相似度計算的實驗結果

其中

3.3 分析

從表1可以看出，改進前的方法準確率在90%以上的例數為42，占總數的28.3%，準確率在60%以下的例數為47，占總數的31.7%。而改進后的方法準確率在90%以上的例數為82，占總數的55.4%，準確率在60%以下的例數為36，占總數的24.3%。改進后的方法明顯占優。通過分析實驗數據發現，當標準答案和學生答案的句子結構不同，對于一個是單句，另一個是復句的情況，由于計算策略不當影響了結果的準確度。基于此，在以后的工作中，將結合句子的結構分析進一步深入研究使上述問題得以解決。

4 結束語

雖然文中對自動批改系統中的句子相似度計算進行了研究，得到了更優的準確度，初步實現了系統的目標。然而，由于中文語言存在的結構和語義上的復雜性，給研究工作帶來較大的挑戰，還有待于不斷地完善。

改進的方法綜合考慮了候選語句篩選、詞性標注分組、使用帶權二分圖最大匹配獲得全局最優匹配，針對具有簡單句子結構的文本處理效果較好，但對于句子結構和邏輯關系復雜的句子，其處理效果不夠理想，尚需進一步的深入研究，這將是未來研究工作的重心之一。

［1］高思丹，袁春風.語句相似度計算在主觀題自動批改技術中的初步應用［J］.計算機工程與應用，2004(14):2－3.

［2］賈電如，李陽明.基于語句結構及語義相似度計算主觀題評分算法的研究［J］.信息化縱橫，2009(5):5－7.

［3］李明琴，李涓子，王作英，等.語義分析和結構化語言模型［J］.軟件學報，2005，16(9):1523 －1524.

［4］劉建舟，劉曉華.主觀題自動批改技術的研究［J］.湖北工業大學學報，2006，21(4):1 －3.

［5］朱嫣嵐，閔錦，周雅倩，等.基于HowNet的詞匯語義傾向計算［J］.中文信息學報，2006，20(1):14 －20.

［6］劉件，魏程.中文分詞算法研究［J］.微計算機應用，2008，29(8):11－16.

［7］張小艷.中文主觀題自動批改中相似句子檢索算法［J］.南京師范大學學報，2007，7(2):3 －4.

［8］王海英，黃強，李傳濤，等.圖論算法及其MATLAB實現［M］.北京:北京航空航天大學出版社，2010.