XDRush

局部敏感哈希算法原理及其应用

发表于 |

1 应用背景

最近在计算word2vec中的相似性的时候，遇到了计算量特别巨大的情况，大到计算在hadoop集群上也计算了好几个小时，在本机上初步估计了下，基本上是不可能算出来的（规模是几十万候选集，维度是100）。

在跟我组一个博士交流这个问题时，他给我推荐了LSH（局部敏感哈希）算法，用这个算法之后，发现计算量瞬间降低了近千倍（这里顺带鄙视下自己的知识面）。后来查了下资料，发现LSH在相似性计算方面，已经有大量应用了（特别是处理海量数据）。下面将详细梳理下LSH的原理及其应用。

2 LSH基本原理

2.1 LSH初探

首先来举个例子，比如说要从海量的网页中，找一个和特定网页相似的其他网页，最简单的办法就是去遍历整个数据集，一个一个页面去比较，看看哪个网页和当前页面最相似，计算相似的方法一般是cosine距离或者Jaccard距离，假设抽取的特征就是网页中出现的单词，给每个网页构造一个向量（特征），那么现在的问题转化为：给定一个向量，如何快速的从海量的向量中找到和这个特征相似的一个向量呢？这时候LSH就派上用场啦。哈希大家都知道，它的查找时间复杂度为$O(1)$，有着极高的查找性能，那什么叫做“局部敏感哈希”呢？它的意思就是：如果原来的数据相似，那么hash以后的数据也保持一定的相似性，这就是LSH。为什么说是保持一定的相似性？这主要是由于哈希冲突造成的。

先来看看通常情况下的hash，比如有一个hash函数：$f(x)=(x7)\%10$，有两个数据$x_1=123$，$x_2=124$，那么经过hash函数之后，$f(x_1)=1,f(x_2)=8$，这表明什么呢？*原来的数据很相似，然而hash之后的数据，就差得很远了！说明这个哈希函数并没有保持相似性，也就不是局部敏感哈希。

可以用一句话总结LSH的思想：它是用hash的方法把数据从原空间经过哈希映射到一个新的空间，使得在原空间相似的数据，在新的空间中也相似的概率很大，而在原始空间不相似的数据，在新的空间中相似的概率很小。

2.2 文档相似度计算

按照文本处理的术语，将一个网页当做一篇文档，度量2篇文档相似度有多重方法，欧氏距离、编辑距离、余弦距离、Jaccard距离等，这里就简单的用Jaccard距离为例，集合$S$和集合$T$的Jaccard相似度计算公式为：
Jaccard距离计算公式

当不考虑文档中重复出现的单词时，一篇文档就可以看成一个集合，集合中的元素是一个个分词之后的词：

1
2
s1 = '''从 决心 减肥 的 这 一刻 起 请 做 如下 小 改变 你 做 得 到 么'''
s2 = '''从 决心 减肥 的 这 一刻 起 请 做 如下 小 改变'''

那么，按照上面Jaccard计算公式，

2.3 文档矩阵表示

假设我们有4篇文档，分词之后的表示如下：

1
2
3
4
s1 = "我 减肥"
s2= "要"
s3 = "他 减肥 成功"
s4 = "我 要 减肥"

那么整个vocabulary集合为{我，他，要，减肥，成功}，将文档表示成矩阵向量，行代表vocabulary集合中的元素，列表示文档，只有文档j出现元素i时，对应的矩阵$M[i][i]=1$，否则$M[i][i]=0$，按照这种方式将上面4篇文档组织成如下形式：
文档矩阵表示

2.3 最小哈希(min-hashing)定义

我们将最小hash的定义如下：特征矩阵按行进行一个随机的排列之后，第一个列值为1的行的行号。举例说明如下，假设之前的一个特征矩阵按行进行一次随机排列之后的结果如下：
按行随机排列依次

那么按照最小哈希的定义，以上4篇文档的最小哈希值分别为：
$h(S_1)=3, h(S_2)=5, h(S_3)=1, h(S_4)=3$

那么为什么要定义最小哈希呢？实际上，两列的最小哈希最就是这两列的Jaccard相似度的一个估计，换句话说，两列最小hash值相同的概率与其相似度相等，也就是$Prob(h(S_i)=h(S_j)) = sim(S_i, S_j)$。

为什么会相等呢？我们来单独考虑$S_i$和$S_j$这两列，它们形成特征矩阵对应的行所有可能的结果可以分为以下三种情况：

  • A类：两列的值都为1
  • B类：一列的值为1，另一列的值为0
  • C类：两列的值都为0

一般情况下，特征矩阵比较稀疏，这就导致大部分的行都是属于C类，只有少数行数据A类和B类，但也只有A类和B类的行决定了$sim(S_i,S_j)$，假设A类的行有a个，B类的行有b个，那么$sim(S_i,S_j)=a/(a+b)$。

现在，只需要证明对矩阵进行随机的行变换，两个的最小哈希值相等的概率$Prob(h(S_i)=h(S_j)) = a/(a+b)$即可。因为C类对计算相似性没有用，可以将所有的C类全部删除，那么第一行不是A类就是B类，如果第一行是A类，那么$h(S_i)=h(S_j)$，因此$Prob(h(S_i)=h(S_j)) = Prob(删掉C类行之后，第一行为A类)=A类行的数目/(所有行的数目) = a/(a+b)$，这就是最小哈希的神奇之处。

2.4 最小hash签名

有了最小hash还不够，因为一次最小hash只是一次独立的随机事件，大数定理告诉我们，只有多次重复随机事件才能造就必然。选择n个随机排列作用于特征矩阵，得到n个最小哈希值，$h_1,h_2,…,h_n$，这n个最下hash值组成一个n维向量，称之为最小hash签名，两列的最小hash签名的相似度即为两列的Jaccard相似度的估计。

2.5 基于最小hash的局部敏感哈希

假设前面的工作中，我们已经将一个文档的集合转化为一个最小签名，虽然这个签名已经大大的压缩了集合的空间，但要计算两列的相似度还是需要两两计算签名矩阵两列的相似度，如果有n篇文档，两两比较的次数为$n*(n-1)/2$，当n较大时，计算的复杂度依旧很高。接下来就看局部敏感哈希怎么个做法。

我们对签名矩阵按行进行分组，将矩阵分成b组，每组由r行组成，下面的实例将一个签名矩阵分成6组，每组由3行组成：
签名矩阵分组

上面每一个分组中，每一列表示一个文档经过最小hash签名之后对应的向量。分组之后，对最小签名向量的每一组进行hash，各个组设置不一样的桶空间，只要两列有一组的最小签名部分相同，那么这两列就会hash到同一个桶中而成为候选相似项。上面签名的分析我们知道，对于某个具体的行，两个签名相同的概率p=两列的相似度=$sim(S_i,S_j)$，并且有：

  • 在某个组中所有行的两个签名都相同的概率是$p^r$
  • 在某个组中至少有一对签名不相等的概率是$1-p^r$
  • 在每一组中至少有一对签名不相等的概率是$(1-p^r)^b$
  • 至少有一个组的所有对签名相等的概率是$1-(1-p^r)^b$

于是，两列称为候选相似对的概率是$1-(1-p^r)^b$，它的采样值以及曲线如下图所示：
采样值
采样曲线

可以看到，当两篇文档的相似度为0.8时，它们hash到同一个桶而成为候选对的概率为0.9996，而当他们的相似度为0.3时，它们成为候选对的概率为0.0475；因此，局部敏感哈希解决了让相似的对以高概率hash到同一个桶中，而不相似的项hash到不同的桶的问题。

3 在cosine距离中应用LSH

上面的章节介绍完了LSH的核心思想，但是在实际应用中，在计算距离时，cosine距离应用相对更广泛一些，那么当相似度是cosine相似性时，hash函数是什么呢？

它用了一个叫随机超平面的概念。就是随机的生成一些超平面，哈希方法是看一个特征向量对应的点，是在平面的哪一侧：
随机超平面

下图示例了LSH应用于cosine的一个例子：
局部敏感哈希计算cosine示意图

随机生成3个超平面{y1, y2, y3}，在平面上有2个点A和B，根据上面的定义，很容易知道A对应的值为[1, 1, 1]，B对应的向量为[-1, -1, 1]，再以A，B的向量来计算A,B之间的相似性就更简单了。

下面以一段代码来进一步说明LSH在计算cosine距离上的应用：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#_*_coding:utf-8_*_
import numpy as np
import math
## 获取签名
def get_signature(user_vector, rand_proj):
    res = 0
    for p in rand_proj:
        res = res << 1
        val = np.dot(p, user_vector)
        if val >= 0:
            res |= 1
    return res
## 获取输入数字中二进制值中1的个数
def nnz(num):
    if num == 0:
        return 0
    res = 1
    while num:
        res += 1
        num = num & (num - 1)
    return res
## 获取真正的cosine距离
def angular_similarity(a, b):
    dot_prod = np.dot(a, b)
    sum_a = sum(a**2) **.5
    sum_b = sum(b**2) **.5
    cosine = dot_prod/(sum_a * sum_b)
    theta = math.acos(cosine)
    return 1.0 - (theta/math.pi)
if __name__ == "__main__":
    dim = 200
    d = 2 ** 10
    nruns = 24
    avg = 0
    for run in xrange(nruns):
        user1 = np.random.randn(dim)
        user2 = np.random.randn(dim)
        ## 生成随机超平面
        randv = np.random.rand(d, dim)
        r1 = get_signature(user1, randv)
        r2 = get_signature(user2, randv)
        xor = r1^r2
        true_sim, hash_sim = (angular_similarity(user1, user2), (d - nnz(xor))/float(d))
        diff = abs(hash_sim - true_sim)/true_sim
        avg += diff
        print "true: %.4f, hash: %.4f, diff: %.4f" % (true_sim, hash_sim, diff)
    print "avg diff: ", avg / nruns

如上面代码所示，采用局部敏感哈希算法，将大大降低计算复杂度。