一. 近鄰搜索

局部敏感哈希，英文locality-sensetive hashing，常簡稱為LSH。局部敏感哈希在部分中文文獻中也會被稱做位置敏感哈希。LSH是一種哈希算法，最早在1998年由Indyk在上提出。不同于我們在數據結構教材中對哈希算法的認識，哈希最開始是為了減少沖突方便快速增刪改查，在這里LSH恰恰相反，它利用的正式哈希沖突加速檢索，并且效果極其明顯。

LSH主要運用到高維海量數據的快速近似查找。近似查找便是比較數據點之間的距離或者是相似度。因此，很明顯，LSH是向量空間模型下的東西。一切數據都是以點或者說以向量的形式表現出來的。在細說LSH之前必須先提一下K最近鄰查找 (kNN，k-Nearest Neighbor)與c最近鄰查找 (cNN，c-Nearest Neighbor )。 　　 　　kNN問題就不多說了，這個大家應該都清楚，在一個點集中尋找距離目標點最近的K個點。我們主要提一下cNN問題。首先給出最近鄰查找（NN，Nearest Neighbor）的定義。

定義 1： 給定一擁有n個點的點P，在此集合中尋找距離q 點最近的一個點。

這個定義很容易被理解，需要說明的是這個距離是個廣義的概念，并沒有說一定是歐式距離。隨著需求的不同可以是不同的距離度量手段。那么接下來給出cNN問題的定義。 　　

定義 2： 給定一擁有n個點的點集P，在點集中尋找點 這個 滿足 其中d 是P中 距離古點最近一點到的的距離。

cNN不同于kNN，cNN和距離的聯系更加緊密。LSH本身設計出來是專門針對解決cNN問題，而不是kNN問題，但是很多時候kNN與cNN有著相似的解集。因此LSH也可以運用在kNN問題上。這些問題若使用一一匹配的暴力搜索方式會消耗大量的時間，即使這個時間復雜度是線性的。

也許一次兩次遍歷整個數據集不會消耗很多時間，但是如果是以用戶檢索訪問的形式表現出來可以發現查詢的用戶多了，每個用戶都需要消耗掉一些資源，服務器往往會承受巨大負荷。那么即使是線性的復雜度也是不可以忍受的。早期為了解決這類問題涌現出了許多基于樹形結構的搜索方案，如KD樹，SR樹。但是這些方法只適用于低維數據。自從LSH的出現，高維數據的近似查找便得到了一定的解決。

二. LSH的定義

LSH不像樹形結構的方法可以得到精確的結果，LSH所得到的是一個近似的結果，因為在很多領域中并不需非常高的精確度。即使是近似解，但有時候這個近似程度幾乎和精準解一致。 　　 LSH的主要思想是，高維空間的兩點若距離很近，那么設計一種哈希函數對這兩點進行哈希值計算，使得他們哈希值有很大的概率是一樣的。同時若兩點之間的距離較遠，他們哈希值相同的概率會很小。給出LSH的定義如下：

定義3： 給定一族哈希函數H，H是一個從歐式空間S到哈希編碼空間U的映射。如果以下兩個條件都滿足, 則稱此 哈希函數滿足性。

若則若則

定義3中B表示的是以q為中心， 或 為半徑的空間。其實還有個版本的定義, 用的是距離的方式, 其實都是一樣的。（至于說為什么是同時時出現，如果要嚴密的說這確實是個問題，但是人家大牛的論文下的定義, 不要在意這些細節 我繪制了一幅圖來說明一下這個定義。

三. 曼哈頓距離轉換成漢明距離

從理論講解的邏輯順序上來說，現在還沒到非要講具體哈希函數的時候，但是為了方便理解，必須要舉一個實例來講解會好一些。那么就以曼哈頓距離下（其實用的是漢明距離的特性）的LSH哈希函數族作為一個參考的例子講解。 　　曼哈頓距離又稱L1L1范數距離。其具體定義如下：

定義 4： 在n維歐式空間 中任意兩點 他們之間的買哈頓距離為:

其實曼哈頓距離我們應該并不陌生。他與歐式距離（L2范數距離）的差別就像直角三角形兩邊之和與斜邊的差別。其實在這篇論文發表的時候歐式距離的哈希函數還沒有被探究出來，原本LSH的設計其實是想解決歐式距離度量下的近似搜索。所以當時這個事情搞得就很尷尬，然后我們的大牛Indyk等人就強行解釋，大致意思是：不要在意這些細節，曼哈頓和歐式距離差不多。他在文章中提出了兩個關鍵的問題。 　　1.使用L1范數距離進行度量。 　　2.所有坐標全部被正整數化。 　　對于第一條他解釋說L1范數距離與L2范數距離在進行近似查找時得到的結果非常相似。對于第二條，整數化是為了方便進行01編碼。

對數據集 所有的點, 令C作為所有點中坐標的最大值m, 也就是上限。下限是0，這個很明顯。然后就可以把 嵌入漢明空間 其中 此處 是數據點在原來歐式空間的維度。對于 個點 如果用 '空間的坐標表示就是:

Unary_ 是一串長度為 二進制的漢明碼，其意思是前 位為1 后 位為0。舉個例子, C若為5 x 為3，則 Unary=11100 。 是多個 Unary 拼接而成。此時可以發現對于兩點 他們之間的曼哈頓距離和通過變換坐標后的漢明距 離是一樣的。到此處, 我們可以針對漢明距離來定義一族哈希函數。

##四. 漢明距離下的LSH哈希函數

五. LSH的重要參數

當基本哈希函數確定, 理論上講只要 通過改變 l都可以將 時的哈希概率差距拉的很大。代價是要 足夠大的 這也是LSH一個致命的弊病。 說了這么多我們來舉一個實例幫助理解。

例1：數據點集合P由以下6個點構成:

可知坐標出現的最大值是4，則 維度為2, 則 顯然n 。我們進行8位漢明碼編碼。

若我我們現在采用k = 2, l = 3生成哈希函數。 由 構成。每個 由它對應的 構成
假設有如下結果。 分別抽取第2，4位。 分別抽取第1，6位。 分別抽取第3，8位。 哈希表的分布如下圖所示。

可以計算出 。則分別取出表1,2，3的11，11，11號哈希桶的數據點與q比較。依次是C,D,E,F。算出距離q最近的點為F。當然這個例子可能效果不是很明顯。原始搜索空間為6個點, 現在搜索空間為4個點。對于剛接觸LSH的人會有個疑問。如果不同哈希表的數據點重復了 怎么辦, 會不會增加搜索空間的大小。

首先要說的是這個概率很小, 為什么呢。試想假設兩個不同哈希表的哈希桶對 查詢有相同點, 這意味著在兩張哈希表中這個點與q都有相同哈希值。如果使用單個哈希函數q和此點被哈希到一起的概率 為 則剛才那個事件發生的概率為 這個概率是很小的。當然也有很多辦法可以解決這個問題。這不是一個大問 題。

我在實際運用時k大概總是取10-20之間的數, l大致20-100左右。每次對 q進行候選點匹配時, 候選的樣本點數量已 經是P的十分之一到百分之一了。就好比P有10000個數據點, 使用暴力匹配要遍歷整個數據集, 使用LSH可能只要匹配1 00到1000個點就可以了。而且往往我都能找到最近點。即使找不到最近的，總體成功率也在90%-98%左右。

之前講解的是一個大致思想，有很多細節沒有說明白。 比如哈希表和哈希桶的具體表現形式。就好比我給出的是個邏輯結構, 并沒有說清楚它的物理結構。現在說說通常是怎么 具體實施的。其實我想說的是物理結構這個東西每個人都可以設計一個自己習慣的，不一定非要按某個標準來。車要的是 思想。 當k的數值很大時, 對于擁有大量數據點的 產生不同的哈希值會很多。這種二進制的編碼的哈希值最多可以有2 種。這樣一來可能會產生大量哈希桶, 于是平我們可以采用一種方法, 叫二級哈希。首先我們可以將數據點p哈希到編碼 為 的哈希桶。

然后我們可以用一個普通的哈希將哈希桶 哈希到一張大小為M 的哈希表中。注意這里的 是針對 哈希桶的數目而不是針對點的數量。至于第二個哈希具體這么做, 我想學過數據結構的同學都應該知道。對于哈希桶而 言，我們限制它的大小為 也就是說它最多可以放下 個點。當它的點數量達到B時, 原本我們可以重新開辟一段空間 放多余的點, 但是我不放入, 舍棄它。

假設點集P有n個點, M與B有如下關系：

是內存利用率。對查詢q的近鄰點時，我們要搜索所有哈希表至少 個點。因此磁盤的訪問是有上界的，上界便是l。 我們現在來分析下l，k的取值問題。首先我們列出兩個事件。 假如我們的哈希函數是滿足 性的。

P1：如果存在一個點 至少存在一個 滿足

P2： q通過 哈希到的塊中僅包含 以外的點的塊數小于cl。

定理 則P1,P2可以保證至少 的概率。其中

總結:

以上便是LSH的基本理論, 我總結一下。對于LSH算的主要流程分為兩個部分，一個是建立哈希結構，另一個便是檢 索。在知道具體度量方式的情況下，利用該度量下的LSH哈希函數，建立哈希結構。首先選取合適的k，l參數，然后建立 l張哈希表，每張哈希表用k個獨立抽取的基本哈希函數聯合判斷，建立哈希表的內部結構。哈希值相同的點放在一起，哈 希值不同的放在不同的地方。至于查詢，當q成為我們的查詢點, 首先計算q在每張哈希表的哈希值，取出對應哈希值的哈 希桶內所有點，與q做距離計算。找到滿足我們條件的點作為查詢結果。

六、局部敏感哈希規整

說到Hash，大家都很熟悉，是一種典型的Key-Value結構，最常見的算法莫過于MD5。其設計思想是使Key集合中的任意關鍵字能夠盡可能均勻的變換到Value空間中，不同的Key對應不同的Value，即使Key值只有輕微變化，Value值也會發生很大地變化。這樣特性可以作為文件的唯一標識，在做下載校驗時我們就使用了這個特性。但是有沒有這樣一種Hash呢？他能夠使相似Key值計算出的Value值相同或在某種度量下相近呢？甚至得到的Value值能夠保留原始文件的信息，這樣相同或相近的文件能夠以Hash的方式被快速檢索出來，或用作快速的相似性比對。位置敏感哈希（Local Sensitive Hashing, LSH）正好滿足了這種需求，在大規模數據處理中應用非常廣泛，例如已下場景：

1. 近似檢測（Near-duplicate detection）：通常運用在網頁去重方面。在搜索中往往會遇到內容相似的重復頁面，它們中大多是由于網站之間轉載造成的。可以對頁面計算LSH，通過查找相等或相近的LSH值找到Near-duplicate。
2. 圖像、音頻檢索：通常圖像、音頻文件都比較大，并且比較起來相對麻煩，我們可以事先對其計算LSH，用作信息指紋，這樣可以給定一個文件的LSH值，快速找到與其相等或相近的圖像和文件。
3. 聚類：將LSH值作為樣本特征，將相同或相近的LSH值的樣本合并在一起作為一個類別。

LSH(Location Sensitive Hash),即位置敏感哈希函數。與一般哈希函數不同的是位置敏感性，也就是散列前的相似點經過哈希之后，也能夠在一定程度上相似，并且具有一定的概率保證。 LSH的形式化定義可參見前面部分。

如下圖，空間上的點經位置敏感哈希函數散列之后，對于q，其rNN有可能散列到同一個桶（如第一個桶）,即散列到第一個桶的概率較大，會大于某一個概率閾值p1;而其(1+emxilong)rNN之外的對象則不太可能散列到第一個桶，即散列到第一個桶的概率很小，會小于某個閾值p2.

LSH的作用:

◆高維下近似查詢 相似性檢索在各種領域特別是在視頻、音頻、圖像、文本等含有豐富特征信息領域中的應用變得越來越重要。豐富的特征信息一般用高維向量表示，由此相似性檢索一般通過K近鄰或近似近鄰查詢來實現。一個理想的相似性檢索一般需要滿足以下四個條件[4]：

1. 高準確性。即返回的結果和線性查找的結果接近。
2. 空間復雜度低。即占用內存空間少。理想狀態下，空間復雜度隨數據集呈線性增長，但不會遠大于數據集的大小。
3. 時間復雜度低。檢索的時間復雜度最好為O（1）或O（logN)。
4. 支持高維度。能夠較靈活地支持高維數據的檢索。

此外, 檢索模式應能快速地構造索引數據結構, 并且可以完成插入、刪除等操作。

傳統主要方法是基于空間劃分的算法——tree類似算法，如R-tree，Kd-tree，SR-tree。這種算法返回的結果是精確的，但是這種算法在高維數據集上的時間效率并不高。實驗[5]指出維度高于10之后，基于空間劃分的算法時間復雜度反而不如線性查找。LSH方法能夠在保證一定程度上的準確性的前提下，時間和空間復雜度得到降低，并且能夠很好地支持高維數據的檢索。

現有的很多檢索算法并不能同時滿足以上的所有性質。以前主要采用基于空間劃分的算法–tree 算法, 例如: R-tree[6], Kd-tree[7],SR-tree。這些算法返回的結果都是精確的, 然而它們在高維數據集上時間效率并不高。文獻[5]的試驗指出在維度高于10之后, 基于空間劃分的算法的時間復雜度反而不如線性查找。

1998年, P.Indy和R.Motwani提出了LSH算法的理論基礎。1999 年Gionis A,P.Indy和R.Motwani使用哈希的辦法解決高維數據的快速檢索問題, 這也是Basic LSH算法的雛形。2004 年, P.Indy 提出了LSH 算法在歐幾里德空間(2-范數)下的具體解決辦法。同年, 在自然語言處理領域中, Deepak Ravichandran使用二進制向量和快速檢索算法改進了Basic LSH 算法, 并將其應用到大規模的名詞聚類中, 但改進后的算法時間效率并不理想。

2005 年, Mayank Bawa, Tyson Condie 和Prasanna Ganesan 提出了LSH Forest算法, 該算法使用樹形結構代替哈希表, 具有自我校正參數的能力。2006 年, R. Panigrahy用產生近鄰查詢點的方法提高LSH 空間效率, 但卻降低了算法的空間效率。2007年,William Josephson 和Zhe Wang使用多重探測的方法改進了歐幾里德空間(2-范數)下的LSH 算法, 同時提高了算法的時間效率和空間效率。

◆分類和聚類 根據LSH的特性，即可將相近（相似）的對象散列到同一個桶之中，則可以對圖像、音視頻、文本等豐富的高維數據進行分類或聚類。

◆數據壓縮。如廣泛地應用于信號處理及數據壓縮等領域的Vector Quantization量子化技術。 總而言之，哪兒需要近似kNN查詢，哪兒都能用上LSH.

進入LSH實現部分，將按LSH的發展順序介紹幾種應用廣泛的LSH算法。

1, 基于Stable Distribution投影方法 2, 基于隨機超平面投影的方法; 3, SimHash; 4, Kernel LSH

1, 基于Stable Distribution投影方法

2008年IEEE Signal Process上有一篇文章Locality-Sensitive Hashing for Finding Nearest Neighbors是一篇較為容易理解的基于Stable Dsitrubution的投影方法的Tutorial, 有興趣的可以看一下. 其思想在于高維空間中相近的物體，投影（降維）后也相近。基于Stable Distribution的投影LSH，就是產生滿足Stable Distribution的分布進行投影，最后將量化后的投影值作為value輸出. 更詳細的介紹在Alexandr Andoni維護的LSH主頁中，理論看起來比較復雜，不過這就是LSH方法的鼻祖啦，缺點顯而易見：你需要同時選擇兩個參數，并且量化后的哈希值是一個整數而不是bit形式的0和1，你還需要再變換一次。如果要應用到實際中，簡直讓你抓狂。

2, 基于隨機超平面投影的方法

大神Charikar改進了上種方法的缺點，提出了一種隨機超平面投影LSH. 這種方法的最大優點在于：

1),不需要參數設定

2),是兩個向量間的cosine距離，非常適合于文本度量

3),計算后的value值是比特形式的1和0，免去了前面算法的再次變化

3, SimHash

前面介紹的LSH算法，都需要首先將樣本特征映射為特征向量的形式，使得我們需要額外存儲一個映射字典，難免麻煩，大神Charikar又提出了大名鼎鼎的SimHash算法，在滿足隨機超平面投影LSH特性的同時避免了額外的映射開銷，非常適合于token形式的特征。 首先來看SimHash的計算過程： a，將一個f維的向量V初始化為0；f位的二進制數S初始化為0； b，對每一個特征：用傳統的hash算法（究竟是哪種算法并不重要，只要均勻就可以）對該特征產生一個f位的簽名b。對i=1到f： 如果b的第i位為1，則V的第i個元素加上該特征的權重； 否則，V的第i個元素減去該特征的權重。 c，如果V的第i個元素大于0，則S的第i位為1，否則為0； d，輸出S作為簽名。

大家引用SimHash的文章通常都標為2002年這篇Similarity Estimation Techniques from Rounding Algorithms, 而這篇文章里實際是討論了兩種metric的hash. 作者猜測, SimHash應該是隨機超平面投影LSH，而不是后來的token形式的SimHash. 其實只是概念的歸屬問題, 已經無關緊要了

我想很多人引用上篇文章也有部分原因是因為07年google研究院的Gurmeet Singh Manku在WWW上的這篇paper: Detecting Near-Duplicates for Web Crawling, 文中給出了simhash在網絡爬蟲去重工作的應用，并利用編碼的重排列方式解決快速Hamming距離搜索問題.

4, Kernel LSH

前面講了三種LSH算法，基本可以解決一般情況下的問題，不過對于某些特定情況還是不行：比如輸入的key值不是均勻分布在整個空間中，可能只是集中在某個小區域內，需要在這個區域內放大距離尺度。又比如我們采用直方圖作為特征，往往會dense一些，向量只分布在大于0的區域中，不適合采用cosine距離，而stable Distribution投影方法參數太過敏感，實際設計起來較為困難和易錯，不免讓我們聯想，是否有RBF kernel這樣的東西能夠方便的縮放距離尺度呢？或是我們想得到別的相似度表示方式。這里就需要更加fancy的kernel LSH了。