python - 欧式距离的高效计算

Question

我有一个 MxN 数组，其中 M 是观察的数量，N 是每个向量的维数。从这个向量数组中，我需要计算向量之间的 mean 和 minimum 欧氏距离。

在我看来，这需要我计算 _MC₂ 距离，这是一个 O(n^{min(k, n-k)} ) 算法。我的 M 是~10,000，我的N 是~1,000，这个计算需要~45 秒。

是否有更有效的方法来计算 mean 和 min 距离？也许是一种概率方法？我不需要它非常精确，只要接近即可。

Answer 1

您没有说明您的矢量来自何处，也没有说明您将如何使用 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 太大了)。在找到两个或多个粗粒度的近邻后，您可以查询原始向量表示以获得它们之间的高分辨率距离，以进行更精细的区分。如果您的数据分布证明有很大一部分点离散化为与最近的邻居相差一位，例如每个氧原子都有伙伴的位置，然后增加全局最小距离估计，以便低阶位提供足够的辨别力。

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