如何理解局部敏感哈希？

Question

我注意到LSH似乎是一种寻找具有高维属性的类似项目的好方法.

在阅读了论文http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf之后,我仍然对这些公式感到困惑.

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

Answer 1

我在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

Answer 2

向量空间中的推文可以是高维数据的一个很好的例子.

查看我的博客文章,将Locality Sensitive Hashing应用于推文以找到类似的推文.

http://micvog.com/2013/09/08/storm-first-story-detection/

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

http://micvog.files.wordpress.com/2013/08/lsh1.png

希望能帮助到你.@mvogiatzis

Answer 3

这是斯坦福大学的一个演讲,解释了它.这给我带来了很大的不同.第二部分更多是关于LSH,但第一部分也包括它.

概述图片(幻灯片中还有更多内容):

高维数据中的邻近搜索 - 第1部分:http: //www.stanford.edu/class/cs345a/slides/04-highdim.pdf

高维数据中的邻近搜索 - 第2部分:http: //www.stanford.edu/class/cs345a/slides/05-LSH.pdf

Answer 4

• LSH是一个过程,它将一组文档/图像/对象作为输入,并输出一种哈希表.
• 该表的索引包含文档,使得同一索引上的文档被认为是相似的,而不同索引上的文档是" 不相似 "的.
• 当类似取决于指标体系,并在阈值相似度小号这就像LSH的全局参数.
• 它是由你来定义什么足够的门槛小号是你的问题.

重要的是要强调不同的相似性度量具有不同的LSH实现.

在我的博客中,我试图彻底解释LSH的minHashing(jaccard相似性度量)和simHashing(余弦距离度量)的情况.我希望你觉得它很有用:https: //aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/