这篇博文简单总结一下局部敏感性hash(locality-sensetive-hash,LSH) 在找相似元素中的应用,这也是最近邻的另外一种解决方案

LSH 的直觉非常简单,设想一下我们判断一个集合 $set$ 中是否存在一个元素 $e$ 的方法,通常是将集合中的所有元素hash到一个一个的桶中,同时将 $e$ hash到桶中,如果存在,那么一定能在 $hash(e)$ 的桶中找到 $e$ ,这样的均摊代价只有 $O(1)$

不过如果我们要找在某种距离下,与元素 $e$ 仅有些许差别(i.e. $distance(e,x) \le \theta$),而不是完全相同时,上面这种通常的hash方案是一定不行的。如果,我们能够找到一个hash 函数 $s.t. \Pr[hash(x)= hash(y)] = sim(x,y),x\ne y$ 即,两个不同元素hash到一个桶的概率和衡量他们之间距离的函数有某种数学关系,那么在加上一些独立实验的trick就能够保证,hash到一个桶中的元素都是距离相近的元素了

case study

假设有 $n$ 个集合 $set_1,\dots,set_n$, 每个集合是一些数字(或者可以将每个集合看做bit vector)表示是否存在某个元素 $e$. 我们要寻找每个集合的相识集合。

Jaccard similarity $sim(A,B)=\frac{|A\cap B|}{|A\cup B|}$.

定义hash 函数 $min-hash(A) =\arg \min_{x \in A} hash(x), \forall x \ne y, hash(x)\ne hash(y) $,(一般来说会选择排列 $\pi$ 作为这样的hash 函数,然而其实通常意义上任意的hash函数都是ok的)。我们会发现 $min-hash$ 的一个好处

$$ \Pr[min-hash(x)=min-hash(y)]= \frac{|A\cap B|}{|A\cup B|} $$

那么这里我们也采用独立实验的思想,选择 $r$ 个这样的hash函数,计算min-hash。两个集合的相似度就可以简单的计算为 $\frac{\#min-hash(A)=min-hash(B)}{r}$.

LSH

将上述计算的 $r$ 个hash函数的值记作 $M_{A,i}$ : 集合 $A$ 在$min-hash_i$ 下的计算值,如果将每个集合的所有 $r$ 个hash值,在用一个 hash映射出去,假设 $A,B$ 两个集合的相似度为 $p$,我们来算算,他们最终进入一个桶的概率.

第 $i$ 个min-hash值相同的概率为 $p$,

最终hash到一个桶的概率为 $p^r$,

没被hash到一个桶的概率为 $1-p^r$,

同理采用独立实验的思想,扩展上面的操作 $b$ 次, 即设置 $b*r$ 个min-hash,分为 $b$ 个band,每个band $r$ 个min-hash,如上。如果有一个band是相同的,即认为他们相同(OR 系统)。

这样他们最终hash到一个桶的概率为 $1 - (1-p^r)^b$,这是一条 $s$ 曲线,需要注意的是,这样做会产生 false positive,与false negtive,分别是曲线与 x轴和 $y=1$ 围成的面积

LSH Theroy

AND 扩展

也就是采用上面的 r 个函数扩展,可以证明, $r$ 个AND 扩展可以变为

$$ (d_1,d_2,p_1^r,p_2^r)-sensitive $$

OR 扩展

$$ (d_1,d_2,1 - (1 - p_1)^b,1-(1-p_2)^b)-sensitive $$

其他距离函数

cosine similarity

random-hyperplane,: $sgn(f_v(x))$

L2 norm

random line projection :$f_\mathbf{v}(\mathbf{x}) = \mathbf{x}\mathbf{v}=\sum x_iv_i$,等距离分桶

code

ref

  1. Anand Rajaraman, Jure Leskovec, and Jeffrey D. Ullman. Mining of Massive Datasets. ch3

版权声明

本作品为作者原创文章,采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

仅允许非商业转载,转载请保留此版权声明,并注明出处