LSH(Locality Sensitive Hashing)局部敏感Hash

大家好，欢迎来到IT知识分享网。

LSH 的哈希函数族（Hash Family）定义

我们将这样的一族hash函数 称为是敏感的，如果对于任意中的函数，满足以下2个条件：

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。

满足(d1,d2,p1,p2)-sensitive的哈希函数构成了 LSH 的哈希函数族。

LSH 的查找过程

使用LSH进行对海量数据建立索引（Hash table）并通过索引来进行近似最近邻查找的过程如下：

• 离线建立索引
  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；
• 在线查找
  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 常见的 Hash Function(降维)

对数据集当中的元素，采用不同的距离函数来进行度量时，对应着不同的 LSH 哈希函数，但并不是所有的距离度量都能够找到满足 locality-sensitive 的 hash functions，下面我们介绍一些满足不同距离度量方式下的locality-sensitive的hash functions：

1. 使用Jaccard系数度量数据相似度时的min-hash
2. 使用欧氏距离度量数据相似度时的P-stable hash

min-hash

Jaccard distance 对应的 LSH hash function 为：min-hash，其是(d1,d2,1-d1,1-d2)-sensitive的。

具体介绍：

1. C1和C2的值都为1，记为a,数量为x；
2. 只有一个值为1，另一个值为0，记为b,数量为y；
3. C1和C2的值都为0，记为c；

C1和C2交集的元素个数为x，并集的元素个数为x+y，所以sim(C1,C2) = Jaccard(C1,C2) = x/(x+y)。接下来计算h(C1)=h(C2)的概率，经过随机行打乱后，从上往下扫描，在碰到Y行之前碰到X行的概率为x/(x+y)，即h(C1)=h(C2)的概率为x/(x+y)。

min-Hash的局部敏感哈希算法（LSH）

这里主要说的是判断文档（集合）相似性中的LSH。

对于集合中元素个数很多，而且有很多集合需要判断相似性的情况，MinHash解决了元素个数很多的集合判断相似性的问题，但是还剩下集合个数很多的问题没有解决，那么给定一组文档，还有MinHash签名矩阵，不去一一计算Hash签名的相似性，怎么快速地寻找与一个查询文档（最）相似的文档呢？

Banding for LSH

把签名矩阵分成 b 个行条（band），每个行条由 r 行组成（假设签名矩阵中有 n 行，那么n = br）。对于每个行条，存在一个哈希函数能够将行条中的每 r 个整数组成的列向量（行条中的每一列）映射到某个桶中，可以对所有行条使用相同的哈希函数，但是每个行条都有独立的桶数组。

我们仅需要计算sim(S2, S3)，sim(S2, S4)，sim(S2, S5)，因为这些集合出现过与S2桶相同的情况。

p-stable LSH

借鉴另一个博主的文章LSH系列3：p-stable LSH&E2LSH——原理介绍