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

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

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

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

2.1 DSC和DSC-SS算法

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

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

2.2 I-Match算法

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

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

2.3 LSH算法

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

2.4 SpotSig算法

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

3 Low-IDF-Sig

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

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

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

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

考慮如下的句子： “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ù)表中獲得了前五個(gè)具有最低的反向文檔頻數(shù)的單詞{as, to, that, of, from}作為先行詞，并以ci=2作為詞鏈的長(zhǎng)度，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)很好地覆蓋到了整個(gè)句子的核心內(nèi)容。

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

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

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

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

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

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

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

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

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。為了測(cè)試不同特征的性能，我們從ClueWeb09-T09B*http://boston.lti.cs.cmu.edu/Data/clueweb09/中手工選擇了2 000篇文檔，總共57 135個(gè)句子，并對(duì)其兩兩間是否互為拷貝進(jìn)行了標(biāo)注，以作為GoldenSet。

5.1 特征精度比較

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

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

圖1 參照特征的F1 Score變化趨勢(shì)

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

本文提出了一種高效的句子級(jí)別的文本特征提取算法——Low-IDF-Sig算法，該算法適合于句子級(jí)別的文本特征提取。在我們未來(lái)的工作中，我們希望能把Low-IDF-Sig算法用于大規(guī)模的部分重復(fù)檢測(cè)任務(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.