8

我正在尝试使用欧几里得距离实现一种方法，根据它们与样本数据集的相似性对测试数据集中的点进行聚类。测试数据集有 500 个点，每个点是一个 N 维向量（N=1024）。训练数据集大约有 10000 个点，每个点也是一个 1024 维向量。目标是找到每个测试点和所有样本点之间的 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 距离计算实现为矩阵乘法的正确方法是什么，其中矩阵具有不同的形状。结果距离矩阵应具有 dist[i,j] = 测试点 i 和样本点 j 之间的欧几里得距离。

谢谢

4

3 回答 3

15

这是广播，其中明确了中间体的形状：

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)

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

于 2016-01-19T14:33:22.890 回答
3

我认为你所要求的已经以cdist函数的形式存在于 scipy 中。

from scipy.spatial.distance import cdist
res = cdist(test, train, metric='euclidean')
于 2016-01-19T14:51:30.503 回答
3

此答案的简化和工作版本：

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中经过测试和验证的功能。

于 2015-11-19T14:27:58.633 回答