我为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
0
我注意到,LSH似乎是查找具有高维属性的类似项目的好方法。
在阅读了http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf论文之后,我仍然对这些公式感到困惑。
有谁知道博客或文章解释这种简单方法?