基于編輯距離的詞序敏感相似度度量方法

張雷， 崔榮一

( 延邊大學(xué) 工學(xué)院， 吉林 延吉 133002 )

0 引言

隨著信息技術(shù)的快速發(fā)展和文檔數(shù)據(jù)的日益增加，如何從海量文檔中找到期望的信息和有效地計算查詢文本與文檔的相似度逐漸成為人們關(guān)注的問題[1].目前，文本表示模型主要有詞袋模型、主題模型和嵌入模型等[2].其中詞袋模型是先將文檔表示為詞典大小維度的向量，然后通過計算兩文檔向量夾角的余弦值來度量二者的相似度，具有易于構(gòu)建的優(yōu)點[3]；但詞袋模型忽略了特征詞之間的詞序、語法及語義等要素，即將目標(biāo)對象僅僅看作是由若干個無序單詞組成的集合，因此由該模型得到的詞袋特征缺乏表達能力和區(qū)分度[4].為改善余弦相似度方法難以反映出用詞袋模型表示的文本的不同詞序所帶來的語義變化，本文提出一種基于編輯距離的詞序敏感相似度算法，并通過實驗驗證本文方法的有效性.

1 基于詞袋模型的相似度計算方法

1.1 基于 tf - idf 的詞袋模型

基于 tf -idf 的詞袋模型是信息檢索領(lǐng)域中一種常用的文本表示模型，其中 tf - idf 可以綜合衡量一個詞對所在文檔和整個文檔集的重要程度[5].在文檔d中，詞t的 tf - idf 值的計算方法為

tf-idf(t,d)=tft,d·idft,

(1)

其中:

tft,d= log10(1+nt,d)，

(2)

(3)

上式中：tft,d是詞t在文檔d中的頻率特征(term frequency,TF)，它反映的是一個詞在所在文檔中的重要程度；nt,d為詞t在文檔d中出現(xiàn)的次數(shù)，詞t出現(xiàn)的次數(shù)越多表示它的頻率特征越大.為了抑制某些高頻詞的權(quán)重，使出現(xiàn)頻率不高的詞語也能發(fā)揮作用，在式(2)中對原始詞的頻數(shù)取對數(shù)，并加了平滑項.idft為逆文檔頻率(inverse document frequency,IDF)；N為文檔集中的文檔數(shù)量；dft為文檔集頻率(document frequency,DF).idf的假設(shè)是：出現(xiàn)詞t的文檔數(shù)越少，則詞t對文檔集越重要，反之詞t越不重要.

將一篇文檔用詞袋模型表示后，無論這些詞語如何排列，每個詞的權(quán)重都與原來相同，且文檔的向量也不變.語序與語義密切相關(guān)，如“狗/咬/人”和“人/咬/狗”，這里的詞雖然相同，但順序不一樣其語義完全不同.為此，本文提出一種基于編輯距離的詞序敏感相似度度量方法，即在相似度計算中考慮語序因素.

1.2 文本相似度的計算方法

目前，常見的文本相似度計算方法有編輯距離、 Jaccard系數(shù)、N-gram相似度、 SimHash、余弦相似度、歐氏距離等[6].其中余弦相似度方法能夠體現(xiàn)出參與計算的兩個向量之間各維度的共性，且效果較好，因此該方法在文本相似度計算場景中被廣泛采用.余弦相似度的值僅與參與計算的兩個向量的方向有關(guān)，而與向量的大小無關(guān).當(dāng)文本表示為向量形式且采用tf-idf作為權(quán)重時，余弦相似度值的范圍為[0,1].將查詢和文檔分別用tf-idf向量Vq和Vd表示后，則Vq和Vd的相似性可通過式(4)進行度量.

(4)

依據(jù)公式(4)，計算查詢與文檔集中的所有文檔的相似度后，按相似度值大小進行排序，并選取相似度最大的文本作為與查詢文本最相似的文本.采用tf-idf作為詞項權(quán)重時，通常采用lnc.ltc作為權(quán)重的計算機制[7].lnc指文檔向量采用的是對數(shù)詞頻，不采用idf因子(同時基于效率和效果考慮)及余弦歸一化； ltc指查詢向量采用的是對數(shù)詞頻、idf權(quán)重因子及余弦歸一化.

用余弦相似度方法衡量用詞袋模型表示的文本的相似度雖然具有很好的實用性，但該方法無法區(qū)分因不同詞序產(chǎn)生的不同語義.例如“太陽/從/東邊/升起/，/從/西邊/落下”和“太陽/從/西邊/升起/，/從/東邊/落下”，這兩個句子的詞語順序稍有變動就會導(dǎo)致語義發(fā)生變化，但二者的余弦相似度值卻為1，即余弦相似度方法將兩個句子視為完全相同，這與事實不符.

2 基于編輯距離的詞序敏感相似度計算方法

下面以信息檢索中的相似度計算為例對本文提出的方法進行說明.假設(shè)查詢q與文檔d均已進行預(yù)處理，即已分詞、去停用詞、關(guān)鍵詞歸一，形成詞語列表(分別用Wq和Wd表示).將Wq和Wd表示為詞袋模型，并用tf-idf權(quán)重作為詞語的特征.構(gòu)建文本向量Vq與Vd， 兩個向量間的夾角余弦值可以表示為cos(Vq,Vd)， 即q與d的余弦相似度.將向量歸一化后，因余弦相似度能夠表現(xiàn)出兩個向量之間各維度的共性，因此余弦相似度能夠度量文本中的共有詞項程度.為了體現(xiàn)詞項之間的順序?qū)ο嗨贫鹊挠绊?，繼而能夠辨別不同語義，本文通過引進能夠體現(xiàn)符號串共性和差異性的度量因子來改造單一的余弦相似度的度量方法，其總體思路是：

1)用符號串之間的共性描述關(guān)注詞序的必要性，因為符號之間的順序重要性僅在相同符號的排列中存在，如果符號串之間沒有公共部分則不存在符號順序的問題.

2)用符號之間的差異性描述詞序差異的程度，該差異表現(xiàn)在相同詞項集合的不同排列之間的差異所帶來的不同語義.差異性與共性相互作用造就了詞序敏感性.

本文采用Jaccard系數(shù)(Jaccard coefficient)和編輯距離量化實現(xiàn)上述思想.

2.1 Jaccard系數(shù)

Jaccard系數(shù)是用于計算兩個集合的公共部分占比大小的指標(biāo)，因其計算簡單而被廣泛應(yīng)用于學(xué)術(shù)論文查重、電子文檔版權(quán)、文本聚類、文本分類、問卷調(diào)查整理、搜索引擎去重等涉及相似度計算的領(lǐng)域[8].Jaccard系數(shù)的計算公式為

(5)

其中#表示集合中詞語的數(shù)量， Jaccard系數(shù)的取值范圍是[0,1].式(5)表明，文檔A和文檔B的Jaccard系數(shù)等于二者交集大小與并集大小的比值.當(dāng)A與B沒有公共詞語時，J(A,B)=0； 當(dāng)A與B的詞語完全一樣時，J(A,B)=1.例如：集合A={a,b,c,d}， 集合B={c,d,e,f}， 則A∩B={c,d}，A∪B={a,b,c,d,e,f}.因交集中有2個元素，并集中有6個元素，因此A與B的Jaccard系數(shù)為J(A,B)=2/6=1/3.

2.2 編輯距離

編輯距離[9]是衡量兩個字符串差異程度的指標(biāo)，其度量方式是一個字符串變?yōu)榱硪粋€字符串的最少操作數(shù)，因此其廣泛應(yīng)用于文本糾錯、抄襲檢測等.

萊文斯坦距離(Levenshtein distance)[10]是編輯距離的一種，其定義的操作包括插入、刪除和替換3種.而本文因只需計算兩序列的公共部分的編輯距離，因此只定義插入、刪除兩種操作即可滿足需求.

本文根據(jù)動態(tài)規(guī)劃思想將所定義的編輯距離算法描述如下：

Algorithm Edit Distance

Input: 兩個中文句子A、B

Output:A與B的編輯距離

Step1 分別對A和B分詞，形成詞語列表LA、LB

Step2 計算LA和LB的長度：

N=LENGTH(LA);M=LENGTH(LB)

Step3 創(chuàng)建編輯距離矩陣E[N+1,M+1]

Step4 初始化：

E[0,0]=0

for each rowifrom 1 toNdo

E[i,0]←E[i-1,0]+del -cost(A[i])

for each columnjfrom 1 toMdo

E[0,j]←E[0,j-1]+ins -cost(B[j])

Step5 循環(huán)執(zhí)行：

for each rowifrom 1 toNdo

for each columnjfrom 1 toMdo

E[i,j]←MIN(E[i-1,j]+del -cost(A

[i]),E[i,j-1]+ins- cost(B[j]))

Step6 返回E[N,M]

例如：A=“海南/比/黑龍江/溫度/更高”，B=“黑龍江/比/海南/溫度/更高”，則二者的編輯距離為4.

當(dāng)編輯距離的操作種類為插入、刪除兩種，且每種操作代價為1時，編輯距離的取值范圍為[0,max{2(M-1),2(N-1)}]， 且取整數(shù).當(dāng)兩個句子的順序完全一致時編輯距離為0， 當(dāng)兩個句子的單詞互為逆序時編輯距離取最大值.編輯距離的時間復(fù)雜度與空間復(fù)雜度均為O(MN).

2.3 改進的相似度計算方法

假設(shè)qc和dc分別是保留文本中原詞序的公共子序列集合；E(qc,dc)表示qc和dc的編輯距離，用以衡量具有公共詞語的兩序列中詞語順序的差異性；J(Wq,Wd)表示q與d中詞語集合的Jaccard系數(shù)，用以度量編輯距離的重要性，其假設(shè)是查詢與文檔公共詞語數(shù)量越多，語序的影響就越大.因此J(Wq,Wd)·E(qc,dc)可以綜合衡量兩序列的差異性.

J·E因素按乘積方式(乘積記為x)對余弦相似度產(chǎn)生修正作用.這種修正為衰減型，即x越大對余弦相似度的衰減作用越大.當(dāng)兩個符號串沒有公共部分或者完全相同時，x=0， 即其相似度還原為余弦相似度.衰減函數(shù)有多種，本文在此僅考慮3個具有代表性的函數(shù)，如式(6)—(8)所示.圖1為這3個函數(shù)的衰減趨勢.由圖1可以看出：函數(shù)(6)和(7)雖然簡單，但它們的衰減趨勢過于強烈，難以保持余弦相似度的固有優(yōu)點；而對數(shù)函數(shù)可以有效緩解衰減趨勢，如式(8)所示.因此本文按對數(shù)方式修整J·E因子，以保持余弦相似度度量方法的固有合理性.

y1=e-x,

(6)

(7)

(8)

因此，查詢q與文檔d的詞序敏感相似度可以表示為

sim(q,d)=Kq,d·cos(Vq,Vd).

(9)

其中Kq,d為余弦相似度的抑制因子，其表達式為

(10)

在式(9)、(10)中， cos(Vq,Vd)∈[0,1]，J(Wq,Wd)∈[0,1]，E(qc,dc)∈[0,max{2(len(Wq)-1),2(len(Wd)-1)}]，Kq,d∈(0,1]， 因此詞序敏感相似度的取值范圍為sim(q,d)∈[0,1].由式(9)、(10)可知，本文方法在計算兩序列的相似度時考慮了序列中詞語的順序因素.詞序敏感算法的核心機制是抑制因子Kq,d，Kq,d值越小對原余弦相似度值的抑制能力越大.式(9)存在以下幾種情況：

1)當(dāng)兩個序列的公共子序列的順序存在不一致時，則根據(jù)不一致程度對相似度值進行一定的削弱.

2)當(dāng)兩個序列的語序越趨向于一致時，二者的相似度值越接近于余弦相似度值.

3)當(dāng)兩個序列的所有公共子序列的順序完全一致時，此時式(10)的值為1， 式(9)退化為余弦相似度.

4)當(dāng)兩個序列完全不同時， cos(Vq,Vd)=0， 此時sim(q,d)=0.

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)的構(gòu)建

本文實驗使用的語料是人工撰寫的307組C語言相關(guān)問題，每組為相似問題的6個不同的表述方式，并將其中的1個表述設(shè)為主問題，其他5種表述設(shè)為副問題.副問題與主問題的語義有些是相同的，有些是不同的.實驗語料如表1所示.

表1 相似度實驗語料

表1中“同義標(biāo)簽”中的數(shù)組元素，分別表示每個副問題與主問題的語義是否相同.其中元素值為1表示語義相同， 0表示語義不同.如[1,0,0,1,1]表示第1、4、5個副問題與主問題是同義句，第2、3個副問題與主問題存在語義區(qū)別.

3.2 實驗結(jié)果與分析

分別使用原始余弦相似度方法和基于編輯距離的詞序敏感相似度計算方法對上述C語言問題集進行文本檢索實驗，結(jié)果如表2所示.圖2為表2的可視化圖.在表2和圖2中，P、R、F1分別代表準(zhǔn)確率、召回率、F1值，@K表示在TopK上的指標(biāo).

以表1中的第1組為例進行說明.q=“數(shù)組名/是/指針/嗎？”，d1=“指針/是/數(shù)組名/嗎？”，d2=“數(shù)組名/和/指針/一樣/嗎?”.由式(10)可以算出，Kq,d1=0.588 6，Kq,d2=0.768 6.由此可見，詞序敏感算法的確能夠抑制因語序的不同而產(chǎn)生的語義差異.

從表2和圖2可以看出，在Top 1、Top 3上，詞序敏感算法的F1值比余弦相似度算法的F1值分別提高了0.082 5、0.112 6.由此表明，詞序敏感算法的準(zhǔn)確率和召回率的綜合值顯著優(yōu)于余弦相似度算法的準(zhǔn)確率和召回率的綜合值.

表2 不同相似度計算方法的實驗結(jié)果

4 結(jié)論

研究表明， 本文所提出的基于編輯距離的詞序敏感相似度算法能夠反映出句子之間的語序差異；因此，利用本文提出的方法在計算詞袋模型表示的文本相似度時，其性能優(yōu)于余弦相似度方法.本文在研究中沒有分析何種語序會影響語義，為此我們今后將建立詞序敏感詞庫，并標(biāo)注查詢和文檔的詞性，研究不同詞序變化而導(dǎo)致的語義變化，以進一步提升本文方法的性能.