浅谈局部敏感哈希(LSH)

本文主要参考了一下文章:
1
2
3
感谢!
LSH主要用来解决高维空间中点的近似最近邻搜索问题,即Approximate Nearest Neighbor(ANN)。
在实际的应用中我们所面对的数据是海量的,并且有着很高的维度。在对数据的各种操作中,查询操作是最常见的一种,这里的查询是指输入一个数据,查找与其相似的数据,那么怎样快速从海量高维数据中找到与某个数据最相似的数据,成为了一个难点。
传统的哈希算法通过哈希函数建立哈希表,由哈希表我们能够得到O(1)的查找时间性能,传统哈希算法的关键在于,找到合适的哈希函数,将原始数据映射到相对应的桶内,如果不同的数据,映射到了同一个位置就是发生了冲突,这是传统哈希算法所避免的。
局部敏感哈希(LSH)的想法恰恰和传统的哈希算法相反,我们渴望冲突,但是我们希望的是原先相邻的两个数据能够以较高的概率被映射为同一个哈希值,而相似对很低的数据以极低的概率映射成同一个哈希值。这样的函数我们叫LSH。

LSH最根本的作用就是能够高效的处理海量高维数据的最近邻问题,其最大的特点就是保持数据的相似性。

一个不满足LSH的简单例子。
假设一个哈希函数$H(x) = x \% 9$.那么我们现在有三个数据分别为356,359,814;上述三个数据经过哈希函数哈希后得到:
$ Hash(356) = 356\%9 =5 $;

$ Hash(359) = 359\%9= 8;$

$Hash(814) = 814\%9 = 4;$
我们可以发现原本356和359很相似,和814相差很远,但是经过哈希影射或后814的哈希值和356的哈希值接近和359的相差较远。也就是经过这样的哈希计算之后,数据之间原有的相似度消失了,所以他不是一个局部敏感哈希。

LSH定义

局部敏感哈希函数需要满足如下条件:

其中H是一个从欧式空间S到哈希编码空间U的映射,$O_1,O_2 \in S$表示两个具有多维属性的数据对象,$d(O_1,O_2)$为两个对象的相异的程度(根据不同的度量方式,理解也不同。如欧式空间就是距离)说白一点就是,当足够相似时映射为同一个hash值的概率足够大,而足够不相似时映射为同一个hash值的概率足够小。 $ r_1 < r_2,p_1 > p_2$
本文主要介绍两种常用的相似度以及不同的LSH:

  1. 使用jaccard(杰卡德)系数度量数据相似度时的Min-hash
  2. 使用欧式距离度量数据相似度时的P-stable hash
    其实不论是哪种LSH,本质上都是将高维数据降维到低维数据,同时还能在一定程度上保持原数据的相似度不变。LSH不是确定性的,而是概率性的。也就是说有一定的概率导致原本很相似的数据映射成两个不相似的hash值或者原本不相似的两个数据映射成同一个hash值。这是高维数据降维过程中所不能避免的(因为降维必将导致损失),不过好在LSH的设计能够通过相应的参数控制出现这种错误的概率。

    Min-hash

    Jaccard系数

    Jaccard相似指数用来度量两个集合之间的相似性,它被定义为两个集合交集元素个数除以两个集合并集元素个数。 Jaccard距离用来度量两个集合之间的差异性m它是jaccard的相似系数的补集: 利用jaccard相似度来衡量文档之间的相似性,使用LSH来实现文档相似度计算。

假设我们有如下四个文档$D_1,D_2,D_3,D_4$的集合情况,每个文档有相应的词项,用$\{w_1,w_2,..w_7\}$ 表示。若某个文档存在这个词项,则标为1,否则标为0。

接下来我们就要选择一个适当的哈希函数,令其满足局部民哈希的条件,在此处我们选用的哈希函数数minhash(最小哈希)。
MinHash 是用于快速检测两个集合相似性的方法。该方法由 Andrei Broder (1997) 发明,最初用于AltaVista搜索引擎中来检测重复的网页。
Minhash的定义为: 特征矩阵按行进行一个随机的排列后,第一个列值为1的行的行号。
可以发现,如果我们对上述的文档进行Minhash,这不会改变文档与此项之间的关系,也不会改变文档之间的相似度。比如可以置换成如下形式:

现在我们做这样一件事: 对这个矩阵按行进行多次置换,每次置换之后统计每一列(对应的是每个文档)第一个不为0位置的行号,这样每次统计的结果能构成一个与文档数等大的向量,我们称之为签名向量
比如,如果对最上面的矩阵做这样的统计,得到$[1,2,1,2]$,对于下面的矩阵做统计,得到$[1,1,2,1]$.
如果拿上面的文档来说,如果两个文档足够相似,也就是说这两个文档中有很多元素是共有的,这样置换出来的签名向量,如果原来其中有一些文档的相似度很高,那么这些文档所对应的签名向量的相应的元素值相同的概率也很高。
我们把初始时的矩阵叫做input matrix,由m个文档m,n个词项组成.而把由t次置换后得到的一个$ t\times m$矩阵叫做signature matrix。
下图很好的展现了这一流程:

图中4个文档做了3次变换,得到了一个$ 3\times 4$的签名矩阵。
通过计算原矩阵和签名矩阵M的 各个文档之间的相似度可以看到原来相似度很高的文档之间哈希之后的相似度仍然很高。这满足LSH函数的性质。
可以想象一下,当我们有一组高维的数据比如100000等,我们可以使用最小哈希将其哈希100或者几百次,然后比较他们的相似度即可。这大大降低了数据的维度和计算的复杂度

定理

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

需要注意的是,置换矩阵的行,在代码实现的时候,可以用这样的算法实现:
1.在当下剩余的行中(初始时,剩余的行为全部行),随机选取任意一行,看看这一行哪些位置(这里的位置其实是列号)的元素是1,如果签名向量中这个位置的元素还未被写入,则在这个位置写入随机选取的这个行的行号。并将这一行排除。
2.持续进行1步的工作,直到签名向量全部被写满为止。

以上2步的意义跟对整个矩阵置换、再统计,结果是一样的。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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

构造LSH函数族

为了能实现前面LSH定义中的两个条件要求,我们通过多次置换求取签名向量,构建了一组哈希函数,也就是最终得到了一个signature matrix。为了控制相似度与映射概率之间的关系,我们需要按下面进行三步操作。
1.将signature matrix水平分割成一些区块(记为band)每个band包含了signature matrix中的r行。需要注意的是,同一列的每个band都是属于同一个文档的。如下图所示。

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

3.如果某两个文档的,同一水平方向上的band,映射成了同一hash值(如果你选的hash函数比较安全,抗碰撞性好,那这基本说明这两个band是一样的),我们就将这两个文档映射到同一个hash bucket中,也就是认为这两个文档是足够相近的。
另外, 需要注意的是,每一层的band只能和同一层的band相比,若hash值相同,则放入同一个哈希桶中。
好了,既然执行的是上面三步的操作,那不难计算出两个文档被映射到同一个hash bucket中的概率:
对于两个文档的任意一个band来说,这两个band值相同的概率是:$s^r$ 其中$ s \in [0,1]$是这两个文档的相似度
也就是说,这两个band不相同的概率是$ 1-s^r$
这两个文档一共存在b个band,这b个band都不相同的概率是 $ (1 - s^r)^b$
所以说b个band至少有一个相同的概率是 $ 1-(1-s^r)^b$
把这样的方法称为AND then OR,它是先要求每个band的所有对应元素必须都相同,再要求多个band中至少有一个相同。符合这两条,才能发生hash碰撞
概率 $ 1-(1-s^r)^b 就是最终两个文档被映射到同一个hash bucket中的概率。我们发现,这样一来实际可以通过控制参数r,b的值来控制两个文档被映射到同一个哈希桶的概率。而且效果非常好。比如令 $ b = 20,r = 5$
当$ s = 0.8$,两个文档被映射到同一个哈希桶的概率是:

当$ s=0.2$ 时,两个文档被映射到同一个哈希桶的概率是:

不难看出,这样的设计通过调节参数值,达到了“越相似,越容易在一个哈希桶;越不相似,越不容易在一个哈希桶”的效果。这也就能实现我们上边说的LSH的两个性质。
我画出了在$ r=5,b=20$ 参数环境下的概率图,大家会有个更清晰的认识。

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

P-stable Hash

目前来讲,还不存在通用的LSH函数,不同的相似度模型LSH也是不同的。上面的jaccard相似度我们使用的minhash,那么对于欧几里得空间我们使用的是P-Stable Hash。

p-stable distribution

p稳定分布的定义:

目前根据相关文献,在$ p \in (0,2]$这个范围内存在稳定分布,我们最常见的是$ p = 1,p = 2$的情况。
$p=1$ 时,这个分布就是标准的柯西分布。概率密度函数:$ c(x) = \frac{1}{\pi} \frac{1}{1 + x^2}$
$p=2$ 时,这个分布就是标准的正态分布。概率密度函数:$ c(x) = \frac{1}{\sqrt{2\pi}} e^{-x^2/2}$
当然,p值不是仅能取1和2. $(0,2]$中的小数也是可以的。
p稳定分布一个重要应用就是可以估计给定向量v在欧式空间下的p范数$||v||_p$的长度:
对于一个向量$v$(相当于上面公式中的$ (v_1,v_2,v…v_n)$)现在从p稳定分布中随机选取v的维度(设维度为n)个随机变量(相当于上面公式中的$ X_1,X_2,..X_n$)构成向量$a$,计算$a\cdot v = \sum_i v_iX_i$,此时$ a \cdot v$与$||v||_pX$同分布.我们就可以通过多给几个不同的向量$a$,多计算几个$a\cdot v$的值,来估计$||v||_p$的值。

p-stable分布LSH函数族构造

在p稳定的局部敏感哈希中,我们将利用$ a\cdot v$可以估计$||v||_p$的长度来构建hash函数族。(这里并不用来估计$||v||_p$而是构造函数)
将空间中的一条直线分成长度为r的等长的若干段,通过一种映射函数(也就是我们需要的,满足局部敏感的函数),将空间中的点映射到这条直线上,给映射到同一段的点赋予相同的hash值。不难理解,若空间中的两点离的距离越近,他们被映射到一段的概率也就越高。之前说过,$a \cdot v$可以用来估计$||v||_p$的长度,那么$ a \cdot v_1 - a \cdot v_2 = a(v_1 - v_2)$也可以用来估计$||v_1 -v_2||_p$的 长度。
由此我们得出结论:空间中的两个点距离: $||v_1-v_2||_p$近到一定程度时应该被hash成同一hash值,而向量点积的性质正好保持了这种局部敏感性,因此可以用点积来设计hash函数族。
有人提出了这一一种hash函数族:

其中$ b \in (0,r)$是一个随机数,$r$是直线的分段长度,hash函数族的函数是依据$a ,b$的不同建立的。可见,若要空间中的两个点$v_1,v_2$映射为同一hash值需要满足的条件为:
这两个点与a的点积加上随机b的计算结果在同一条线段上。
现在估计下这个概率,定义符合p-stable分布的随机变量绝对值的概率密度函数为$f_p(t)$设
$ c = ||v_1-v_2||_p$,则$a \cdot v_1 - a \cdot v_2$与$cX$同分布。概率公式如下:

当r值确定的时候,这个公式可以看做是一个仅与C的取值有关的函数。概率p(c)是关于c的单调递减函数,c越大,函数值越小(碰撞概率越低),c越小,函数值越大(碰撞概率越高)。
上式$p(c)$的证明:
设$a \cdot v_1$在点M处,$a \cdot v_2$在点B出,此处设N点在靠近Q的位置。
1.b对映射后点的影响

2.点积对映射后点的影响

但是关于r的取值,并没有给出一个确定的值。这需要我们根据c与p的值来设定。

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

我们构建hash table的过程就是要用这个函数族的每一个函数对每一个向量执行hash计算。为了减少漏报率False Negative(就是本来很相近的两条数据被认为是不相似的),一种解决方案是用多个hash函数对向量执行hash运算。比如说,对任意一个向量$v_i$现在准备了k个hash函数$(h_1(), h_2(), \dots , h_k())$这k个hash函数是从LSH函数族中随机选取的k个,这样通过计算,就得到了k个hash值$(h_1(v_i), h_2(v_i), \dots , h_k(v_i))$,而对于查询q用同样的k个hash函数,也能得到一组值$ (h_1(q), h_2(q), \dots , h_k(q))$,这两组值间只要有一个对应位的值相等,我们就认为$v_i$是查询q的一个近邻。
但是上面这种做法也存在一个问题,就是说选用k个hash函数确实减少了漏报率,但是也增加了误报率(本来不相近的数据认为是相近的)。所以需要在上面方法的基础上再增加一个措施。我们从LSH函数族中,随机选取L组这样的函数族,每个函数组都有k个随机选取的函数构成,当然L个函数组之间不一定是一样的。现在这L组函数分别对数据处理,只要有一组完全相等就认为两条数据是相近的。
其实上面两段的做法,就是一个简单的AND then OR的逻辑,与我们上面说的min-hash的思路是一致的。
现在假设$ P = Pr[h_{a, b}(v_1) = h_{a, b}(v_2)]$(这个概率可由上面的积分公式算出),那么两条数据被认为是近邻的概率是:

构建hash table时,如果把一个函数组对向量的一组hash值$ (h_1(v_i), h_2(v_i), \dots , h_k(v_i))$作为hash bucket的标识,有两个缺点:1. 空间复杂度大;2. 不易查找。为了解决这个问题,我们采用如下方法:
先设计两个hash函数:$H_1,H_2$:
$H_1:Z^k \to \{0, 1, 2, \dots, size - 1\}$ 简单说就是把一个k个数组成的整数向量映射到hash table的某一个位上,其中size是hash table的长度。
$H_2:Z^k \to \{0, 1, 2, \dots, C\},C = 2^{32} - 5$ 是一个大素数
这两个函数具体的算法如下,其中$r_i, r_i^{‘}$是两个随机整数

我们把H2计算的结果成为一个数据向量的“指纹”,这也好理解,它就是由数据向量的k个hash值计算得到的。而H1相当于是数据向量的指纹在hash table中的索引,这个算法跟基本的散列表算法是一个思路.
通过这两个新建的函数,我们可以将hash table的构建步骤作以下详细说明:
1.从设计好的LSH函数族中,随机选取L组hash函数,每组由k个hash函数构成,记为$\{g_1(\cdot), g_2(\cdot), \dots, g_L(\cdot)\}$,其中:$g_i(\cdot) = (h_1(\cdot), h_2(\cdot), \dots , h_k(\cdot))$
2.每个数据向量经过$g_i(⋅)$被映射成一个整型向量,记为$(x_1,…,x_k)$
3.将2步生成的$(x_1,…,x_k)(x_1,…,x_k)$通过$H_1,H_2$计算得到两个数值:index,fp,前者是hash table的索引,后者是数据向量对应的指纹。这里,为了方便描述这种hash table的结构,我将我们用的hash table的结构画出,如图Fig.1所示。
4.若其中有数据向量拥有相同的数据指纹,那么必然会被映射到同一个hash bucket当中

annoy


-------------本文结束感谢您的阅读-------------


本文标题:浅谈局部敏感哈希(LSH)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2018年11月20日 - 15:11

最后更新:2018年12月20日 - 21:12

原始链接:https://statusrank.xyz/articles/84288273.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!