如何理解本地敏感哈希?
c
machine-learning
5
0

我注意到,LSH似乎是查找具有高维属性的类似项目的好方法。

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

有谁知道博客或文章解释这种简单方法?

参考资料:
Stack Overflow
收藏
评论
共 5 个回答
高赞 时间 活跃

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

收藏
评论

我是一个有视觉感的人。这是我的直觉。

假设您要搜索的每件事物大约都是物理对象,例如苹果,立方体,椅子。

我对LSH的直觉是,采取这些对象的阴影类似于。就像您拍摄3D立方体的阴影一样,您在一张纸上会得到一个2D正方形的阴影,或者3D球面会在一张纸上得到一个像圆形的阴影。

最终,一个搜索问题涉及的维数不止三个(其中文本中的每个单词可以是一个维),但是影子类比对我来说仍然非常有用。

现在,我们可以有效地比较软件中的位字符串。固定长度的位串或多或少有点像一维的线。

因此,使用LSH,我最终将对象的阴影投影为单个固定长度的线/位字符串上的点(0或1)。

整个技巧是采取阴影,使其在较低维度上仍然有意义,例如,它们以足以被识别的良好方式类似于原始对象。

透视图中的多维数据集的2D图告诉我这是一个多维数据集。但是我无法轻易地将2D正方形与3D立方体阴影区分开来:它们对我来说都像正方形。

我如何将物体呈现在灯光下将决定我是否能获得良好的可识别阴影。因此,我认为一种“好的” LSH可以将我的物体置于灯光前,从而最好地将其阴影识别为代表我的物体。

回顾一下:我认为用LSH进行索引的对象是诸如多维数据集,桌子或椅子之类的物理对象,我将它们的阴影以2D投影,最后沿着一条线(一点串)投影。而“良好的” LSH“功能”就是我将物体呈现在灯光前的方式,以便在2D平坦地带以及后来的我的钻头串中获得近似可分辨的形状。

最后,当我想搜索我所拥有的对象是否与我索引的某些对象相似时,我使用相同的方式拍摄该“查询”对象的阴影,以将我的对象呈现在灯光前(最终以一点点结束)字符串)。现在,我可以比较该位字符串与所有其他索引的位字符串的相似程度,如果我找到了一种很好的且可识别的方式将我的对象呈现给我的物体,则该字符串可以搜索整个对象。

收藏
评论
  • LSH是将一组文档/图像/对象作为输入并输出一种哈希表的过程。
  • 该表的索引包含文档,因此位于同一索引上的文档被视为相似 ,而位于不同索引上的文档则被视为“ 相异 ”。
  • 其中, 相似度取决于度量系统,也取决于阈值相似度s ,它类似于LSH的全局参数。
  • 它是由你来定义什么足够的阈值S是你的问题。

在此处输入图片说明

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

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

收藏
评论

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

查阅我的博客文章,其中将本地敏感哈希应用于推文以查找类似的内容。

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

并且由于一张图片是一千个单词,因此请检查以下图片:

在此处输入图片说明 http://micvog.files.wordpress.com/2013/08/lsh1.png

希望能帮助到你。 @mvogiatzis

收藏
评论

这是斯坦福大学的演讲,对此进行了解释。这对我来说意义重大。第二部分是关于LSH的更多内容,但第一部分也将介绍它。

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

在此处输入图片说明

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

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

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号