使用Python广播的内存高效L2规范

Question

我正在尝试实现一种方法，基于它们与样本数据集的相似性，使用欧几里德距离对测试数据集中的点进行聚类。测试数据集有500个点，每个点都是一个N维向量(N=1024)。训练数据集大约有10000个点，每个点也是一个1024d的向量。目标是找到每个测试点和所有采样点之间的L2距离，以找到最接近的样本(不使用任何python距离函数)。由于测试数组和训练数组的大小不同，我尝试使用广播：

    import numpy as np
    dist = np.sqrt(np.sum( (test[:,np.newaxis] - train)**2, axis=2))

其中test是形状(500,1024)的数组，train是形状(10000,1024)的数组。我要买一台MemoryError。但是，相同的代码适用于较小的数组。例如：

     test= np.array([[1,2],[3,4]])
     train=np.array([[1,0],[0,1],[1,1]])

有没有一种内存效率更高的方法来进行上面的计算而不需要循环？基于在线帖子，我们可以使用矩阵乘法sqrt(X * X-2*X * Y+Y * Y)来实现L2范数。因此，我尝试了以下方法：

    x2 = np.dot(test, test.T)
    y2 = np.dot(train,train.T)
    xy = 2* np.dot(test,train.T)

    dist = np.sqrt(x2 - xy + y2)

因为矩阵有不同的形状，当我尝试广播时，有一个维度不匹配，我不确定什么是正确的广播方式(没有太多的Python广播经验)。我想知道在Python语言中将L2距离计算实现为矩阵乘法的正确方法是什么，因为在Python中矩阵具有不同的形状。所得到的距离矩阵应该具有disti，j =测试点i和采样点j之间的欧几里得距离。

谢谢

Answer 1

这是一个清晰的中间层形状的广播：

m = x.shape[0] # x has shape (m, d)
n = y.shape[0] # y has shape (n, d)
x2 = np.sum(x**2, axis=1).reshape((m, 1))
y2 = np.sum(y**2, axis=1).reshape((1, n))
xy = x.dot(y.T) # shape is (m, n)
dists = np.sqrt(x2 + y2 - 2*xy) # shape is (m, n)

关于广播的documentation有一些很好的例子。

Answer 2

来自this answer的简化和工作版本

x, y = test, train

x2 = np.sum(x**2, axis=1, keepdims=True)
y2 = np.sum(y**2, axis=1)
xy = np.dot(x, y.T)
dist = np.sqrt(x2 - 2*xy + y2)

因此，您脑海中的方法是正确的，但您需要小心如何应用它。

为了让您的工作更轻松，请考虑使用scipy或scikit-learn提供的经过测试和验证的功能。

Answer 3

我认为您所请求的内容已经以cdist函数的形式存在于scipy中。

from scipy.spatial.distance import cdist
res = cdist(test, train, metric='euclidean')