如何理解局部性散列?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (12)

我注意到LSH似乎是找到具有高维特性的相似项目的好方法。

阅读完这篇文章http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf后,我仍然对这些公式感到困惑。

有没有人知道一个博客或文章解释简单的方法?

提问于
用户回答回答于

我在LSH看到的最好的教程在书中:海量数据集的挖掘。检查第3章 - 查找类似项目 http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

另外我建议下面的幻灯片:http : //www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf。幻灯片中的示例有助于我理解余弦相似性的哈希算法。

我从ACL2010的Benjamin Van Durme&Ashwin Lall那里借了两张幻灯片并试图解释LSH家庭对余弦距离的直觉。

  • 在图中,有两个带红色黄色的圆圈,代表两个二维数据点。我们试图用LSH 找到它们的余弦相似性
  • 灰线是一些随机挑选的飞机。
  • 根据数据点位于灰线之上还是之下,我们将此关系标记为0/1。
  • 在左上角有两排白色/黑色方块,分别表示两个数据点的签名。每个正方形对应于位0(白色)或1(黑色)。
  • 所以一旦你有一个飞机池,你可以编码数据点与他们的位置各自的飞机。想象一下,当我们在池中有更多的平面时,签名中编码的角度差异更接近实际差异。因为只有位于两点之间的平面会给两个数据不同的位值。

  • 现在我们看看两个数据点的签名。正如在这个例子中,我们只使用6位(方块)来表示每个数据。这是我们拥有的原始数据的LSH哈希值。
  • 两个散列值之间的汉明距离为1,因为它们的签名仅相差1位。
  • 考虑到签名的长度,我们可以计算它们的角度相似性,如图所示。

我有一些示例代码(只有50行)在Python中使用余弦相似性。 https://gist.github.com/94a3d425009be0f94751

用户回答回答于

因为一张图片是千言万语,请查看下面的图片:

扫码关注云+社区