紧跟上一篇博客
k-shingles与minhash技术
，我们使用minhash压缩内容量较大的文档，但是文档相互之间的相似性计算仍然比较麻烦，因为两两之间的文档pairs太多了。有时候我们只需要最相似的文档pairs，没有必要计算所有pairs，为此我们引入LSH(locality-sensitive hashing)技术。
LSH的基本思想
将原始数据空间中的两个相邻数据点通过相同的映射后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。也就是说，如果我们对原始数据进行一些hash映射后，我们希望原先相邻的两个数据能够被hash到相同的桶内，具有相同的桶号。因此，LSH算法使用的关键是针对某一种相似度计算方法，找到一个具有以上描述特性的hash函数。如果能够找到这样一些hash functions，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入相同的桶内，那么我们在该数据集合中进行近邻查找就变得容易，只需要将查询数据进行哈希映射得到其桶号，然后取出该桶号对应桶内的所有数据，再进行线性匹配即可查找到与查询数据相邻的数据。如果不相似的pairs哈希到同一个桶中，这样会使结果的false positive增加；反之，如果真正相似的pairs哈希到不同的桶中，那么会使结果的false negative增加。我们的目标是让false positive和false negative的比例尽可能的小。
LSH直观解释
locality sensitive：彼此相近的数据点能够映射到相似的哈希值（以很高的概率放入相同哈希桶中）。
在上图中，有红色和黄色的圆圈，表示二维空间中的数据点，下面利用LSH找到它们的cosine相似性。灰色的线表示被选中的随机平面。如果数据点落在灰色线条的上面，用0（白色）表示，否则用1（黑色）表示。一旦选中一组平面，就可以根据平面对数据点进行编码，得到一个签名。数据点的签名角度的差异和实际的差异程度非常接近，因为夹在两个点之间的一个平面会给出1bit的差异。
如上图所示，只用6bits就可以表示两个数据点，这就是原始数据的LSH哈希值。由于两个数据点的签名只有1位不同，两个哈希值之间的海明距离为1，根据签名的长度，可以计算出夹角的相似性。
Banding技术
对于minhash 的signature矩阵，将其分成b个bands，每个band有r行组成，然后使用hash函数将每个band中每一列哈希到一个很大的hash table中，只要hash table中桶的数量足够大，那么地址碰撞的机率是非常小的。
解释banding技术：
假设有b个bands，每个band有r行，文档的Jaccard相似性为s，那么两篇文档映射到同一个桶中的概率为：
1 −(1 − s
r
)
b
对于一个特定band，两篇文档在该band的列都相同的概率为s
r
，至少有一个不相同的概率为1-s
r
，任何一个band都不相同的概率为(1-s
r
)
b
，那么至少有一个band相同的概率为1 − (1− s
r
)
b
，即为映射到同一个桶中的概率。
假如有100 000篇文档，100个signatures（行数），那么signatures的大小为40MB，选择b=20，r = 5，接下来我们找到相似性至少为s=0.8的相似文档pairs。
假设SIM(C
1
,C
2
) = 0.8，那么C
1
和C
2
至少映射到一个hash桶中（即至少有一个band是相同的），C
1
和C
2
在一个特定的band中相同的概率为(0.8)
5
=0.328，在20个band中都不相同的概率为(1-0.328)
20
=0.00035，即false negative。
假设SIM(C
1
,C
2
) = 0.3，那么C
1
和C
2
应该映射到不同的hash桶中（即所有的band都是不同的），C
1
和C
2
在一个特定的band中相同的概率为(0.3)
5
=0.00243，在20个band中至少有一个相同的概率为1-(1-0.00243)
20
=0.0474，即false positive。
参数的选择
1. minhash的个数n
2. b个bands
3. 每个band中r行
如何选择合适的n、b、r是的false negative和false positive下降？
只有1个band和1行：
LSH Family
上面提到，通过找到一些hash functions，使得经过它们的哈希映射变换后，就可以使原始空间中相邻的数据落入相同的桶内，那具有怎样特点的hash function才能够使得原本相邻的两个数据点经过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的hashfunction对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing。
d(x,y)是x和y之间的一个距离度量，但并不是所有的距离度量都能够找到满足locality-sensitive的hash functions。下面给出一些满足不同距离度量方式下的locality-sensitive的hash functions。
1. Jaccard距离
Jaccard距离： 即(1 – Jaccard相似性)，而Jaccard相似性通常用来判断两个集合的相似性。Jaccard相似性对应的LSH为minhash，是(d1,d2,1-d1,1-d2)-sensitive的。
2. Hamming距离
Hamming距离：两个具有相同长度的向量中对应位置处值不同的次数。Hamming距离对应的LSH为H(V) = 向量V的第i位上的值，是(d1,d2,1-d1/d,1-d2/d)-sensitive的。
3. Cosine距离
Cosine距离常用来判断两个向量之间的夹角，夹角越小，表示它们越相似。Cosine距离对应的LSH为H(V) = sign(V·R)，R是一个随机向量。V·R可以看成是将V向R上进行投影操作，是(d1,d2,(180-d1)/180,(180-d2)/180)-sensitive的。
4. 正规化的欧式距离
欧式距离是衡量d维空间中两个点之间的距离的一种距离度量方式。欧式距离对应的LSH为：H(V) = |V·R + b| / a，R是一个随机向量，a是桶宽，b是一个在[0,a]之间均匀分布的随机变量。V·R可以看做是将V向R上进行投影操作，是(a/2,2a,1/2,1/3)-sensitive的。
为了false negative和false positive能够降低，那应该增强LSH，使得主要有两个途径来实现：1）在一个hash table内使用更多的LSH function；2）建立多个hash table。
下面给出一些常用的增强LSH的方法：
1. 使用多个独立的hash table
每个hash table由k个LSH function创建，每次选用k个LSH function（同属于一个LSH function family）就得到了一个hash table，重复多次，即可创建多个hash table，多个hash table的好处在于能够降低false positive。
2. AND操作（
like “rows in a band”
）
从同一个LSH function family中挑选出k个LSH function，H(X) = H(Y)有且仅当这k个H
i
(X) = H
i
(Y)都满足，也就是说只有当两个数据的这k个hash值都对应相同时，才会被投影到相同的桶内，只要有一个不满足就不会被投影到同一个桶内。AND操作能够使得找到近邻数据的p1概率保持高概率的同时降低p2概率，即降低了false negative。
3. OR操作（
like “many bands”
）
从同一个LSH function family中挑选出k个LSH function，H(X) = H(Y)有且仅当存在一个以上的Hi(X) = Hi(Y)，也就是说只要两个数据的这k个hash值中有一对以上相同时，就会被投影到相同的桶内，只有当这k个hash值都不相同时才不被投影到同一个桶内。OR操作能够使得找到近邻数据的p1概率变的更大（越接近1）的同时保持p2概率较小，即降低了false positive。
4. AND和OR的级联
将AND操作和OR操作级联在一起，产生更多的hash table，这样的好处在于能够使得p1更接近1，而p2更接近0。
参考资料：
LSH Algorithm and Implementation (E2LSH)
Understanding Locality Sensitive hashing(LSH)