python - 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)。所以第 1 行的向量是 (0,20,20,0,10,10,0,0,0,20)，第 2 行的向量是 (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]

Answer 1

您的“非传统”向量通常称为“稀疏向量”(或通常称为“稀疏矩阵”)。 Scipy 有 a package创建它们并对它们执行代数运算。

这或多或少是你想要的:

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