几天前，我在Stack Overflow上提出了一个问题，关于如何为给定向量找到最近邻。现在我的向量有21个维度，在继续之前，由于我并不来自机器学习或数学领域，我开始问自己一些基本问题：

• 首先，欧几里得距离是否是寻找最近邻的好方法？如果不是，我的选择是什么？
• 此外，如何决定确定k邻居的正确阈值？是否有某种分析可以用来确定这个值？
• 之前，有人建议我使用kd树，但维基百科页面明确指出，在高维度情况下，kd树几乎等同于暴力搜索。在这种情况下，在百万点数据集中高效查找最近邻的最佳方法是什么？

能否请有人澄清上述一些（或全部）问题？

回答：

我目前正在研究这些问题——分类、最邻近搜索——用于音乐信息检索。

你可能对近似最近邻（ANN）算法感兴趣。其核心思想是允许算法返回足够近邻（可能不是最近邻），这样做可以降低复杂度。你提到了kd树；那是一个例子。但正如你所说，kd树在高维度下表现不佳。事实上，所有当前基于空间分区的索引技术在足够高维度下都会退化为线性搜索[1][2][3]。

在最近提出的ANN算法中，可能最流行的是局部敏感哈希（LSH），它将高维空间中的一组点映射到一组桶，即一个哈希表[1][3]。但与传统的哈希不同，局部敏感哈希会将附近的点放入同一个桶中。

LSH有一些巨大的优势。首先，它很简单。你只需计算数据库中所有点的哈希，然后从中创建一个哈希表。要查询，只需计算查询点的哈希，然后从哈希表中检索同一个桶中的所有点。

其次，有一套严谨的理论支持其性能。可以证明查询时间在数据库大小上的是次线性的，即比线性搜索快。具体快多少取决于我们能容忍多少近似度。

最后，LSH与任何Lp范数兼容，适用于0 < p <= 2。因此，回答你的第一个问题，你可以使用LSH与欧几里得距离度量，或者与曼哈顿（L1）距离度量一起使用。还有针对汉明距离和余弦相似度的变体。

马尔科姆·斯莱尼和迈克尔·凯西在2008年为IEEE信号处理杂志撰写了一篇不错的概述[4]。

LSH似乎已被应用于各个领域。你可能想尝试一下。

[1] Datar, Indyk, Immorlica, Mirrokni, “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,” 2004.

[2] Weber, Schek, Blott, “A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces,” 1998.

[3] Gionis, Indyk, Motwani, “Similarity search in high dimensions via hashing,” 1999.

[4] Slaney, Casey, “Locality-sensitive hashing for finding nearest neighbors”, 2008.