楊 榮 李 兵 王電化 吳 謀 鄧樹(shù)文

1(湖北科技學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 咸寧 437100) 2(武漢大學(xué)國(guó)際軟件學(xué)院 湖北 武漢 430079)

0 引 言

如今，隨著智能時(shí)代的到來(lái)，軟件服務(wù)生態(tài)發(fā)生了很大的變化，Web信息呈爆炸式增長(zhǎng)，同時(shí)也造成網(wǎng)絡(luò)中存在海量的相似頁(yè)面。這些海量的相似性?xún)?nèi)容，不僅浪費(fèi)檢索資源，而且也不便于人們的使用。因此，以此為背景，本文研究一種高效的網(wǎng)頁(yè)重復(fù)檢測(cè)方法。

對(duì)于兩個(gè)頁(yè)面，通過(guò)shingling每一個(gè)文檔，能夠得到相關(guān)詞匯大小構(gòu)成的集合，即w-shingling集合(w為給定的詞匯組合個(gè)數(shù))，對(duì)于這種大規(guī)模文檔，已經(jīng)涌現(xiàn)了很多相似性度量技術(shù)。例如，文獻(xiàn)[1-3]提出的minwise哈希算法，是一種較成熟、性能穩(wěn)定的文檔相似性檢測(cè)技術(shù)。最小哈希算法把求解集合的交集問(wèn)題，轉(zhuǎn)換為一個(gè)事件發(fā)生的概率問(wèn)題。利用大量的實(shí)驗(yàn)，來(lái)對(duì)文檔的相似性進(jìn)行估計(jì)。該方法，后來(lái)被推廣到很多的應(yīng)用領(lǐng)域，包括：Web重復(fù)檢測(cè)[4]、協(xié)同過(guò)濾[5]、關(guān)聯(lián)規(guī)則學(xué)習(xí)[6]等。

常規(guī)的最小哈希算法，利用32位或64位去存儲(chǔ)每一個(gè)哈希值。然而，當(dāng)數(shù)據(jù)規(guī)模很大時(shí)，這將承受巨大的存儲(chǔ)壓力。為了解決此困境，文獻(xiàn)[7-10]提出了一種空間高效的b位最小哈希算法(b-bit minwise hashing)，該方法只存儲(chǔ)最小哈希值的最低b位(b=1, 2, 3,…)。雖然上述方法大大降低了存儲(chǔ)空間，但是也犧牲了一定的精度。為此，本文提出一種ES_SSE方法，該方法在原始最小哈希函數(shù)的基礎(chǔ)上，采用壓縮的n位二進(jìn)制編碼，不僅在空間需求上大大降低，而且性能也大大改善。

1 方法概述

文獻(xiàn)[7-10]等的大量研究，都是基于這樣一個(gè)直觀認(rèn)識(shí)：來(lái)自于不同的兩個(gè)集合中的元素，如果他們的哈希值相等，則兩個(gè)哈希值的最低b位肯定相等；如果他們的哈希值不同，則兩個(gè)哈希值的最低b位以1-1/2b概率不相等。因此，在精度要求不是特別嚴(yán)格的情況下，可以采用空間高效的b位哈希算法。然而，當(dāng)精度要求高時(shí)，必須探尋更加高效的方法。

圖1所示為本文研究所經(jīng)過(guò)的幾個(gè)階段，即首先對(duì)數(shù)據(jù)源進(jìn)行預(yù)處理，比如shingling文檔，去除shingling文檔后得到集合中的重復(fù)值等。接著，對(duì)集合中的每個(gè)元素計(jì)算最小哈希值(這一步與其他的普通最小哈希方法沒(méi)有本質(zhì)的不同)。第三個(gè)階段，為本文研究的核心，即對(duì)計(jì)算出的每一個(gè)哈希值，進(jìn)行如圖2所示的處理。最后一步即對(duì)相似性進(jìn)行估計(jì)。

圖1 ES_SSE處理流程圖

圖2 ES_SSE構(gòu)造示意圖

圖3描述了b位最小哈希算法的實(shí)現(xiàn)過(guò)程，如圖3所示，對(duì)于給定的兩個(gè)原始集合S1和S2，圖中的陰影交集部分，其哈希值的最低b位相同。

圖3 b-bit構(gòu)造示意圖

2 模型描述

(1)

li為所有哈希到第i個(gè)位置的元素個(gè)數(shù)的奇偶性。采用此方法，特別是處理海量數(shù)據(jù)集時(shí)，能夠大大降低存儲(chǔ)空間，因?yàn)橹慌袛喙５侥硞€(gè)位置元素個(gè)數(shù)的奇偶性，大大壓縮了空間；然后利用二進(jìn)制位的異或運(yùn)算，消除相同的公共部分，只保留記憶了原始集合差異性的部分，進(jìn)一步降低了存儲(chǔ)空間。圖1中，進(jìn)行了兩次哈希處理，本文通過(guò)對(duì)第二次哈希后的集合進(jìn)行杰卡德相似性估計(jì)，反過(guò)來(lái)會(huì)推出原始集合的相似性。

2.1 從ES_SSE估計(jì)集合的基數(shù)

本小節(jié)介紹如何從ES_SSE估計(jì)集合的基數(shù)。假定用n位二進(jìn)制位來(lái)存儲(chǔ)ES_SSE，m表示集合的基數(shù)。由圖2可以看出，求解ES_SSE的過(guò)程，其實(shí)可以當(dāng)作一個(gè)投票問(wèn)題。ES_SSE的構(gòu)造過(guò)程，相當(dāng)于m個(gè)選民對(duì)n個(gè)候選人進(jìn)行投票，每次投票后對(duì)候選人的票數(shù)進(jìn)行統(tǒng)計(jì)，并算出每個(gè)候選人所得票數(shù)的奇偶性，即求出li。反過(guò)來(lái)，當(dāng)?shù)弥薊S_SSE向量值，可以對(duì)集合的基數(shù)進(jìn)行估計(jì)。本文把ES_SSE向量每位的奇偶性當(dāng)作一個(gè)簡(jiǎn)單雙態(tài)馬爾可夫鏈模型，即兩狀態(tài)分別對(duì)應(yīng)奇數(shù)和偶數(shù)，狀態(tài)變化概率為1/n。當(dāng)i個(gè)選民行使了自己的選舉權(quán)以后，假定任何一個(gè)候選人所擁有的票數(shù)為偶素的概率為pi，基于馬爾可夫鏈的簡(jiǎn)單推導(dǎo)，可以得到以下等式：

(2)

實(shí)際上，如果用一個(gè)0-1變量Xi表示m個(gè)選民投票后，第i個(gè)候選人所得票數(shù)的奇偶性(Xi為1，表示所得票數(shù)為偶數(shù)，否則為奇數(shù))，假設(shè)X=∑iXi，通過(guò)推導(dǎo)則有：

(3)

(4)

因此得出:

(5)

2.2 從ES_SSE估計(jì)Jaccard similarity系數(shù)

(6)

(7)

(8)

在文獻(xiàn)[11]中，也探討了跟本文類(lèi)似的估計(jì)問(wèn)題，其解決的是一個(gè)將m個(gè)球扔進(jìn)n個(gè)箱子的問(wèn)題，并利用標(biāo)準(zhǔn)近似泊松分布進(jìn)行建模，分析了數(shù)據(jù)的集中性(即數(shù)據(jù)分布在其均值的周?chē)?和方差區(qū)間。本文對(duì)此相關(guān)問(wèn)題不作進(jìn)一步討論。

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

本節(jié)將通過(guò)實(shí)驗(yàn)，驗(yàn)證本文所提出的模型性能。本文實(shí)驗(yàn)以處理器Intel(R)Core(TM)i5 CPU(3.30 GHz)，4 GB內(nèi)存，64位Win7操作系統(tǒng)為實(shí)驗(yàn)環(huán)境。所有實(shí)驗(yàn)在Matlab中進(jìn)行，為了減小誤差，所有實(shí)驗(yàn)都是重復(fù)10次并取均值。

3.1 參數(shù)設(shè)置

本文對(duì)ES_SSE和b-bit進(jìn)行對(duì)比。正如在文獻(xiàn)[9]中討論的結(jié)果，b-bit的性能要依賴(lài)于用在原始最小哈希函數(shù)上的獨(dú)立排列的數(shù)目。ES_SSE也是基于原始最小哈希函數(shù)進(jìn)行構(gòu)造的，因此，它也要依賴(lài)于獨(dú)立排列的數(shù)目。如果總存儲(chǔ)空間為SS位，每個(gè)排列的位數(shù)為b(b≥1)位，則一共有kb=SS/b個(gè)排列。從后面實(shí)驗(yàn)可以看出，kb越大，實(shí)驗(yàn)精度越高。

在ES_SSE實(shí)驗(yàn)中，獨(dú)立排列的數(shù)目kES_SSE由每個(gè)ES_SSE向量大小和設(shè)置的相似度閾值J0決定，一般情況下，只對(duì)那些J>J0的集合對(duì)感興趣。同kb，kES_SSE也是盡量越大越好，來(lái)減少圖1中兩次哈希所造成的誤差。選取一個(gè)最理想的kES_SSE值將非常困難。不過(guò)通過(guò)后面的實(shí)驗(yàn)，本文得出：如果兩個(gè)ES_SSE向量具有相似度J0，它們異或后為1的位數(shù)占總位數(shù)大約31%時(shí)，實(shí)驗(yàn)將獲得最小方差。

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

圖4 MSE比較實(shí)驗(yàn)：J=0.9,n=500-1 000

圖5 MSE比較實(shí)驗(yàn)：n=750,J=0.75-0.95

圖6 ES_SSE和b-bit比較實(shí)驗(yàn):n=512

圖7 ES_SSE和b-bit比較實(shí)驗(yàn):n=1 024

4 結(jié) 語(yǔ)

本文提出了一種壓縮二進(jìn)制方法ES_SSE來(lái)對(duì)集合間的杰卡德相似系數(shù)進(jìn)行估計(jì)。在原始最小哈希函數(shù)的基礎(chǔ)上，通過(guò)再次哈希，利用哈希到某個(gè)位置上的元素個(gè)數(shù)的偶數(shù)性，并進(jìn)行ES_SSE向量之間的異或運(yùn)算，最后通過(guò)模型對(duì)原始集合的相似性進(jìn)行估計(jì)。ES_SSE算法大大節(jié)約了存儲(chǔ)空間，尤其適用于相似度高的場(chǎng)景。實(shí)驗(yàn)也驗(yàn)證了本文模型和算法的性能。