本文转至：Locality Sensitive Hashing
当需要从大量文档中检测相似文档，使用Min hashing+LSH（Locality-sensitive hashing）需要有如下几个大的步骤：

  • Shingling
  • Min hashing
  • LSH
    steps

Shingling

将每个文档转换为一组长度为k的字符（也称为k-shingles或k-gram），即将每个文档转换成k-shingles表示.
例如有一个文档：“Nadal”，如果将其转换成为2-shingles表示为{Na，ad，da，al}.

  • 相似的文档理论上会共享shingles
  • 一篇文章，个别词做替换或段落重新排序对shingles影响不大
  • 通常k的取值为8-10

Jaccard指数

我们将每个文档使用shingles形式表示后，我们需要使用一个指标表示文档间的相似度，Jaccard指数就是一个很好的选择，使用Jaccard指数表示A和B两个文档的相似度可以被定义为：

J(A,B)=∣A∩B∣∣A∪B∣J(A,B)=\frac {|A \cap B|} { |A \cup B|}

加入A为“Nadal”，B为“Nadia”，使用2-shingles表示后：

  • A：{Na, ad, da, al}
  • B: {Na, ad, di, ia}
    Jaccard指数为：2/6

上面的算法看似简单，但是如果需要进行大量文档的相似度比对，那么算法的时间复杂度和空间复杂度都会极具上升。

散列的想法是使用散列函数H将每个文档转换为签名。假设我们的语料库中的文档用d表示：

  • H(d)是文档签名，与原文档相比，它的内存占用足够小
  • 如果文档d1d_1和d2d_2相似度很高，那么H(d1)==H(d2)H(d1)==H(d2)相等的概率也会很高

对于使用Jaccard指标度量文档相似度，min hash是最好的选择。

Min Hash

min hash算法的核心在于：

  • 步骤1：按行随机排序文档的shingle矩阵
    permutation
    • 步骤2：Hash函数值就是C列中第一次出现1所在的行索引，该值就是min-hash

如此重复的进行n次排序创建列的签名。
例如对下面4个文档做三次排序，那么得到的签名矩阵如下：
1
2

如上图，那么C1和C3的相似度为2/3，两个签名的相似度近似于Jaccard相似性，签名越长，则错误率越低。

另外，我们可以发现，使用min-hash后我们不但保持了文档的相似性，同时也消除了向量的稀疏性。

在实际场景中，如果我们要生成100个签名的min-hash，按照理论的话，我们需要对shingle矩阵做100次可重现的按行随机排序，但是随着文档数量的增强，这个实现代价较高， 所以通常我们会选择100个hash函数，并将文档的shingles串，逐个串hash，每次去取hash最小，这样100个hash函数就会生成长度为100的签名列。
大致思想就是把文档看作一个词袋，从袋子里抽取100次，用这100个词代表该文档，如果两个文档抽取到的这100个词相似，那两个文档则相似。

LSH（Locality-sensitive hashing）

当文档量较大是，我们希望能够加速相似文档的查找，而非对所有文档进行线性比较。那么LSH的思想就是，假如我们输入两个文档的签名，则会告诉我们这两个文档是否构成候选对。
对于min-hash签名矩阵：

  • 签名矩阵M的Hash列使用多个Hash函数
  • 如果至少有一个Hash函数将2个文档映射至同一个hash桶中，我们则可以把这两个文档看作候选对
    那么现在的问题就是如何创建不同的hash函数，这里我们使用波段分区。
    算法的思路为：
  • 将签名矩阵划分为b个波段，每个波段具有r行
  • 对于每个波段，将其hash映射至具有k个桶的hash表中
  • 候选列对是那些至少有一个波段被映射至同一个桶中的签名列
  • 可以通过调整波段数量或者每个波段的行数来控制相似对数量
Band partition

理想情况下，对于每个波段，我们希望k等于列在波段内可以采用的所有可能值组合，即理想情况我们不希望产生碰撞，但是这显然不可能，否则k将是一个庞大的数字，这在计算上是不可行的。例如一个波段有5行，签名中的元素是32位整数，那么在这种情况下k将是（2³²）⁵~1.4615016e+ 48，通常k约为100万。

如果波段数量（b）较多，就意味着需要较多的hash函数，随之，每个波段的行数（r）也会减小。直观地说，这意味着我们增加了找到候选对的概率。

假如签名举证有100行，考虑如下两种场景：
（1）b=10 r=10
（1）b=20 r=5
第二种情况下，2个文档出现在同一个桶的概率更高，因为较多波段且少量签名元素的比较意味着机会更多。较高的b意味着较低的相似性阈值，而较低的b意味着较高的相似性阈值。

下面使用一个例子来理解上面的观点：

  • 100000个文档，签名长度为100
  • 签名举证即为：100*100000
  • 波段数量b=20，每个波段行数r=5
  • 相似度阈值t：80%

我们希望2个文档（D1和D2）具有80％的相似性，那20个波段中的至少一个波段中会被映射至同一个桶中。

  • 那么在特定的一个波段中，文档D1和D2相同，即5行相同的概率为：(0.8)⁵=0.328
    • 在20个波段中，文档D1和D2所有波段不同的概率为 ：(1–0.328)^20 = 0.00035

这就意味着在相似度为0.8时，我们有0.035%的概率漏召回文档。

假如我们希望两个相似度为30%的文档D3 和 D4，20个段的任何一个都不会被映射至同一个hash桶中。

  • 那么在特定波段中，文档D3和D4相同，即5行相同的概率为：(0.3)⁵ = 0.00243
  • D3和D4在20个频带中的至少一个中是相似的概率为：1 — (1–0.00243)^20 = 0.0474