LSH局部敏感哈希

1、局部敏感哈希(Locality-SensitiveHashing,LSH)方法介紹本文主要介紹一種用于海量高維數(shù)據(jù)的近似最近鄰快速查找技術(shù)據(jù)據(jù)局部敏感哈希(Locality-SensitiveHashing,LSH)，內(nèi)容包括了LSH的原理、LSH哈希函數(shù)集、以及LSH的一些參考資料。一、局部敏感哈希LSH在很多應用領域中，我們面對和需要處理的數(shù)據(jù)往往是海量并且具有很高的維度，怎樣快速地從海量的高維數(shù)據(jù)集合中找到與某個數(shù)據(jù)最相似(距離最近)的一個數(shù)據(jù)或多個數(shù)據(jù)成為了一個難點和問題。如果是低維的小數(shù)據(jù)集，我們通過線性查找(LinearSearch)就可以容易解決，但如果是對一個海量的高維數(shù)據(jù)集采

2、用線性查找匹配的話，會非常耗時，因此，為了解決該問題，我們需要采用一些類似索引的技術(shù)來加快查找過程，通常這類技術(shù)稱為最近鄰查找(NearestNeighbor,AN)，例如K-dtree；或近似最近鄰查找(ApproximateNearestNeighbor,ANN)，例如K-dtreewithBBF,RandomizedKd-trees,HierarchicalK-meansTree。而LSH是ANN中的一類方法。我們知道，通過建立HashTable的方式我們能夠得到O的查找時間性能，其中關(guān)鍵在于選取一個hashfunction，將原始數(shù)據(jù)映射到相對應的桶內(nèi)(bucket,hashbin)，

3、例如對數(shù)據(jù)求模：h=xmodw，w通常為一個素數(shù)。在對數(shù)據(jù)集進行hash的過程中，會發(fā)生不同的數(shù)據(jù)被映射到了同一個桶中(即發(fā)生了沖突collision)，這一般通過再次哈希將數(shù)據(jù)映射到其他空桶內(nèi)來解決。這是普通Hash方法或者叫傳統(tǒng)Hash方法，其與LSH有些不同之處。ED/icvpr局部敏感哈希示意圖(from:PiotrIndyk)LSH的基本思想是：將原始數(shù)據(jù)空間中的兩個相鄰數(shù)據(jù)點通過相同的映射或投影變換(projection)后，這兩個數(shù)據(jù)點在新的數(shù)據(jù)空間中仍然相鄰的概率很大，而不相鄰的數(shù)據(jù)點被映射到同一個桶的概率很小。也就是說，如果我們對原始數(shù)據(jù)進行一些hash映射后，我們希望原先相

4、鄰的兩個數(shù)據(jù)能夠被hash到相同的桶內(nèi)，具有相同的桶號。對原始數(shù)據(jù)集合中所有的數(shù)據(jù)都進行hash映射后，我們就得到了一個hashtable,這些原始數(shù)據(jù)集被分散到了hashtable的桶內(nèi)，每個桶會落入一些原始數(shù)據(jù)，屬于同一個桶內(nèi)的數(shù)據(jù)就有很大可能是相鄰的，當然也存在不相鄰的數(shù)據(jù)被hash到了同一個桶內(nèi)。因此，如果我們能夠找到這樣一些hashfunctions，使得經(jīng)過它們的哈希映射變換后，原始空間中相鄰的數(shù)據(jù)落入相同的桶內(nèi)的話，那么我們在該數(shù)據(jù)集合中進行近鄰查找就變得容易了，我們只需要將查詢數(shù)據(jù)進行哈希映射得到其桶號，然后取出該桶號對應桶內(nèi)的所有數(shù)據(jù)，再進行線性匹配即可查找到與查詢數(shù)據(jù)相鄰的

5、數(shù)據(jù)。換句話說，我們通過hashfunction映射變換操作，將原始數(shù)據(jù)集合分成了多個子集合,而每個子集合中的數(shù)據(jù)間是相鄰的且該子集合中的元素個數(shù)較小，因此將一個在超大集合內(nèi)查找相鄰元素的問題轉(zhuǎn)化為了在一個很小的集合內(nèi)查找相鄰元素的問題，顯然計算量下降了很多。那具有怎樣特點的hashfunctions才能夠使得原本相鄰的兩個數(shù)據(jù)點經(jīng)過hash變換后會落入相同的桶內(nèi)？這些hashfunction需要滿足以下兩個條件：1）如果d（x,y）di，則h（x）=h（y）的概率至少為p1；2）如果d（x,y）d2，則h（x）=h（y）的概率至多為p2；其中d（x,y）表示x和y之間的距離，did2，卜僅）

6、和h（y）分別表示對x和y進行hash變換。滿足以上兩個條件的hashfunctions稱為912口1口2）66門$計26。而通過一個或多個（d1,d2,p1,p2）-sensitive的hashfunction對原始數(shù)據(jù)集合進行hashing生成一個或多個hashtable的過程稱為Locality-sensitiveHashing。使用LSH進行對海量數(shù)據(jù)建立索引（Hashtable）并通過索引來進行近似最近鄰查找的過程如下：1.離線建立索引（1）選取滿足（d1,d2,p1,p2）-sensitive的LSHhashfunctions；（2）根據(jù)對查找結(jié)果的準確率（即相鄰的數(shù)據(jù)被查找到的概

7、率）確定hashtable的個數(shù)L，每個table內(nèi)的hashfunctions的個數(shù)K，以及跟LSHhashfunction自身有關(guān)的參數(shù)；（3）將所有數(shù)據(jù)經(jīng)過LSHhashfunction哈希到相應的桶內(nèi)，構(gòu)成了一個或多個hashtable；2.在線查找（1）將查詢數(shù)據(jù)經(jīng)過LSHhashfunction哈希得到相應的桶號；（2）將桶號中對應的數(shù)據(jù)取出；（為了保證查找速度，通常只需要取出前2L個數(shù)據(jù)即可）；（3）計算查詢數(shù)據(jù)與這2L個數(shù)據(jù)之間的相似度或距離，返回最近鄰的數(shù)據(jù)；LSH在線查找時間由兩個部分組成：（1）通過LSHhashfunctions計算hash值（桶號）的時間；（2）將查詢

8、數(shù)據(jù)與桶內(nèi)的數(shù)據(jù)進行比較計算的時間。因此，LSH的查找時間至少是一個sublinear時間。為什么是至少？因為我們可以通過對桶內(nèi)的屬于建立索引來加快匹配速度，這時第（2）部分的耗時就從O（N）變成了O（logN）或0（1）（取決于采用的索引方法）。LSH為我們提供了一種在海量的高維數(shù)據(jù)集中查找與查詢數(shù)據(jù)點（querydatapoint）近似最相鄰的某個或某些數(shù)據(jù)點。需要注意的是，LSH并不能保證一定能夠查找到與querydatapoint最相鄰的數(shù)據(jù)，而是減少需要匹配的數(shù)據(jù)點個數(shù)的同時保證查找到最近鄰的數(shù)據(jù)點的概率很大。二、的應用LSH的應用場景很多，凡是需要進行大量數(shù)據(jù)之間的相似度（或距離）

9、計算的地方都可以使用LSH來加快查找匹配速度，下面列舉一些應用：（1）查找網(wǎng)絡上的重復網(wǎng)頁互聯(lián)網(wǎng)上由于各式各樣的原因（例如轉(zhuǎn)載、抄襲等）會存在很多重復的網(wǎng)頁，因此為了提高搜索引擎的檢索質(zhì)量或避免重復建立索引，需要查找出重復的網(wǎng)頁，以便進行一些處理。其大致的過程如下：將互聯(lián)網(wǎng)的文檔用一個集合或詞袋向量來表征，然后通過一些hash運算來判斷兩篇文檔之間的相似度，常用的有minhash+LSH、simhash。（2）查找相似新聞網(wǎng)頁或文章與查找重復網(wǎng)頁類似，可以通過hash的方法來判斷兩篇新聞網(wǎng)頁或文章是否相似，只不過在表達新聞網(wǎng)頁或文章時利用了它們的特點來建立表征該文檔的集合。（3）圖像檢索在圖像

10、檢索領域，每張圖片可以由一個或多個特征向量來表達，為了檢索出與查詢圖片相似的圖片集合，我們可以對圖片數(shù)據(jù)庫中的所有特征向量建立LSH索引，然后通過查找LSH索引來加快檢索速度。目前圖像檢索技術(shù)在最近幾年得到了較大的發(fā)展，有興趣的讀者可以查看基于內(nèi)容的圖像檢索引擎的相關(guān)介紹。（4）音樂檢索對于一段音樂或音頻信息，我們提取其音頻指紋（AudioFingerprint）來表征該音頻片段，采用音頻指紋的好處在于其能夠保持對音頻發(fā)生的一些改變的魯棒性，例如壓縮，不同的歌手錄制的同一條歌曲等。為了快速檢索到與查詢音頻或歌曲相似的歌曲，我們可以對數(shù)據(jù)庫中的所有歌曲的音頻指紋建立LSH索引，然后通過該索引來加

11、快檢索速度。（5）指紋匹配一個手指指紋通常由一些細節(jié)來表征，通過對比較兩個手指指紋的細節(jié)的相似度就可以確定兩個指紋是否相同或相似。類似于圖片和音樂檢索，我們可以對這些細節(jié)特征建立LSH索引，加快指紋的匹配速度。三、LSHfamily我們在第一節(jié)介紹了LSH的原理和LSHhashfunction需要滿足的條件，回顧一下：滿足以下兩個條件的hashfunctions稱為(d1,d2,p1,p2)-sensitive：1)如果d(x,y)di，則h(x)=h(y)的概率至少為p1；2)如果d(x,y)d2，則h(x)=h(y)的概率至多為p2；d(x,y)是x和y之間的一個距離度量(distance

12、measure)，需要說明的是，并不是所有的距離度量都能夠找到滿足locality-sensitive的hashfunctions。下面我們介紹一些滿足不同距離度量方式下的locality-sensitive的hashfunctions：JaccarddistanceJaccarddistance：(1-Jaccardsimilarity)，WJaccardsimilarity=(AintersectionB)/(AunionB)，Jaccardsimilarity通常用來判斷兩個集合的相似性。Jaccarddistance對應的LSHhashfunction為：minhash，其是912,1

13、七1,1P2)66門$計26的。HammingdistanceHammingdistance：兩個具有相同長度的向量中對應位置處值不同的次數(shù)。Hammingdistance對應的LSHhashfunction為：H(V)=向量V的第i位上的值，其是(d1,d2,1-d1/d,1-d2/d)-sensitive的。CosinedistanceCosinedistance：cos(theta)=A.B/|A|B|，常用來判斷兩個向量之間的夾角，夾角越小，表示它們越相似。Cosinedistance對應的LSHhashfunction為：H(V)=sign(VR),R是一個隨機向量。V-R可以看做是

14、將V向R上進行投影操作。其是912,(180七1)180,(180七2)/180)66門$如6的。理解：利用隨機的超平面(randomhyperplane)將原始數(shù)據(jù)空間進行劃分，每一個數(shù)據(jù)被投影后會落入超平面的某一側(cè)，經(jīng)過多個隨機的超平面劃分后，原始空間被劃分為了很多cell，而位于每個cell內(nèi)的數(shù)據(jù)被認為具有很大可能是相鄰的(即原始數(shù)據(jù)之間的cosinedistance很小)。normalEuclideandistanceEuclideandistance是衡量D維空間中兩個點之間的距離的一種距離度量方式。Euclideandistance對應的LSHhashfunction為:H(V)

15、=MR+b|/a，R是一個隨機向量，a是桶寬，b是一個在0,a之間均勻分布的隨機變量。V-R可以看做是將V向R上進行投影操作。其是(a/2,2a,1/2,1/3)-sensitive的。理解：將原始數(shù)據(jù)空間中的數(shù)據(jù)投影到一條隨機的直線(randomline)上，并且該直線由很多長度等于a的線段組成，每一個數(shù)據(jù)被投影后會落入該直線上的某一個線段上(對應的桶內(nèi))，將所有數(shù)據(jù)都投影到直線上后，位于同一個線段內(nèi)的數(shù)據(jù)將被認為具有很大可能是相鄰的(即原始數(shù)據(jù)之間的Euclideandistance很小)。四、增強LSH(AmplifyingLSH)通過LSHhashfunctions我們能夠得到一個或多

16、個hashtable，每個桶內(nèi)的數(shù)據(jù)之間是近鄰的可能性很大。我們希望原本相鄰的數(shù)據(jù)經(jīng)過LSHhash后，都能夠落入到相同的桶內(nèi)，而不相鄰的數(shù)據(jù)經(jīng)過LSHhash后，都能夠落入到不同的桶中。如果相鄰的數(shù)據(jù)被投影到了不同的桶內(nèi)，我們稱為falsenegtive；如果不相鄰的數(shù)據(jù)被投影到了相同的桶內(nèi)，我們稱為falsepositive。因此，我們在使用LSH中，我們希望能夠盡量降低falsenegtiverate和falsepositiverate。通常，為了能夠增強LSH，即使得falsenegtiverate和/或falsepositiverate降低，我們有兩個途徑來實現(xiàn)：1)在一個hasht

17、able內(nèi)使用更多的LSHhashfunction；2)建立多個hashtableo下面介紹一些常用的增強LSH的方法：使用多個獨立的hashtable每個hashtable由k個LSHhashfunction創(chuàng)建，每次選用k個LSHhashfunction(同屬于一個LSHfunctionfamily)就得到了一個hashtable,重復多次，即可創(chuàng)建多個hashtable。多個hashtable的好處在于能夠降低falsepositiverate。AND與操作從同一個LSHfunctionfamily中挑選出k個LSHfunction，H(X)=H(Y)有且僅當這k個Hi(X)=Hi(Y)

18、都滿足。也就是說只有當兩個數(shù)據(jù)的這k個hash值都對應相同時，才會被投影到相同的桶內(nèi)，只要有一個不滿足就不會被投影到同一個桶內(nèi)。AND與操作能夠使得找到近鄰數(shù)據(jù)的p1概率保持高概率的同時降低p2概率，即降低了falsenegtiverate。OR或操作從同一個LSHfunctionfamily中挑選出k個LSHfunction，H(X)=H(Y)有且僅當存在一個以上的Hi(X)=Hi(Y)。也就是說只要兩個數(shù)據(jù)的這k個hash值中有一對以上相同時，就會被投影到相同的桶內(nèi)，只有當這k個hash值都不相同時才不被投影到同一個桶內(nèi)。OR或操作能夠使得找到近鄰數(shù)據(jù)的p1概率變的更大(越接近1)的同時保

19、持p2概率較小，即降低了falsepositiverate。AND和OR的級聯(lián)將與操作和或操作級聯(lián)在一起，產(chǎn)生更多的hahstable，這樣的好處在于能夠使得p1更接近1,而p2更接近0。除了上面介紹的增強LSH的方法外，有時候我們希望將多個LSHhashfunction得到的hash值組合起來，在此基礎上得到新的hash值，這樣做的好處在于減少了存儲hashtable的空間。下面介紹一些常用方法：.求模運算newhashvalue=oldhashvalue%N.隨機投影假設通過k個LSHhashfunction得到了k個hash值：hi,h2.,hk。那么新的hash值采用如下公式求得：ne

20、whashvalue=h1*r1+h2*r2+.+hk*rk，其中ri,r2,.,rk是一些隨機數(shù)。.XOR異或假設通過k個LSHhashfunction得到了k個hash值：hi,h2,hk。那么新的hash值采用如下公式求得：newhashvalue=hiXORh2XORh3.XORhk五、相關(guān)參考資料Website: HYPERLINK /indyk/ /indyk/(LSH原作者) HYPERLINK /andoni/LSH/ /andoni/LSH/(E2LSH)Paper:Approximatenearestneighbor:towardsremovingthecurseofdimensionalitySimilaritysearchinhighdimensionsviahashingLocality-sensitivehashingschemebasedonp-stabledistributionsMultiProbeLSHEfficientIndexingforHighDimensionalSimilaritySearchNear-OptimalHashingAl