如果只对最近点感兴趣，则优化欧几里得距离矩阵算法

Question

下面的欧几里得距离算法创建MxN输入矩阵行之间距离的MxM矩阵(表示某个N维空间中的点(。该算法的速度以O(m^2(为单位。如果只对彼此最接近的行(即点(感兴趣，这是否可以改进？(我的下游任务包括执行K-NN等(

import numpy as np

vectors = np.random.randn(100, 20)
m = vectors.shape[0]
distances = np.zeros([m, m])
for i in range(m):
vec = vectors[i]
distances[i] = [np.linalg.norm(vec - vectors[j]) for j in range(m)]

Answer 1

我建议利用scipy的压缩距离矩阵，而不是成对比较的for循环。特别是

from scipy.spatial.distance import pdist, squareform
distances = squareform(pdist(vectors))

提供了~85倍的加速！文档可在此处找到。

从根本上讲，复杂性似乎仍然是二次的(因为你需要将vectors的每个元素相互比较(。然而，该实现利用了对称性和每个元素到其自身的距离为0的事实，从而仅计算上三角子矩阵，然后沿对角线镜像它以获得二次距离矩阵。

您的代码运行时间为71毫秒，而SciPy运行时间为0.83毫秒；前面提到的85倍加速。

无论如何，如果您尝试运行kNN，您可能需要考虑scikit-learn，在这里您可以简单地将vectors提供为X，如图所示。