在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-Learn中最快的实现是什么，可以执行初始距离矩阵的计算。

2. 是否存在一个现有的多维距离方法，可以自动完成所有的步骤?

对于问题2，我已经搜索过了，但没有找到任何内置步骤能够按照我想要的方式进行“相对重要性”的距离计算。

欢迎提出其他建议。如果我漏掉了细节，很乐意进行澄清。

- roblanf

---

Scipy似乎有一个函数http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html#scipy.spatial.distance.pdist，其中包括加权。你不能使用它吗？我不确定我理解你的“按最大值缩放”到底是什么意思，以及你如何使用它。当你计算“距离矩阵”时，“乘以每个距离矩阵”是什么意思 - 你如何在最后使用这些信息（因为你所做的只是排序）。 - Floris

Answer 1

scipy.spatial.distance 是你需要查看的模块，它有许多可以轻松应用的不同规范。

我建议使用加权的Monkowski 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.        ]]

- Thorsten Kranz

---

谢谢你的提示。这个（非常好的）答案的问题在于输入值没有被规范化。因此，最终矩阵被第三个测量所主导，这是不应该的。有什么解决方法吗？ - roblanf

wminkowski已被弃用：在最新的Scipy版本中，它简单地变成了minkowski。 - AlessioX

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

- Jaime