1. 问题描述

一些应用场景涉及到从大量文档中查找与某个已知文档相似的文档，典型的做法是用文档集中的每个文档和已知文档进行相似度计算，然后获取相似度满足条件的文档。当文档集规模很大时，这种方法因为比较耗时而难以实用，考虑到文档集中和已知文档相似的目标文档数一般不多，对上述方法的一种改进方案是首先快速获取那些可能相似的文档，然后对这个集合中的每个候选文档，进行具体的相似度计算验证。其中快速获取候选集可以通过一种叫做局部敏感哈希（Locality-sensitive hashing，简称 LSH）的技术来实现。

下面首先介绍 LSH 的一般原理以及它的一种形式——Simhash，然后描述通过 Simhash 实现快速查找相似文档的过程。

2. Jaccard 相似度和局部敏感哈希

集合 S 和 T 之间的 Jaccard 相似度是指集合 S 和 T 的交集和并集之间的比值，即 Jaccard_Sim(S, T) = |S∩T|/|S∪T|。

例如：
若 S={a, d}，T={a, c, d}
则 Jaccard_Sim(S, T) = |{a, d}|/|{a, c, d}| = 2/3

一篇文档可能包含上百个元素，对大量的文档，保存这些元素需要很大的空间，我们通过一种方法来减少元素个数，并且通过少量元素依然可以得到原来的 Jaccard 相似度，过程如下：

假设对元素集 E={a, b, c, d, e}上的集合 S1={a, d}，S2={a, c, d}，它们的特征矩阵为：

元素 S1 S2

a 1 1

b 0 0

c 0 1

d 1 1

e 0 0

定义 f 为 E 上的一个映射关系，将 f 作用于 S1，S2 上：

元素 S1 S2 f(S1) f(S2)

a 1 1 f(a) f(a)

b 0 0

c 0 1 f(c)

d 1 1 f(d) f(d)

e 0 0

取 m1 为 f(S1) 中的最小值，即 m1 = min{f(a), f(d)}， m2 为 f(S2) 中的最小值，即 m2 = min{f(a), f(c), f(d)}， 则 m1 与 m2 相等的概率为：

P(m1=m2)
= P(min{f(a), f(b)} = min{f(a), f(c), f(d)})
= |{f(a), f(d)}|/|{f(a), f(c), f(d)}|
= |{a, d}|/|{a, c, d}|
= Jaccard_Sim(S1, S2)

因此，令 m1 为 S1 的一个签名，m2 为 S2 的一个签名，通过少量的签名，能够得到 Jaccard_Sim(S1, S2) 的一个近似值。不难理解，将上面的映射关系 f 替换为一个 E 上的随机哈希函数，这个结论依然成立。

综上所述，对一篇文档使用 n 个随机哈希函数可以得到 n 个签名，称为文档的最小哈希签名，并且通过比较最小哈希签名可以得到两篇文档间的 Jaccard 相似度。

局部敏感哈希（LSH）是指这样的哈希方法：对两篇文档，如果它们相似，则它们的哈希值有较高的概率是相同的。有了文档的最小哈希签名，我们就能实现这种哈希方法。直观的做法是，将包含 b×r 个值最小哈希签名分为 b 等份，每份 r 个，对两个文档，定义 P 为两个文档至少含有1个相同份的概率，显然，文档间的 Jaccard 相似度越高，哈希签名具有相同值的位数就越多，概率 P 就越大。

3. Simhash 算法

Simhash 是一种用单个哈希函数得到文档最小哈希签名的方法，过程为：

将一个 f 维的向量 V 初始化为0；f 位的二进制数 S 初始化为0；

对每一个特征：用传统的 hash 算法对该特征产生一个 f 位的签名 b。对 i=1 到 f：

如果 b 的第 i 位为1，则 V 的第 i 个元素加上该特征的权重；

否则，V 的第 i 个元素减去该特征的权重。

如果 V 的第 i 个元素大于0，则 S 的第 i 位为1，否则为0；

输出 S 作为签名。

对两篇文档，它们的 Simhash 值之间不同位的个数越少（即海明距离越小），它们之间的 Jaccard 相似度越高。

4. 利用 Simhash 查找相似文档

已知两篇文档 Simhash 值之间的海明距离越小，Jaccard 相似度越高，假设我们能够接受的最大海明距离为 K，根据上面对 LSH 的描述，我们可以实现一种快速查找相似文档的方法：

对文档集中的每一篇文档：

查找时：

假设文档集中有一篇文档和查找文档的 Simhash 值间海明距离为 K，则上述查找过程能够找到这个文档（即 Key 命中）的概率：

对 T 次排列，前 K 位至少有一次相同的概率为：1 - (1 - (1-K/N)**P)**T
因此， Key 命中的概率为 1 - (1 - (1-K/N)**P)**T。

例如当 N=64，P=16，K=6，T=8 时，P = 0.791520。

参考

~ullman/mmds/ch3.pdf

您可能感兴趣的文章