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

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

一、局部敏感哈希LSH

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

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

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

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

那具有如何特點的hash functions才可以使得原本相鄰的兩個數據點經過hash變換后會落入同樣的桶內？這些hash function須要滿足下面兩個條件：

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

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

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

滿足以上兩個條件的hash functions稱為(d1,d2,p1,p2)-sensitive。 而通過一個或 多個 (d1,d2,p1,p2)-sensitive 的hash function對原始數據集合進行hashing生成一個或多個hash table的過程稱為Locality-sensitive Hashing。

使用LSH進行對海量數據建立索引（Hash table）并通過索引來進行近似近期鄰查找的步驟例如以下：

1. 離線建立索引

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

（2）依據對查找結果的準確率（即相鄰的數據被查找到的概率）確定hash table的個數L，每一個table內的hash functions的個數K，以及跟LSH hash function自身有關的參數；

（3）將全部數據經過LSH hash function哈希到對應的桶內，構成了一個或多個hash table；

2. 在線查找

（1）將查詢數據經過LSH hash function哈希得到對應的桶號；

（2）將桶號中相應的數據取出；（為了保證查找速度，通常僅僅須要取出前2L個數據就可以）；

（3）計算查詢數據與這2L個數據之間的相似度或距離，返回近期鄰的數據；

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

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

二、LSH的應用

LSH的應用場景非常多，凡是須要進行大量數據之間的相似度（或距離）計算的地方都能夠使用LSH來加快查找匹配速度，以下列舉一些應用：

（1）查找網絡上的反復網頁

互聯網上因為各式各樣的原因（比如轉載、抄襲等）會存在非常多反復的網頁，因此為了提高搜索引擎的檢索質量或避免反復建立索引，須要查找出反復的網頁，以便進行一些處理。其大致的步驟例如以下：將互聯網的文檔用一個集合或詞袋向量來表征，然后通過一些hash運算來推斷兩篇文檔之間的相似度，經常使用的有minhash+LSH、simhash。

（2）查找相似新聞網頁或文章

與查找反復網頁類似，能夠通過hash的方法來推斷兩篇新聞網頁或文章是否相似，僅僅只是在表達新聞網頁或文章時利用了它們的特點來建立表征該文檔的集合。

（3）圖像檢索

在圖像檢索領域，每張圖片能夠由一個或多個特征向量來表達，為了檢索出與查詢圖片相似的圖片集合，我們能夠對圖片數據庫中的全部特征向量建立LSH索引，然后通過查找LSH索引來加快檢索速度。眼下圖像檢索技術在近期幾年得到了較大的發展，有興趣的讀者能夠查看 基于內容的圖像檢索引擎 的相關介紹。

（4）音樂檢索

對于一段音樂或音頻信息，我們提取其音頻指紋（Audio Fingerprint）來表征該音頻片段，採用音頻指紋的優點在于其可以保持對音頻發生的一些改變的魯棒性，比如壓縮，不同的歌手錄制的同一條歌曲等。為了高速檢索到與查詢音頻或歌曲相似的歌曲，我們可以對數據庫中的全部歌曲的音頻指紋建立LSH索引，然后通過該索引來加快檢索速度。

（5）指紋匹配

一個手指指紋通常由一些細節來表征，通過對照較兩個手指指紋的細節的相似度就能夠確定兩個指紋是否同樣或相似。類似于圖片和音樂檢索，我們能夠對這些細節特征建立LSH索引，加快指紋的匹配速度。

三、LSH family

我們在第一節介紹了LSH的原理和LSH hash function須要滿足的條件，回想一下：

滿足下面兩個條件的hash functions稱為(d1,d2,p1,p2)-sensitive ：

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

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

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

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

1. Jaccard distance

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

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

2. Hamming distance

Hamming distance： 兩個具有同樣長度的向量中相應位置處值不同的次數。

Hamming distance 相應的 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| ，經常使用來推斷兩個向量之間的夾角，夾角越小，表示它們越相似。

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

理解：利用隨機的超平面（random hyperplane）將原始數據空間進行劃分，每個數據被投影后會落入超平面的某一側，經過多個隨機的超平面劃分后，原始空間被劃分為了非常多cell，而位于每個cell內的數據被覺得具有非常大可能是相鄰的（即原始數據之間的cosine distance非常小）。

4. normal Euclidean distance

Euclidean distance 是衡量 D維空間中 兩個點之間的距離的一種距離度量方式 。

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

理解：將原始數據空間中的數據投影到一條隨機的直線（random line）上，而且該直線由非常多長度等于a的線段組成，每個數據被投影后會落入該直線上的某一個線段上（相應的桶內），將全部數據都投影到直線上后，位于同一個線段內的數據將 被覺得具有非常大可能是相鄰的（ 即原始數據之間的 Euclidean distance 非常小）。

四、增強LSH（Amplifying LSH ）

通過LSH hash functions我們可以得到一個或多個hash table，每一個桶內的數據之間是近鄰的可能性非常大。我們希望原本相鄰的數據經過LSH hash后，都可以落入到同樣的桶內，而不相鄰的數據經過LSH hash后，都可以落入到不同的桶中。假設相鄰的數據被投影到了不同的桶內，我們稱為false negtive；假設不相鄰的數據被投影到了同樣的桶內，我們稱為false positive。因此，我們在使用LSH中，我們希望可以盡量減少false negtive rate和false positive rate。

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

以下介紹一些經常使用的增強LSH的方法：

1. 使用多個獨立的hash table

每一個hash table由k個LSH hash function創建，每次選用k個 LSH hash function （同屬于一個LSH function family）就得到了一個hash table，反復多次，就可以創建多個hash table。多個hash table的優點在于可以減少 false positive rate 。

2. AND 與操作

從同一個 LSH function family中挑選出k個LSH function，H(X) = H(Y)有且僅當這k個 Hi(X) = Hi(Y)都滿足。也就是說僅僅有當兩個數據的這k個hash值都相應同樣時，才會被投影到同樣的桶內，僅僅要有一個不滿足就不會被投影到同一個桶內。

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

3. OR 或操作

從同一個 LSH function family中挑選出k個LSH function，H(X) = H(Y)有且僅當存在一個以上的 Hi(X) = Hi(Y)。也就是說僅僅要兩個數據的這k個hash值中有一對以上同樣時，就會被投影到同樣的桶內，僅僅有當這k個hash值都不同樣時才不被投影到同一個桶內。

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

4. AND和OR的級聯

將與操作和或操作級聯在一起，產生很多其它的hahs table，這種優點在于可以使得p1更接近1，而p2更接近0。

除了上面介紹的增強LSH的方法外，有時候我們希望將多個LSH hash function得到的hash值組合起來，在此基礎上得到新的hash值，這樣做的優點在于降低了存儲hash table的空間。以下介紹一些經常用法：

1. 求模運算

new hash value = old hash value % N

2. 隨機投影

如果通過k個LSH hash function得到了k個hash值：h1, h2..., hk。那么新的hash值採用例如以下公式求得：

new hash value = h1*r1 + h2*r2 + ... + hk*rk，當中r1, r2, ..., rk是一些隨機數。

3. XOR異或

如果通過k個LSH hash function得到了k個hash值：h1, h2..., hk。那么新的hash值採用例如以下公式求得：

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

五、相關參考資料

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