给定一个向量，快速查找字典向量中与之最相似的向量。高维度。

Question

6

我正在寻找一个可扩展的答案，但是针对我的特定目的，我有一个48维向量。这可以表示为48个介于0和255之间的整数数组。

我有一个大型的这些向量的字典，大约有25,000个。

我需要能够快速地找到可能在数据库中的向量，并找出与数据库中最接近的向量。最接近的意思是传统的距离公式。

我的代码最终将在Python中实现，但这更是一个一般性问题。

暴力搜索太慢了。我需要一个近似字典速度的查找。有人有想法吗？

- Piper Merriam

2个回答

4

从你的问题中不清楚是否需要精确的最近邻。如果您满意于返回一个近似最近邻向量，则有更快的解决方案。请参见此处（http://www.cs.umd.edu/~mount/ANN/）。

- Aaron

LSH目前对我来说似乎是最好的选择。http://www.mit.edu/~andoni/LSH/ 是一个很好的资源。该算法的2006年论文是最有帮助的。 - Piper Merriam

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

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

- Il-Bhima · Accepted Answer

我建议实现一个 kd-tree，它可以执行最近邻搜索。在 k 维中，N 个点的最坏情况搜索时间为 O(k.N^(1-1/k))，因此它应该在 N 中呈次线性缩放。

如果我有时间，我会回来提供比维基百科更详细的解释。

由于你正在使用 Python，因此这个关于 kdtrees 的 Scipy cookbook 条目应该会有所帮助。