高维数据中的最近邻居？

Question

我几天前问了一个问题，该问题是如何找到给定向量的最近邻居。我的向量现在是21维，在继续下一步之前，因为我既不是机器学习也不是数学领域的专家，所以我开始问自己一些基本问题：欧几里得距离是一个很好的度量标准，可以用来首先找到最近的邻居？如果没有，我有什么选择？另外，如何确定用于确定k个邻居的正确阈值？是否可以进行一些分析以找出该值？以前，有人建议我使用kd-Trees，但Wikipedia页面上明确指出，对于高维，kd-Tree几乎等同于蛮力搜索。在那种情况下，有效地找到一百万个点数据集中的最近邻居的最佳方法是什么？有人可以澄清以上部分（或全部）问题吗？

Answer 1

我目前正在研究此类问题-分类，最近邻居搜索-以获取音乐信息。

您可能对近似最近邻（ANN）算法感兴趣。这个想法是让算法允许返回足够近的邻居（也许不是最近的邻居）。这样可以减少复杂性。您提到了kd-tree；那是一个例子。但是正如您所说，kd-tree在高维度上效果不佳。实际上，所有当前的索引技术（基于空间划分）都降级为对足够高的尺寸进行线性搜索[1] [2] [3]。

在最近提出的ANN算法中，也许最流行的是局部敏感哈希（LSH），它将高维空间中的一组点映射到一组bin中，即哈希表[1] [3]。但是与传统的哈希不同，对位置敏感的哈希将附近的点放置在同一容器中。

LSH具有一些巨大的优势。首先，它很简单。您只需为数据库中的所有点计算哈希，然后根据它们创建哈希表。要进行查询，只需计算查询点的哈希值，然后从哈希表中检索同一bin中的所有点。

其次，有一个严格的理论可以支持其性能。可以看出，查询时间在数据库大小上是次线性的，即比线性搜索快。快多少取决于我们可以忍受的近似程度。

最后，LSH与的任何Lp规范兼容0 < p <= 2。因此，要回答第一个问题，您可以将LSH与欧几里德距离度量标准结合使用，或者将其与曼哈顿（L1）距离度量标准结合使用。汉明距离和余弦相似度也有变体。

Malcolm Slaney和Michael Casey在2008年为IEEE Signal Processing Magazine撰写了不错的综述[4]。

LSH似乎已在所有地方得到应用。您可能需要尝试一下。

---

[1] Datar，Indyk，Immorlica，Mirrokni，“基于p稳定分布的局部敏感散列方案”，2004年。

[2] Weber，Schek，Blott，“高维空间中相似性搜索方法的定量分析和性能研究”，1998年。

[3] Gionis，Indyk，Motwani，“通过散列在高维中进行相似性搜索”，1999年。

[4] Slaney，Casey，“对位置敏感的哈希，用于寻找最近的邻居”，2008年。