欧几里得距离的高效计算

Question

我有一个 MxN 的数组，其中 M 是观察数， N 是每个向量的维度。我需要从这些向量中计算平均值和最小欧几里得距离。在我的想法中，这要求我计算 M 选 2 的距离，这是一个 O(n^min(k, n-k)) 的算法。我的 M 大约是10,000，我的 N 大约是1,000，这个计算需要大约45秒。是否有更有效的方法来计算平均值和最小距离？也许是概率方法？我不需要精确结果，只需要接近即可。

- japata

---

https://dev59.com/xGfWa4cB1Zd3GeqPjKUs - Mitch Wheat

你能发一下你现在的代码吗？我脑海中只看到O(m^2*n)，也许我有什么误解。 - pgreen2

有趣的问题。然而，我不确定您从哪里得到变量C_2和k。正如pgreen2所提到的，我认为O(n*m^2)算法是最直接的方法。 - Filip Kilibarda

这是一个详尽的讨论和证明，用O(nlogn)的时间复杂度解决这个问题。https://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf - Filip Kilibarda

@FilipKilibarda 应该更仔细地看：在一维中，可以考虑n个点之间的n-1个线段，并计算每个线段对成对距离的贡献次数：它左边的点数乘以它右边的点数。 因此，在一维中，可以利用成对距离的总和分解为较小距离的乘积和的事实。然而，从二维开始，这似乎并不容易。 - S. Huber

Answer 1

您可以通过某种空间划分来加速处理。

对于最小距离计算，您只需要考虑同一或相邻分区中的点对。对于近似均值，您可以根据分区之间的距离和其中的点数得出一些加权平均值。

- Martin Stone

Answer 2

您没有说明向量来自哪里，也没有说明您将如何使用“mean”和“median”。以下是一些关于一般情况的观察。有限范围、误差容忍度和离散值可能会采用更有效的方法。

M个点之间的平均距离听起来是二次的，即O（M ^ 2）。但是，M / N为10，相当小，而N很大，因此数据可能类似于1e3空间中的毛茸茸的球体。计算M个点的质心，然后计算到质心的M个距离，在您的问题域中可能会变得有用，很难说。

M个点之间的最小距离更有趣。随机选择少量对，例如100对，计算它们的距离，并将最小距离的一半作为全局最小距离的估计值。（如果需要，通过比较接下来的几个最小距离进行验证。）现在使用UB-tree模拟每个点作为正整数。这涉及找到M x N个值的N个最小值，添加常量使最小值变为零，缩放以使估计的全局最小距离对应至少为1.0，然后截断为整数。

有了这些转换后的向量，我们准备将它们转化为UB树表示，然后对排序后的值进行最近邻空间查询。对于每个点计算一个整数。将每个维度值的低位比特位移入结果中，然后迭代。在所有维度上继续迭代，直到所有非零位都已消耗并出现在结果中，并继续到下一个点。对整数结果值进行数值排序，得到类似于PostGIS索引的数据结构。

现在你拥有了一种离散化表示，支持相对高效的最近邻查询（尽管N=1e3可能有些大）。在找到两个或更多粗粒度附近的邻居之后，您可以查询原始向量表示以获取它们之间的高分辨率距离，以进行更细致的区分。如果您的数据分布结果有很大一部分点被离最近邻只差一个比特位的位置所离散化，例如氧原子的位置，每个原子都有一个伙伴，则增加全局最小距离估计，以便低位比特提供足够的区分度。

类似的离散化方法是适当缩放例如2维输入，并标记一个最初为空的网格，然后扫描相邻区域。这依赖于全局最小值在“小”邻域内，由于适当的缩放。在您的情况下，您将标记一个N维网格。

- J_H

Answer 3

我以前也有同样的问题，但是在归一化数值后，问题得以解决。因此，在计算距离之前，请尝试对数据进行归一化处理。

- Srinivas746

---

@Srinivas746 向量元素的大小可能会对浮点稳定性产生一定影响，但问题是关于时间复杂度的。 - awiebe