局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介紹

本文主要介紹一種用于海量高維數(shù)據(jù)的近似近期鄰高速查找技術(shù)——局部敏感哈希(Locality-Sensitive Hashing, LSH)，內(nèi)容包含了LSH的原理、LSH哈希函數(shù)集、以及LSH的一些參考資料。

一、局部敏感哈希LSH

在非常多應(yīng)用領(lǐng)域中，我們面對(duì)和須要處理的數(shù)據(jù)往往是海量而且具有非常高的維度，如何高速地從海量的高維數(shù)據(jù)集合中找到與某個(gè)數(shù)據(jù)最相似（ 距離 近期）的一個(gè)數(shù)據(jù)或多個(gè)數(shù)據(jù)成為了一個(gè)難點(diǎn)和問(wèn)題。假設(shè)是低維的小數(shù)據(jù)集，我們通過(guò)線(xiàn)性查找（Linear Search）就能夠easy解決，但假設(shè)是對(duì)一個(gè)海量的高維數(shù)據(jù)集採(cǎi)用線(xiàn)性查找匹配的話(huà)，會(huì)非常耗時(shí)，因此，為了解決該問(wèn)題，我們須要採(cǎi)用一些類(lèi)似索引的技術(shù)來(lái)加快查找過(guò)程，通常這類(lèi)技術(shù)稱(chēng)為近期鄰查找（ Nearest? Neighbor ,AN）， 比如K-d tree ；或近似近期鄰查找（Approximate Nearest? Neighbor, ANN），比如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH是ANN中的一類(lèi)方法。

我們知道，通過(guò)建立Hash Table的方式我們可以得到O(1)的查找時(shí)間性能，當(dāng)中關(guān)鍵在于選取一個(gè)hash function，將原始數(shù)據(jù)映射到相相應(yīng)的桶內(nèi)（bucket, hash bin），比如對(duì)數(shù)據(jù)求模：h = x mod w，w通常為一個(gè)素?cái)?shù)。在對(duì)數(shù)據(jù)集進(jìn)行hash 的過(guò)程中，會(huì)發(fā)生不同的數(shù)據(jù)被映射到了同一個(gè)桶中（即發(fā)生了沖突collision），這一般通過(guò)再次哈希將數(shù)據(jù)映射到其它空桶內(nèi)來(lái)解決。這是普通Hash方法或者叫傳統(tǒng)Hash方法，其與LSH有些不同之處。

局部敏感哈希示意圖（from: Piotr Indyk）

LSH的基本思想是：將原始數(shù)據(jù)空間中的兩個(gè)相鄰數(shù)據(jù)點(diǎn)通過(guò)同樣的映射或投影變換（projection）后，這兩個(gè)數(shù)據(jù)點(diǎn)在新的數(shù)據(jù)空間中仍然相鄰的概率非常大，而不相鄰的數(shù)據(jù)點(diǎn)被映射到同一個(gè)桶的概率非常小。也就是說(shuō)，假設(shè)我們對(duì)原始數(shù)據(jù)進(jìn)行一些hash映射后，我們希望原先相鄰的兩個(gè)數(shù)據(jù)可以被hash到同樣的桶內(nèi)，具有同樣的桶號(hào)。對(duì)原始數(shù)據(jù)集合中全部的數(shù)據(jù)都進(jìn)行hash映射后，我們就得到了一個(gè)hash table，這些原始數(shù)據(jù)集被分散到了hash table的桶內(nèi)，每一個(gè)桶會(huì)落入一些原始數(shù)據(jù)，屬于同一個(gè)桶內(nèi)的數(shù)據(jù)就有非常大可能是相鄰的，當(dāng)然也存在不相鄰的數(shù)據(jù)被hash到了同一個(gè)桶內(nèi)。因此，假設(shè)我們可以找到這樣一些hash functions，使得經(jīng)過(guò)它們的哈希映射變換后，原始空間中相鄰的數(shù)據(jù)落入同樣的桶內(nèi)的話(huà)，那么我們?cè)谠摂?shù)據(jù)集合中進(jìn)行近鄰查找就變得easy了，我們僅僅須要將查詢(xún)數(shù)據(jù)進(jìn)行哈希映射得到其桶號(hào)，然后取出該桶號(hào)相應(yīng)桶內(nèi)的全部數(shù)據(jù)，再進(jìn)行線(xiàn)性匹配就可以查找到與查詢(xún)數(shù)據(jù)相鄰的數(shù)據(jù)。換句話(huà)說(shuō)，我們通過(guò)hash function映射變換操作，將原始數(shù)據(jù)集合分成了多個(gè)子集合，而每一個(gè)子集合中的數(shù)據(jù)間是相鄰的且該子集合中的元素個(gè)數(shù)較小，因此將一個(gè)在超大集合內(nèi)查找相鄰元素的問(wèn)題轉(zhuǎn)化為了在一個(gè)非常小的集合內(nèi)查找相鄰元素的問(wèn)題，顯然計(jì)算量下降了非常多。

那具有如何特點(diǎn)的hash functions才可以使得原本相鄰的兩個(gè)數(shù)據(jù)點(diǎn)經(jīng)過(guò)hash變換后會(huì)落入同樣的桶內(nèi)？這些hash function須要滿(mǎn)足下面兩個(gè)條件：

1）假設(shè)d(x,y) ≤ d1， 則h(x) = h(y)的概率至少為p1；

2）假設(shè) d(x,y) ≥ d2， 則h(x) = h(y)的概率至多為p2；

當(dāng)中d(x,y)表示x和y之間的距離，d1 < d2， h(x)和h(y)分別表示對(duì)x和y進(jìn)行hash變換。

滿(mǎn)足以上兩個(gè)條件的hash functions稱(chēng)為(d1,d2,p1,p2)-sensitive。 而通過(guò)一個(gè)或 多個(gè) (d1,d2,p1,p2)-sensitive 的hash function對(duì)原始數(shù)據(jù)集合進(jìn)行hashing生成一個(gè)或多個(gè)hash table的過(guò)程稱(chēng)為L(zhǎng)ocality-sensitive Hashing。

使用LSH進(jìn)行對(duì)海量數(shù)據(jù)建立索引（Hash table）并通過(guò)索引來(lái)進(jìn)行近似近期鄰查找的步驟例如以下：

1. 離線(xiàn)建立索引

（1）選取滿(mǎn)足 (d1,d2,p1,p2)-sensitive 的LSH hash functions；

（2）依據(jù)對(duì)查找結(jié)果的準(zhǔn)確率（即相鄰的數(shù)據(jù)被查找到的概率）確定hash table的個(gè)數(shù)L，每一個(gè)table內(nèi)的hash functions的個(gè)數(shù)K，以及跟LSH hash function自身有關(guān)的參數(shù)；

（3）將全部數(shù)據(jù)經(jīng)過(guò)LSH hash function哈希到對(duì)應(yīng)的桶內(nèi)，構(gòu)成了一個(gè)或多個(gè)hash table；

2. 在線(xiàn)查找

（1）將查詢(xún)數(shù)據(jù)經(jīng)過(guò)LSH hash function哈希得到對(duì)應(yīng)的桶號(hào)；

（2）將桶號(hào)中相應(yīng)的數(shù)據(jù)取出；（為了保證查找速度，通常僅僅須要取出前2L個(gè)數(shù)據(jù)就可以）；

（3）計(jì)算查詢(xún)數(shù)據(jù)與這2L個(gè)數(shù)據(jù)之間的相似度或距離，返回近期鄰的數(shù)據(jù)；

LSH在線(xiàn)查找時(shí)間由兩個(gè)部分組成： （1）通過(guò)LSH hash functions計(jì)算hash值（桶號(hào)）的時(shí)間；（2）將查詢(xún)數(shù)據(jù)與桶內(nèi)的數(shù)據(jù)進(jìn)行比較計(jì)算的時(shí)間。因此，LSH的查找時(shí)間至少是一個(gè)sublinear時(shí)間。為什么是“至少”？由于我們能夠通過(guò)對(duì)桶內(nèi)的屬于建立索引來(lái)加快匹配速度，這時(shí)第（2）部分的耗時(shí)就從O(N)變成了O(logN)或O(1)（取決于採(cǎi)用的索引方法）。

LSH為我們提供了一種在海量的高維數(shù)據(jù)集中查找與查詢(xún)數(shù)據(jù)點(diǎn)（query data point）近似最相鄰的某個(gè)或某些數(shù)據(jù)點(diǎn)。須要注意的是，LSH并不能保證一定可以查找到與query data point最相鄰的數(shù)據(jù)，而是降低須要匹配的數(shù)據(jù)點(diǎn)個(gè)數(shù)的同一時(shí)候保證查找到近期鄰的數(shù)據(jù)點(diǎn) 的概率 非常大。

二、LSH的應(yīng)用

LSH的應(yīng)用場(chǎng)景非常多，凡是須要進(jìn)行大量數(shù)據(jù)之間的相似度（或距離）計(jì)算的地方都能夠使用LSH來(lái)加快查找匹配速度，以下列舉一些應(yīng)用：

（1）查找網(wǎng)絡(luò)上的反復(fù)網(wǎng)頁(yè)

互聯(lián)網(wǎng)上因?yàn)楦魇礁鳂拥脑颍ū热甾D(zhuǎn)載、抄襲等）會(huì)存在非常多反復(fù)的網(wǎng)頁(yè)，因此為了提高搜索引擎的檢索質(zhì)量或避免反復(fù)建立索引，須要查找出反復(fù)的網(wǎng)頁(yè)，以便進(jìn)行一些處理。其大致的步驟例如以下：將互聯(lián)網(wǎng)的文檔用一個(gè)集合或詞袋向量來(lái)表征，然后通過(guò)一些hash運(yùn)算來(lái)推斷兩篇文檔之間的相似度，經(jīng)常使用的有minhash+LSH、simhash。

（2）查找相似新聞網(wǎng)頁(yè)或文章

與查找反復(fù)網(wǎng)頁(yè)類(lèi)似，能夠通過(guò)hash的方法來(lái)推斷兩篇新聞網(wǎng)頁(yè)或文章是否相似，僅僅只是在表達(dá)新聞網(wǎng)頁(yè)或文章時(shí)利用了它們的特點(diǎn)來(lái)建立表征該文檔的集合。

（3）圖像檢索

在圖像檢索領(lǐng)域，每張圖片能夠由一個(gè)或多個(gè)特征向量來(lái)表達(dá)，為了檢索出與查詢(xún)圖片相似的圖片集合，我們能夠?qū)D片數(shù)據(jù)庫(kù)中的全部特征向量建立LSH索引，然后通過(guò)查找LSH索引來(lái)加快檢索速度。眼下圖像檢索技術(shù)在近期幾年得到了較大的發(fā)展，有興趣的讀者能夠查看 基于內(nèi)容的圖像檢索引擎 的相關(guān)介紹。

（4）音樂(lè)檢索

對(duì)于一段音樂(lè)或音頻信息，我們提取其音頻指紋（Audio Fingerprint）來(lái)表征該音頻片段，採(cǎi)用音頻指紋的優(yōu)點(diǎn)在于其可以保持對(duì)音頻發(fā)生的一些改變的魯棒性，比如壓縮，不同的歌手錄制的同一條歌曲等。為了高速檢索到與查詢(xún)音頻或歌曲相似的歌曲，我們可以對(duì)數(shù)據(jù)庫(kù)中的全部歌曲的音頻指紋建立LSH索引，然后通過(guò)該索引來(lái)加快檢索速度。

（5）指紋匹配

一個(gè)手指指紋通常由一些細(xì)節(jié)來(lái)表征，通過(guò)對(duì)照較兩個(gè)手指指紋的細(xì)節(jié)的相似度就能夠確定兩個(gè)指紋是否同樣或相似。類(lèi)似于圖片和音樂(lè)檢索，我們能夠?qū)@些細(xì)節(jié)特征建立LSH索引，加快指紋的匹配速度。

三、LSH family

我們?cè)诘谝还?jié)介紹了LSH的原理和LSH hash function須要滿(mǎn)足的條件，回想一下：

滿(mǎn)足下面兩個(gè)條件的hash functions稱(chēng)為(d1,d2,p1,p2)-sensitive ：

1）假設(shè)d(x,y) ≤ d1， 則h(x) = h(y)的概率至少為p1；

2）假設(shè) d(x,y) ≥ d2， 則h(x) = h(y)的概率至多為p2；

d(x,y)是x和y之間的一個(gè)距離度量（distance measure），須要說(shuō)明的是，并非全部的距離度量都可以找到滿(mǎn)足 locality-sensitive 的hash functions。

以下我們介紹一些滿(mǎn)足不同距離度量方式下的 locality-sensitive 的hash functions：

1. Jaccard distance

Jaccard distance： (1 - Jaccard similarity)，而 Jaccard similarity = (A intersection B) / (A union B)， Jaccard similarity 通經(jīng)常使用來(lái)推斷兩個(gè)集合的相似性。

Jaccard distance相應(yīng)的 LSH hash function為：minhash，其是(d1,d2,1-d1,1-d2)-sensitive的。

2. Hamming distance

Hamming distance： 兩個(gè)具有同樣長(zhǎng)度的向量中相應(yīng)位置處值不同的次數(shù)。

Hamming distance 相應(yīng)的 LSH hash function為：H(V) = 向量V的第i位上的值，其是(d1,d2,1-d1/d,1-d2/d)-sensitive

的。

3. Cosine distance

Cosine distance：cos(theta) = A · B / |A||B| ，經(jīng)常使用來(lái)推斷兩個(gè)向量之間的夾角，夾角越小，表示它們?cè)较嗨啤?

Cosine distance相應(yīng)的LSH hash function為：H(V) = sign(V · R)，R是一個(gè)隨機(jī)向量。V · R能夠看做是將V向R上進(jìn)行投影操作。其是(d1,d2,(180-d1)180,(180-d2)/180)-sensitive的。

理解：利用隨機(jī)的超平面（random hyperplane）將原始數(shù)據(jù)空間進(jìn)行劃分，每個(gè)數(shù)據(jù)被投影后會(huì)落入超平面的某一側(cè)，經(jīng)過(guò)多個(gè)隨機(jī)的超平面劃分后，原始空間被劃分為了非常多cell，而位于每個(gè)cell內(nèi)的數(shù)據(jù)被覺(jué)得具有非常大可能是相鄰的（即原始數(shù)據(jù)之間的cosine distance非常?。?

4. normal Euclidean distance

Euclidean distance 是衡量 D維空間中 兩個(gè)點(diǎn)之間的距離的一種距離度量方式 。

Euclidean distance相應(yīng)的LSH hash function為：H(V) = |V·R + b| / a，R是一個(gè)隨機(jī)向量，a是桶寬，b是一個(gè)在[0,a]之間均勻分布的隨機(jī)變量。V·R能夠看做是將V向R上進(jìn)行投影操作。其是(a/2,2a,1/2,1/3)-sensitive的。

理解：將原始數(shù)據(jù)空間中的數(shù)據(jù)投影到一條隨機(jī)的直線(xiàn)（random line）上，而且該直線(xiàn)由非常多長(zhǎng)度等于a的線(xiàn)段組成，每個(gè)數(shù)據(jù)被投影后會(huì)落入該直線(xiàn)上的某一個(gè)線(xiàn)段上（相應(yīng)的桶內(nèi)），將全部數(shù)據(jù)都投影到直線(xiàn)上后，位于同一個(gè)線(xiàn)段內(nèi)的數(shù)據(jù)將 被覺(jué)得具有非常大可能是相鄰的（ 即原始數(shù)據(jù)之間的 Euclidean distance 非常?。?。

四、增強(qiáng)LSH（Amplifying LSH ）

通過(guò)LSH hash functions我們可以得到一個(gè)或多個(gè)hash table，每一個(gè)桶內(nèi)的數(shù)據(jù)之間是近鄰的可能性非常大。我們希望原本相鄰的數(shù)據(jù)經(jīng)過(guò)LSH hash后，都可以落入到同樣的桶內(nèi)，而不相鄰的數(shù)據(jù)經(jīng)過(guò)LSH hash后，都可以落入到不同的桶中。假設(shè)相鄰的數(shù)據(jù)被投影到了不同的桶內(nèi)，我們稱(chēng)為false negtive；假設(shè)不相鄰的數(shù)據(jù)被投影到了同樣的桶內(nèi)，我們稱(chēng)為false positive。因此，我們?cè)谑褂肔SH中，我們希望可以盡量減少false negtive rate和false positive rate。

通常，為了可以增強(qiáng)LSH，即使得false negtive rate 和/或 false positive rate減少，我們有兩個(gè)途徑來(lái)實(shí)現(xiàn)：1）在一個(gè)hash table內(nèi)使用很多其它的LSH hash functio n；2）建立多個(gè)hash table。

以下介紹一些經(jīng)常使用的增強(qiáng)LSH的方法：

1. 使用多個(gè)獨(dú)立的hash table

每一個(gè)hash table由k個(gè)LSH hash function創(chuàng)建，每次選用k個(gè) LSH hash function （同屬于一個(gè)LSH function family）就得到了一個(gè)hash table，反復(fù)多次，就可以創(chuàng)建多個(gè)hash table。多個(gè)hash table的優(yōu)點(diǎn)在于可以減少 false positive rate 。

2. AND 與操作

從同一個(gè) LSH function family中挑選出k個(gè)LSH function，H(X) = H(Y)有且僅當(dāng)這k個(gè) Hi(X) = Hi(Y)都滿(mǎn)足。也就是說(shuō)僅僅有當(dāng)兩個(gè)數(shù)據(jù)的這k個(gè)hash值都相應(yīng)同樣時(shí)，才會(huì)被投影到同樣的桶內(nèi)，僅僅要有一個(gè)不滿(mǎn)足就不會(huì)被投影到同一個(gè)桶內(nèi)。

AND與操作可以使得找到近鄰數(shù)據(jù)的p1概率保持高概率的同一時(shí)候減少p2概率，即減少了 false negtive rate 。

3. OR 或操作

從同一個(gè) LSH function family中挑選出k個(gè)LSH function，H(X) = H(Y)有且僅當(dāng)存在一個(gè)以上的 Hi(X) = Hi(Y)。也就是說(shuō)僅僅要兩個(gè)數(shù)據(jù)的這k個(gè)hash值中有一對(duì)以上同樣時(shí)，就會(huì)被投影到同樣的桶內(nèi)，僅僅有當(dāng)這k個(gè)hash值都不同樣時(shí)才不被投影到同一個(gè)桶內(nèi)。

OR或操作可以使得找到近鄰數(shù)據(jù)的p1概率變的更大（越接近1）的同一時(shí)候保持p2概率較小，即減少了 false positive rate 。

4. AND和OR的級(jí)聯(lián)

將與操作和或操作級(jí)聯(lián)在一起，產(chǎn)生很多其它的hahs table，這種優(yōu)點(diǎn)在于可以使得p1更接近1，而p2更接近0。

除了上面介紹的增強(qiáng)LSH的方法外，有時(shí)候我們希望將多個(gè)LSH hash function得到的hash值組合起來(lái)，在此基礎(chǔ)上得到新的hash值，這樣做的優(yōu)點(diǎn)在于降低了存儲(chǔ)hash table的空間。以下介紹一些經(jīng)常用法：

1. 求模運(yùn)算

new hash value = old hash value % N

2. 隨機(jī)投影

如果通過(guò)k個(gè)LSH hash function得到了k個(gè)hash值：h1, h2..., hk。那么新的hash值採(cǎi)用例如以下公式求得：

new hash value = h1*r1 + h2*r2 + ... + hk*rk，當(dāng)中r1, r2, ..., rk是一些隨機(jī)數(shù)。

3. XOR異或

如果通過(guò)k個(gè)LSH hash function得到了k個(gè)hash值：h1, h2..., hk。那么新的hash值採(cǎi)用例如以下公式求得：

new hash value = h1 XOR h2 XOR h3 ... XOR hk

五、相關(guān)參考資料

Website:

[1] http://people.csail.mit.edu/indyk/ （LSH原作者）

[2] http://www.mit.edu/~andoni/LSH/ (E2LSH)

Paper:

[1] Approximate nearest neighbor: towards removing the curse of dimensionality

[2] Similarity search in high dimensions via hashing

[3] Locality-sensitive hashing scheme based on p-stable distributions?

[4] MultiProbe LSH Efficient Indexing for HighDimensional Similarity Search

[5] Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

Tutorial:

[1] Locality-Sensitive Hashing for Finding Nearest Neighbors

[2] Approximate Proximity Problems in High Dimensions via Locality-Sensitive Hashing

[3] Similarity Search in High Dimensions

Book:

[1] Mining of Massive Datasets
[2] Nearest Neighbor Methods in Learning and Vision: Theory and Practice

Cdoe:

[1] http://sourceforge.net/projects/lshkit/?source=directory

[2] http://tarsos.0110.be/releases/TarsosLSH/TarsosLSH-0.5/TarsosLSH-0.5-Readme.html?

[3] http://www.cse.ohio-state.edu/~kulis/klsh/klsh.htm?

[4] http://code.google.com/p/likelike/?

[5] https://github.com/yahoo/Optimal-LSH

[6] OpenCV LSH（分別位于legacy module和flann module中）

聲明：

作者： icvpr ?? | ?blog.csdn.net/icvpr