python - 计算成对距离矩阵的有效方法？

Question

我有一个对象列表list_of_objects，我使用scipy.cluster.hierarchy.linkage(). 作为输入scipy.cluster.hierarchy.linkage()采用压缩距离矩阵。我通过itertools.combinations仅比较唯一组合来计算压缩距离矩阵：

distances = map(do_comparison, itertools.combinations(list_of_objects, 2))

即便如此，它所花费的时间随着list_of_objects. 有没有更快的方法来做到这一点？

Answer 1

如果存在距离不再重要的临界截止值（取决于数据的答案），您可以尝试使用scipy.spatial.KDTree.sparse_distance_matrix. KDTree 的知识应该显着减少计算更长距离的时间。

要使其与集群一起使用，您可能需要注意：

计算两个 KDTree 之间的距离矩阵，将大于 max_distance 的任何距离留为零。

并将零更改为np.inf。

Answer 2

距离计算是对称的：d(x, y) = d(y, x)，所以不需要复制它们。并且所有对角项都为零：d(x, x) = 0。

但是，一旦您知道这一点，就无法绕过需要完成的计算次数。

幸运的是，它们很容易并行化。创建具有多个线程的矩阵，您将加快速度。