當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

局部敏感哈希-Locality Sensitive Hashing

發布時間：2025/3/21 编程问答 37 豆豆

生活随笔收集整理的這篇文章主要介紹了局部敏感哈希-Locality Sensitive Hashing 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

局部敏感哈希

轉載請注明http://blog.csdn.net/stdcoutzyx/article/details/44456679?
在檢索技術中，索引一直需要研究的核心技術。當下，索引技術主要分為三類：基于樹的索引技術（tree-based index）、基于哈希的索引技術（hashing-based index）與基于詞的倒排索引（visual words based inverted index）[1]。本文主要對哈希索引技術進行介紹。

哈希技術概述

在檢索中，需要解決的問題是給定一個查詢樣本query，返回與此query相似的樣本，線性搜索耗時耗力，不能承擔此等重任，要想快速找到結果，必須有一種方法可以將搜索空間控制到一個可以接受的范圍，哈希在檢索中就是承擔這樣的任務，因而，這些哈希方法一般都是局部敏感（Locality-sensitive）的，即樣本越相似，經過哈希后的值越有可能一樣。所以，本文中介紹的技術都是局部敏感哈希（Locality Sensitive Hashing，LSH），與hashmap、hashtable等數據結構中的哈希函數有所不同。

哈希技術分類

圖 1 LSH分層法使用

對于哈希技術，可以按照不同的維度對齊進行劃分。

按照其在檢索技術中的應用方法來劃分，可以分為分層法和哈希碼法：

分層法即為在數據查詢過程中使用哈希技術在中間添加一層，將數據劃分到桶中；在查詢時，先對query計算桶標號，找到與query處于同一個桶的所有樣本，然后按照樣本之間的相似度計算方法（比如歐氏距離、余弦距離等）使用原始數據計算相似度，按照相似度的順序返回結果，在該方法中，通常是一組或一個哈希函數形成一個表，表內有若干個桶，可以使用多個表來提高查詢的準確率，但通常這是以時間為代價的。分層法的示意圖如圖1所示。在圖1中，H1、H2等代表哈希表，g1、g2等代表哈希映射函數。

分層法的代表算法為E2LSH[2]。
哈希碼法則是使用哈希碼來代替原始數據進行存儲，在分層法中，原始數據仍然需要以在第二層被用來計算相似度，而哈希碼法不需要，它使用LSH函數直接將原始數據轉換為哈希碼，在計算相似度的時候使用hamming距離來衡量。轉換為哈希碼之后的相似度計算非常之快，比如，可以使用64bit整數來存儲哈希碼，計算相似度只要使用同或操作就可以得到，唰唰唰，非常之快，忍不住用擬聲詞來表達我對這種速度的難言之喜，還望各位讀者海涵。

哈希碼法的代表算法有很多，比如KLSH[3]、Semantic Hashing[4]、KSH[5]等。

以我看來，兩者的區別在于如下幾點：

在對哈希函數的要求上，哈希碼方法對哈希函數的要求更高，因為在分層法中，即便哈希沒有計算的精確，后面還有原始數據直接計算相似度來保底，得到的結果總不會太差，而哈希碼沒有后備保底的，勝則勝敗則敗。
在查詢的時間復雜度上，分層法的時間復雜度主要在找到桶后的樣本原始數據之間的相似度計算，而哈希碼則主要在query的哈希碼與所有樣本的哈希碼之間的hamming距離的相似計算。哈希碼法沒有太多其他的需要，但分層法中的各個桶之間相對較均衡方能使復雜度降到最低。按照我的經驗，在100W的5000維數據中，KSH比E2LSH要快一個數量級。
在哈希函數的使用上，兩者使用的哈希函數往往可以互通，E2LSH使用的p-stable LSH函數可以用到哈希碼方法上，而KSH等哈希方法也可以用到分層法上去。?
上述的區別分析是我自己分析的，如果有其他意見歡迎討論。

按照哈希函數來劃分，可以分為無監督和有監督兩種：

無監督，哈希函數是基于某種概率理論的，可以達到局部敏感效果。如E2LSH等。
有監督，哈希函數是從數據中學習出來的，如KSH、Semantic Hashing等。

一般來說，有監督算法比無監督算法更加精確，因而也更常用于哈希碼法中。?
本文中，主要對無監督的哈希算法進行介紹。

Origin LSH

最原始的LSH算法是1999年提出來的[6]。在本文中稱之為Origin LSH。

Embedding

Origin LSH在哈希之前，首先要先將數據從L1準則下的歐幾里得空間嵌入到Hamming空間。在做此embedding時，有一個假設就是原始點在L1準則下的效果與在L2準則下的效果相差不大，即歐氏距離和曼哈頓距離的差別不大，因為L2準則下的歐幾里得空間沒有直接的方法嵌入到hamming空間。

Embedding算法如下：

找到所有點的所有坐標值中的最大值C；
對于一個點P來說，P=(x₁,x₂,…,x_d)，d是數據的維度；
將每一維x_i轉換為一個長度為C的0/1序列，其中序列的前x_i個值為1，剩余的為0.
然后將d個長度為C的序列連接起來，形成一個長度為Cd的序列.

這就是embedding方法。注意，在實際運算過程中，通過一些策略可以無需將embedding值預先計算出來。

Algorithm of Origin LSH

在Origin LSH中，每個哈希函數的定義如下：

即輸入是一個01序列，輸出是該序列中的某一位上的值。于是，hash函數簇內就有Cd個函數。

在將數據映射到桶中時，選擇k個上述哈希函數，組成一個哈希映射，如下：

再細化，LSH的算法步驟如下：

從[0,Cd]內取L個數，形成集合G，即組成了一個桶哈希函數g。
對于一個向量P，得到一個L維哈希值，即P_|G，其中L維中的每一維都對應一個哈希函數h。
由于直接以上步中得到的L維哈希值做桶標號不方便，因而再進行第二步哈希，第二步哈希就是普通的哈希，將一個向量映射成一個實數。

其中，a是從[0,M-1]中隨機抽選的數字。

這樣，就把一個向量映射到一個桶中了。

LSH based on p-stable distribution

該方法由[2]提出，E2LSH[7]是它的一種實現。

p-stable分布

定義：對于一個實數集R上的分布D，如果存在P>=0，對任何n個實數v1,…,vn和n個滿足D分布的變量X1,…,Xn，隨機變量Σ_iv_iX_i和(∑_i|v_i|^p)^(1/p)X有相同的分布，其中X是服從D分布的一個隨機變量，則稱D為一個p穩定分布。

對任何p∈(0,2]存在穩定分布。P=1時是柯西分布；p=2時是高斯分布。

當p=2時，兩個向量v1和v2的映射距離a·v1-a·v2和||v1-v2||_pX的分布是一樣的，此時對應的距離計算方式為歐式距離。

利用p-stable分布可以有效的近似高維特征向量，并在保證度量距離的同時，對高維特征向量進行降維，其關鍵思想是，產生一個d維的隨機向量a，隨機向量a中的每一維隨機的、獨立的從p-stable分布中產生。對于一個d維的特征向量v，如定義，隨機變量a·v具有和(∑_i|v_i|^p)^(1/p)X一樣的分布，因此可以用a·v表示向量v來估算||v||_p。

E2LSH

基于p-stable分布，并以‘哈希技術分類’中的分層法為使用方法，就產生了E2LSH算法。

E2LSH中的哈希函數定義如下：

其中，v為d維原始數據，a為隨機變量，由正態分布產生; w為寬度值，因為a?v+b得到的是一個實數，如果不加以處理，那么起不到桶的效果，w是E2LSH中最重要的參數，調得過大，數據就被劃分到一個桶中去了，過小就起不到局部敏感的效果。b使用均勻分布隨機產生，均勻分布的范圍在[0,w]。

與Origin LSH類似，選取k個上述的哈希函數，組成一個哈希映射，效果如圖2所示：

圖 2 E2LSH映射

但是這樣，得到的結果是(N₁,N₂,…,N_k)，其中N₁,N₂,…,N_k在整數域而不是只有0,1兩個值，這樣的k元組就代表一個桶。但將k元組直接當做桶標號存入哈希表，占用內存且不便于查找，為了方便存儲，設計者又將其分層，使用數組+鏈表的方式，如圖3所示：

圖 3 E2LSH為存儲桶標號而產生的數組+鏈表二層結構

對每個形式為k元組的桶標號，使用如下h1函數和h2函數計算得到兩個值，其中h1的結果是數組中的位置，數組的大小也相當于哈希表的大小，h2的結果值作為k元組的代表，鏈接到對應數組的h1位置上的鏈表中。在下面的公式中,r^’為[0,prime-1]中依據均勻分布隨機產生。

經過上述組織后，查詢過程如下：

對于查詢點query，
使用k個哈希函數計算桶標號的k元組；
對k元組計算h1和h2值，
獲取哈希表的h1位置的鏈表，
在鏈表中查找h2值，
獲取h2值位置上存儲的樣本
Query與上述樣本計算精確的相似度，并排序
按照順序返回結果。

E2LSH方法存在兩方面的不足[8]：首先是典型的基于概率模型生成索引編碼的結果并不穩定。雖然編碼位數增加，但是查詢準確率的提高確十分緩慢；其次是需要大量的存儲空間，不適合于大規模數據的索引。E2LSH方法的目標是保證查詢結果的準確率和查全率，并不關注索引結構需要的存儲空間的大小。E2LSH使用多個索引空間以及多次哈希表查詢，生成的索引文件的大小是原始數據大小的數十倍甚至數百倍。

Hashcode of p-stable distribution

E2LSH可以說是分層法基于p-stable distribution的應用。另一種當然是轉換成hashcode，則定義哈希函數如下：

其中，a和v都是d維向量，a由正態分布產生。同上，選擇k個上述的哈希函數，得到一個k位的hamming碼，按照”哈希技術分類”中描述的技術即可使用該算法。

Reference

[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.

[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

總結

以上是生活随笔為你收集整理的局部敏感哈希-Locality Sensitive Hashing的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。