一種基于公共詞塊的英文短文本相似度算法

黃賢英，劉英濤，饒勤菲

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

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

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

考慮到詞序?qū)Χ涛谋鞠嗨菩缘挠绊?，本文引入公共詞塊信息，在基于詞項(xiàng)重合的關(guān)鍵詞重疊相似度算法基礎(chǔ)上，集合公共詞塊在文本中出現(xiàn)的次序，提出一種利用公共詞塊作為計(jì)算單元的短文本相似度的算法——公共詞塊相似度算法(common chunks similarity algorithm，CCS)。該算法主要是將兩個(gè)文本中所有連續(xù)出現(xiàn)的相同關(guān)鍵詞看做一個(gè)詞塊單元，利用所有公共詞塊中的關(guān)鍵詞計(jì)算重疊相似度，并考慮這些公共詞塊在兩個(gè)文本中的出現(xiàn)次序?qū)Χ涛谋鞠嗨贫鹊挠绊懀黾訖?quán)處理，以提高文本相似度計(jì)算的算法性能。

1 相關(guān)算法

1.1 基于詞項(xiàng)重合的重疊相似度算法

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

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

1.2 基于詞項(xiàng)的詞序相似度算法

基于詞項(xiàng)的詞序相似度算法對(duì)兩個(gè)短文本的每個(gè)關(guān)鍵詞給定各不相同的距離值來(lái)表示每個(gè)關(guān)鍵詞的位置信息，通過(guò)每個(gè)關(guān)鍵詞在兩個(gè)短文本里的位置關(guān)系來(lái)判斷兩個(gè)短文本的相似性［8］。當(dāng)關(guān)鍵詞在兩個(gè)短文本里的位置越相近，相對(duì)距離越小，兩個(gè)短文本相似度值就越大;反之，相對(duì)距離越大，兩個(gè)短文本相似度值越小。該算法提取出兩個(gè)短文本的所有關(guān)鍵詞的詞序信息，按“先短文本一、后短文本二”的順序?qū)啥涛谋静煌年P(guān)鍵詞合并在一起，且關(guān)鍵詞的相對(duì)位置保持不變，同時(shí)每個(gè)關(guān)鍵詞只保留第一次出現(xiàn)的位置，組成一個(gè)新的關(guān)鍵詞集合。根據(jù)每個(gè)關(guān)鍵詞在組合關(guān)鍵詞集合中的次序給每個(gè)關(guān)鍵詞設(shè)置距離值，根據(jù)這些關(guān)鍵詞在兩個(gè)短文本中的相對(duì)距離計(jì)算兩個(gè)短文本相似度值，若短文本中無(wú)該詞，則距離值設(shè)為0。相似度計(jì)算公式如下:

其中:posi(S1)表示第i個(gè)關(guān)鍵詞在S1中的距離值;posi(S2)表示第i個(gè)關(guān)鍵詞在S2中的距離值;posi(S1)－posi(S2)表示第i個(gè)關(guān)鍵詞在S1與S2中的相對(duì)距離。

2 公共詞塊改進(jìn)相似度算法

2.1 文本預(yù)處理

英文文本相比中文文本處理更為方便。英文文本的詞是以空格或標(biāo)點(diǎn)自然隔開(kāi)，所以對(duì)于英文文本的分詞處理較簡(jiǎn)單，主要是對(duì)關(guān)鍵詞進(jìn)行詞根化處理。示例如下:

分詞處理并進(jìn)行詞根化后的結(jié)果為:

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

在對(duì)S1與S2的關(guān)鍵詞距離值設(shè)定時(shí)，所確定的組合關(guān)鍵詞集合為:

為方便計(jì)算，取距離值的間隔為1，每個(gè)關(guān)鍵詞在S1與S2中的距離值分別為:

基于詞項(xiàng)的詞序相似度算法在計(jì)算相似度時(shí)，連續(xù)的相似關(guān)鍵詞可能因?yàn)槲恢玫牟煌瑢?dǎo)致相對(duì)距離的和值較大，計(jì)算得到的相似度較小。然而實(shí)際上，連續(xù)的關(guān)鍵詞數(shù)量越多，兩個(gè)短文本就越相似。對(duì)此，本文結(jié)合公共詞塊信息，對(duì)基于詞項(xiàng)的詞序相似度計(jì)算方法做了改進(jìn)。

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

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

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

每個(gè)關(guān)鍵詞在S1與S2中的距離值分別為:

2.3 文本相似度計(jì)算

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

3.2 實(shí)驗(yàn)結(jié)果

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

方法1:基于詞項(xiàng)的余弦相似度算法;

方法2:基于詞項(xiàng)的關(guān)鍵詞重疊相似度算法;

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

方法4:基于詞項(xiàng)的最長(zhǎng)公共子序列相似度算法;

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

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

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

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

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

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

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

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

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

3.3 結(jié)果分析

實(shí)驗(yàn)部分主要比較了基于詞項(xiàng)的余弦相似度算法、基于詞項(xiàng)的關(guān)鍵詞重疊相似度算法、基于語(yǔ)義工具的語(yǔ)義詞典相似度算法、基于詞項(xiàng)的最長(zhǎng)公共子序列相似度算法和本文算法。

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

［7］孫建旺，呂學(xué)強(qiáng)，張雷瀚.基于語(yǔ)義與最大匹配度的短文本分類(lèi)研究［J］.計(jì)算機(jī)工程與設(shè)計(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］朱征宇，孫俊華.改進(jìn)的基于《知網(wǎng)》的詞匯語(yǔ)義相似度計(jì)算［J］.計(jì)算機(jī)應(yīng)用，2013，33(8):2276 －2279，2288.

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

［12］程佳.熱點(diǎn)新聞間關(guān)系的研究［D］.上海:上海交通大學(xué)，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.