我注意到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查找它们的余弦相似性。
• 灰色线条是一些随机均匀选取的平面。
• 根据数据点位于灰色线条的上方还是下方，我们将这种关系标记为0/1。
• 在左上角，有两行白/黑方块，分别代表两个数据点的签名。每个方块对应一个位0（白）或1（黑）。
• 所以一旦你有一组平面，你就可以根据数据点相对于平面的位置对其进行编码。想象一下，当我们有一组更多的平面时，签名中编码的角度差异会更接近实际差异。因为只有位于两个点之间的平面才会给两个数据不同的位值。

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

我在这里有一些用Python编写的示例代码（仅50行），使用的是余弦相似性。https://gist.github.com/94a3d425009be0f94751