blocks|key|455058|text|向量空间中的Tweets就是高维数据的一个很好的例子。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|455059|请查看我的博客文章，将位置敏感的散列应用到tweet中，以找到类似的推文。|455060|http://micvog.com/2013/09/08/storm-first-story-detection/|offset|length|455061|因为一张图片是千言万语，所以看看下面的图片：|455062|​|455063|📷|atomic|455064|http://micvog.files.wordpress.com/2013/08/lsh1.png|455065|希望能有所帮助。@mvogiatzis|455066|entityMap|0|LINK|mutability|MUTABLE|url|1|IMAGE|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/dee5b9492bb55cb123058377cd25bdc6.png|imageAlt|2^0|0|0|0|1L|0|0|0|0|0|1|1|0|0|1E|2|0|0^^$0|@$1|2|3|4|5|6|7|16|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|17|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|18|8|@]|9|@$F|19|G|1A|1|1B]]|A|$]]|$1|H|3|I|5|6|7|1C|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1D|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|1E|8|@]|9|@$F|1F|G|1G|1|1H]]|A|$]]|$1|O|3|P|5|6|7|1I|8|@]|9|@$F|1J|G|1K|1|1L]]|A|$]]|$1|Q|3|R|5|6|7|1M|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|1N|8|@]|9|@]|A|$]]]|T|$U|$5|V|W|X|A|$Y|E]]|Z|$5|10|W|11|A|$12|13|14|-4]]|15|$5|V|W|X|A|$Y|P]]]]

Tweets in vector space can be a great example of high dimensional data.

Check out my blog post on applying Locality Sensitive Hashing to tweets to find similar ones. 

<a href="http://micvog.com/2013/09/08/storm-first-story-detection/" rel="noreferrer">http://micvog.com/2013/09/08/storm-first-story-detection/</a>

And because one picture is a thousand words check the picture below:

<img src="https://i.stack.imgur.com/cKVUs.png" alt="enter image description here">
<a href="http://micvog.files.wordpress.com/2013/08/lsh1.png" rel="noreferrer">http://micvog.files.wordpress.com/2013/08/lsh1.png</a>

Hope it helps.
@mvogiatzis

blocks|key|455121|text|这是来自斯坦福大学的演示文稿，解释了这一点。这对我来说有很大的不同。第二部分更多的是关于LSH，但第一部分也涵盖了它。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|455122|概述图片(幻灯片中有更多内容)：|455123|​|455124|📷|atomic|offset|length|455125|455126|高维数据中的近邻搜索--+Part1：http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf|455127|高维数据中的近邻搜索--+Part2：http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf|455128|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/98ef6ffce1a98a6f50e7227af6f51d28.png|imageAlt|1|LINK|MUTABLE|url|http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf|2|http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf^0|0|0|0|0|1|0|0|0|J|1M|1|0|J|1I|2|0^^$0|@$1|2|3|4|5|6|7|15|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|16|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|17|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|18|8|@]|9|@$I|19|J|1A|1|1B]]|A|$]]|$1|K|3|E|5|6|7|1C|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1D|8|@]|9|@$I|1E|J|1F|1|1G]]|A|$]]|$1|N|3|O|5|6|7|1H|8|@]|9|@$I|1I|J|1J|1|1K]]|A|$]]|$1|P|3|-4|5|6|7|1L|8|@]|9|@]|A|$]]]|Q|$R|$5|S|T|U|A|$V|W|X|-4]]|Y|$5|Z|T|10|A|$11|12]]|13|$5|Z|T|10|A|$11|14]]]]

Here's a presentation from Stanford that explains it. It made a big difference for me. Part two is more about LSH, but part one covers it as well.

A picture of the overview (There are much more in the slides):

<img src="https://i.stack.imgur.com/HYPWE.png" alt="enter image description here">

Near Neighbor Search in High Dimensional Data - Part1:
<a href="http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf" rel="noreferrer">http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf</a>

Near Neighbor Search in High Dimensional Data - Part2:
<a href="http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf" rel="noreferrer">http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf</a>

blocks|key|455170|text|我是一个视觉的人。这就是我的直觉。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|455171|假设你要搜索的每一样东西都是物理对象，如苹果、立方体、椅子。|455172|我对LSH的直觉是，它类似于拍摄这些物体的阴影。例如，如果你把一个三维立方体的阴影放在一张纸上，你会得到一个2D方形的阴影，或者一个三维球体会让你在一张纸上得到一个圆形的阴影。|455173|最终，搜索问题中存在的不仅仅是三维问题(文本中的每个单词都可以是一个维度)，但shadow类比对我仍然非常有用。|offset|length|455174|现在我们可以有效地比较软件中的位串。固定长度的位串有点，或多或少，就像一维的一条线。|455175|因此，使用LSH，我最终将对象的阴影投影为单个固定长度的线/位字符串上的点(0或1)。|455176|整个技巧是采取阴影，使它们在较低的维度仍然有意义，例如，它们以足够好的方式与原始对象相似，可以识别。|455177|透视中的立方体的2D图形告诉我这是一个立方体。但是，如果没有透视，我很难区分2D正方形和3D立方体阴影:在我看来，它们都像一个正方形。|455178|我如何将我的物体呈现给光线将决定我是否得到一个好的可识别的阴影。因此，我认为一个“好的”LSH会将我的物体转到光的前面，这样它们的阴影就可以很好地识别为代表我的物体。|455179|所以重述一下:我把要用LSH索引的东西想象成像立方体、桌子或椅子这样的物理对象，然后在2D中投影它们的阴影，最终沿着一条线(位字符串)投影。一个“好的”LSH“函数”是我如何将我的物体呈现在光的前面，以便在2D平面中获得大致可区分的形状，然后是我的位串。|455180|最后，当我想要搜索我拥有的对象是否与我索引的一些对象相似时，我使用相同的方式获取这个"query“对象的阴影，将我的对象呈现在光的前面(最终也以位串结束)。现在我可以比较这个位串和我所有其他索引位串的相似性，如果我找到了一种好的和可识别的方式来将我的对象呈现给我的光，它是搜索整个对象的代理。|455181|entityMap|0|LINK|mutability|MUTABLE|url|https://www.youtube.com/watch?v=N0WjV6MmCyM^0|0|0|0|13|6|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|15|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|16|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|17|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|18|8|@]|9|@$H|19|I|1A|1|1B]]|A|$]]|$1|J|3|K|5|6|7|1C|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1D|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1E|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1F|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|1G|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|1H|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|1I|8|@]|9|@]|A|$]]|$1|X|3|-4|5|6|7|1J|8|@]|9|@]|A|$]]]|Y|$Z|$5|10|11|12|A|$13|14]]]]

I am a visual person. Here is what works for me as an intuition.

Say each of the things you want to search for approximately are physical objects such as an apple, a cube, a chair.

My intuition for an LSH is that it is similar to take the shadows of these objects. Like if you take the shadow of a 3D cube you get a 2D square-like on a piece of paper, or a 3D sphere will get you a circle-like shadow on a piece of paper.

Eventually, there are many more than three dimensions in a search problem (where each word in a text could be one dimension) but the <a href="https://www.youtube.com/watch?v=N0WjV6MmCyM" rel="nofollow noreferrer">shadow</a> analogy is still very useful to me.

Now we can efficiently compare strings of bits in software. A fixed length bit string is kinda, more or less, like a line in a single dimension. 

So with an LSH, I project the shadows of objects eventually as points (0 or 1) on a single fixed length line/bit string.

The whole trick is to take the shadows such that they still make sense in the lower dimension e.g. they resemble the original object in a good enough way that can be recognized. 

A 2D drawing of a cube in perspective tells me this is a cube. But I cannot distinguish easily a 2D square from a 3D cube shadow without perspective: they both looks like a square to me. 

How I present my object to the light will determine if I get a good recognizable shadow or not. So I think of a "good" LSH as the one that will turn my objects in front of a light such that their shadow is best recognizable as representing my object.

So to recap: I think of things to index with an LSH as physical objects like a cube, a table, or chair, and I project their shadows in 2D and eventually along a line (a bit string). And a "good" LSH "function" is how I present my objects in front of a light to get an approximately distinguishable shape in the 2D flatland and later my bit string.

Finally when I want to search if an object I have is similar to some objects that I indexed, I take the shadows of this "query" object using the same way to present my object in front of the light (eventually ending up with a bit string too). And now I can compare how similar is that bit string with all my other indexed bit strings which is a proxy for searching for my whole objects if I found a good and recognizable way to present my objects to my light.

I noticed that LSH seems a good way to find similar items with high-dimension properties.

After reading the paper <a href="http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf" rel="noreferrer">http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf</a>, I'm still confused with those formulas.

Does anyone know a blog or article that explains that the easy way?

How to understand Locality Sensitive Hashing?

我注意到LSH似乎是一种查找具有高维属性的相似项的好方法。在阅读了论文之后，我仍然对这些公式感到困惑。有没有人知道有博客或文章可以简单地解释这一点？

问如何理解位置敏感的哈希？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何理解位置敏感的哈希？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何理解位置敏感的哈希？
EN