Simhash算法在文本去重中的應(yīng)用

張 航，盛志偉，張仕斌，楊 敏

成都信息工程大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，成都610225

1 引言

隨著計算機與信息技術(shù)的高速發(fā)展以及信息存儲技術(shù)[1]的廣泛應(yīng)用，人們已經(jīng)步入大數(shù)據(jù)時代[2]，數(shù)字化信息量呈現(xiàn)爆炸式增長。數(shù)據(jù)量大、復(fù)雜度高以及冗余度高是當前大數(shù)據(jù)信息的特點。研究表明，一些存儲系統(tǒng)中的冗余數(shù)據(jù)已經(jīng)達到了60%[3]，并且會隨著數(shù)據(jù)量的上升而增多。因此在有限的存儲空間和時間內(nèi)，如何存儲更多有效精煉的信息成為當前研究的熱點。

在去除冗余數(shù)據(jù)方面，Simhash 算法是當前公認的最好的去重算法。該算法是一種局部敏感哈希算法[4]，它能夠?qū)⒏呔S數(shù)據(jù)進行概率降維并映射為位數(shù)較少且固定的指紋，之后再對指紋進行相似度比較來反應(yīng)數(shù)據(jù)之間的相似程度。其中比較算法通常使用海明距離[5]及編輯距離[6]。Simhash算法優(yōu)勢在于處理速度快，并且結(jié)果準確度高。

如今，Simhash 算法被廣泛應(yīng)用在近似文本檢測、冗余數(shù)據(jù)去重、異常檢測[7]等領(lǐng)域。文獻[8]提出了一種基于多Simhash 指紋算法，利用多種指紋值經(jīng)過k 維多曲面進行相似度計算，有效地解決了指紋單一、信息丟失嚴重的問題。文獻[9]在Simhash 算法中加入了減值運算，對最后合并的結(jié)果序列串結(jié)果減去一個閾值T ，從而提升了Simhash算法的準確性。文獻[10]將Simhash算法和CNN 進行結(jié)合用于惡意軟件檢測，通過轉(zhuǎn)化為灰度圖像提高惡意軟件識別率和性能。

但是以上對Simhash 的應(yīng)用都存在一些問題，首先沒有突出關(guān)鍵項在Simhash 指紋中的比重，比如文獻[8]只是簡單地進行了術(shù)語長度統(tǒng)計從而確定文章的信息，文獻[9]中設(shè)置關(guān)鍵詞權(quán)重為1，這樣造成嚴重的信息失真。其次沒有考慮到信息位置分布對指紋的影響。為了提升Simhash 算法的文本去重效果、準確率，解決Simhash 算法無法體現(xiàn)分布信息的缺點，引入信息熵的概念，采用熵加權(quán)的方式給文檔中的關(guān)鍵詞進行賦權(quán)，優(yōu)化權(quán)重計算公式，并在hash 計算中加入關(guān)鍵詞分布信息，從而達到對傳統(tǒng)Simhash 算法的優(yōu)化，最后通過仿真實驗論證了該算法的可行性、合理性。

2 相關(guān)問題研究

2.1 Simhash算法的分析

定義1 Simhash 算法的原理是對于兩個給定的變量x,y，哈希函數(shù)h 總是滿足下式：

其中，Pr 表示h( x )=h( y )的可能性，sim( x,y )∈[0,1]是相似度函數(shù)，一般也用雅可比函數(shù)Jac(x,y)來表示變量x,y 的相似度，sim( x,y )表示如下：

h 屬于哈希函數(shù)簇F，需要滿足以下條件：

稱F 為(d1,d2,p1,p1)上的敏感哈希簇函數(shù)[11]。其中d( )

x,y 表示x,y 變量之間的距離，通俗而言，表示如果x,y 足夠相似時，那么它們映射為同一hash 函數(shù)的概率也就足夠大，反之哈希值相等的概率足夠小。

由于傳統(tǒng)hash函數(shù)[12]與Simhash函數(shù)最大的不同在于局部敏感性，如果針對輸入的數(shù)據(jù)做些局部修改，經(jīng)過傳統(tǒng)hash函數(shù)運算后可能會得到完全不同的結(jié)果，而Simhash 計算的結(jié)果則很相似，因此可以使用Simhash函數(shù)產(chǎn)生的指紋相似程度來表示源數(shù)據(jù)之間的相似程度。

2.2 Simhash算法流程

Simhash 算法的流程是首先定義一個f 維度的空間，然后在這個空間中定義每一個特征所對應(yīng)的向量，接著將所有的向量結(jié)合自身的權(quán)重進行加權(quán)、求和就得到了一個和向量作為結(jié)果。最后再對該結(jié)果進一步地進行壓縮轉(zhuǎn)化，其規(guī)則是：對每一個向量得出一個相對應(yīng)的f 位簽名信息，若向量維度的值大于0，則置其簽名所在的位置為1，否則置為0。通過這樣的轉(zhuǎn)化方式，得到的簽名信息表證了此向量在各個維度中的值的信息。Simhash的算法流程圖如圖1所示。

圖1 Simhash指紋生成

Simhash算法的具體步驟如下：

步驟1 初始化

針對數(shù)據(jù)集大小及存儲成本確定Simhash 位數(shù)以及f 維向量空間，同時初始化f 位二進制數(shù)S 均置為0。

步驟2 文檔預(yù)處理

主要包含兩部分，第一部分是分詞，尋找文檔的特征詞匯以及去除文檔停用詞等。第二就是賦權(quán)，一般而言這里普遍忽略了權(quán)重的計算設(shè)置為1[13]。

步驟3 生成hash值

利用傳統(tǒng)的散列算法對步驟2 中的每個特征詞計算一個f 位hash值，并進行下列運算：

for k in V ：

for i in f ：

if（i==0）：

Vi=Vi+wki

else：

Vi=Vi-wki

步驟4 壓縮變換

針對最后生成的向量V ，對每一位進行轉(zhuǎn)化處理。

if V[i]＞0：

S[i]=1

else：

S[i]=0

步驟5 指紋生成

輸出最終的簽名S 作為該文檔的指紋，之后再進行海明距離或編輯距離計算相似度。

步驟6 距離計算

在Simhash 算法中通常使用海明距離進行相似度計算。海明距離通過比較兩個文檔指紋中不相同的個數(shù)來度量兩個文檔之間的相似度[14]。海明距離越大，代表兩個字符串的相似度越低，反之則兩個字符串相似度越高。對于二進制字符串而言，可以使用異或運算來計算兩個二進制的海明距離。舉例說明如下：

例1 設(shè)a,b 為兩個二進制數(shù)，其中：

則可知a,b 兩個二進制數(shù)只有第二位不同，故Hamming(a,b)=1。

也可利用異或操作，統(tǒng)計異或結(jié)果中1 的個數(shù)。a⊕b=01000，共有1個1，故海明距離為1。

2.3 Simhash存在的一些問題

傳統(tǒng)Simhash算法在權(quán)重計算方面通常設(shè)置為1或特征詞出現(xiàn)的次數(shù)，這很容易造成信息丟失，導(dǎo)致最終的Simhash 指紋準確性降低，并且根據(jù)Simhash 算法可知它不表現(xiàn)出詞匯分布信息，關(guān)鍵特征詞調(diào)整順后，不會影響最終生成的Simhash指紋。

如圖2所示，兩個關(guān)鍵詞的位置調(diào)整下就可能導(dǎo)致最終的意義大不相同，但是傳統(tǒng)的Simhash算法生成的指紋卻是一樣的。

3 改進的Simhash算法

本文提出了一種新的基于信息熵的Simhash 算法，考慮到傳統(tǒng)Simhash算法中針對權(quán)重的計算不充分，以及不能更好地反應(yīng)文檔中詞匯的分布特征，本文中引入信息熵理論來解決上述問題，并且在hash計算中加入位置關(guān)系特征，從而提升Simhash算法的準確度。

3.1 熵加權(quán)權(quán)重計算方法

（1）詞頻-逆向文件頻率

詞頻-逆向文件頻率（TF-IDF）[15]算法是一種常用的文本特征權(quán)重計算方法，特征詞tk在文檔dj中的TF-IDF值記為tfidf(tk,dj)，有如下定義：

定義2 特征項tk在文檔dj中出現(xiàn)的頻率tf(tk,dj)為：

式中，nj,k表示特征詞tk在文檔dj中出現(xiàn)的次數(shù)，表示文檔dj中的所有特征詞的個數(shù)。

定義3 反文檔頻率idf(tk,dj)是權(quán)衡特征詞重要性的系數(shù)，其定義為：

式中，{ j:tk∈dj} 為含有特征詞tk的文檔綜述，|D|為語料庫中的文件總數(shù)。

定義4 TF-IDF函數(shù)，特征詞的詞頻權(quán)重定義為：

（2）信息熵

信息熵[16]是由香農(nóng)在1948 年提出的一個概念，用它來表示在隨機事件發(fā)生之前的結(jié)果不確定性的量度，以及在隨機事件發(fā)生之后，人們從該事件中得到的信息量。

根據(jù)信息熵的定義：

其中，X 表示信息概率空間X=(x1:P(x1),x2:P(x2),…,xn:P(xn))，H( )X 表示隨機變量X 不確定性的量度。（3）左右信息熵

左右熵[17]是指多字詞表達的左邊界的熵和右邊界的熵。左右熵的公式如下：

式中，W 表示某個單詞，El(W)表示該單詞的左熵，P( a W|W )表示該單詞左側(cè)出現(xiàn)不同詞的概率，a 變量是一個變化值，表示與W 相結(jié)合的詞匯。Er(W)右熵同理。

（4）熵加權(quán)計算法

本文采用熵加權(quán)計算方法這里對特征詞左右信息熵取平均。用Hk(w)來表示該單詞的熵信息量。把熵因子Hk加入權(quán)值計算公式中，取兩者的平方平均數(shù)作為詞權(quán)重，如下所示：上式的物理意義為：特征項tk在文檔dj中出現(xiàn)的次數(shù)越多，在訓(xùn)練集中出現(xiàn)該特征項的文檔越少，并且其信息量越大，則其權(quán)重越高。

3.2 基于熵加權(quán)的Simhash算法

基于信息熵的Simhash 算法主要是在權(quán)重方面進行優(yōu)化，首先利用基于TF-IDF 算法與信息熵進行加權(quán)得到權(quán)重，并按照其在文檔中的分布進行排序，針對每個特征詞匯生成的hash再與其所在位置進行異或。

但是經(jīng)過改進的權(quán)重計算后，由于訓(xùn)練集的不完整等因素，會導(dǎo)致部分特征次權(quán)重過大，最終引起查準率下降，為了解決這一問題，引入權(quán)重閾值Wt。下面就權(quán)重不均導(dǎo)致的問題進行證明。

設(shè)一個文檔中提取出n 個關(guān)鍵詞分別為{p1,p2,…,pn}，各關(guān)鍵詞的權(quán)重為W={w1,w2,…,wn}。對n 個關(guān)鍵詞生成hash 值，其結(jié)果為H={h1,h2,…,hn}，經(jīng)過疊加后生成二級指紋F={f1,f2,…,fm} ，m 為指紋位數(shù)，最后根據(jù)F 中fi是否大于0生成Simhash指紋為S。

若存在某一特征詞pk，其權(quán)重：

則S 主要由pk決定。證明如下：

設(shè)hi={ai1,ai2,…,aim},aij是一個二進制變量，則：

提取出wk，則有：

因wk?wj，故：

所以此時：

最終有F 主要與pk相關(guān)，證明完成。

以上證明同時也反映出權(quán)重對Simhash 指紋的影響。

引入權(quán)重閾值后，此時的權(quán)重計算如式（13）所示。

綜上所述，E-Simhash算法流程如圖3所示。

圖3 E-Simhash算法過程

E-Simhash 算法與傳統(tǒng)的Simhash 算法有三點不同，這里主要在TF-IDF 的基礎(chǔ)上引入信息熵進行特征詞權(quán)重計算，并使用兩者的平方平均數(shù)作為最后的特征詞權(quán)重，同時為了避免權(quán)重過高的情況導(dǎo)致指紋失真，引入權(quán)重閾值，計算方式如式（16）所示。最后在生成特征詞hash 時與特征詞位置進行異或，使其hash 包含文檔的位置分布信息。

4 仿真實驗與分析

本章主要模擬真實的應(yīng)用場景，驗證E-Simhash 算法的性能是否比傳統(tǒng)Simhash算法優(yōu)越。

4.1 實驗環(huán)境及數(shù)據(jù)集

實驗環(huán)境部署在一臺臺式機上，機器參數(shù)如表1所示。

數(shù)據(jù)集來自搜狗實驗室中的全網(wǎng)新聞數(shù)據(jù)2012版，它是來自多家新聞?wù)军c近20個欄目的分類新聞，剔除低于800 字符的數(shù)據(jù)，并從中隨機選取1 565 篇進行后續(xù)實驗。

首先從1 565篇新聞中，根據(jù)修改比例，隨機選取若干篇新聞進行修改、刪除、移位、替換等隨機操作，并控制修改后的文章與原始文章有一定閾值T 的相似度，生成待測樣本集，之后使用傳統(tǒng)Simhash與本文中的算法進行比較，統(tǒng)計實驗的相關(guān)指標。

表1 實驗環(huán)境參數(shù)

4.2 實驗結(jié)果分析

實驗結(jié)果中常用四種指標進行評估，分別是去重率、查準率、召回率以及F 值[18]，其中去重率是指分類正確的樣本數(shù)與總樣本的比值，就本實驗而言即預(yù)測為同源文章集數(shù)與總文章數(shù)的比值。

實驗1 去重率對比

在1 565 篇新聞中隨機選取1 162 篇進行任意修改，選取不同的海明距離，對比兩種算法中的準確率，實驗中T =15%，即每篇新聞保持不超過15%修改，指紋長度為128 位，詞權(quán)重閾值Wt=90，實驗結(jié)果如圖4所示。

圖4 不同海明距離下去重率對比

實驗結(jié)果表明在海明距離大于2 時，E-Simhash 算法均具有很高的去重率。在實際應(yīng)用中海明距離一般取10左右，所以E-Simhash算法的去重效果更好。

實驗2 修改T 閾值對比

本次實驗修改文本的相似度閾值T ，分別對5%、10%、15%、20%的修改下，海明距離選為10，即低于10 則認為相似，比較兩種算法的去重率，結(jié)果如圖5所示。

圖5 不同閾值下去重率對比

從實驗結(jié)果中可知，E-Simhash 算法去重率分別以0.833∶0.679、0.751∶0.529，0.687∶0.476、0.661∶0.451優(yōu)于傳統(tǒng)的Simhash 算法，并且隨著文章變動的增加，其去重率都呈現(xiàn)下降趨勢。實驗結(jié)果表明在不同修改閾值T 下，E-Simhash算法均優(yōu)于傳統(tǒng)的Simhash算法。

實驗3 查準率、召回率以及F 值對比

在實驗中，從新聞集中隨機選取一篇文章進行隨機修改，并保證與原文有90%的相似度，對比基于Simhash指紋與E-Simhash 算法的查準率、查全率以及F1 值。其中海明距離選取10；實驗進行100 次，并取它們的平均值，作為最終結(jié)果，結(jié)果如圖6所示。

圖6 綜合性能比較

通過實驗數(shù)據(jù)可知，E-Simhash 算法在查準率0.963∶0.818，召回率0.867∶0.621，F(xiàn)1 值0.912∶0.706 優(yōu)于傳統(tǒng)的Simhash算法。結(jié)果表明E-Simhash算法在查準率、召回率以及F 值方面均比普通的Simhash算法有很大的提升，也足以證明E-Simhash算法的優(yōu)越性。

5 總結(jié)與展望

針對傳統(tǒng)Simhash 算法在權(quán)重計算方面的欠缺，以及算法中不能考慮到文檔特征詞匯的分布信息，本文通過優(yōu)化權(quán)重計算，使用TF-IDF 和信息熵的平方平均數(shù)作為特征詞的權(quán)重值，考慮到部分權(quán)重過大導(dǎo)致信息失真，引入權(quán)重閾值，并在此基礎(chǔ)上將特征詞的位置信息引入到hash 計算中去，從而提升Simhash 算法的去重率、查準率，并通過仿真實驗論證了E-Simhash算法在各方面均優(yōu)于傳統(tǒng)的Simhash 算法，但是E-Simhash 算法依然存在一些不足，在短文本相似度檢測方面準確度不高，而且本文中的權(quán)重計算方法仍有可改進之處，計算中的關(guān)鍵詞權(quán)重未必非常準確，未來可通過優(yōu)化權(quán)重計算，如引入LDA主題模型[19]可提升Simhash算法的適應(yīng)范圍。