0%

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

发表于 分类于

1 应用背景

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

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

2 LSH 基本原理

2.1 LSH 初探

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

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

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

2.2 文档相似度计算

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

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

1
2

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

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

sim(s1,s2)=11/16=0.69sim(s1,s2)=11/16=0.69sim(s_1,s_2)=11/16=0.69

2.3 文档矩阵表示

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

1
2
3
4

s1 = "我 减肥"
s2= "要"
s3 = "他 减肥 成功"
s4 = "我 要 减肥"

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

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

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

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

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

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

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

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

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

2.4 最小 hash 签名

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

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

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

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

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

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

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

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

3 在 cosine 距离中应用 LSH

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

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

下图示例了 LSH 应用于 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

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