淺析常用局部敏感哈希算法
上一年記錄的東西，整理下...
一.哈希檢索概述
LSH是Locality Sensitive Hashing的縮寫，也翻譯為局部敏感哈希，是一種通過設計滿足特殊性質即局部敏感的哈希函數，提高相似查詢效率的方法。 雖然從正式提出距今不過十余年，由于其局部敏感的特殊性質，以及在高維數據上相當于k-d樹等方法的優越性，LSH被廣泛地運用于各種檢索（包括并不僅限于文本、音頻、圖片、視頻、基因等）領域。
1.1 檢索分類
在檢索技術中，索引一直需要研究的核心技術。當下，索引技術主要分為三類：基于樹的索引技術（tree-based index）、基于哈希的索引技術（hashing-based index）與基于詞的倒排索引（visual words based inverted index）。
在檢索中，需要解決的問題是給定一個查詢樣本query，返回與此query相似的樣本，線性搜索耗時耗力，不能承擔此等重任，要想快速找到結 果，必須有一種方法可以將搜索空間控制到一個可以接受的范圍，哈希在檢索中就是承擔這樣的任務，因而，這些哈希方法一般都是局部敏感（Locality- sensitive）的，即樣本越相似，經過哈希后的值越有可能一樣。所以，本文中介紹的技術都是局部敏感哈希（Locality Sensitive Hashing，LSH），與hashmap、hashtable等數據結構中的哈希函數有所不同。
1.2 分層法與哈希碼法
對于哈希技術，可以按照不同的維度對齊進行劃分。
按照其在檢索技術中的應用方法來劃分，可以分為分層法和哈希碼法：
</div>1.分層法即為在數據查詢過程中使用哈希技術在中間添加一層，將數據劃分到桶中；在查詢時，先對query計算桶標號，找到與query處于同 一個桶的所有樣本，然后按照樣本之間的相似度計算方法（比如歐氏距離、余弦距離等）使用原始數據計算相似度，按照相似度的順序返回結果，在該方法中，通常 是一組或一個哈希函數形成一個表，表內有若干個桶，可以使用多個表來提高查詢的準確率，但通常這是以時間為代價的。
分層法的代表算法為E2LSH。
</div>2.哈希碼法則是使用哈希碼來代替原始數據進行存儲，在分層法中，原始數據仍然需要以在第二層被用來計算相似度，而哈希碼法不需要，它使用LSH 函數直接將原始數據轉換為哈希碼，在計算相似度的時候使用hamming距離來衡量。轉換為哈希碼之后的相似度計算非常之快，比如，可以使用64bit整 數來存儲哈希碼，計算相似度只要使用同或操作就可以得到，唰唰唰，非常之快，忍不住用擬聲詞來表達我對這種速度的難言之喜，還望各位讀者海涵。哈希碼法的 代表算法有很多，比如KLSH、Semantic Hashing、KSH等。
1.3 分層法與哈希碼法區別
以我看來，兩者的區別在于如下幾點：
1.在對哈希函數的要求上，哈希碼方法對哈希函數的要求更高，因為在分層法中，即便哈希沒有計算的精確，后面還有原始數據直接計算相似度來保底，得到的結果總不會太差，而哈希碼沒有后備保底的，勝則勝敗則敗。
2.在查詢的時間復雜度上，分層法的時間復雜度主要在找到桶后的樣本原始數據之間的相似度計算，而哈希碼則主要在query的哈希碼與所有樣本 的哈希碼之間的hamming距離的相似計算。哈希碼法沒有太多其他的需要，但分層法中的各個桶之間相對較均衡方能使復雜度降到最低。按照我的經驗，在 100W的5000維數據中，KSH比E2LSH要快一個數量級。
3.在哈希函數的使用上，兩者使用的哈希函數往往可以互通，E2LSH使用的p-stable LSH函數可以用到哈希碼方法上，而KSH等哈希方法也可以用到分層法上去。
4.按照哈希函數來劃分，可以分為無監督和有監督兩種：
</div>無監督，哈希函數是基于某種概率理論的，可以達到局部敏感效果。如E2LSH等。
有監督，哈希函數是從數據中學習出來的，如KSH、Semantic Hashing等。
一般來說，有監督算法比無監督算法更加精確，因而也更常用于哈希碼法中。
</div>二.常用LSH
2.1 原始LSH
Origin LSH在哈希之前，首先要先將數據從L1準則下的歐幾里得空間嵌入到Hamming空間。 在做此embedding時，有一個假設就是原始點在L1準則下的效果與在L2準則下的效果相差不大， 即歐氏距離和曼哈頓距離的差別不大，因為L2準則下的歐幾里得空間沒有直接的方法嵌入到hamming空間。
Embedding算法如下：
找到所有點的所有坐標值中的最大值C；
對于一個點P來說，P=(x1,x2,…,xd)，d是數據的維度；
將每一維xi轉換為一個長度為C的0/1序列，其中序列的前xi個值為1，剩余的為0.
然后將d個長度為C的序列連接起來，形成一個長度為Cd的序列.
這就是embedding方法。注意，在實際運算過程中，通過一些策略可以無需將embedding值預先計算出來。
</div>Algorithm of Origin LSH
在Origin LSH中，每個哈希函數的定義如下：
</div>
即輸入是一個01序列，輸出是該序列中的某一位上的值。于是，hash函數簇內就有Cd個函數（有Cd中可能，只不過選k個）。 在將數據映射到桶中時，選擇k個上述哈希函數，組成一個哈希映射，如下：
再細化，LSH的算法步驟如下：
從[0,Cd]內取L個數，形成集合G，即組成了一個桶哈希函數g。
對于一個向量P，得到一個L維哈希值，即P|G，其中L維中的每一維都對應一個哈希函數h。
由于直接以上步中得到的L維哈希值做桶標號不方便，因而再進行第二步哈希，
第二步哈希就是普通的哈希，將一個向量映射成一個實數。
</div>
這樣，就把一個向量映射到一個桶中了。
</div>筆者注：這種嵌入方法下，海明距離恰好是曼哈頓距離，那為什么不直接算曼哈頓距離呢？
其實是這樣的，先哈希，找到一些位，然后算海明距離，這不是曼哈頓距離，而且這樣的曼哈頓距離毫無意義。
2.1 LSH based on p-stable distribution
E2LSH 基于p-stable分布，并以‘哈希技術分類’中的分層法為使用方法，就產生了E2LSH算法。
E2LSH中的哈希函數定義如下：
其中，v為d維原始數據，a為隨機變量，由正態分布產生; w為寬度值，因為a?v+b得到的是一個實數，如果不加以處理，那么起不到桶的效果，w是E2LSH中最重要的參數，調得過大，數據就被劃分到一個桶中去 了，過小就起不到局部敏感的效果。b使用均勻分布隨機產生，均勻分布的范圍在[0,w]。
與Origin LSH類似，選取k個上述的哈希函數，組成一個哈希映射。
但是這樣，得到的結果是(N 1 ,N 2 ,…,N k )，其中N 1 ,N 2 ,…,N k 在整數域而不是只有0,1兩個值，這樣的k元組就代表一個桶。但將k元組直接當做桶標號存入哈希表，占用內存且不便于查找，為了方便存儲，設計者又將其分層，使用數組+鏈表的方式，如下圖
對每個形式為k元組的桶標號，使用如下h1函數和h2函數計算得到兩個值，其中h1的結果是數組中的位置，數組的大小也相當于哈希表的大小，h2的結果值作為k元組的代表，鏈接到對應數組的h1位置上的鏈表中。在下面的公式中,r ’ 為[0,prime-1]中依據均勻分布隨機產生。
經過上述組織后，查詢過程如下： - 對于查詢點query，
- 使用k個哈希函數計算桶標號的k元組；
- 對k元組計算h1和h2值，
- 獲取哈希表的h1位置的鏈表，
- 在鏈表中查找h2值，
- 獲取h2值位置上存儲的樣本
- Query與上述樣本計算精確的相似度，并排序
- 按照順序返回結果。 </ul>
E2LSH方法存在兩方面的不足：首先是典型的基于概率模型生成索引編碼的結果并不穩定。雖然編碼位數增加，但是查詢準確率的提高確十分緩慢；其 次是需要大量的存儲空間，不適合于大規模數據的索引。E2LSH方法的目標是保證查詢結果的準確率和查全率，并不關注索引結構需要的存儲空間的大小。 E2LSH使用多個索引空間以及多次哈希表查詢，生成的索引文件的大小是原始數據大小的數十倍甚至數百倍。
2.3 Hashcode of p-stable distribution
E2LSH可以說是分層法基于p-stable distribution的應用。另一種當然是轉換成hashcode，則定義哈希函數如下：
其中，a和v都是d維向量，a由正態分布產生。同上，選擇k個上述的哈希函數，得到一個k位的hamming碼，按照”哈希技術分類”中描述的技術即可使用該算法。
三.疑難點
1.疑問：歐式距離映射到海明空間？
不同的哈希函數可以選擇不同的a和b，選擇多個哈希函數進行映射增加了沖突概率？
</div>答：并不是增加沖突概率，說的就是與構建，是拉大p1^k和p2^k的差距，但是二者都變小了，或構建又同時拉大二者。
2.編輯距離
編輯距離d(x,y) = |x| + |y| - 2|LCS(x,y)|，其中LCS是longest common subsequence，最長公共子序列。?沒驗證過。
[1]. Ai L, Yu J, He Y, et al. High-dimensional indexing technologies for large scale content-based image retrieval: a review[J]. Journal of Zhejiang University SCIENCE C, 2013, 14(7): 505-520.
</div>[2]. Datar M, Immorlica N, Indyk P, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]//Proceedings of the twentieth annual symposium on Computational geometry. ACM, 2004: 253-262.
[3]. Kulis B, Grauman K. Kernelized locality-sensitive hashing[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2012, 34(6): 1092-1104.
[4]. Salakhutdinov R, Hinton G. Semantic hashing[J]. International Journal of Approximate Reasoning, 2009, 50(7): 969-978.
[5]. Liu W, Wang J, Ji R, et al. Supervised hashing with kernels[C]//Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012: 2074-2081.
[6]. Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing[C]//VLDB. 1999, 99: 518-529.
[7]. http://web.mit.edu/andoni/www/LSH/
[8]. http://blog.csdn.net/jasonding1354/article/details/38237353
[9]. http://dataunion.org/12912.html
</div> </div> 原文 http://www.cnblogs.com/hxsyl/p/4627477.html