我正在寻找一种有效的方法(no for loops)来计算一组样本和一组簇质心之间的欧几里德距离。在
示例:
import numpy as np
X = np.array([[1,2,3],[1, 1, 1],[0, 2, 0]])
y = np.array([[1,2,3], [0, 1, 0]])
预期产量:
^{pr2}$这是X中每个样本到y中每个质心之间的平方欧几里德距离
我想出了两个解决方案:
解决方案1:
def dist_2(X,y):
X_square_sum = np.sum(np.square(X), axis = 1)
y_square_sum = np.sum(np.square(y), axis = 1)
dot_xy = np.dot(X, y.T)
X_square_sum_tile = np.tile(X_square_sum.reshape(-1, 1), (1, y.shape[0]))
y_square_sum_tile = np.tile(y_square_sum.reshape(1, -1), (X.shape[0], 1))
dist = X_square_sum_tile + y_square_sum_tile - (2 * dot_xy)
return dist
dist = dist_2(X, y)
解决方案2:
import scipy
dist = scipy.spatial.distance.cdist(X,y)**2
两种解决方案的性能(挂钟时间)
import time
X = np.random.random((100000, 50))
y = np.random.random((100, 50))
start = time.time()
dist = scipy.spatial.distance.cdist(X,y)**2
end = time.time()
print (end - start)
平均挂钟时间=0.7秒
start = time.time()
dist = dist_2(X,y)
end = time.time()
print (end - start)
平均挂钟时间=0.3秒
在大量质心上进行测试
X = np.random.random((100000, 50))
y = np.random.random((1000, 50))
“解决方案1”的平均挂钟时间=50秒(+内存问题)
“解决方案2”的平均挂钟时间=6秒!!!在
结论
似乎“解决方案1”比“解决方案2”在平均已用墙上时钟时间(在小数据集上)更有效,但在内存方面效率低下。在
有什么建议吗?在
这个问题经常与nereast邻居搜索结合使用。如果是这种情况,请看一看kdtree approach。这将比计算欧几里得距离更有效,无论是在内存消耗还是性能方面。在
如果不是这样,这里有一些可能的方法。前两个来自an answer of Divakar。第三种方法使用
Numba
进行jit编译。两个版本的临时避让是第一个数组的主要区别。在计算欧几里得距离的三种方法
计时
^{pr2}$相关问题 更多 >
编程相关推荐