我有 n=10000 个10维向量。
对于每一个向量 v1，我想知道最小化 v1 和另一个向量 v2 之间夹角的向量 v2 是什么。
有没有一种比 O(n^2) 更快的方法来解决这个问题？
在对数时间内找到向量之间的最小角度
8
- Christian
1
4我希望“10”的意思是二进制的… - Donal Fellows
4个回答
2
您所需翻译的内容与IT技术有关，其实您拥有的是最接近球体问题(因为向量之间的角度大约等于它们单位向量所在的球面上的点之间的距离)，因此您可以进行某种二进制(也许三进制会更容易避免过多边界问题)空间分割分解。但这将很难编码，并且对于仅有10,000个点来说可能比朴素方法快不了多少(特别是您开始通过将点划分到3^10 = 59049个框中，尽管其中大部分都为空)。一亿个十元素点积应该在不到一秒钟内完成。
- Tom Womack
2
您可以在O(n)时间内对所有向量进行归一化，并将它们参数化到结果为9维的超球面上。然后，您可以在n-1维空间中使用空间搜索结构，如Kd树，来加速最近邻查询。有已知的方法（ANN）可以做到这一点。
- Victor Liu
1
哇，十维向量？那你打算拿它们做什么？
我想我会先将每个向量缩小为单位长度——也就是在超球面上的点，然后使用一些“最近邻搜索”（NNS）算法，例如kD树（k维二叉树）、R树、Best Bin First等。
可能无法比O（n log n）更快地解决这个问题，因为如果您可以比这更快地解决此问题，则可以比当前下限O（n log n）更快地解决更简单的“最近对点问题”。
正如Tom Womack所指出的那样，“暴力”的O（n ^ 2）算法将需要比这些更复杂的算法更少的实际墙钟时间，而“n = 10000”在10个维度中看起来相对较小。
- David Cary
-3
你可以为每个向量计算角度（O(n)），然后根据角度对数组进行排序（O(nlogn)），最后遍历整个数组（O(n)），最接近的向量要么是i+1，要么是i-1。
编辑： 正如评论中指出的那样，这种方法只适用于二维空间。
- Kugel
1
完全不是这样的；在超过2个维度的情况下，等效的方法是用单位向量替换物体，这会将维度降低一维，但仍然太高以至于无法很好地排序。 - Tom Womack
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接