如何理解区域敏感性散列？

小开

最佳答案

我所看到的关于 LSH 的最好的教程是在书中: 海量数据集的挖掘。检视第三章-寻找相似的项目 Http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

我从 Benjamin Van Durme & Ashwin Lall，ACL2010借了两张幻灯片，并试图解释一点 LSH 家庭的余弦距离的直觉。 enter image description here

在图中，有两个圆圈 w/红色和黄色着色，表示两个二维数据点。我们试图找到他们的余弦距离使用 LSH。
灰线是一些均匀随机选择的平面。
根据数据点位于灰线之上还是之下，我们将这个关系标记为0/1。
在左上角，有两行白色/黑色正方形，分别代表两个数据点的签名。每个正方形对应一个位0(白色)或1(黑色)。
因此，一旦有了一个平面池，就可以对数据点进行编码，使它们的位置与平面相对应。想象一下，当我们在池中有更多的平面时，编码在签名中的角度差更接近实际的差。因为只有位于两点之间的平面才会给两个数据不同的位值。

enter image description here

我在 python 中有一些示例代码(只有50行) ，它使用的是余弦距离。 Https://gist.github.com/94a3d425009be0f94751

小开

矢量空间中的 tweet 可以是高维数据的一个很好的例子。

你可以看看我的博客文章，关于如何将本地敏感哈希应用到 tweet 中，以找到类似的方法。

因为一张图片就是一千个单词，请看下面的图片:

希望能有帮助。 @ mvogiatzis

小开

这是斯坦福大学的演讲解释。这对我来说意义重大。第二部分是更多关于 LSH，但第一部分也涵盖了它。

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

enter image description here

小开

我是一个视觉型的人，以下是我的直觉。

假设你想搜索的每一样东西大致都是物理对象，比如苹果、立方体、椅子。

我对 LSH 的直觉是，它类似于采取这些对象的阴影。比如，如果你取一个3D 立方体的阴影，你会在一张纸上得到一个2D 正方形的阴影，或者一个3D 球体会在一张纸上得到一个圆形的阴影。

最终，在一个搜索问题中有许多超过三个维度(文本中的每个单词可以是一个维度) ，但是影子类比对我来说仍然非常有用。

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

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

整个技巧是采取阴影，使他们仍然有意义的较低维度，例如，他们相似的原始对象在一个足够好的方式，可以识别。

一个立方体的二维透视图告诉我这是一个立方体。但是，如果没有透视图，我无法轻易区分2D 正方形和3D 立方体阴影: 它们在我看来都像一个正方形。

我如何呈现我的对象的光线将决定我是否得到一个良好的可识别的阴影与否。所以我认为一个“好”的 LSH 是一个将我的物体在光线前面，使他们的阴影是最好的识别代表我的对象。

总结一下: 我把 LSH 作为物理对象来索引，比如一个立方体、一张桌子或者一把椅子，我将它们的阴影投影到2D 中，最终沿着一条线(一个小字符串)。一个“好的”LSH“函数”是我如何在一盏灯前呈现我的物体，以获得一个近似可区分的形状在2D 平面和后来我的位字符串。

最后，当我想搜索一个对象是否类似于我索引的一些对象时，我使用同样的方法将我的对象显示在光线前(最终也以一个位字符串结束)来获取这个“查询”对象的阴影。现在我可以比较一下这个位串和我其他所有的索引位串有多相似如果我找到一个好的，可识别的方法把我的物体呈现给我的光，它就是一个搜索我的整个物体的代理。

小开

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

在我的博客中，我试图为 minHash (jaccard 相似性度量)和 simHash (余弦距离度量)的例子详细解释 LSH。我希望你会觉得它很有用: Https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

小开

作为一个非常简短的 剧情回顾回答:

区域敏感散列的一个例子可以是首先在你的输入空间中随机设置平面(带有旋转和偏移量) ，然后在空间中丢弃你的点散列，对于你测量的每个平面，如果点在它的上面或下面(例如: 0或1) ，答案是散列。所以空间中相似的点，如果用余弦距离来度量，在之前或之后，也会有相似的散列。