我注意到LSH似乎是一种寻找具有高维属性的类似项目的好方法.
在阅读了论文http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf之后,我仍然对这些公式感到困惑.
有没有人知道一个博客或文章解释这个简单的方法？
c machine-learning hashmap nearest-neighbor locality-sensitive-hash
我正在寻找一个轻量级的Java库,它支持Locality Sensitive Hashing的最近邻搜索,用于在具有数十万个数据点的高维(在我的情况下为32)数据集中几乎均匀分布的数据.
将查询中的所有条目都放入存储桶中就足够了.考虑到我的问题包括的一些过滤器参数,我可以以不同的方式处理我真正需要的那些.
我已经发现了可能性,但希望有一些更小的东西,而不需要任何其他工具(如可爱的情况下的Apache Hadoop).
在C/C++/Java/C#中是否有任何相对简单易懂(并且易于实现)的局部敏感哈希示例？
我想更多地了解这个概念,所以想尝试一些文本文件只是为了看看它是如何工作的,所以我不需要任何高性能或任何东西......只是一个哈希的例子为类似输入返回类似哈希的函数.之后我可以通过实例了解更多信息.:)
有没有允许LSH在Elasticsearch上的插件？如果是的话,你能指点我的位置,并告诉我一些如何使用它？谢谢
编辑:我发现ES使用MinHash插件.我怎么能用这个比较文件呢？找到重复的好设置是什么？
我想使用Locality敏感哈希来大致匹配字符串.我有很多字符串> 10M可能包含错别字.对于每个String,我想与所有其他字符串进行比较,并根据某个阈值选择具有编辑距离的字符串.
也就是说,天真的解决方案需要O(n ^ 2)个比较.为了避免这个问题,我正在考虑使用Locality Sensitive Hashing.然后接近相似的字符串会产生相同的桶,我只需要在桶搜索中进行.所以它是O(n*C),其中C是桶大小.
但是,我不明白如何表示字符串.如果是文本,我将在向量空间中表示.我的主要问题是,如果使用LSH这是易处理的,然后是字符串的适当矢量表示.
我可以使用已经实现的库来执行此任务吗？或者这取决于我的问题,所以我必须自己实施？是否有任何python包执行此操作？
我有一个大的稀疏numpy/scipy矩阵,其中每一行对应于高维空间中的一个点.我想要进行以下类型的查询:
给定一个点P(矩阵中的行)和距离小量,找到距离的所有点,最小量从P.
我使用的距离度量是Jaccard相似度,因此应该可以使用MinHash等Locality Sensitive Hashing技巧.
在某处(我似乎无法找到一个)稀疏numpy数组是否有MinHash的实现,或者有一种简单的方法可以做到这一点？
我不仅仅是为Github上的非稀疏数组提取内容的原因是scipy中的稀疏数据结构可能会导致时间复杂度的爆炸.
目前我正在研究如何使用局部敏感散列查找最近邻居.然而,当我在阅读论文和搜索网页时,我发现了两种算法:
1-使用L个具有L个随机LSH函数的哈希表,从而增加两个相似的文档获得相同签名的机会.例如,如果两个文档的80%相似,则有80%的可能性从一个LSH函数获得相同的签名.但是,如果我们使用多个LSH函数,那么从一个LSH函数获取文档的相同签名的可能性就更高.这个方法在维基百科中解释,我希望我的理解是正确的:
http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search
2-另一种算法使用了一篇论文中的方法(第5节),称为:来自Moses S. Charikar的舍入算法的相似性估计技术.它基于使用一个LSH函数生成签名,然后在其上应用P排列,然后对列表进行排序.其实我不太了解这个方法,我希望有人能澄清一下.
我的主要问题是:为什么有人会使用第二种方法而不是第一种方法？因为我发现它更容易,更快.
我真的希望有人可以帮忙!
编辑:实际上我不确定@ Raff.Edward是否在"第一"和"第二"之间混合.因为只有第二种方法使用半径,而第一种方法只使用由散列族F组成的新散列族g.请检查维基百科链接.他们只使用了很多g函数来生成不同的签名,然后对于每个g函数,它都有一个相应的哈希表.为了找到一个点的最近邻居,您只需让该点遍历g函数并检查相应的哈希表是否存在冲突.因此,我将其理解为更多功能......更多碰撞机会.
我没有发现任何关于第一种方法的半径.
对于第二种方法,它们仅为每个特征向量生成一个签名,然后对它们应用P置换.现在我们有P个排列列表,其中每个包含n个签名.然后他们然后从P对每个列表进行排序.在给定查询点q之后,他们为它生成签名然后在其上应用P排列,然后在每个置换和排序的P列表上使用二进制搜索来找到最相似的签名.查询q.我在阅读了很多关于它的论文之后得出了这个结论,但我仍然不明白为什么有人会使用这种方法,因为它看起来并不快找到汉明距离!
对我来说,我只需要执行以下操作来查找查询点q的最近邻居.给定签名列表N,我将生成查询点q的签名,然后扫描列表N并计算N中每个元素与q的签名之间的汉明距离.因此,我最终会得到q的最近邻居.它需要O(N)!!!
我已经阅读了许多使用min-hash实现LSH(局部敏感哈希)的教程,文档和代码片段.
LSH试图通过散列随机子集并在这些子集上进行聚合来找到两组的Jaccard系数.我查看了code.google.com中的实现,但也无法理解他们的方法.我理解Google新闻个性化的文章:可扩展的在线协同过滤,但我无法理解那里的任何实现.
有人可以用简单的话来解释我如何用MinHash实现LSH吗？
我正在实现一个近邻搜索应用程序，它将找到相似的文档。到目前为止，我已经阅读了很多有关LSH的资料（LSH背后的理论有些令人困惑，我还不能100％理解它）。
我的代码能够使用minhash函数计算签名矩阵（我已经接近尾声了）。我也将签名策略应用于签名矩阵。但是，我不明白如何将一个带中的（列的）签名向量散列到存储桶中。
我的最后一个问题可能是最重要的一个，但我不得不问一些introduction问题：
问题1：哈希函数是否只会将相同的向量映射到相同的存储桶？（假设我们有足够的水桶）
问题2：哈希函数是否应将相似的向量映射到同一存储桶？如果是，那么这种相似性的程度/定义是多少，因为我不是在计算比较，而是在进行哈希处理。
q3：根据上面的问题，我应该使用哪种哈希表算法？
q4：我认为我的最弱点是我不知道如何生成将向量作为输入并选择存储桶作为输出的哈希函数。我可以根据q1和q2自己实现一个...关于为LSH生成哈希函数的任何建议bucketing？
我正在寻找一种高性能算法，根据以下数据结构按位置、性别和年龄匹配大量人员：
对于任何人 P，算法应返回适用的候选人 C：
该算法应按距离（纬度/经度）顺序返回前 100 个候选 C。该算法应该针对搜索和更新进行优化，因为人们可能经常改变他们的位置。
我目前的想法是，kd 树可能比局部敏感哈希更适合这些需求，我应该朝这个方向发展。
您对我有什么建议？我应该寻找什么？您看到什么风险？
谢谢！
更新：
algorithm kdtree nearest-neighbor locality-sensitive-hash azure-cosmosdb