用Python计算加权成对距离矩阵

Question

我正试图找到在Python中执行以下成对距离计算的最快方法。我想使用距离来根据它们的相似性对list_of_objects进行排序。

list_of_objects中的每个项目都有四个测量值a、b、c、d，这些测量值在非常不同的尺度上进行，例如：

object_1 = [0.2, 4.5, 198, 0.003]
object_2 = [0.3, 2.0, 999, 0.001]
object_3 = [0.1, 9.2, 321, 0.023]
list_of_objects = [object_1, object_2, object_3]

目的是得到list_of_objects中对象的成对距离矩阵。然而，我希望能够通过每次测量一个权重的权重向量，在距离计算中指定每次测量的"相对重要性"，例如：

weights = [1, 1, 1, 1]

将指示所有测量都是相等加权的。在这种情况下，我希望每次测量对物体之间的距离都有同等的贡献，而不考虑测量尺度。或者：

weights = [1, 1, 1, 10]

将表明我希望测量值d对物体之间距离的贡献是其他测量值的10倍。

我目前的算法是这样的：

1. 为每次测量计算成对距离矩阵
2. 对每个距离矩阵进行归一化，使最大值为1
3. 将每个距离矩阵乘以weights中的适当权重
4. 对距离矩阵求和以生成单个成对矩阵
5. 使用4中的矩阵提供list_of_objects中对象对的排序列表

这很好，并且给了我一个物体之间城市街区距离的加权版本。

我有两个问题：

1. 在不改变算法的情况下，SciPy、NumPy或SciKit中最快的实现是什么？学习执行初始距离矩阵计算。

2. 有没有一种现有的多维距离方法可以为我做到这一切？

对于Q 2，我已经看过了，但找不到任何内置步骤能以我想要的方式实现"相对重要性"。

欢迎其他建议。很高兴澄清我是否遗漏了细节。

Answer 1

scipy.spatial.distance是您想要了解的模块。它有很多不同的规范，可以很容易地应用。

我建议使用加权Monkowski Metrik

加权Minkowski Metrik

您可以使用此软件包中的pdist方法进行成对距离计算。

例如

import numpy as np
from scipy.spatial.distance import pdist, wminkowski, squareform
object_1 = [0.2, 4.5, 198, 0.003]
object_2 = [0.3, 2.0, 999, 0.001]
object_3 = [0.1, 9.2, 321, 0.023]
list_of_objects = [object_1, object_2, object_3]
# make a 3x4 array from the list of objects
X = np.array(list_of_objects)
#calculate pairwise distances, using weighted Minkowski norm
distances = pdist(X,wminkowski,2, [1,1,1,10])
#make a square matrix from result
distances_as_2d_matrix = squareform(distances)
print distances
print distances_as_2d_matrix

这将打印

[ 801.00390786  123.0899671   678.0382942 ]
[[   0.          801.00390786  123.0899671 ]
 [ 801.00390786    0.          678.0382942 ]
 [ 123.0899671   678.0382942     0.        ]]

Answer 2

将成对距离除以最大值的归一化步骤似乎是非标准的，并且可能很难找到一个现成的函数来完成您想要的任务。不过自己做还是很容易的。一个起点是将list_of_objects变成一个数组：

>>> obj_arr = np.array(list_of_objects)
>>> obj_arr.shape
(3L, 4L)

然后，您可以使用广播来获得成对的距离。这有点低效，因为它没有利用度量的对称性，并且每距离计算两次：

>>> dists = np.abs(obj_arr - obj_arr[:, None])
>>> dists.shape
(3L, 3L, 4L)

归一化非常容易：

>>> dists /= dists.max(axis=(0, 1))

您的最终称重可以通过多种方式进行，您可能需要基准测试哪种最快：

>>> dists.dot([1, 1, 1, 1])
array([[ 0.        ,  1.93813131,  2.21542674],
       [ 1.93813131,  0.        ,  3.84644195],
       [ 2.21542674,  3.84644195,  0.        ]])
>>> np.einsum('ijk,k->ij', dists, [1, 1, 1, 1])
array([[ 0.        ,  1.93813131,  2.21542674],
       [ 1.93813131,  0.        ,  3.84644195],
       [ 2.21542674,  3.84644195,  0.        ]])