基于Low-IDF-SIG的句子重復(fù)檢測

俞昊旻，張 玥，張 奇，黃萱菁

(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201203)

1 引言

隨著互聯(lián)網(wǎng)時代的發(fā)展，信息呈現(xiàn)出爆炸式增長的趨勢。由于數(shù)字文檔本身易于被復(fù)制的特點(diǎn)，導(dǎo)致網(wǎng)絡(luò)中出現(xiàn)了大量的重復(fù)網(wǎng)頁和文檔[1]。這些重復(fù)信息給基于Web的應(yīng)用造成了嚴(yán)重的負(fù)擔(dān)。因此，對于重復(fù)檢測問題的研究，在近年來逐漸成為了信息檢索領(lǐng)域的一個研究熱點(diǎn)。

然而現(xiàn)有的研究工作主要著眼于如何進(jìn)行文檔級別的重復(fù)檢測，如對文檔級別文本特征選取的研究[2-7]，或是對文檔級別快速拷貝檢測系統(tǒng)的研究[8-11]。文檔級別重復(fù)檢測已經(jīng)在一般網(wǎng)頁的重復(fù)檢測中取得了不錯的成果。但目前仍存在一些未能很好處理的問題。兩個較為典型的例子分別為文檔中抄襲部分和引用部分的重復(fù)檢測。由于抄襲通常不會是文檔級別的抄襲，而是段落級別和句子級別的抄襲，即將他人文章中的部分段落或句子抄入自己的文章中，因此無法使用文檔級別的重復(fù)檢測方法有效地檢測。而對于文檔中的引用也存在相同的問題。在文章或是新聞中出現(xiàn)引用時，引用的通常會是幾句話或是一個短小的段落，因此兩個文檔之間的相似度不會高，無法簡單使用文檔級別的重復(fù)檢測方法。

除了以上的問題之外，在網(wǎng)頁的重復(fù)檢測中還存在一些不能使用文檔級別重復(fù)檢測方法解決的問題，如分頁新聞以及論壇中帖子(Thread)等的重復(fù)檢測[12]。這些問題的一個共同特點(diǎn)是，兩個文檔之中只是部分互為拷貝，這些部分拷貝需要基于更細(xì)粒度的句子級別重復(fù)檢測的方法才能有效檢測。我們在文獻(xiàn)[12]中提出了一個兩個步驟的解決方案： 首先進(jìn)行句子級別的重復(fù)檢測，即先檢測文檔中互為拷貝的句子對；然后，通過對互為拷貝的句子進(jìn)行序列匹配，從而檢測并定位出文檔間互為拷貝的部分。如文檔A中第i個句子到第j個句子的部分與文檔B中第m個句子到第n個句子的部分互為拷貝，這樣就將句子級別的重復(fù)檢測提高到了段落的級別。

本文是對文獻(xiàn)[12]的進(jìn)一步深化，本文主要貢獻(xiàn)主要有以下兩個方面：

(1) 提出了一種改進(jìn)型的句子級別的文本特征提取方法-Low-IDF-Sig算法。該算法可以高效地從句子中提取出表示整個句子核心內(nèi)容的Low-IDF-Sig特征。

(2) 在句子級別的GoldenSet實(shí)驗(yàn)集上對我們的Low-IDF-Sig方法，以及現(xiàn)在已有的文檔級別上較有代表性的方法(包括Shingling算法、SpotSig算法以及I-Match算法)進(jìn)行了綜合性的評測。評測結(jié)果表明了我們提出的方法在句子級別重復(fù)檢測中，具有較高的精度，并對時間空間的占用較少，適用于句子級別重復(fù)檢測。

2 相關(guān)工作

重復(fù)檢測在過去的數(shù)年中成為了信息檢索領(lǐng)域一個熱門問題。至今為止，關(guān)于重復(fù)檢測的研究工作大體上可以被分為兩大類別。第一類研究工作主要關(guān)注如何使用特征來表示文檔。另外，由于文檔集合中通常包含上億個文檔，因此對它們之間進(jìn)行比較的效率也成為一個研究熱點(diǎn)。本文的工作集中于對句子級別文本的特征提取的精度和效率的研究上，因此在本節(jié)中對已有的文本表示方法進(jìn)行簡單的回顧。

2.1 DSC和DSC-SS算法

Border在1997年提出一種Shingling算法，即DSC (Digital Syntactic Clustering)算法[2]。該算法將文本按照若干個詞一組組合起來，稱為一個Shingle，而整個文本則由一個Shingle的集合組成。隨后按照一種過濾策略，對集合中的Shingle進(jìn)行篩選，由選中的Shingle參加比較，并使用Jaccard算法來衡量兩個集合間的相似度。DSC中采取每25個Shingle中取一個的篩選方法，這種篩選方法雖然快速，但卻極大地降低了算法的精度。

由于在文檔集合較大時，DSC算法的比較次數(shù)過多，效率不高。因此在同年Border提出了DSC-SS算法，該算法將幾個Shingle合并為一個SuperShingle，以減少比較次數(shù)，提高算法效率。該算法雖然總體上的精確性只是略有較低，但對于較為短小的文檔卻造成了比較精度的大幅下降[3]。

2.2 I-Match算法

I-Match算法[4]基于對文檔集合的外部統(tǒng)計(jì)結(jié)果。I-Match算法將輸入文檔中的非常常見(即具有很低反向文檔頻數(shù))與非常少見的Token(即具有很高反向文檔頻數(shù))過濾掉，并將剩下的Token插入到升序排列的排序樹中，對每一個Token，相加得到一個哈希值，直到文檔結(jié)束為止。具有相同的哈希值的文檔互為拷貝[4]。

I-Match算法的一個缺點(diǎn)是穩(wěn)定性較差。如果文檔中的一個詞發(fā)生變化，則最后的哈希值就會發(fā)生顯著的變化。一個解決方法是使用隨機(jī)化的方法，如A Kocz等人在2008年提出的隨機(jī)化的I-Match算法[5]。

2.3 LSH算法

Indyk和Motwani提出的LSH算法的基本思想為： 如果兩個文本相似，可以用哈希函數(shù)將它們投影到相近的空間中[6]。具體來說，算法首先將文檔轉(zhuǎn)換為特征的集合，每一個特征有一個權(quán)重；然后利用LSH函數(shù)把特征向量轉(zhuǎn)換為指紋；最后查找指紋的海明距離。該算法在文檔級別的重復(fù)檢測中也被廣泛地使用。

2.4 SpotSig算法

2008年，M·Theobald等人提出了SpotSig算法[7]。SpotSig算法是Shingle算法的一種改良算法，該算法使用禁用詞(Stopword)作為開始抽取Shingle的標(biāo)志，并將先行詞之后的數(shù)個詞組合起來形成一個Shingle，作為一個特征。在比較時，SpotSig使用Jaccard相似度，并提出了一種基于文檔特征向量長度的剪枝方法，大大提高了SpotSig在比較階段的效率。盡管SpotSig特征在文檔級別的重復(fù)檢測中取得了很好的效果，但由于SpotSig特征選取有限的禁用詞作為先行詞進(jìn)行特征抽取，因此在文本普遍長度較短的句子級別進(jìn)行特征抽取時，無法抽取出足夠多的優(yōu)質(zhì)特征以表示整個句子的核心內(nèi)容，因此在精度上效果不好。

3 Low-IDF-Sig

句子級別上的文本重復(fù)檢測的首要問題是如何抽取出足夠的優(yōu)質(zhì)特征以很好地表示一個句子。好的特征抽取方法既可以大幅地提高句子重復(fù)檢測的精度，又可以提高在句子兩兩間計(jì)算相似度時的效率。

我們在SpotSig基礎(chǔ)上提出了一種新的改進(jìn)算法Low-IDF-Sig，該算法選取一定數(shù)量的具有最低反向文檔頻數(shù)(Inverse Document Frequency，IDF)的常見詞匯作為先行詞，以抽取改進(jìn)的Shingle特征，用以表示整個句子。

3.1 概念與標(biāo)記方法

一個Low-IDF-Sig特征si可以表示為一條緊跟在一個先行詞ai后的具有固定長度ci的詞鏈，該詞鏈的取詞間隔為一個固定值dj。事實(shí)上我們使用標(biāo)記ai(di,ci)表示一個先行詞為ai，詞鏈長度為ci，取詞間隔為di的Low-IDF-Sig特征si。舉例來說，as(1, 2)表示在句子中每次出現(xiàn)as時進(jìn)行提取，其中提取的間隔為1，詞鏈長度為2。注意如果在前一先行詞的詞鏈范圍內(nèi)出現(xiàn)了其他的先行詞的情況下，有可能出現(xiàn)兩個特征部分重疊的情況。

考慮如下的句子： “As we are taking your candidature ahead we would like to highlight that INTEL as an organization believes and practices high standards of ethical behavior from every potential candidate.”

假設(shè)我們從反向文檔頻數(shù)表中獲得了前五個具有最低的反向文檔頻數(shù)的單詞{as, to, that, of, from}作為先行詞，并以ci=2作為詞鏈的長度，di=1作為取詞間隔，則我們可以將上面的句子變?yōu)槿缦碌挠蒐ow-IDF-Sig特征組成的集合： S={as:we:are, to:highlight:that, that:intel:as, as:an:organization, of:ethical:behavior, from:every:potential}?？梢钥闯錾鲜黾弦呀?jīng)很好地覆蓋到了整個句子的核心內(nèi)容。

Low-IDF-Sig特征作為一種改進(jìn)型的SpotSig算法，與SpotSig算法主要存在以下幾個差別：

(1) Low-IDF-Sig特征在選取先行詞時，總是從作為外部資源的一個反向文檔頻數(shù)表中選取具有最低反向文檔頻數(shù)的前n個常見詞作為Low-IDF-Sig特征的先行詞；為了保證每個句子至少有一個特征，我們簡單地選取句子中的第一個詞作為一個特殊的先行詞；

(2) Low-IDF-Sig特征在構(gòu)成Shingle時，詞鏈中不僅包括在先行詞后提取的詞，同時也包括先行詞本身；

(3) SpotSig算法在選取構(gòu)成詞鏈的詞語時，簡單地跳過了所有的禁用詞，即禁用詞不會出現(xiàn)在任何一條詞鏈中。SpotSig的理由是禁用詞本身的語義信息較少，對于文檔級別的文本來說可以忽略。但我們在實(shí)驗(yàn)中發(fā)現(xiàn)，對于文本長度較短的句子而言，禁用詞仍對整個句子可以產(chǎn)生較大的影響，因此不應(yīng)該簡單地跳過所有的禁用詞。在Low-IDF-Sig算法中，我們在選取構(gòu)成詞鏈的詞語時，只跳過少部分的禁用詞，這部分的禁用詞包括部分的冠詞與介詞。原因是我們在實(shí)驗(yàn)中發(fā)現(xiàn)兩個互為拷貝的句子，可能會使用不同的冠詞或介詞，但仍然表示相同的意義。

經(jīng)過如上改進(jìn)的Low-IDF-Sig特征可以克服SpotSig先行詞不足的缺陷，保證即使在文本長度較短的句子中也能夠抽取出足夠多的特征，從而較好地覆蓋到整個句子的核心內(nèi)容，以提高句子級別重復(fù)檢測的精度。

4 相似度計(jì)算方法

給定一個句子集，重復(fù)檢測需要進(jìn)行句子間兩兩的相似度計(jì)算。我們使用常見的Jaccard相似度作為相似度計(jì)算方法。假設(shè)兩個句子經(jīng)過上一節(jié)中的轉(zhuǎn)換，變?yōu)榱藘蓚€由Low-IDF-Sig特征組成的集合：A和B。注意到同一個Low-IDF-Sig特征可能在一個句子中出現(xiàn)多次，因此A和B實(shí)際上是一個包(Bag)，它們間的相似度定義為：

其中freqA(sj)表示特征sj在包A中出現(xiàn)的頻率。freqB(sj)的含義類似。

5 實(shí)驗(yàn)

Low-IDF-Sig算法使用Java進(jìn)行實(shí)現(xiàn)。實(shí)驗(yàn)機(jī)器配置為，處理器： Intel(R) Core(TM)2 CPU 6320 @ 1.86GHz 1.87GHz， 內(nèi)存： 3.50GB。為了測試不同特征的性能，我們從ClueWeb09-T09B*http://boston.lti.cs.cmu.edu/Data/clueweb09/中手工選擇了2 000篇文檔，總共57 135個句子，并對其兩兩間是否互為拷貝進(jìn)行了標(biāo)注，以作為GoldenSet。

5.1 特征精度比較

我們使用標(biāo)準(zhǔn)的Precision、Recall和F1 Score作為精度的評測標(biāo)準(zhǔn)，對Shingle，I-Match，SpotSig特征在句子級別重復(fù)檢測中的表現(xiàn)進(jìn)行評測，以驗(yàn)證以上三種在文檔級別表現(xiàn)較好的特征是否也能在句子級別取得較好的精度。

圖1的左圖顯示了3-Shingle、4-Shingle、5-Shingle在調(diào)整相似度閾值τ時的F1 Score的變化?？梢钥闯鋈叩谋憩F(xiàn)在句子級別上較為相近，同時都在相似度閾值τ=0.6時獲得了最高的F1 Score。其中3-Shingle在τ=0.6時，F(xiàn)1 Score達(dá)到最高值0.960。這表明Shingle特征在句子級別的精度也較高，但還需考察其在空間時間上的占用以決定其是否適用于句子級別的重復(fù)檢測。

圖1 參照特征的F1 Score變化趨勢

圖1的中圖顯示了I-Match特征在變化IDF范圍時，F(xiàn)1 Score的變化。從圖中可以看出，IDF范圍取[0.3, 1.0]時，F(xiàn)1 Score達(dá)到最大值0.877。另外，可以發(fā)現(xiàn)I-Match算法在句子級別的表現(xiàn)要好于其在文檔級別的表現(xiàn)[4]。這是因?yàn)樵谖覀僄oldenSet中可以發(fā)現(xiàn)，句子級別互為拷貝的兩個句子，有80%以上是完全相同的句子，這與文檔級別的情況有很大的差別。

圖1的右圖顯示了SpotSig特征在變化相似度閾值τ時的F1 Score的變化，其中詞鏈長度取3，取詞間隔為1。M·Theobald等人發(fā)現(xiàn)在文檔級別先行詞只需選取24個禁用詞時就可以取得足夠好的F1 Score。但在我們的實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn)，24個先行詞無法從句子中抽取中足夠多的特征，因此F1 Score較低。而選取全部共365個禁用詞作為先行詞時，總體的F1 Score較高，并在相似度閾值τ=0.7時得到最高值0.764。

接下來我們將通過實(shí)驗(yàn)對本文提出的Low-IDF-SIG特征在句子級別重復(fù)檢測中的精度進(jìn)行評測，以驗(yàn)證Low-IDF-SIG特征是否適用于句子級別。

圖2的左圖顯示了Low-IDF-Sig特征在變化先行詞數(shù)量時的F1 Score的變化， 其中相似度閾值τ此時固定為0.6，詞鏈長度取3，取詞間隔為1?？梢钥闯鯨ow-IDF-Sig特征在只選取了少量的先行詞時就可以取得比較好的F1 Score值。隨著先行詞數(shù)量的增多，F(xiàn)1 Score略有上升后穩(wěn)定在0.95左右。圖2中右圖顯示了Low-IDF-Sig特征在變化相似度閾值τ時時的F1 Score的變化， 其中詞鏈長度取3，取詞間隔為1?？梢钥闯鱿刃性~取10、500以及1 000時，F(xiàn)1 Score隨相似度閾值τ變化的變化趨勢基本相同。對比Shingle算法的結(jié)果圖，可以發(fā)現(xiàn)Low-IDF-Sig與其表現(xiàn)出了相同的變化趨勢。F1 Score的最大值出現(xiàn)在先行詞取500個，τ=0.6時，為0.954。

圖2 調(diào)整先行詞數(shù)量(左)與調(diào)整τ(右)時Low-IDF-Sig的F1 Score變化

5.2 特征綜合表現(xiàn)比較

接下來我們通過比較各特征的綜合表現(xiàn)，以挑選出適合運(yùn)用于句子級別重復(fù)檢測的特征算法。

表1 各特征在GoldenSet上的綜合表現(xiàn)

表1中顯示了各個特征在GoldenSet上的綜合表現(xiàn)。從表中可以看出3-Shingle在F1 Score一項(xiàng)上取得了所有特征中最高的0.960，但對比Low-IDF-Sig(50)的F1 Score來說，優(yōu)勢并不顯著。且在空間占用上，Low-IDF-Sig(50)具有明顯的優(yōu)勢，僅為3-Shingle的三分之一。從時間占用上可以看出無論是索引階段還是相似度計(jì)算階段，Low-IDF-Sig(50)都明顯少于3-Shingle。特別是相似度計(jì)算階段的用時僅為3-Shingle的1/11。3-Shingle用時過長的原因在于存在某些特征過于常見，即索引中該特征對應(yīng)的句子過多，根據(jù)本文第4節(jié)中的介紹，假設(shè)該特征對應(yīng)的句子數(shù)為n的話，則這n個句子進(jìn)行兩兩比較，需要n2級別次計(jì)算。因此當(dāng)句子數(shù)增長時，這部分的時間可能出現(xiàn)n2級別的增長。因此3-Shingle不適合大規(guī)模的部分重復(fù)檢測任務(wù)。而I-Match盡管在時間與空間的占用上比Low-IDF-Sig(50)要少，但F1 Score卻明顯低于Low-IDF-Sig(50)，因此僅僅適合于對算法效率要求相當(dāng)高，而對精度要求不高的任務(wù)中。另外Low-IDF-Sig(50)在空間、時間占用以及F1 Score上均要優(yōu)于SpotSig。同時SpotSig在GoldenSet上抽取出的特征總數(shù)要多于Low-IDF-Sig(50)，也就是說SpotSig平均用于表示每個句子的特征要多于Low-IDF-Sig(50)，但其F1 Score卻低于Low-IDF-Sig(50)。說明SpotSig抽取出的特征未能有效地表現(xiàn)句子的核心內(nèi)容，因此Low-IDF-Sig比SpotSig更適合于句子級別的特征抽取。

綜上所述，Low-IDF-Sig算法的F1 Score僅比3-Shingle略低1%，但算法的空間占用僅為3-Shingle的29%，同時索引階段用時僅為3-Shingle的37%，而相似度計(jì)算階段的用時更是僅為3-Shingle的8.6%。而對比I-Match以及SpotSig算法，Low-IDF-Sig算法的精度高出許多。因此該算法極適合于句子級別的特征提取。

6 結(jié)論

本文提出了一種高效的句子級別的文本特征提取算法——Low-IDF-Sig算法，該算法適合于句子級別的文本特征提取。在我們未來的工作中，我們希望能把Low-IDF-Sig算法用于大規(guī)模的部分重復(fù)檢測任務(wù)中。

[1] D. Fetterly, M. Manasse, and M. Najork. On the Evolution of Clusters of Near-Duplicate Web Pages[C]//1st Latin American Web Congress, 2003: 37-37.

[2] A.Z.Broder, S.C.Glassman, M.S.Manasse, and G.Zweig. Syntactic clustering of the Web[J]. Computer Networks, 1997， 29(8-13): 1157-1166.

[3] A.Z.Broder. Identifying and filtering near-duplicate documents[C]//Proceedings of COM2000, London, UK, 2000： 1-10.

[4] A.Chowdhury, O.Frieder, D.Grossman, and M.C.McCabe. Collection statistics for fast duplicate document detection[J]. ACM Trans. Inf. Syst., 2002. 20(2): 171-191.

[6] P.Indyk and R.Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//STOC’98, New York, NY, USA, ACM. 1998: 604-613.

[7] M.Theobald, J.Siddharth, and A.Paepcke. Spotsigs: robust and efficient near duplicated etection in large web collections[C]//SIGIR’08, New York, NY, USA, ACM.2008: 563-570.

[8] N. Shivakumar and H. Garcia-Molina. Building a scalable and accurate copy detection mechanism[C]//ACM New York, NY, USA, 1996: 160-168.

[9] N. Shivakumar and H. Garcia-Molina. Finding near-replicas of documents and servers on the web[C]//Proceedings of WebDB 1998, London, UK, Springer-Verlag. 1999: 204-212.

[10] A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing[C]//VLDB ’99, pages 518-529, San Francisco, CA, USA, 1999: 204-212.

[11] K. Muthmann, W. M. Barczynski, F. Brauer, and A. Loser. Near-duplicate detection for web-forums[C]//IDEAS ’09, New York, NY, USA, ACM. 2009: 142-151.

[12] Qi Zhang, Yue Zhang, Haomin Yu, Xuanjing Huang. Efficient Partial-Duplicate Detection Based on Sequence Matching[C]//Proc. of the 33rd Annual ACM SIGIR, 2010: 675-682.