最近發(fā)郵件討論Semantic Hashing的同學(xué)和同事很多，推薦李老師的文獻(xiàn)列表供大家參閱：http://cs.nju.edu.cn/lwj/L2H.html

說到Hash，大家都很熟悉，是一種典型的Key-Value結(jié)構(gòu)，最常見的算法莫過于MD5。其設(shè)計思想是使Key集合中的任意關(guān)鍵字能夠盡可能均勻的變換到Value空間中，不同的Key對應(yīng)不同的Value，即使Key值只有輕微變化，Value值也會發(fā)生很大地變化。這樣特性可以作為文件的唯一標(biāo)識，在做下載校驗時我們就使用了這個特性。但是有沒有這樣一種Hash呢？他能夠使相似Key值計算出的Value值相同或在某種度量下相近呢？甚至得到的Value值能夠保留原始文件的信息，這樣相同或相近的文件能夠以Hash的方式被快速檢索出來，或用作快速的相似性比對。位置敏感哈希（Local Sensitive Hashing, LSH）正好滿足了這種需求，在大規(guī)模數(shù)據(jù)處理中應(yīng)用非常廣泛，例如已下場景[1]：
1. 近似檢測（Near-duplicate detection）：通常運用在網(wǎng)頁去重方面。在搜索中往往會遇到內(nèi)容相似的重復(fù)頁面，它們中大多是由于網(wǎng)站之間轉(zhuǎn)載造成的。可以對頁面計算LSH，通過查找相等或相近的LSH值找到Near-duplicate。
2. 圖像、音頻檢索：通常圖像、音頻文件都比較大，并且比較起來相對麻煩，我們可以事先對其計算LSH，用作信息指紋，這樣可以給定一個文件的LSH值，快速找到與其相等或相近的圖像和文件。
3. 聚類：將LSH值作為樣本特征，將相同或相近的LSH值的樣本合并在一起作為一個類別。
LSH(Location Sensitive Hash),即位置敏感哈希函數(shù)。與一般哈希函數(shù)不同的是位置敏感性，也就是散列前的相似點經(jīng)過哈希之后，也能夠在一定程度上相似，并且具有一定的概率保證[3]。
LSH的形式化定義:
對于任意q,p屬于S，若從集合S到U的函數(shù)族H={h1,h2…h(huán)n}對距離函數(shù)D(q,p)，如歐式距離、曼哈頓距離等等，滿足條件：
若D(p,q)≤rD(p,q)≤r, 且Pro[h(p)=h(q)]≥p1Pro[h(p)=h(q)]≥p1
若D(p,q)>r(1+ε)D(p,q)>r(1+ε), 且Pro[h(p)=h(q)]≤p2Pro[h(p)=h(q)]≤p2
則稱D(p,q)是位置敏感的。
如下圖，空間上的點經(jīng)位置敏感哈希函數(shù)散列之后，對于q，其rNN有可能散列到同一個桶（如第一個桶）,即散列到第一個桶的概率較大，會大于某一個概率閾值p1;而其(1+emxilong)rNN之外的對象則不太可能散列到第一個桶，即散列到第一個桶的概率很小，會小于某個閾值p2.

LSH的作用:
◆高維下近似查詢
相似性檢索在各種領(lǐng)域特別是在視頻、音頻、圖像、文本等含有豐富特征信息領(lǐng)域中的應(yīng)用變得越來越重要。豐富的特征信息一般用高維向量表示，由此相似性檢索一般通過K近鄰或近似近鄰查詢來實現(xiàn)。一個理想的相似性檢索一般需要滿足以下四個條件[4]：
1. 高準(zhǔn)確性。即返回的結(jié)果和線性查找的結(jié)果接近。
2. 空間復(fù)雜度低。即占用內(nèi)存空間少。理想狀態(tài)下，空間復(fù)雜度隨數(shù)據(jù)集呈線性增長，但不會遠(yuǎn)大于數(shù)據(jù)集的大小。
3. 時間復(fù)雜度低。檢索的時間復(fù)雜度最好為O（1）或O（logN)。
4. 支持高維度。能夠較靈活地支持高維數(shù)據(jù)的檢索。
此外, 檢索模式應(yīng)能快速地構(gòu)造索引數(shù)據(jù)結(jié)構(gòu), 并且可以完成插入、刪除等操作。

傳統(tǒng)主要方法是基于空間劃分的算法——tree類似算法，如R-tree，Kd-tree，SR-tree。這種算法返回的結(jié)果是精確的，但是這種算法在高維數(shù)據(jù)集上的時間效率并不高。實驗[5]指出維度高于10之后，基于空間劃分的算法時間復(fù)雜度反而不如線性查找。LSH方法能夠在保證一定程度上的準(zhǔn)確性的前提下，時間和空間復(fù)雜度得到降低，并且能夠很好地支持高維數(shù)據(jù)的檢索。
現(xiàn)有的很多檢索算法并不能同時滿足以上的所有性質(zhì)。
以前主要采用基于空間劃分的算法–tree 算法, 例如: R-tree[6], Kd-tree[7],SR-tree。這些算法返回的結(jié)果都是精確的, 然而它們在高維數(shù)據(jù)集上時間效率并不高。文獻(xiàn)[5]的試驗指出在維度高于10之后, 基于空間劃分的算法的時間復(fù)雜度反而不如線性查找。
1998年, P.Indy和R.Motwani提出了LSH算法的理論基礎(chǔ)。1999 年Gionis A,P.Indy和R.Motwani使用哈希的辦法解決高維數(shù)據(jù)的快速檢索問題, 這也是Basic LSH算法的雛形。2004 年, P.Indy 提出了LSH 算法在歐幾里德空間(2-范數(shù))下的具體解決辦法。同年, 在自然語言處理領(lǐng)域中, Deepak Ravichandran使用二進(jìn)制向量和快速檢索算法改進(jìn)了Basic LSH 算法[8] , 并將其應(yīng)用到大規(guī)模的名詞聚類中, 但改進(jìn)后的算法時間效率并不理想。2005 年, Mayank Bawa, Tyson Condie 和Prasanna Ganesan 提出了LSH Forest算法[9], 該算法使用樹形結(jié)構(gòu)代替哈希表, 具有自我校正參
數(shù)的能力。2006 年, R. Panigrahy[10]用產(chǎn)生近鄰查詢點的方法提高LSH 空間效率, 但卻降低了算法的空間效率。2007年,William Josephson 和Zhe Wang使用多重探測的方法改進(jìn)了歐幾里德空間(2-范數(shù))下的LSH 算法, 同時提高了算法的時間效率和空間效率。

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

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

維基百科對LSH的解釋給出了幾種不同的定義形式。不過還是大牛Moses Charikar的定義相對簡單明了：對于兩個物體(可以理解為兩個文件、兩個向量等)，LSH生成的value值的每一bit位相等的概率等于這兩個物體的相似度,?這里不需要明確是什么度量方式(由此引申出了各種各樣的LSH算法), 只要滿足上式的就叫做LSH.?顯然這種定義天生就使LSH在hash后能夠保留原始樣本差異程度的信息，相近的物體的漢明距離就相近。介紹LSH，先從起源開始，我們先拿最初為LSH做出貢獻(xiàn)的三個大牛開始說起。

【1】. 1998年P(guān)iotr Indyk在Stanford讀PHD時與導(dǎo)師Rajeev Motwani提出一種hash方法:?Locality Sensitive Hashing [Indyk-Motwani'98].?Approximate Nearest Neighbors: Towards Removing the?Curse of Dimensionality?被引用1627次, 作者Piotr Indyk2000年從Stanford畢業(yè)后就職于MIT, 現(xiàn)在是MIT的教授, 主頁中有關(guān)于LSH的相關(guān)代碼及研究介紹。LSH的相關(guān)代碼工作主要由他的學(xué)生Alexandr Andoni編寫并維護(hù).
[文章總結(jié)]: 首先NN問題應(yīng)用于很多場合，常常是設(shè)計相似搜索，例如：data compression; databases and data mining; information retrieval; image and video database; machine learning; pattern recognition; and, statistics and data analysis. 因為之前過去KNN總是通過一種brute-force algorithm對所有樣本點進(jìn)行逐一匹配. 所以人們開始探索一種approximate nearest neighbors problem. 這篇文章的目的主要是為了Removing the Curse of Dimensionality而提出的一種Approximate Nearest Neighbors Algorithms,并命名為locality-sensitive hashing. 應(yīng)用場景: information retrieval, pattern recognition, dynamic closest-pairs, and fast clustering algorithms. LSH的key idea is to use hash functions such that the probability of collision is much higher for objects that are close to each other than for those that are far apart. and they prove that existence of such functions for any domain. 并且給出了兩種functions, one for a Hamming space and the other for a family of subsets of a set under the resemblance measure used by?Broder?et al. to?cluster web documents.
1. P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality[A]. In STOC ’98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, New York, USA: ACM Press, 1998:604–613.

【2】. 1999年P(guān)iotr Indyk的同門師弟Aristides Gionis對之前的LSH雛形算法進(jìn)行完善發(fā)表了Similarity Search in High Dimensions via Hashing這篇文章目前也被引用了1250次, 而且在Alexandr Andoni維護(hù)的LSH主頁上也說明最初的Original LSH algorithm (1999)指向的是這篇文章. 作者Aristides Gionis現(xiàn)在在芬蘭Aalto University任教.
[文章總結(jié)]:This paper presents locality-sensitive hashing(LSH). This technique was originally introduced by Indyk and Motwani for the purposes of devising main memory algorithms for the?εε-NNS problem. Here this paper gives an improved version of their algorithm. The new algorithm is in many respects more natural than the earlier one: it does not require the hash buckets to store only one point; it has better running time guarantees; and, the analysis is generalized to the case of secondary memory.
2.Gionis A, Indyk P, Motwani R. Similarity search in high dimension s via hashing [C] Proceedings of the 25th International Conference on Very Large Data Bases (VLDB). 1999

【3】. 現(xiàn)在回到Alexandr Andoni維護(hù)的LSH主頁中來了解LSH的發(fā)展近況. 早期時候, 2005年,?Alexandr Andoni給出一篇Ann(Approximate Nearest Neighbor)?Introduction for LSH, 算是一篇普及型文章, 可翻來讀讀.作者是Greg Shakhnarovich, 之前在MIT讀的PHD, 現(xiàn)在在Toyota Technological Institute at Chicago任教.
[文章總結(jié)]:A naive algorithm for this problem is as follows: given a query q, compute the distance from q to each point in P, and report the point with the minimum distance. This linear scan approach has query time of Θ(dn). This is tolerable for small data sets, but is too ine?cient for large ones. The?“holy grail” of the research in the area is to design an algorithm for this problem that achieves sublinear (or even logarithmic) query time.The nearest-neighbor problem has been extensively investigated in the ?eld of computational geometry. Unfortunately, as the dimension grows, the algorithms become less and less e?cient. The lack of success in removing the exponential dependence on the dimension led many researchers to conjecture that no e?cient solutions exist for this problem when the dimension is su?ciently large. At the same time, it raised the question: Is it possible to remove the exponential dependence on d, if we allow the answers to be approximate? The approximate nearest neighbor search problem is de?ned as follows: Given a set P of points in a d-dimensional space d, construct a data structure which given any query point q, reports any point within distance at most c times the distance from q to p, where p is the point in P closest to q.
[插曲:]介紹KNN的時候會順帶介紹一些KD-Tree相關(guān)的工作，關(guān)于KD-Tree相關(guān)知識可看一下這篇博文：從K近鄰算法、距離度量談到KD樹、SIFT+BBF算法。
進(jìn)入LSH實現(xiàn)部分，將按LSH的發(fā)展順序介紹幾種應(yīng)用廣泛的LSH算法。
1, 基于Stable Distribution投影方法
2, 基于隨機超平面投影的方法;
3, SimHash;
4, Kernel LSH

1, 基于Stable Distribution投影方法
2008年IEEE Signal Process上有一篇文章Locality-Sensitive Hashingfor Finding Nearest Neighbors是一篇較為容易理解的基于Stable Dsitrubution的投影方法的Tutorial, 有興趣的可以看一下. 其思想在于高維空間中相近的物體，投影（降維）后也相近。基于Stable Distribution的投影LSH，就是產(chǎn)生滿足Stable Distribution的分布進(jìn)行投影，最后將量化后的投影值作為value輸出.?更詳細(xì)的介紹在Alexandr Andoni維護(hù)的LSH主頁中，理論看起來比較復(fù)雜，不過這就是LSH方法的鼻祖啦，缺點顯而易見：你需要同時選擇兩個參數(shù)，并且量化后的哈希值是一個整數(shù)而不是bit形式的0和1，你還需要再變換一次。如果要應(yīng)用到實際中，簡直讓你抓狂。
2, 基于隨機超平面投影的方法
大神Charikar改進(jìn)了上種方法的缺點，提出了一種隨機超平面投影LSH.
這種方法的最大優(yōu)點在于：
1),不需要參數(shù)設(shè)定
2),是兩個向量間的cosine距離，非常適合于文本度量
3),計算后的value值是比特形式的1和0，免去了前面算法的再次變化
3, SimHash
前面介紹的LSH算法，都需要首先將樣本特征映射為特征向量的形式，使得我們需要額外存儲一個映射字典，難免麻煩，大神Charikar又提出了大名鼎鼎的SimHash算法，在滿足隨機超平面投影LSH特性的同時避免了額外的映射開銷，非常適合于token形式的特征。
首先來看SimHash的計算過程[2]：
a，將一個f維的向量V初始化為0；f位的二進(jìn)制數(shù)S初始化為0；
b，對每一個特征：用傳統(tǒng)的hash算法（究竟是哪種算法并不重要，只要均勻就可以）對該特征產(chǎn)生一個f位的簽名b。對i=1到f：
如果b的第i位為1，則V的第i個元素加上該特征的權(quán)重；
否則，V的第i個元素減去該特征的權(quán)重。
c，如果V的第i個元素大于0，則S的第i位為1，否則為0；
d，輸出S作為簽名。
大家引用SimHash的文章通常都標(biāo)為2002年這篇Similarity Estimation Techniques from Rounding Algorithms, 而這篇文章里實際是討論了兩種metric的hash. 參考[1]的作者猜測, SimHash應(yīng)該是隨機超平面投影LSH，而不是后來的token形式的SimHash. 其實只是概念的歸屬問題, 已經(jīng)無關(guān)緊要了, 我想很多人引用上篇文章也有部分原因是因為07年Google研究院的Gurmeet Singh Manku在WWW上的這篇paper:?Detecting Near-Duplicates for Web Crawling, 文中給出了simhash在網(wǎng)絡(luò)爬蟲去重工作的應(yīng)用，并利用編碼的重排列方式解決快速Hamming距離搜索問題.
這里插曲抱怨一下網(wǎng)絡(luò)爬蟲去重的一些抱怨，例如文獻(xiàn)[1]，標(biāo)題顯示是一篇轉(zhuǎn)發(fā)的文章，而且內(nèi)容中很多圖片已經(jīng)無法顯示，轉(zhuǎn)發(fā)作者卻沒有給出原文出處。或許是因為csdn的rank值高再加上爬蟲的去重工作，搜索引擎中竟搜不到原文！
4, Kernel LSH
前面講了三種LSH算法，基本可以解決一般情況下的問題，不過對于某些特定情況還是不行：比如輸入的key值不是均勻分布在整個空間中，可能只是集中在某個小區(qū)域內(nèi)，需要在這個區(qū)域內(nèi)放大距離尺度。又比如我們采用直方圖作為特征，往往會dense一些，向量只分布在大于0的區(qū)域中，不適合采用cosine距離，而stable Distribution投影方法參數(shù)太過敏感，實際設(shè)計起來較為困難和易錯，不免讓我們聯(lián)想，是否有RBF kernel這樣的東西能夠方便的縮放距離尺度呢？或是我們想得到別的相似度表示方式。這里就需要更加fancy的kernel LSH了。
我們觀察前面的幾種LSH，發(fā)現(xiàn)其形式都可以表示成內(nèi)積的形式，提到內(nèi)積自然會想到kernel方法，是不是LSH也能使用kernel呢？
Kernel LSH的工作可參看下面這三篇文章：
1). 2009年ICCV上的?Kernelized Locality-Sensitive Hashing for Scalable Image Search
2). 2009年NIPS上的Locality-Sensitive Binary Codes From Shift-Invariant Kernels[PPT]
3). 2007年NIPS上的Random Features for Large-Scale Kernel Machines
下面是文獻(xiàn)[1]作者的總結(jié): 這里介紹了四種LSH方法，最原始的Sable Distribution的投影LSH，滿足cosine距離的隨機超平面投影LSH，以及他的文本特征改進(jìn)SimHash，最后介紹了RBF kernel下的LSH，基本可以滿足我們的需要。當(dāng)然kernel LSH還會隨著kernel map技術(shù)的發(fā)展而發(fā)展，現(xiàn)在有了不錯的顯示映射方法，比如 Efficient Additive Kernels via Explicit Feature Maps，提供了一種有限維有損的顯示映射方法，但是值域并不是均勻分布的，需要額外小心。另外一些方法就是有監(jiān)督的或半監(jiān)督的，隨著應(yīng)用場景不同而改變，這兩年CVPR里有很多此類LSH方法的文章，看來還是比較受歡迎的。Spectral Hash用過一下，感覺效果不好，估計是因為距離度量不適合使用的樣本。其實LSH問題的關(guān)鍵是根據(jù)數(shù)據(jù)集和需要度量的相似度，選擇合適的manifold進(jìn)行投影，也算是manifold learning的一個思想吧。

這十年時間內(nèi)，大家在Hash上做了很多工作來完善Hash算法，恰巧在寫這份總結(jié)的時候(13年07月23日)上海交通大學(xué)Wu-Jun Li實驗室share了一份Learning to Hash的PPT. 這是2013年1月份的一個talk. 不過Wu-Jun Li關(guān)于Hash的工作還是值得參考的. 而且share了很多matlab代碼和data, 很贊.

====================分割線說明=========================
近期很多同學(xué)留言需要李老師的PPT，由于未經(jīng)李老師同意在網(wǎng)盤上進(jìn)行公開其內(nèi)容尚不確定是否合適，目前若有所需暫先發(fā)送郵件給您們，李老師目前在南大的官方主頁為：http://cs.nju.edu.cn/lwj/，留意到其主頁中也有Learning to Hash的鏈接地址，但不知何故貌似打不開，大家可以發(fā)郵件告知李老師更新其內(nèi)容。祝好！
====================分割線說明=========================

Hash函數(shù)學(xué)習(xí)的兩個階段:
1). Projection Stage(Dimension Reduction)映射階段(降維)
Projected with real-valued projection function;
Given a point?xx, each projected dimension?ii?will be associated with a real-value projection functionfi(x)fi(x)(e.g.?fi(x)=wTixfi(x)=wiTx).
2). Quantization Stage量化階段
Turn real into binary.

根據(jù)是否依賴于數(shù)據(jù)集又可分為兩類:
Data-Independent Methods
The hashing function family is defined independently of the training dataset:
Locality-sensitive hashing (LSH): (Gionis et al., 1999; Andoni and Indyk, 2008) and its extensions (Datar et al., 2004; Kulis and Grauman, 2009; Kulis et al., 2009).
SIKH: Shift invariant kernel hashing (SIKH) (Raginsky and Lazebnik, 2009).
Hashing function: random projections.

Data-Dependent Methods
Hashing functions are learned from a given training dataset.
Relatively short codes
依賴于數(shù)據(jù)的Hash方法又分為two categories:
a). Supervised methods
s(xi,xj)=1s(xi,xj)=1?or 0
b). Unsupervised methods

Unsupervised Methods有以下幾種:
No labels to denote the similarity (neighborhood) between points.
PCAH: principal component analysis.
ITQ: (Gong and Lazebnik, 2011) orthogonal rotation matrix to refine the initial projection matrix learned by PCA.
Supervised(semi-supervised)Methods有以下幾種:
Training dataset contains additional supervised information, (e.g. class labels or pairwise constraints).
SH: Spectral Hashing (SH) (Weiss et al., 2008) adopts the eigenfunctions computed from the data similarity graph.
SSH: Semi-Supervised Hashing (SSH) (Wang et al., 2010a,b) exploits both labeled data and unlabeled data for hash function learning.
MLH: Minimal loss hashing (MLH) (Norouzi and Fleet, 2011) based on the latent structural SVM framework.
AGH: Graph-based hashing (Liu et al., 2011).

現(xiàn)在大數(shù)據(jù)互聯(lián)網(wǎng)應(yīng)用中，如何能把Hash應(yīng)用到Web相似性搜索中(最近語義搜索和知識圖譜已經(jīng)成為各大搜索公司必爭之地).這篇博士論文《2011 基于LSH的Web數(shù)據(jù)相似性查詢研究》可以參考一下.
Web數(shù)據(jù)的特點:
a).海量性;
b).異構(gòu)性, 種類繁多
Web數(shù)據(jù)的異構(gòu)性和多樣化的應(yīng)用使得Web上的數(shù)據(jù)種類也呈現(xiàn)多樣化的特征。Web數(shù)據(jù)可分為3中1).非結(jié)構(gòu)化數(shù)據(jù)(Unstructured Data); 2).結(jié)構(gòu)化數(shù)據(jù)(Structured Data); 3). 多媒體數(shù)據(jù)(Multimedia Data). 例如, 非結(jié)構(gòu)化的數(shù)據(jù)比如Web頁面數(shù)據(jù), 字符串?dāng)?shù)據(jù)(String Data)等。帶結(jié)構(gòu)的數(shù)據(jù)包括半結(jié)構(gòu)化數(shù)據(jù)和結(jié)構(gòu)化數(shù)據(jù), 其中Web上廣泛使用的XML是半結(jié)構(gòu)化的. 而結(jié)構(gòu)化數(shù)據(jù)包括圖數(shù)據(jù)(Graph)和關(guān)系數(shù)據(jù)(Relational Data). 例如, 整個Web的結(jié)構(gòu)可以看作一張圖, 社會網(wǎng)絡(luò)結(jié)構(gòu)也可以使用圖進(jìn)行建模. 多媒體數(shù)據(jù)包括圖像數(shù)據(jù)(Image), 視頻數(shù)據(jù)(Video)和音頻數(shù)據(jù)(Audio).
c).帶有噪音
由于人們輸入的錯誤，誤差，簡寫，OCR識別以及多個數(shù)據(jù)源格式不一致等情況，導(dǎo)致了Web數(shù)據(jù)帶有大量的噪音，這給Web數(shù)據(jù)的查詢，數(shù)據(jù)集成等帶來了困難和挑戰(zhàn).

參考資料:
[1]:?http://blog.csdn.net/zhou191954/article/details/8494438
[2]:?http://gemantic.iteye.com/blog/1701101
[3]:?http://www.jiahenglu.net/NSFC/LSH.html
[4]:基于LSH的中文文本快速檢索 2009.
[5]:Weber R, Schek H, Blott S. A quantitative analysis and performance study for similarity search methods in high dimensional spaces Proc.of the 24th Intl.Conf.on Very Large Data Bases (VLDB).1998:194-205
[6] Guttman A. R-trees: A dynamic index structure for spatial searching[C] Proc. of ACM Conf. on Management of Data
(SIGMOD). 1984: 47-57
[7] Bentley J L. K-D trees for semi-dynamic point sets[C] Proc. of the 6th ACM Symposium on Computational Geometry (SCG). 1990: 187-197
[8] Ravichandran D, Pantel P, Hovy E. Randomized Algorithms and NLP: Using Locality Sensitive Hash Function for High S peed Noun Clustering[M]. Information Sciences Institute University of Southern California, 2004
[9] Bawa M, Condie T, Ganesan P. LSH Forest: SelfTuning[C] Indexes for Similarity Search International World Wide Web
Conference Proceedings of the 14th International Conference on World Wide Web. 2005
[10] “Entropy based Nearest Neighbor Search in High Dimensions”. SODA 2006

from:?http://jacoxu.com/?p=496

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。