我注意到 LSH 似乎是找到具有高维度属性的类似项目的好方法。
阅读论文http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf后，我仍然对这些公式感到困惑。
有谁知道解释这个简单方法的博客或文章？
问问题
71396 次
6 回答
256
我见过的关于 LSH 的最好的教程在这本书中：Mining of Massive Datasets。检查第 3 章 - 查找类似项目 http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf
我还推荐下面的幻灯片： http ://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf 。幻灯片中的示例有助于我理解余弦相似度的散列。
我从 ACL2010 的Benjamin Van Durme 和 Ashwin Lall那里借了两张幻灯片，并尝试解释一下 LSH Families 对于余弦距离的直觉。
- 在图中，有两个红色和黄色的圆圈，代表两个二维数据点。我们正在尝试使用 LSH找到它们的余弦相似度。
- 灰线是一些均匀随机选取的平面。
- 根据数据点是位于灰线之上还是之下，我们将此关系标记为 0/1。
- 左上角有两排白/黑方块，分别代表两个数据点的签名。每个方块对应一个位 0（白色）或 1（黑色）。
- 因此，一旦您拥有一个平面池，您就可以使用它们相对于平面的位置对数据点进行编码。想象一下，当我们在池中有更多平面时，签名中编码的角度差异更接近实际差异。因为只有位于两点之间的平面才会给两个数据不同的位值。
- 现在我们看看两个数据点的签名。如示例所示，我们仅使用 6 位（正方形）来表示每个数据。这是我们拥有的原始数据的 LSH 哈希。
- 两个散列值之间的汉明距离为 1，因为它们的签名仅相差 1 位。
- 考虑到签名的长度，我们可以计算它们的角度相似度，如图所示。
我在 python 中有一些使用余弦相似度的示例代码（只有 50 行）。 https://gist.github.com/94a3d425009be0f94751
于 2012-10-19T04:45:20.427 回答
35
向量空间中的推文可以是高维数据的一个很好的例子。
查看我的博客文章，将 Locality Sensitive Hashing 应用于推文以查找类似的推文。
http://micvog.com/2013/09/08/storm-first-story-detection/
因为一张图片是一千个单词，请查看下面的图片：
http://micvog.files.wordpress.com/2013/08/lsh1.png
希望能帮助到你。@mvogiatzis
于 2013-09-18T21:52:06.267 回答
21
这是斯坦福大学的一个演示文稿，对此进行了解释。这对我来说有很大的不同。第二部分更多关于 LSH，但第一部分也涵盖了它。
概述图片（幻灯片中有更多内容）：
高维数据中的近邻搜索 - 第 1 部分：http: //www.stanford.edu/class/cs345a/slides/04-highdim.pdf
高维数据中的近邻搜索 - 第 2 部分：http: //www.stanford.edu/class/cs345a/slides/05-LSH.pdf
于 2014-03-24T09:14:59.970 回答
10
- LSH 是将一组文档/图像/对象作为输入并输出一种哈希表的过程。
- 该表的索引包含文档，使得相同索引上的文档被认为是相似的，而不同索引上的文档是“不同的”。
- 其中相似性取决于度量系统以及阈值相似性s，其作用类似于 LSH 的全局参数。
- 您可以为您的问题定义适当的阈值s 。
重要的是要强调不同的相似性度量有不同的 LSH 实现。
在我的博客中，我尝试对 minHashing（jaccard 相似性度量）和 simHashing（余弦距离度量）的情况进行彻底的 LSH 解释。我希望你觉得它有用： https ://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/
于 2018-01-27T19:18:25.150 回答
2
我是一个视觉的人。这对我来说是一种直觉。
假设您要搜索的每个事物大致都是物理对象，例如苹果、立方体、椅子。
我对 LSH 的直觉是拍摄这些物体的阴影是相似的。就像如果你拍摄 3D 立方体的阴影，你会在一张纸上得到一个 2D 正方形，或者一个 3D 球体会给你一张纸上的圆形阴影。
最终，搜索问题中的维度不止三个（文本中的每个单词都可能是一个维度），但阴影类比对我来说仍然非常有用。
现在我们可以有效地比较软件中的位串。固定长度的位串或多或少有点像单一维度中的一条线。
因此，使用 LSH，我最终将对象的阴影投影为单个固定长度的线/位字符串上的点（0 或 1）。
整个技巧是使阴影在较低维度上仍然有意义，例如它们以可以识别的足够好的方式与原始对象相似。
透视立方体的 2D 绘图告诉我这是一个立方体。但是我无法在没有透视的情况下轻易地区分 2D 正方形和 3D 立方体阴影：它们在我看来都像正方形。
我如何将我的物体呈现在灯光下将决定我是否得到一个可识别的良好阴影。所以我认为一个“好”的 LSH 可以将我的物体转向灯光前，这样它们的阴影就可以最好地识别为代表我的物体。
回顾一下：我认为用 LSH 索引的东西是像立方体、桌子或椅子这样的物理对象，我将它们的阴影投射到 2D 中，并最终沿着一条线（一条线）投射。一个“好的”LSH“功能”是我如何在灯光前呈现我的对象，以便在 2D 平地和后来的位串中获得大致可区分的形状。
最后，当我想搜索我拥有的对象是否与我索引的某些对象相似时，我使用相同的方式获取这个“查询”对象的阴影，以在灯光前呈现我的对象（最终以字符串也是）。现在，我可以比较该位字符串与我所有其他索引位字符串的相似程度，如果我找到一种好的且可识别的方式将我的对象呈现在我的灯光下，它是搜索我的整个对象的代理。
于 2017-12-18T17:42:21.083 回答
0
作为一个非常简短的tldr答案：
局部敏感散列的一个示例可能是首先在您的输入空间中随机设置平面（带有旋转和偏移）以进行散列，然后将您的点放到该空间中的散列中，并且对于每个平面，您测量该点是否为高于或低于它（例如：0 或 1），答案是哈希。因此，如果用之前或之后的余弦距离测量，空间中相似的点将具有相似的哈希值。
您可以使用 scikit-learn 阅读此示例：https ://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer
于 2019-06-22T07:29:07.580 回答