局部敏感哈希算法中寻找最近邻的两种算法，哪一种更好？

Question

局部敏感哈希算法中寻找最近邻的两种算法，哪一种更好？

algorithmmachine-learninglocality-sensitive-hash

8

目前我正在学习如何使用局部敏感哈希找到最近的邻居。然而，在阅读论文和搜索网络时，我发现了两种实现此目的的算法：

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）！

- Jack Twain

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Raff.Edward · Accepted Answer

你对第一个算法的理解有些偏差。碰撞发生的概率与相似性成正比，而是是否小于预定义半径。目标是在半径内的任何物体都有很高的碰撞几率，而在半径外*(1+eps)的任何物体都有很低的碰撞几率（中间的区域有点模糊）。

第一个算法实际上非常难以实现，但可以获得良好的结果。特别地，第一个算法适用于L1和L2（以及技术上还有一些）指标。

第二个算法非常容易实现，尽管一个天真的实现可能会使用太多的内存，以至于根据问题的规模来说不是很有用。在这种情况下，碰撞的概率与输入的相似性成正比。然而，它仅适用于余弦相似度（或基于相似度转换的距离指标）。

因此，你要使用哪个算法主要取决于你在最近邻（或其他应用程序）中使用的距离度量。

第二个算法比第一个算法实际上更容易理解和实现，只是论文写得太啰嗦了。

简而言之：取一个随机向量V，给每个索引分配一个独立的随机单位正常值。创建与所需签名长度相同的向量。当进行矩阵向量乘积时，签名是每个索引的符号。现在，任意两个签名之间的汉明距离与相应数据点之间的余弦相似度有关。

由于您可以将签名编码为int数组，并使用位计数指令进行XOR以快速获取汉明距离，因此可以快速获得近似余弦相似度分数。

LSH算法没有很多标准化，这两篇论文（和其他论文）使用不同的定义，因此有时会感到有些混乱。我最近才在JSAT中实现了这两种算法，并且仍在努力完全理解它们。

编辑：回复您的编辑。维基百科的文章对LSH不是很好。如果您阅读原始论文，您所谈论的第一种方法仅适用于固定半径。然后基于该半径创建哈希函数，并串联以增加在碰撞中接近点的概率。然后，他们构建了一个系统，在其上进行k-NN（最近邻）搜索，通过确定他们想要的k的最大值，并找到第k个最近邻居可能存在的最大合理距离。这样，半径搜索很可能返回k-NN的集合。为了加快速度，他们还创建了几个额外的小半径，因为密度通常不均匀，使用较小的半径可以加快结果。

您链接的维基百科部分取自“稳定分布”部分的论文描述，介绍了搜索半径r = 1的哈希函数。

对于第二篇论文，“排序”并不是哈希的一部分，而是为了更快地搜索汉明空间的一种方法。正如我之前提到的，我最近实现了这个功能，并且您可以看到使用暴力搜索进行的快速基准测试仍然比NN的朴素方法快得多。同样，如果您需要余弦相似性而不是L2或L1距离，则还会选择此方法。您会发现许多其他论文提出了不同的方案，用于搜索通过签名创建的汉明空间。

如果您需要帮助说服自己即使您仍在进行暴力搜索，适合也可能更快，请看这个角度：假设平均稀疏文档与另一个文档有40个共同的单词（根据我的经验，这是一个非常保守的数字）。您有n个文档要进行比较。暴力余弦相似性将涉及约40 * n浮点乘法（以及一些额外的工作）。如果您有1024位的签名，那只有32个整数。这意味着我们可以在32 * n个整数操作中进行暴力LSH搜索，这些操作比浮点运算快得多。

这里还有其他因素在起作用。对于一个稀疏数据集，我们需要保留双精度和整数索引来表示非零索引，因此稀疏点积要做很多额外的整数运算才能看出它们有哪些共同的索引。LSH也可以帮助我们节省内存，因为我们不需要为每个向量存储所有这些整数和双精度数，而是只需保留其哈希值-仅几个字节即可。减少内存使用可以帮助我们更好地利用CPU缓存。

你的O(n)是我在博客文章中使用的朴素方法。它很快。但是，如果您提前对位进行排序，您可以在O(log(n))中执行二进制搜索。即使您有L个这些列表，L << n，因此应该更快。唯一的问题是它会给您近似的汉明NN，这已经近似了余弦相似度，因此结果可能会变得更糟。这取决于您需要什么。