位置敏感哈希(Locality Sensitive Hashing,LSH)是近似最近鄰搜索算法中最流行的一種，它有堅(jiān)實(shí)的理論依據(jù)并且在高維數(shù)據(jù)空間中表現(xiàn)優(yōu)異。由于網(wǎng)絡(luò)上相關(guān)知識(shí)的介紹比較單一，現(xiàn)就LSH的相關(guān)算法和技術(shù)做一介紹總結(jié)，希望能給感興趣的朋友提供便利，也希望有興趣的同道中人多交流、多指正。
LSH原理
最近鄰問題（nearest neighbor problem）可以定義如下：給定n個(gè)對(duì)象的集合并建立一個(gè)數(shù)據(jù)結(jié)構(gòu)，當(dāng)給定任意的要查詢對(duì)象時(shí)，該數(shù)據(jù)結(jié)構(gòu)返回針對(duì)查詢對(duì)象的最相似的數(shù)據(jù)集對(duì)象。LSH的基本思想是利用多個(gè)哈希函數(shù)把高維空間中的向量映射到低維空間，利用低維空間的編碼來表示高維向量。通過對(duì)向量對(duì)象進(jìn)行多次哈希映射，高維向量按照其分布以及自身的特性落入不同哈希表的不同桶中。在理想情況下可以認(rèn)為在高維空間中位置比較接近的向量對(duì)象有很大的概率最終落入同一個(gè)桶中，而距離比較遠(yuǎn)的對(duì)象則以很大的概率落入不同的桶中。因此在查詢的時(shí)候，通過對(duì)查詢向量進(jìn)行同樣的多次哈希操作，綜合多個(gè)哈希表中的查詢操作得到最終的結(jié)果。
使用哈希函數(shù)對(duì)整個(gè)數(shù)據(jù)集進(jìn)行過濾，得到可能滿足查詢條件的點(diǎn)再計(jì)算距離，這樣就避免了查詢點(diǎn)與數(shù)據(jù)集中所有點(diǎn)進(jìn)行距離計(jì)算，提高了查詢效率。該框架可以被稱為過濾-驗(yàn)證框架。
LSH函數(shù)族定義
為了形式化地描述LSH使用的哈希函數(shù)的性質(zhì)，現(xiàn)定義LSH函數(shù)族概念。
令S為d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)域，D為相似性度量函數(shù)，p和q為S中任意兩點(diǎn)。函數(shù)族H={h:S->U}被稱為(r1,r2,p1,p2)-敏感的，當(dāng)且僅當(dāng)：
通過使用LSH函數(shù)族中函數(shù)進(jìn)行哈希，可以保證距離近的點(diǎn)沖突的概率大于距離遠(yuǎn)的點(diǎn)沖突的概率。
通用的LSH算法框架
構(gòu)建LSH索引（哈希過程，Hashing）
定義一個(gè)函數(shù)族G={g:S->U}，其中g(shù)(v)=(h1(v),...,hk(v))，hi∈H，獨(dú)立隨機(jī)地從G中選擇L個(gè)哈希函數(shù)g1,...,gL。對(duì)于數(shù)據(jù)集中任意一點(diǎn)v，將其存儲(chǔ)到桶gi(v)中，i=1,...,L。
這種算法是完全索引算法（full-indexing algorithms）,它為每個(gè)可能的查詢點(diǎn)提供一個(gè)查詢表，因此，響應(yīng)一個(gè)查詢點(diǎn)，該算法只需在特殊構(gòu)造的哈希表中進(jìn)行一次查詢（look-up）。
LSH搜索算法
對(duì)于一個(gè)查詢點(diǎn)q以及給定的距離閾值r，搜索桶g1(q),...,gL(q)，取出其中的所有點(diǎn)v1,...,vn作為候選近似最近鄰點(diǎn)。對(duì)于任意的vj，如果D(q,vj)<=r，那么返回vj，其中D為相似性度量函數(shù)。
在創(chuàng)建LSH索引時(shí),選取的哈希函數(shù)是k個(gè)LSH函數(shù)的串聯(lián)函數(shù),這樣就相對(duì)拉大了距離近的點(diǎn)沖突的概率pn與距離遠(yuǎn)的點(diǎn)沖突的概率pf之間的差值,但這同時(shí)也使這兩個(gè)值一起減小了,于是需要同時(shí)使用L張哈希表來加大pn同時(shí)減小pf。通過這樣的構(gòu)造過程,在查詢時(shí),與查詢點(diǎn)q距離近的點(diǎn)就有很大的概率被取出作為候選近似最近鄰點(diǎn)并進(jìn)行最后的距離計(jì)算,而與查詢點(diǎn)q距離遠(yuǎn)的點(diǎn)被當(dāng)作候選近似最近鄰點(diǎn)的概率則很小,從而能夠在很短的時(shí)間內(nèi)完成查詢。
參考資料：
1、陳永健.基于內(nèi)容的大規(guī)模圖像檢索關(guān)鍵技術(shù)研究[D].華中科技大學(xué).2011
2、凌康.基于位置敏感哈希的相似性搜索技術(shù)研究[D].南京大學(xué).2012
