如何理解局部敏感哈希？(How to understand Locality Sensitive H

我注意到，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 。 在幻灯片中的例子帮助了我很多理解为余弦相似散列。

我借用两个幻灯片本杰明·范·Durme＆阿什温拉尔，ACL2010并试图解释LSH家庭的直觉的余弦距离有点。

• 在图中，有两个圆W / 红色和黄色 ，代表两个二维数据点。 我们正在努力寻找他们的余弦相似度使用LSH。
• 灰线是一些均匀随机挑选的平面。
• 根据数据点是否位于上方或灰色线以下，我们纪念该关系为0/1。
• 在左上角，有两行的白色/黑色方块，分别表示两个数据点的签名。 每个正方形对应于位0（白色）或1（黑色）。
• 所以一旦你拥有私人飞机的一个游泳池，您可以编码与他们的位置分别在平面上的数据点。 试想一下，当我们在游泳池有更多的飞机，在签名编码的角度差更接近实际的差异。 因为只有驻留在两个点之间的双雄会给出两个数据不同的位值。

• 现在我们来看看两个数据点的签名。 如在示例中，我们只使用6比特（正方形）来表示每个数据。 这是LSH哈希因为我们有原始数据。
• 两个哈希值之间的汉明距离是1，因为它们的签名仅由1位不同。
• 考虑到签名的长度，就可以计算出它们的角度相似性如该曲线图所示。

我有一些示例代码（仅50行）在python这里其通过使用余弦相似性。 https://gist.github.com/94a3d425009be0f94751

Answer 2:

在矢量空间鸣叫可以是高维数据的一个很好的例子。

看看上应用局部敏感哈希到微博找到类似的人我的博客文章。

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的全局参数阈值相似度秒 。
• 它是由你来定义什么足够的阈值S是你的问题。

必须强调的是不同的相似性措施有LSH的不同实现是非常重要的。

在我的博客，我想详细解释LSH为minHashing（Jaccard相似度量）和simHashing（余弦距离测量）的情况下。 我希望你觉得它有用： https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Answer 5:

我是一个视觉化的人。 下面是我的什么作品作为一种直觉。

说你们每个人要搜索近似东西，如一个苹果，一个立方体，椅子物理对象。

我的一个LSH直觉是，它是类似于把这些物体的阴影。 如果你喜欢拍摄3D立方体的阴影，你得到一个二维方形像一张纸，或3D球体将让你在一张纸的圆圈状阴影。

最后，还有一个搜索问题（其中在文本中的每个字可以是一维）许多多于三维但阴影比喻还是很实用的给我。

现在，我们可以有效地在软件中比较位的字符串。 的固定长度的位串是有点儿，或多或少，就象是在单一尺寸的线。

因此，与一个LSH，我项目对象的阴影最终为点（0或1）上的单个固定长度的线/位串。

整个关键是要采取阴影，使得它们仍然是有意义的低维例如，他们像在可以识别一个足够好的方式原始对象。

透视多维数据集的2D绘图告诉我这是一个立方体。 但我不能轻易区分一个3D立方体阴影二维方形无视角：他们都看起来像一个方形我。

我如何展示我的目标光将决定如果我得到一个很好的识别阴影或没有。 因此，我认为“好” LSH作为一个会变成我的对象在光的前方，从而使他们的影子是作为代表我的对象最好辨认。

因此，要回顾一下：我觉得事情有LSH索引像一个立方体，桌子，椅子或物理对象，我预测这些公司的2D，并最终沿着一条线（位串）的阴影。 和“好” LSH“功能”是我目前在光前我的对象来获得在2D平地大致区分的形状，后来我的位串。

最后，当我要搜索某个对象我都有些相似的对象，我索引，我想借此“查询”对象的使用相同的方式来表达我的目标在光前面的阴影（最终结束了一个位串太）。 现在我可以比较的相似与所有我的其他索引位的字符串，位串是用于搜索我的整个对象，如果我发现我介绍对象，我的光了良好的和可识别的方式代理。

文章来源: How to understand Locality Sensitive Hashing?