黃賢英，劉英濤，饒勤菲

(重慶理工大學計算機科學與工程學院，重慶 400054)

文本相似度是指文本在語義表達上的相似程度，兩個文本的相似度值越大，文本所表達的含義也就越接近。文本相似度的計算在信息檢索、圖像檢索、文本摘要自動生成、文本復制檢測等方面都有著廣泛的應用［1］。隨著網(wǎng)絡的普及和人們生活節(jié)奏的加快，短文本越來越多地出現(xiàn)在人們的視野中。短文本具有內容較短、特征稀疏、口語化等特點，因此傳統(tǒng)的文本相似度量方法在短文本的處理方面效果較差。改進相似度度量方法，提高短文本相似度度量效果成為自然語言處理方面的一個研究熱點。

對于短文本相似度的研究，大多都是通過擴展短文本文本信息來提高短文本相似度計算。文獻［2］利用概念網(wǎng)絡擴展文本信息進行短文本分類。文獻［3］利用動態(tài)變量來發(fā)現(xiàn)短文本間的內在關聯(lián)以計算短文本相似度。文獻［4］通過構建概念樹來計算短文本相似度值。文獻［5－6］針對微博短文本，分別利用隱主題分析技術和相關度模型來度量短文本相似度。以上方法都是在犧牲效率的前提下來提高短文本相似度計算的準確率。文獻［7］提出了基于語義和最大匹配度的短文本相似度算法。文獻［8］提出了一種基于語義信息和詞序的短文本相似度算法。文獻［9］提出了一種基于語義信息和句法信息的短文本相似度算法。文獻［10－11］通過改進基于《知網(wǎng)》的語義相似度計算方法來提高短文本相似度的計算準確率。這些方法都是結合語義信息計算短文本相似度，對語義詞典有很強的依賴性。

考慮到詞序對短文本相似性的影響，本文引入公共詞塊信息，在基于詞項重合的關鍵詞重疊相似度算法基礎上，集合公共詞塊在文本中出現(xiàn)的次序，提出一種利用公共詞塊作為計算單元的短文本相似度的算法——公共詞塊相似度算法(common chunks similarity algorithm，CCS)。該算法主要是將兩個文本中所有連續(xù)出現(xiàn)的相同關鍵詞看做一個詞塊單元，利用所有公共詞塊中的關鍵詞計算重疊相似度，并考慮這些公共詞塊在兩個文本中的出現(xiàn)次序對短文本相似度的影響，做加權處理，以提高文本相似度計算的算法性能。

1 相關算法

1.1 基于詞項重合的重疊相似度算法

基于詞項重合的重疊相似度算法將短文本內容看成是獨立關鍵詞的集合，通過兩個短文本的共現(xiàn)詞的個數(shù)來判斷兩個短文本的相似性［12］。若兩個短文本中共現(xiàn)詞的個數(shù)越多，則兩個短文本就越相似;反之，兩個短文本的相似度就越低。同時，為保證兩個短文本的相對相似度一致，采用相似度計算公式如下:

其中:samewords(S1，S2)表示S1與S2中都出現(xiàn)的關鍵詞個數(shù);Len(S1)表示S1中的關鍵詞個數(shù)，Len(S2)表示S2中的關鍵詞個數(shù)。

1.2 基于詞項的詞序相似度算法

基于詞項的詞序相似度算法對兩個短文本的每個關鍵詞給定各不相同的距離值來表示每個關鍵詞的位置信息，通過每個關鍵詞在兩個短文本里的位置關系來判斷兩個短文本的相似性［8］。當關鍵詞在兩個短文本里的位置越相近，相對距離越小，兩個短文本相似度值就越大;反之，相對距離越大，兩個短文本相似度值越小。該算法提取出兩個短文本的所有關鍵詞的詞序信息，按“先短文本一、后短文本二”的順序將兩短文本不同的關鍵詞合并在一起，且關鍵詞的相對位置保持不變，同時每個關鍵詞只保留第一次出現(xiàn)的位置，組成一個新的關鍵詞集合。根據(jù)每個關鍵詞在組合關鍵詞集合中的次序給每個關鍵詞設置距離值，根據(jù)這些關鍵詞在兩個短文本中的相對距離計算兩個短文本相似度值，若短文本中無該詞，則距離值設為0。相似度計算公式如下:

其中:posi(S1)表示第i個關鍵詞在S1中的距離值;posi(S2)表示第i個關鍵詞在S2中的距離值;posi(S1)－posi(S2)表示第i個關鍵詞在S1與S2中的相對距離。

2 公共詞塊改進相似度算法

2.1 文本預處理

英文文本相比中文文本處理更為方便。英文文本的詞是以空格或標點自然隔開，所以對于英文文本的分詞處理較簡單，主要是對關鍵詞進行詞根化處理。示例如下:

分詞處理并進行詞根化后的結果為:

基于詞項重合的重疊相似度算法在計算S1與 S2相似度時，samewords(S1，S2)=7，Len(S1)=Len(S2)=7，S1與S2的相似度值為1。從上面的例子中可以看出:S1與S2講述的主題是相同的，且關鍵詞相同，但由于關鍵詞的詞序差別，它們的語義不同，相似程度也不是完全相同。然而基于詞項重合的重疊相似度算法存在著獨立性假設的條件，將短文本中的各個關鍵詞看成是獨立存在的個體，忽略了關鍵詞間的序列信息，導致相似度計算出現(xiàn)誤差。如果考慮詞序的影響，可以更好地提高短文本相似度計算的準確率。

在對S1與S2的關鍵詞距離值設定時，所確定的組合關鍵詞集合為:

為方便計算，取距離值的間隔為1，每個關鍵詞在S1與S2中的距離值分別為:

基于詞項的詞序相似度算法在計算相似度時，連續(xù)的相似關鍵詞可能因為位置的不同導致相對距離的和值較大，計算得到的相似度較小。然而實際上，連續(xù)的關鍵詞數(shù)量越多，兩個短文本就越相似。對此，本文結合公共詞塊信息，對基于詞項的詞序相似度計算方法做了改進。

2.2 基于公共詞塊的文本向量表示

本文算法在基于詞項重合的重疊相似度算法的基礎上做出改進，詞序方面的相似度算法僅考慮兩個短文本中的共現(xiàn)詞。因此，要先從處理后的兩個短文本關鍵詞集中提取出共現(xiàn)詞，然后在共現(xiàn)詞集合中查找在兩個短文本中都連續(xù)出現(xiàn)的共現(xiàn)詞組，將其標注為一個詞塊(每個詞塊中關鍵詞的個數(shù)大于等于1)，并標注這些詞塊在兩個短文本中的距離值。

對于S1與S2，提取的公共詞塊集合為:{{quick，brown}，{dog}，{jump，over，lazy}，{fox}}

每個關鍵詞在S1與S2中的距離值分別為:

2.3 文本相似度計算

利用結合公共詞塊信息得到的短文本詞序表示向量來計算兩個短文本間的詞序相似度，綜合考慮重疊相似度計算方法與基于公共詞塊的相似度計算方法得到新的相似度值，對式(1)和式(2)做加權處理，得到本文的公共詞塊相似度值?；诠苍~塊的相似度計算方法僅考慮共現(xiàn)詞的情況，當兩個短文本的共現(xiàn)詞數(shù)量較多時，共現(xiàn)詞間的詞序因素對兩個短文本相似度值的影響較大;反之，基于詞項重合的重疊相似度算法就起到?jīng)Q定作用。對此，本文采用了一種基于共現(xiàn)詞的自適應系數(shù)分配方案來確定兩種相似度算法的權重。相似度計算公式如式(3)所示。

對 于 S1與 S2，Simoverlap(S1，S2)=1.0，Simorder(S1，S2)=0.732 7，則兩短文本的相似度值為 SimCCS(S1，S2)=0.732 7。

3 實驗結果與分析

3.1 實驗數(shù)據(jù)

選取微軟研究院釋義語料庫(MSRP)［13－14］數(shù)據(jù)集作為測試文本，數(shù)據(jù)集中包含從數(shù)千個網(wǎng)頁源中收集的5 801條句子對，同時挑選一定量的測試者對句子對之間的相似性進行人工判斷，從而決定該句子對是否相似。相似的記為1，不相似的記為0。

3.2 實驗結果

本文采用基于詞項的余弦相似度算法、基于詞項的關鍵詞重疊相似度算法、基于詞典的語義相似度算法、最長公共子序列相似度算法［15］和本文算法，分別對數(shù)據(jù)集進行相似度值的計算，并做對比研究。

方法1:基于詞項的余弦相似度算法;

方法2:基于詞項的關鍵詞重疊相似度算法;

方法3:基于詞典的語義相似度算法;

方法4:基于詞項的最長公共子序列相似度算法;

方法5:本文的相似度算法。

表1是在數(shù)據(jù)集中提取了前N條句子對時，5種算法計算的人工標注狀態(tài)為1的句子對的相似度平均值。由于該數(shù)據(jù)集句子對間的相似性經(jīng)過較嚴格的人工標注，若句子對的相似性狀態(tài)為1，則該句子對的相似值也應較高。很明顯，本文算法的相似度平均值要高于其他5種方法，并保持在0.84附近，且最大值與最小值之差不超過0.01，表明本文算法在相似度的計算和算法穩(wěn)定性方面都有著比較好的效果。表1中，方法1、方法2和方法4的相似度平均值也較高，而方法3的相似度平均值卻保持在較低的水平。方法1、方法2和方法4的相似度平均值的起伏超過0.01。

表1 各算法在不同數(shù)據(jù)集數(shù)目時狀態(tài)為1的句子對的相似度平均值

圖1是不同相似度閾值下5種方法對數(shù)據(jù)集相似性計算得到的準確率的比較。由圖1可見:方法3在相似度閾值低于0.55時，準確率要高于其他算法;在相似度閾值超過0.55之后，方法3的準確率逐漸低于方法4、方法2、方法1;在相似度閾值超過0.95后，方法3的準確率達到100%，高于其他算法;當相似度閾值低于0.3時，方法1、方法2、方法4和方法5的準確率基本相同;當相似度閾值超過0.3后，方法5(即本文方法)計算所得的準確率明顯低于其他4種方法。

圖1 不同相似度閾值下5種方法的準確率比較

圖2是不同相似度閾值下5種方法對數(shù)據(jù)集相似性計算得到的召回率的比較。由圖2可見:方法3的召回率要低于其他方法;當相似度閾值低于0.3時，方法1、方法2、方法4和方法5的召回率基本都是100%;當相似度閾值大于0.3時，方法5的召回率最大，方法1和方法2的召回率基本相同，只小于方法5，大于其他方法，其中方法1略大于方法2。從圖2還可以看出，方法5即本文方法的召回率要遠大于其他方法。

圖2 不同相似度閾值下5種方法的召回率比較

圖3是不同相似度閾值下5種方法對數(shù)據(jù)集相似性計算得到的F值的比較。各方法計算所得的F值情況基本與計算得到的召回率情況相同，這是由于F值綜合考慮了算法的準確率和召回率的情況。各算法的準確率的增大速率要低于它們召回率的減少速率，因而召回率的值對F值影響較大，F(xiàn)值的變化曲線接近于召回率的變化曲線。

圖3 不同相似度閾值下五種方法的F值比較

3.3 結果分析

實驗部分主要比較了基于詞項的余弦相似度算法、基于詞項的關鍵詞重疊相似度算法、基于語義工具的語義詞典相似度算法、基于詞項的最長公共子序列相似度算法和本文算法。

MSRP數(shù)據(jù)集中，句子對之間的詞項重復較多，相似度值主要取決于詞項間的關聯(lián)關系，基于語義工具的語義詞典相似度算法集中于關鍵詞間的相似關系，缺乏對句子中詞項間深層次含義的挖掘，計算所得的相似度均值較低，F(xiàn)值也較低?；谠~項的余弦相似度算法和基于詞項的關鍵詞重疊相似度算法只集中于獨立詞項的相同數(shù)量關系，未考慮詞項間的詞序關系，雖然相似度均值較大，但F值較低?；谠~項的最長公共子序列相似度算法集中于句子對間的最長公共子序列，考慮了詞序信息，但僅提取了部分共現(xiàn)詞，相似度均值不高。本文算法加入了公共詞塊信息，考慮詞序關系影響，通過句子對中共現(xiàn)詞的數(shù)量自動調整加權系數(shù)，既考慮了共現(xiàn)詞的詞項信息，又兼顧了詞項間的詞序信息，得到了較高的相似度均值和較好的F值曲線，且算法具有較好的穩(wěn)定性。

4 結束語

本文在關鍵詞重疊相似度算法的基礎上，結合公共詞塊信息，設計了一種新的短文本相似度算法。該算法增加了基于公共詞塊的關鍵詞位置信息約束條件，兼顧了文本的詞項信息和詞序因素。實驗結果顯示:該算法在英文短文本相似度計算方面具有較好的性能。此方法的不足之處是忽略了詞意相近、詞形不同的詞對對相似度計算的影響，僅適用于共現(xiàn)詞較多的數(shù)據(jù)的相似度計算。若進一步添加語義信息進行相似度計算可能會提高算法的算法性能，但語義相似度計算應盡量減少對于詞典的依賴，同時避免無用或錯誤詞項的添加，防止詞典約束和噪聲加入對相似度計算的影響。

［1］華秀麗，朱巧明，李培峰.語義分析與詞頻統(tǒng)計相結合的中文文本相似度量方法研究［J］.計算機應用研究，2012，29(3):833 －836.

［2］林小俊，張猛，暴筱，等.基于概念網(wǎng)絡的短文本分類方法［J］.計算機工程，2010，36(21):4 －6.

［3］金春霞，周海巖.動態(tài)向量的中文短文本聚類［J］.計算機工程與應用，2011，47(33):156 －158.

［4］趙小謙，鄭彥，儲海慶.概念樹在短文本語義相似度上的應用［J］.計算機技術與發(fā)展，2012，22(6):159－162.

［5］路榮，項亮，劉明榮，等.基于隱主題分析和文本聚類的微博客中新聞話題的發(fā)現(xiàn)［J］.模式識別與人工智能，2012，25(3):382 －387.

［6］鄭斐然，苗奪謙，張志飛，等.一種中文微博新聞話題檢測的方法［J］.計算機科學，2012，39(1):138 －141.

［7］孫建旺，呂學強，張雷瀚.基于語義與最大匹配度的短文本分類研究［J］.計算機工程與設計，2013，34(10):3613－3618.

［8］Yuhua Li，David McLean，Zuhair A.Bandar，et al.Sentence Similarity Based on Semantic Nets and Corpus Statistics［J］.Knowledge and Data Engineering，2006，18(8):1138－1150.

［9］IslamA，Inkpen D.Semantic Text Similarity Using Corput-based Word Similarity and String Similarity［J］.ACM Transactions on Knowledge Discovery from Data，2008(2):10.

［10］朱征宇，孫俊華.改進的基于《知網(wǎng)》的詞匯語義相似度計算［J］.計算機應用，2013，33(8):2276 －2279，2288.

［11］張瑞霞，楊國增，吳慧欣.基于《知網(wǎng)》的漢語未登陸詞語義相似度計算［J］.中文信息學報，2012，26(1):16－21.

［12］程佳.熱點新聞間關系的研究［D］.上海:上海交通大學，2011.

［13］Quirk C，Brockett C，Dolan W B.Monolingual Machine Translation for Paraphrase Generation［C］//EMNLP.USA:［s.n.］，2004:142 －149.

［14］Dolan B，Quirk C，Brockett C.Unsupervised construction of large paraphrase corpora:Exploiting massively parallel news sources［C］//Proceedings of the 20th international conference on Computational Linguistics.Association for Computational Linguistics，2004:350.

［15］Irvine V C，Samir Khuller.Design and Analysis of Algorithms Lecture Notes［R］.Maryland，USA:Dept of Computer Science University of Maryland，2003.