Python中加权成对距离矩阵的计算

Question

我试图找到最快的方法来执行以下Python中的成对距离计算。我想用这些距离来根据它们的相似性对a 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是您要查看的模块。它有很多不同的规范，可以很容易地应用。

我建议你用加权蒙科夫斯基矩阵

Weighted 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 4x3 matrix from 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)

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

>>> 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.        ]])