LSH(Locality Sensitive Hashing)翻译成中文，叫做“局部敏感哈希”，它是一种针对海量高维数据的快速最近邻查找算法。
在信息检索，数据挖掘以及推荐系统等应用中，我们经常会遇到的一个问题就是面临着海量的高维数据，查找最近邻。如果使用线性查找，那么对于低维数据效率尚可，而对于高维数据，就显得非常耗时了。为了解决这样的问题，人们设计了一种特殊的hash函数，使得2个相似度很高的数据以较高的概率映射成同一个hash值，而令2个相似度很低的数据以极低的概率映射成同一个hash值。我们把这样的函数，叫做LSH（局部敏感哈希）。LSH最根本的作用，就是能高效处理海量高维数据的最近邻问题
我们将这样的一族hash函数 H={
h:S→U} H = { h : S → U } 称为是 (r1,r2,p1,p2) ( r 1 , r 2 , p 1 , p 2 ) 敏感的，如果对于任意 H H 中的函数
其中， O1,O2∈S O 1 , O 2 ∈ S ，表示两个具有多维属性的数据对象， d(O1,O2) d ( O 1 , O 2 ) 为2个对象的相异程度，也就是1 - 相似度。其实上面的这两个条件说得直白一点，就是当足够相似时，映射为同一hash值的概率足够大；而足够不相似时，映射为同一hash值的概率足够小。
相似度的定义根据实际情况自己决定（有关数据对象相似度的比较，详情可以参考我的另一篇博文：数据相似性的度量方法总结），后面我们可以看到，针对不同的相似度测量方法，局部敏感哈希的算法设计也不同，我们主要看看在两种最常用的相似度下，两种不同的LSH：
当然，无论是哪种LSH，其实说白了，都是将高维数据降维到低维数据，同时，还能在一定程度上，保持原始数据的相似度不变。LSH不是确定性的，而是概率性的，也就是说有一定的概率导致原本很相似的数据映射成2个不同的hash值，或者原本不相似的数据映射成同一hash值。这是高维数据降维过程中所不能避免的（因为降维势必会造成某种程度上数据的失真），不过好在LSH的设计能够通过相应的参数控制出现这种错误的概率，这也是LSH为什么被广泛应用的原因。
了解min-hash之前，首先普及一下Jaccard系数的概念。Jaccard系数主要用来解决的是非对称二元属性相似度的度量问题，常用的场景是度量2个集合之间的相似度，公式这里我不写了，就是2个集合的交比2个集合的并。
比如，我在底下的表格中写出了4个对象（你可以看做是4个文档）的集合情况，每个文档有相应的词项，用词典 { w1,w2,…,w7} { w 1 , w 2 , … , w 7 } 表示。若某个文档存在这个词项，则标为1，否则标0.
| word | D1 D 1 | D2 D 2 | D3 D 3 | D4 D 4 |
|---|---|---|---|---|
| w1 w 1 | 1 | 0 | 1 | 0 |
| w2 w 2 | 1 | 1 | 0 | 1 |
| w3 w 3 | 0 | 1 | 0 | 1 |
| w4 w 4 | 0 | 0 | 0 | 1 |
| w5 w 5 | 0 | 0 | 0 | 1 |
| w6 w 6 | 1 | 1 | 1 | 0 |
| w7 w 7 | 1 | 0 | 1 | 0 |
首先，我们现在将上面这个word-document的矩阵按行置换，比如可以置换成以下的形式：
| word | D1 D 1 | D2 D 2 | D3 D 3 | D4 D 4 |
|---|---|---|---|---|
| w2 w 2 | 1 | 1 | 0 | 1 |
| w1 w 1 | 1 | 0 | 1 | 0 |
| w4 w 4 | 0 | 0 | 0 | 1 |
| w3 w 3 | 0 | 1 | 0 | 1 |
| w7 w 7 | 1 | 0 | 1 | 0 |
| w6 w 6 | 1 | 1 | 1 | 0 |
| w5 w 5 | 0 | 0 | 0 | 1 |
可以确定的是，这没有改变文档与词项的关系。现在做这样一件事：对这个矩阵按行进行多次置换，每次置换之后，统计每一列（其实对应的就是每个文档）第一个不为0的位置（行号），这样每次统计的结果能构成一个与文档数等大的向量，这个向量，我们称之为签名向量。
比如，如果对最上面的矩阵做这样的统计，得到 [1,2,1,2] [ 1 , 2 , 1 , 2 ] ，对于下面的矩阵做统计，得到 [1,1,2,1] [ 1 , 1 , 2 , 1 ] .
简单来想这个问题，就拿上面的文档来说，如果两个文档足够相似，那也就是说这两个文档中有很多元素是共有的，换句话说，这样置换之后统计出来的签名向量，如果其中有一些文档的相似度很高，那么这些文档所对应的签名向量的相应的元素，值相同的概率就很高。
我们把最初始时的矩阵叫做input matrix，由 m m 个文档，
下面是我盗的一张图，能够很清晰的展现出这一套流程：
图中，4个文档，做了3次置换，得到了一个3 x 4的签名矩阵。感谢提供图的这篇博文的作者：http://blog.sina.com.cn/s/blog_4ff49c7e0102vl52.html
需要注意的是，置换矩阵的行，在代码实现的时候，可以用这样的算法实现：
在当下剩余的行中（初始时，剩余的行为全部行），随机选取任意一行，看看这一行哪些位置（这里的位置其实是列号）的元素是1，如果签名向量中这个位置的元素还未被写入，则在这个位置写入随机选取的这个行的行号。并将这一行排除。
持续进行1步的工作，直到签名向量全部被写满为止。
以上2步的意义跟对整个矩阵置换、再统计，结果是一样的。这么说可能有点抽象，我把函数放在下面：
def sigGen(matrix):
"""
* generate the signature vector
:param matrix: a ndarray var
:return a signature vector: a list var
"""
# the row sequence set
seqSet = [i for i in range(matrix.shape[0])]
# initialize the sig vector as [-1, -1, ..., -1]
result = [-1 for i in range(matrix.shape[1])]
count = 0
while len(seqSet) > 0:
# choose a row of matrix randomly
randomSeq = random.choice(seqSet)
for i in range(matrix.shape[1]):
if matrix[randomSeq][i] != 0 and result[i] == -1:
result[i] = randomSeq
count += 1
if count == matrix.shape[1]:
break
seqSet.remove(randomSeq)
# return a list
return result现在给出一个定理。
定理：对于签名矩阵的任意一行，它的两列元素相同的概率是 xn x n ，其中 x x 代表这两列所对应的文档所拥有的公共词项的数目。而
这个定理我想不用证明了。实际上，置换input matrix的行，取每列第一个非0元的做法，就是一个hash函数。这个hash函数成功地将多维数据映射成了一维数据。而从这个定理我们发现，这样的映射没有改变数据相似度。
需要注意的一点是，这里的hash函数只能对Jaccard系数定义数据相似度的情况起作用。不同的相似度模型，LSH是不同的，目前，还不存在一种通用的LSH。
为了能实现前面LSH定义中的2个条件的要求，我们通过多次置换，求取向量，构建了一组hash函数。也就是最终得到了一个signature matrix. 为了控制相似度与映射概率之间的关系，我们需要按下面的操作进行，一共三步。
(1) 将signature matrix水平分割成一些区块（记为band），每个band包含了signature matrix中的 r r 行。需要注意的是，同一列的每个band都是属于同一个文档的。如下图所示。这个图我还是盗的上面链接中的博文，特此说明。
(2) 对每个band计算hash值，这里的hash算法没有特殊要求，MD5，SHA1等等均可。一般情况下，我们需要将这些hash值做处理，使之成为事先设定好的hash桶的tag，然后把这些band“扔”进hash桶中。如下图所示。但是这里，我们只是关注算法原理，不考虑实际操作的效率问题。所以，省略处理hash值得这一项，得到每个band的hash值就OK了，这个hash值也就作为每个hash bucket的
