LSH(Locality Sensitive Hashing)原理与实现(上)

LSH(Locality Sensitive Hashing)翻译成中文,叫做“局部敏感哈希”,它是一种针对海量高维数据的快速最近邻查找算法。

在信息检索,数据挖掘以及推荐系统等应用中,我们经常会遇到的一个问题就是面临着海量的高维数据,查找最近邻。如果使用线性查找,那么对于低维数据效率尚可,而对于高维数据,就显得非常耗时了。为了解决这样的问题,人们设计了一种特殊的hash函数,使得2个相似度很高的数据以较高的概率映射成同一个hash值,而令2个相似度很低的数据以极低的概率映射成同一个hash值。我们把这样的函数,叫做LSH(局部敏感哈希)。 LSH最根本的作用,就是能高效处理海量高维数据的最近邻问题

定义

我们将这样的一族hash函数 H = { h : S U } H=\{h: S \rightarrow U\} 称为是 ( r 1 , r 2 , p 1 , p 2 ) (r_1,r_2,p_1,p_2) 敏感的,如果对于任意H
中的函数 h h ,满足以下2个条件:

  1. 如果 d ( O 1 , O 2 ) < r 1 d\left(O_{1}, O_{2}\right)<r_1 ,那么 Pr [ h ( O 1 ) = h ( O 2 ) ] p 1 \operatorname{Pr}\left[h\left(O_{1}\right)=h\left(O_{2}\right)\right] \geq p_{1}
  2. 如果 d ( O 1 , O 2 ) > r 2 d\left(O_{1}, O_{2}\right)>r_2 ,那么 Pr [ h ( O 1 ) = h ( O 2 ) ] p 2 \operatorname{Pr}\left[h\left(O_{1}\right)=h\left(O_{2}\right)\right] \leq p_{2}

其中, O 1 , O 2 S O_{1}, O_{2} \in S 为两个对象的相异程度,也就是相似度。其实上面的这两个条件说得直白一点,就是当足够相似时,映射为同一hash值的概率足够大;而足够不相似时,映射为同一hash值的概率足够小。

相似度的定义根据实际情况自己决定(有关数据对象相似度的比较,详情可以参考我的另一篇博文: 数据相似性的度量方法总结 ),后面我们可以看到,针对不同的相似度测量方法,局部敏感哈希的算法设计也不同,我们主要看看在两种最常用的相似度下,两种不同的LSH:

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

当然,无论是哪种LSH,其实说白了,都是将高维数据降维到低维数据,同时,还能在一定程度上,保持原始数据的相似度不变。LSH不是确定性的,而是概率性的,也就是说有一定的概率导致原本很相似的数据映射成2个不同的hash值,或者原本不相似的数据映射成同一hash值。这是高维数据降维过程中所不能避免的(因为降维势必会造成某种程度上数据的失真),不过好在LSH的设计能够通过相应的参数控制出现这种错误的概率,这也是LSH为什么被广泛应用的原因。

min-hash

hash函数的选择

了解min-hash之前,首先普及一下Jaccard系数的概念。Jaccard系数主要用来解决的是非对称二元属性相似度的度量问题,常用的场景是度量2个集合之间的相似度,公式这里我不写了,就是2个集合的交比2个集合的并。

比如,我在底下的表格中写出了4个对象(你可以看做是4个文档)的集合情况,每个文档有相应的词项,用词典 { w 1 , w 2 , , w 7 } \{w_1,w_2,…,w_7\} 表示。若某个文档存在这个词项,则标为1,否则标0

Word D 1 D_1 D 2 D_2 D 3 D_3 D 4 D_4
w 1 w_1 1 0 1 0
w 2 w_2 1 1 0 1
w 3 w_3 0 1 0 1
w 4 w_4 0 0 0 1
w 5 w_5 0 0 0 1
w 6 w_6 1 1 1 0
w 7 w_7 1 0 1 0

首先,我们现在将上面这个word-document的矩阵按行置换,比如可以置换成以下的形式:

Word D 1 D_1 D 2 D_2 D 3 D_3 D 4 D_4
w 2 w_2 1 1 0 1
w 1 w_1 1 0 1 0
w 4 w_4 0 0 0 1
w 3 w_3 0 1 0 1
w 7 w_7 1 0 1 0
w 6 w_6 1 1 1 0
w 5 w_5 0 0 0 1

可以确定的是,这没有改变文档与词项的关系。现在做这样一件事:对这个矩阵按行进行多次置换,每次置换之后,统计每一列(其实对应的就是每个文档)第一个不为0的位置(行号),这样每次统计的结果能构成一个与文档数等大的向量,这个向量,我们称之为 签名向量。

比如,如果对最上面的矩阵做这样的统计,得到[1,2,1,2],对于下面的矩阵做统计,得到[1,1,2,1]

简单来想这个问题,就拿上面的文档来说,如果两个文档足够相似,那也就是说这两个文档中有很多元素是共有的,换句话说,这样置换之后统计出来的签名向量,如果其中有一些文档的相似度很高,那么这些文档所对应的签名向量的相应的元素,值相同的概率就很高。

我们把最初始时的矩阵叫做 input matrix m m 个文档, n n 个词项组成。而把由 t t 次置换后得到的一个 t × m t×m 的矩阵叫做 signature matrix .

下图能够很清晰的展现出这一套流程:
福昕截屏20230415142910038.PNG

需要注意的是,置换矩阵的行,在代码实现的时候,可以用这样的算法实现:

  1. 在当下剩余的行中(初始时,剩余的行为全部行),随机选取任意一行,看看这一行哪些位置(这里的位置其实是列号)的元素是1,如果签名向量中这个位置的元素还未被写入,则在这个位置写入随机选取的这个行的行号。并将这一行排除。
  2. 持续进行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

现在给出一个定理。

定理:对于签名矩阵的任意一行,它的两列元素相同的概率是 x n \frac{x}{n} ,其中 x x 代表这两列所对应的文档所
拥有的公共词项的数目。而也就是这两个文档的Jaccard系数。

这个定理我想不用证明了。实际上,置换input matrix的行,取每列第一个非0元的做法,就是一个hash函数。这个hash函数成功地将多维数据映射成了一维数据。而从这个定理我们发现,这样的映射没有改变数据相以度。

需要注意的一点是,这里的hash函数只能对Jaccard系数定义数据相似度的情况起作用。不同的相似度模型,LSH是不同的,目前,还不存在一种通用的LSH。

构造LSH函数族

为了能实现前面LSH定义中的2个条件的要求,我们通过多次置换,求取向量,构建了一组hash函数。也就是最终得到了一个signature matrix. 为了控制相似度与映射概率之间的关系,我们需要按下面的操作进行,一共三步。

(1)将signature matrix水平分割成一些区块(记为band),每个band包含了signature matrix中的m
行。需要注意的是,同一列的每个bad都是属于同一个文档的。如下图所示:
福昕截屏20230415143257769.PNG

(2)对每个band计算hash值,这里的hash算法没有特殊要求,MD5,SHA1等等均可。一般情况下,我们需要将这些hash值做处理,使之成为事先设定好的hash桶的tag,然后把这些band“扔”进hash桶中。如下图所示。但是这里,我们只是关注算法原理,不考虑实际操作的效率问题。所以,省略处理hash值得这一项,得到每个band的hash值就OK了,这个hash值也就作为每个hash bucket的tag。
福昕截屏20230415143448959.PNG

(3) 如果某两个文档的,同一水平方向上的band,映射成了同一hash值(如果你选的hash函数比较安全,抗碰撞性好,那这基本说明这两个band是一样的),我们就将这两个文档映射到同一个hash bucket中,也就是认为这两个文档是足够相近的。

好了,既然执行的是上面三步的操作,那不难计算出两个文档被映射到同一个hash bucket中的概率:

  • 对于两个文档的任意一个band来说,这两个band值相同的概率是: s r s^r ,其中 s [ 0 , 1 ] s\in [0,1] 是这两个文档的相似度。
  • 也就是说,这两个band不相同的概率是 1 s r 1-s^r
  • 这两个文档一共存在b个band,这b个band都不相同的概率是 ( 1 s r ) b (1-s^r)^b
  • 所以说,这b个band至少有一个相同的概率是 1 ( 1 s r ) b 1-(1-s^r)^b

它是先要求每个band的所有对应元素必须都相同,再要求多个band中至少有一个相同。符合这两条,才能发生hash碰撞。

概率 1 ( 1 s r ) b 1-(1-s^r)^b 就是最终两个文档被映射到同一个hash bucket中的概率。我们发现,这样一来,实际上可以通过控制参数r,b的值来控制两个文档被映射到同一个哈希桶的概率。而且效果非常好。比如,令 b = 2 0 , r = 5 b=20,r=5

  • s = 0 . 8 s=0.8 时,两个文档被映射到同一个哈希桶的概率是:

Pr ( L S H ( O 1 ) = L S H ( O 2 ) ) = 1 ( 1 0 . 8 5 ) 5 = 0 . 9 9 9 6 4 3 9 4 2 1 0 9 4 7 9 3 \operatorname{Pr}\left(L S H\left(O_{1}\right)=L S H\left(O_{2}\right)\right)=1-\left(1-0.8^{5}\right)^{5}=0.9996439421094793

  • s = 0 . 2 s=0.2 时,两个文档被映射到同一个哈希桶的概率是:

Pr ( L S H ( O 1 ) = L S H ( O 2 ) ) = 1 ( 1 0 . 2 5 ) 5 = 0 . 0 0 6 3 8 0 5 8 1 3 0 4 7 6 8 2 \operatorname{Pr}\left(L S H\left(O_{1}\right)=L S H\left(O_{2}\right)\right)=1-\left(1-0.2^{5}\right)^{5}=0.0063805813047682

不难看出,这样的设计通过调节参数值,达到了“越相似,越容易在一个哈希桶;越不相似,越不容易在一个哈希桶”的效果。这也就能实现我们上边说的LSH的两个性质。

我画出了在r=5,b=20参数环境下的概率图,大家会有个更清晰的认识。
福昕截屏20230415144313844.PNG

当相似度高于某个值的时候,概率会变得非常大,并且快速靠近1,而当相似度低于某个值的时候,概率会变得非常小,并且快速靠近0

限于篇幅,代码就不在博客里罗列了,需要的话可以访问我的github主页:
https://github.com/guoziqingbupt/Locality-sensitive-hashing

这个项目中,我一共写了min-hash和e2LSH两个算法的实现,min-hash部分请参见模块min_hash.py。另外, 需要注意的是,每一层的band只能和同一层的band相比,若hash值相同,则放入同一个哈希桶中。

P-stable hash

最开始的时候,我们已经说过,不同的相似度判别方法,对应着不同的LSH,那对于最常见的Lp范数下的欧几里得空间,应该用怎样的LSH呢?这就要介绍P-stable hash了。

P-stable distribution

在讲解P-stable hash之前,先简单介绍一下 p p 稳定分布的概念。

定义: 一个分布 D D 称为 p p 稳定分布,如果对于任意 n \mathrm{n} 个实数 v 1 , v 2 , , v n v_{1}, v_{2}, \ldots, v_{n} 和符合 D D 分布的 n \mathrm{n} 个独立同分布的随机变量 X 1 , X 2 , , X n X_{1}, X_{2}, \ldots, X_{n} , 都存在一个 p 0 p \geq 0 ,使得 i v i X i \sum_{i} v_{i} X_{i} ( i v i p ) 1 / p X \left(\sum_{i}\left|v_{i}\right|^{p}\right)^{1 / p} X 具有相同的分布,其中, X X 是一个满足 D D 分布的随机变量。

目前,根据相关文献,在 p ( 0 , 2 ] p\in (0,2] 这个范围内存在稳定分布。我们最常见的是 p = 1 p=1 以及 p = 2 p=2 时的情况。

  • p = 1  时,这个分布就是标准的柯西分布。概率密度函数:  c ( x ) = 1 π 1 1 + x 2 p=1 \text { 时,这个分布就是标准的柯西分布。概率密度函数: } c(x)=\frac{1}{\pi} \frac{1}{1+x^{2}}
  • p = 2  时,这个分布就是标准的正态分布。概率密度函数:  c ( x ) = 1 2 π e x 2 / 2 p=2 \text { 时,这个分布就是标准的正态分布。概率密度函数: } c(x)=\frac{1}{\sqrt{2 \pi}} e^{-x^{2} / 2}

当然, p p 值不是仅能取1和2. (0,2]中的小数也是可以的。

p p 稳定分布有什么作用呢,我们为什么在这里提出来?它有一个重要的应用,就是可以估计给定向量 v v 在欧式空间下的 p p 范数的长度,也就是 v p ||v||_p

可以这样实现: 对于一个向量 v v (相当于上面公式中的 ( v 1 , v 2 , , v n ) \left(v_{1}, v_{2}, \ldots, v_{n}\right) ,现在从 p p 稳定分布中,随机选取 v v 的维度个随机变量(相当于上面公式中的 X 1 , X 2 , , X n ) \left.X_{1}, X_{2}, \ldots, X_{n}\right) 构成向量 a a ,计算 a v = i v i X i a \cdot v=\sum_{i} v_{i} X_{i} ,此时, a v a \cdot v v p X \|v\|_{p} X 同分布。我们就可以通过多给几个不同的向量 a a ,多计算几个 a v a \cdot v 的值,来估计 v p \|v\|_{p} 的值。

p-stable分布LSH函数族构造

p p 稳定的局部敏感hash中,我们将利用 a v a \cdot v 可以估计 v p ||v||_p 长度的性质来构建hash函数族。具体如下:

  • 将空间中的一条直线分成长度为r的,等长的若干段。
  • 通过一种映射函数(也就是我们要用的hash函数),将空间中的点映射到这条直线上,给映射到同一段的点赋予相同的hash值。不难理解,若空间中的两个点距离较近,他们被映射到同一段的概率也就越高。
  • 之前说过, a v a \cdot v 可以估计 v p \|v\|_{p} 长度,那么, ( a v 1 a v 2 ) = a ( v 1 v 2 ) \left(a \cdot v_{1}-a \cdot v_{2}\right)=a\left(v_{1}-v_{2}\right) 也就可以用来估计 v 1 v 2 p \left\|v_{1}-v_{2}\right\|_{p} 的长度。
  • 综合上面的3条,可以得到这样一个结论:空间中两个点距离:||v1−v2||_p,近到一定程度时,应该被hash成同一hash值,而向量点积的性质,正好保持了这种局部敏感性。因此,可以用点积来设计hash函数族。

文献[1]提出了这样一种hash函数族:

h a , b ( v ) = a v + b r h_{a, b}(v)=\left\lfloor\frac{a \cdot v+b}{r}\right\rfloor

其中, b b ∈(0,r)是一个随机数, r r 是直线的分段长度,hash函数族的函数是依据 a , b a,b 的不同建立的。
可见,若要空间中的两个点 v 1 , v 2 v_1,v_2 映射为同一hash值,需要满足的条件为:这两点与 a a 的点积加上随机值 b b 的计算结果在同一条线段上。

现在估计一下这个概率。设 c = v 1 v 2 p c=\left\|v_{1}-v_{2}\right\|_{p} ,则 a v 1 a v 2 a \cdot v_{1}-a \cdot v_{2} c X c X 同分布。概率公式如下:

p ( c ) = Pr [ h a , b ( v 1 ) = h a , b ( v 2 ) ] = 0 r 1 c f p ( t c ) ( 1 t r ) d t p(c)=\operatorname{Pr}\left[h_{a, b}\left(v_{1}\right)=h_{a, b}\left(v_{2}\right)\right]=\int_{0}^{r} \frac{1}{c} f_{p}\left(\frac{t}{c}\right)\left(1-\frac{t}{r}\right) d t

r r 的值取定的时候,这个公式可以看做是一个仅与 c c 的取值相关的函数。 c c 越大,函数值越小(碰撞的概率越低); c c 越小,函数值越大(碰撞的概率越高)。相关的具体证明参见参考文献[2].

但是关于 r r 的取值,在文献[1]中,并没有给出一个确定的值。这需要我们根据 c c p p 的值来设定。

试想,因为我们设定的 S H \mathrm{SH} ( r 1 , r 2 , p 1 , p 2 ) \left(r_{1}, r_{2}, p_{1}, p_{2}\right) 敏感的,所以,当 r 2 / r 1 = c r_{2} / r_{1}=c 的时候(这里的 c c 可以看做是一个标准),也就不难推出: p 1 = p ( 1 ) , p 2 = p ( c ) p_{1}=p(1), p_{2}=p(c)

文献[1]指出,选取合适的r值,能够使得 ρ = ln ( 1 / p 1 ) ln ( 1 / p 2 ) \rho=\frac{\ln \left(1 / p_{1}\right)}{\ln \left(1 / p_{2}\right)} 尽可能地小。这里面的理论非常复杂,所以,在这里,我给出文献[1]的一张图:
福昕截屏20230415151548407.PNG
这是在 L 2 L_2 范数下, ρ \rho 和最优的 r r 的关系,可以看出以下几点信息:

  • c c 的取值不同时,即便对于相同的r,\rhp也不同
  • r r 的取值大于某一点后, ρ \rho r r 的变化不再敏感
  • 虽然从图像的趋势上看, r r 越大, ρ \rho 越小,但是, r r 的取值也不能太大,否则会导致 p 1 , p 2 p_1,p_2 都接近于1,增大搜索时间(我觉得这就导致LSH没意义了)
  • 所以,可见 r r 的取值要根据实际情况,自己设定。我有个想法,不知道在具体实施的时候合不合理:可以先确定一下 r 1 , r 2 r_1,r_2 的取值,然后选择合适的 r r ,使得 p 1 , p 2 p_1,p_2 都达到我们的要求即可。

p-stable 分布LSH相似性搜索算法

上面完成了对p-stable 分布LSH函数族构造。那么接下来的问题是怎样具体实现hash table的构造以及查询最近邻。我将这个问题按照本人自己的理解写在下面。因为确实难以找到一个权威的文献具体论述这个问题,虽然文献[3]中讲解了这个问题,但是表达有点模糊不清。所以,下面的内容是我自己的理解,个人觉得问题应该不大,如有错误,请批评指正。

我们构建hash table的过程就是要用这个函数族的每一个函数对每一个向量执行hash运算。为了减少漏报率False Negative(就是本来很相近的两条数据被认为是不相似的),一种解决方案是用多个hash函数对向量执行hash运算,比如说,对任意一个向量 v i v_{i} ,现在准备了 k k 个hash函数 ( h 1 ( ) , h 2 ( ) , , h k ( ) ) \left(h_{1}(), h_{2}(), \ldots, h_{k}()\right) ,这 k k 个hash函数是从LSH函数族中随机选取的 k k 个,这样,通过计算,就得到了 k k 个hash值: ( h 1 ( v i ) , h 2 ( v i ) , , h k ( v i ) ) \left(h_{1}\left(v_{i}\right),h_{2}\left(v_{i}\right),\ldots,h_{k}\left(v_{i}\right)\right) ,而对于查询 q q ,用同样的 k k 个hash函数,也能得到一组值 ( h 1 ( q ) , h 2 ( q ) , , h k ( q ) ) \left(h_{1}(q), h_{2}(q), \ldots, h_{k}(q)\right)