Python中两个（非传统）向量的欧几里得距离

Question

我有两个非传统向量，我想计算它们之间的欧几里得距离。这些向量设置如下：

line1 = '2:20 3:20 5:10 6:10 10:20'
line2 = '1:18 2:20 4:10 6:10 8:20 9:10 10:10'

对于每个元素，第一个数字是向量中的位置，第二个数字是值（例如，2:20表示在向量中的第2个元素的值为20）。因此，line1的向量为(0,20,20,0,10,10,0,0,0,20)，line2的向量为(18,20,0,10,0,10,0,20,10,10)。

我编写了以下程序，它运行得很好。问题是我有巨大的向量，并且我想将它们与数千个其他向量进行比较。当我尝试这样运行它时，我的计算机开始给出内存错误。是否有一种方法可以在不实际创建具有许多0条目的长向量的情况下计算设置为此方式的两个向量之间的欧几里得距离？

def vec_line(line):
    vector = [0]*10
    datapoints = line.split(' ')
    for d,datapoint in enumerate(datapoints):
        element = int(datapoint.split(':')[0])
        value = float(datapoint.split(':')[1])
        vector[element-1]=value

    npvec = np.array(vector)
    return npvec

vector1 = vec_line(line1)
vector2 = vec_line(line2)

dist = np.linalg.norm(vector1-vector2)
print dist
--> [39.0384425919]

- myname

Answer 1

您所需要的“非传统”向量通常被称作“稀疏向量”（或一般的“稀疏矩阵”）。Scipy有一个软件包可以创建这些向量并执行代数运算。以下是大致您所需要的内容：

import numpy as np
from scipy.sparse import csr_matrix


def parse_sparse_vector(line):
    tokens = line.split()
    indexes = []
    values = []
    for token in tokens:
        index, value = token.split(':')
        index = int(index)
        value = int(value)
        indexes.append(index)
        values.append(value)
    return csr_matrix((values, ([0] * len(indexes), indexes)))

v = parse_sparse_vector(line1)
w = parse_sparse_vector(line2)
dist = v - w
# avoiding a cast to dense matrix:
np.sqrt(dist.dot(dist.T).sum())
## result is 39.038442591886273

- logc

---

非常感谢您的帮助。我不知道这些被称为稀疏向量，所以这对我很有帮助。我的代码得到了不同的欧几里得距离，是39.0384425919。我会看看能否找出差异所在。再次感谢！ - myname

@myname 没关系 :) 请检查代码片段的最新版本，我刚刚想出了如何避免在任何地方转换为密集矩阵。此外，我无法确定这是否能解决您所有的效率需求：进行大量成对距离计算是*O(n^2)*的。 - logc

刚刚发现了区别。我想你的意思是写成 value = int(value)，而不是 value = int(index)。再次感谢！ - myname

我刚发现了相同的错误并纠正了代码片段和结果。现在只有精度上的差异。 - logc