局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介绍
本文主要介绍一种用于海量高维数据的近似近期邻高速查找技术——局部敏感哈希(Locality-Sensitive Hashing, LSH)，内容包含了LSH的原理、LSH哈希函数集、以及LSH的一些參考资料。
一、局部敏感哈希LSH
在非常多应用领域中，我们面对和须要处理的数据往往是海量而且具有非常高的维度，如何高速地从海量的高维数据集合中找到与某个数据最相似（ 距离 近期）的一个数据或多个数据成为了一个难点和问题。假设是低维的小数据集，我们通过线性查找（Linear Search）就能够easy解决，但假设是对一个海量的高维数据集採用线性查找匹配的话，会非常耗时，因此，为了解决该问题，我们须要採用一些类似索引的技术来加快查找过程，通常这类技术称为近期邻查找（ Nearest Neighbor ,AN）， 比如K-d tree ；或近似近期邻查找（Approximate Nearest Neighbor, ANN），比如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH是ANN中的一类方法。
我们知道，通过建立Hash Table的方式我们可以得到O(1)的查找时间性能，当中关键在于选取一个hash function，将原始数据映射到相相应的桶内（bucket, hash bin），比如对数据求模：h = x mod w，w通常为一个素数。在对数据集进行hash 的过程中，会发生不同的数据被映射到了同一个桶中（即发生了冲突collision），这一般通过再次哈希将数据映射到其它空桶内来解决。这是普通Hash方法或者叫传统Hash方法，其与LSH有些不同之处。
局部敏感哈希示意图（from: Piotr Indyk）
LSH的基本思想是：将原始数据空间中的两个相邻数据点通过同样的映射或投影变换（projection）后，这两个数据点在新的数据空间中仍然相邻的概率非常大，而不相邻的数据点被映射到同一个桶的概率非常小。也就是说，假设我们对原始数据进行一些hash映射后，我们希望原先相邻的两个数据可以被hash到同样的桶内，具有同样的桶号。对原始数据集合中全部的数据都进行hash映射后，我们就得到了一个hash table，这些原始数据集被分散到了hash table的桶内，每一个桶会落入一些原始数据，属于同一个桶内的数据就有非常大可能是相邻的，当然也存在不相邻的数据被hash到了同一个桶内。因此，假设我们可以找到这样一些hash functions，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入同样的桶内的话，那么我们在该数据集合中进行近邻查找就变得easy了，我们仅仅须要将查询数据进行哈希映射得到其桶号，然后取出该桶号相应桶内的全部数据，再进行线性匹配就可以查找到与查询数据相邻的数据。换句话说，我们通过hash function映射变换操作，将原始数据集合分成了多个子集合，而每一个子集合中的数据间是相邻的且该子集合中的元素个数较小，因此将一个在超大集合内查找相邻元素的问题转化为了在一个非常小的集合内查找相邻元素的问题，显然计算量下降了非常多。
那具有如何特点的hash functions才可以使得原本相邻的两个数据点经过hash变换后会落入同样的桶内？这些hash function须要满足下面两个条件：
1）假设d(x,y) ≤ d1， 则h(x) = h(y)的概率至少为p1；
2）假设 d(x,y) ≥ d2， 则h(x) = h(y)的概率至多为p2；
当中d(x,y)表示x和y之间的距离，d1 < d2， h(x)和h(y)分别表示对x和y进行hash变换。
满足以上两个条件的hash functions称为(d1,d2,p1,p2)-sensitive。 而通过一个或 多个 (d1,d2,p1,p2)-sensitive 的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing。
使用LSH进行对海量数据建立索引（Hash table）并通过索引来进行近似近期邻查找的步骤例如以下：
1. 离线建立索引
（1）选取满足 (d1,d2,p1,p2)-sensitive 的LSH hash functions；
（2）依据对查找结果的准确率（即相邻的数据被查找到的概率）确定hash table的个数L，每一个table内的hash functions的个数K，以及跟LSH hash function自身有关的參数；
（3）将全部数据经过LSH hash function哈希到对应的桶内，构成了一个或多个hash table；
2. 在线查找
（1）将查询数据经过LSH hash function哈希得到对应的桶号；
（2）将桶号中相应的数据取出；（为了保证查找速度，通常仅仅须要取出前2L个数据就可以）；
（3）计算查询数据与这2L个数据之间的相似度或距离，返回近期邻的数据；
LSH在线查找时间由两个部分组成： （1）通过LSH hash functions计算hash值（桶号）的时间；（2）将查询数据与桶内的数据进行比較计算的时间。因此，LSH的查找时间至少是一个sublinear时间。为什么是“至少”？由于我们能够通过对桶内的属于建立索引来加快匹配速度，这时第（2）部分的耗时就从O(N)变成了O(logN)或O(1)（取决于採用的索引方法）。
LSH为我们提供了一种在海量的高维数据集中查找与查询数据点（query data point）近似最相邻的某个或某些数据点。须要注意的是，LSH并不能保证一定可以查找到与query data point最相邻的数据，而是降低须要匹配的数据点个数的同一时候保证查找到近期邻的数据点 的概率 非常大。
二、LSH的应用
LSH的应用场景非常多，凡是须要进行大量数据之间的相似度（或距离）计算的地方都能够使用LSH来加快查找匹配速度，以下列举一些应用：
（1）查找网络上的反复网页
互联网上因为各式各样的原因（比如转载、抄袭等）会存在非常多反复的网页，因此为了提高搜索引擎的检索质量或避免反复建立索引，须要查找出反复的网页，以便进行一些处理。其大致的步骤例如以下：将互联网的文档用一个集合或词袋向量来表征，然后通过一些hash运算来推断两篇文档之间的相似度，经常使用的有minhash+LSH、simhash。
（2）查找相似新闻网页或文章
与查找反复网页类似，能够通过hash的方法来推断两篇新闻网页或文章是否相似，仅仅只是在表达新闻网页或文章时利用了它们的特点来建立表征该文档的集合。
（3）图像检索
在图像检索领域，每张图片能够由一个或多个特征向量来表达，为了检索出与查询图片相似的图片集合，我们能够对图片数据库中的全部特征向量建立LSH索引，然后通过查找LSH索引来加快检索速度。眼下图像检索技术在近期几年得到了较大的发展，有兴趣的读者能够查看 基于内容的图像检索引擎 的相关介绍。
（4）音乐检索
对于一段音乐或音频信息，我们提取其音频指纹（Audio Fingerprint）来表征该音频片段，採用音频指纹的优点在于其可以保持对音频发生的一些改变的鲁棒性，比如压缩，不同的歌手录制的同一条歌曲等。为了高速检索到与查询音频或歌曲相似的歌曲，我们可以对数据库中的全部歌曲的音频指纹建立LSH索引，然后通过该索引来加快检索速度。
（5）指纹匹配
一个手指指纹通常由一些细节来表征，通过对照较两个手指指纹的细节的相似度就能够确定两个指纹是否同样或相似。类似于图片和音乐检索，我们能够对这些细节特征建立LSH索引，加快指纹的匹配速度。
三、LSH family
我们在第一节介绍了LSH的原理和LSH hash function须要满足的条件，回想一下：
满足下面两个条件的hash functions称为(d1,d2,p1,p2)-sensitive ：
1）假设d(x,y) ≤ d1， 则h(x) = h(y)的概率至少为p1；
2）假设 d(x,y) ≥ d2， 则h(x) = h(y)的概率至多为p2；
d(x,y)是x和y之间的一个距离度量（distance measure），须要说明的是，并非全部的距离度量都可以找到满足 locality-sensitive 的hash functions。
以下我们介绍一些满足不同距离度量方式下的 locality-sensitive 的hash functions：
1. Jaccard distance
Jaccard distance： (1 - Jaccard similarity)，而 Jaccard similarity = (A intersection B) / (A union B)， Jaccard similarity 通经常使用来推断两个集合的相似性。
Jaccard distance相应的 LSH hash function为：minhash，其是(d1,d2,1-d1,1-d2)-sensitive的。
2. Hamming distance
Hamming distance： 两个具有同样长度的向量中相应位置处值不同的次数。
Hamming distance 相应的 LSH hash function为：H(V) = 向量V的第i位上的值，其是(d1,d2,1-d1/d,1-d2/d)-sensitive
的。
3. Cosine distance
Cosine distance：cos(theta) = A · B / |A||B| ，经常使用来推断两个向量之间的夹角，夹角越小，表示它们越相似。
Cosine distance相应的LSH hash function为：H(V) = sign(V · R)，R是一个随机向量。V · R能够看做是将V向R上进行投影操作。其是(d1,d2,(180-d1)180,(180-d2)/180)-sensitive的。
理解：利用随机的超平面（random hyperplane）将原始数据空间进行划分，每个数据被投影后会落入超平面的某一側，经过多个随机的超平面划分后，原始空间被划分为了非常多cell，而位于每个cell内的数据被觉得具有非常大可能是相邻的（即原始数据之间的cosine distance非常小）。
4. normal Euclidean distance
Euclidean distance 是衡量 D维空间中 两个点之间的距离的一种距离度量方式 。
Euclidean distance相应的LSH hash function为：H(V) = |V·R + b| / a，R是一个随机向量，a是桶宽，b是一个在[0,a]之间均匀分布的随机变量。V·R能够看做是将V向R上进行投影操作。其是(a/2,2a,1/2,1/3)-sensitive的。
理解：将原始数据空间中的数据投影到一条随机的直线（random line）上，而且该直线由非常多长度等于a的线段组成，每个数据被投影后会落入该直线上的某一个线段上（相应的桶内），将全部数据都投影到直线上后，位于同一个线段内的数据将 被觉得具有非常大可能是相邻的（ 即原始数据之间的 Euclidean distance 非常小）。
四、增强LSH（Amplifying LSH ）
通过LSH hash functions我们可以得到一个或多个hash table，每一个桶内的数据之间是近邻的可能性非常大。我们希望原本相邻的数据经过LSH hash后，都可以落入到同样的桶内，而不相邻的数据经过LSH hash后，都可以落入到不同的桶中。假设相邻的数据被投影到了不同的桶内，我们称为false negtive；假设不相邻的数据被投影到了同样的桶内，我们称为false positive。因此，我们在使用LSH中，我们希望可以尽量减少false negtive rate和false positive rate。
通常，为了可以增强LSH，即使得false negtive rate 和/或 false positive rate减少，我们有两个途径来实现：1）在一个hash table内使用很多其它的LSH hash functio n；2）建立多个hash table。
以下介绍一些经常使用的增强LSH的方法：
1. 使用多个独立的hash table
每一个hash table由k个LSH hash function创建，每次选用k个 LSH hash function （同属于一个LSH function family）就得到了一个hash table，反复多次，就可以创建多个hash table。多个hash table的优点在于可以减少 false positive rate 。
2. AND 与操作
从同一个 LSH function family中挑选出k个LSH function，H(X) = H(Y)有且仅当这k个 Hi(X) = Hi(Y)都满足。也就是说仅仅有当两个数据的这k个hash值都相应同样时，才会被投影到同样的桶内，仅仅要有一个不满足就不会被投影到同一个桶内。
AND与操作可以使得找到近邻数据的p1概率保持高概率的同一时候减少p2概率，即减少了 false negtive rate 。
3. OR 或操作
从同一个 LSH function family中挑选出k个LSH function，H(X) = H(Y)有且仅当存在一个以上的 Hi(X) = Hi(Y)。也就是说仅仅要两个数据的这k个hash值中有一对以上同样时，就会被投影到同样的桶内，仅仅有当这k个hash值都不同样时才不被投影到同一个桶内。
OR或操作可以使得找到近邻数据的p1概率变的更大（越接近1）的同一时候保持p2概率较小，即减少了 false positive rate 。
4. AND和OR的级联
将与操作和或操作级联在一起，产生很多其它的hahs table，这种优点在于可以使得p1更接近1，而p2更接近0。
除了上面介绍的增强LSH的方法外，有时候我们希望将多个LSH hash function得到的hash值组合起来，在此基础上得到新的hash值，这样做的优点在于降低了存储hash table的空间。以下介绍一些经常用法：
1. 求模运算
new hash value = old hash value % N
2. 随机投影
如果通过k个LSH hash function得到了k个hash值：h1, h2..., hk。那么新的hash值採用例如以下公式求得：
new hash value = h1*r1 + h2*r2 + ... + hk*rk，当中r1, r2, ..., rk是一些随机数。
3. XOR异或
如果通过k个LSH hash function得到了k个hash值：h1, h2..., hk。那么新的hash值採用例如以下公式求得：
new hash value = h1 XOR h2 XOR h3 ... XOR hk
五、相关參考资料
Website:
[1] http://people.csail.mit.edu/indyk/ （LSH原作者）
[2] http://www.mit.edu/~andoni/LSH/ (E2LSH)
Paper:
[1] Approximate nearest neighbor: towards removing the curse of dimensionality
[2] Similarity search in high dimensions via hashing
[3] Locality-sensitive hashing scheme based on p-stable distributions
[4] MultiProbe LSH Efficient Indexing for HighDimensional Similarity Search
[5] Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Tutorial:
[1] Locality-Sensitive Hashing for Finding Nearest Neighbors
[2] Approximate Proximity Problems in High Dimensions via Locality-Sensitive Hashing
[3] Similarity Search in High Dimensions
Book:
[1] Mining of Massive Datasets
[2] Nearest Neighbor Methods in Learning and Vision: Theory and Practice
Cdoe:
[1] http://sourceforge.net/projects/lshkit/?source=directory
[2] http://tarsos.0110.be/releases/TarsosLSH/TarsosLSH-0.5/TarsosLSH-0.5-Readme.html
[3] http://www.cse.ohio-state.edu/~kulis/klsh/klsh.htm
[4] http://code.google.com/p/likelike/
[5] https://github.com/yahoo/Optimal-LSH
[6] OpenCV LSH（分别位于legacy module和flann module中）
声明：
作者： icvpr | blog.csdn.net/icvpr
