c - 如何理解本地敏感哈希？

我注意到，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。
幻灯片中的示例对我了解余弦相似性的哈希值有很大帮助。

我从Benjamin Van Durme & Ashwin Lall, ACL2010中借了两张幻灯片，并尝试解释LSH系列的余弦距离直觉。

在图中，有两个圆圈，分别是红色和黄色彩色，代表两个二维数据点。我们正在尝试使用LSH查找他们的cosine similarity。

灰线是一些均匀地随机拾取的平面。

根据数据点位于灰线的上方还是下方，我们将此关系标记为0/1。

在左上角，有两行白色/黑色正方形，分别代表两个数据点的签名。每个正方形对应于位0(白色)或1(黑色)。

因此，一旦有了一个平面池，就可以使用它们相对于平面的位置对数据点进行编码。想象一下，当池中有更多平面时，签名中编码的 Angular 差将更接近实际差。因为只有位于两个点之间的平面才会赋予两个数据不同的位值。

现在我们来看两个数据点的签名。如示例所示，我们仅使用6位(正方形)表示每个数据。这是我们拥有的原始数据的LSH哈希。

两个哈希值之间的汉明距离为1，因为它们的签名仅相差1位。

考虑到签名的长度，我们可以计算出它们的 Angular 相似度，如图所示。

我在这里有一些使用余弦相似度的python示例代码(仅50行)。
https://gist.github.com/94a3d425009be0f94751