用np矩阵计算计算点集之间的距离

Question

我是向量化的新手…这似乎是一个棘手的问题，让它出来使用numpy而不是for循环。在

我有一组培训数据和一系列查询。我需要计算每个查询和训练数据的每一位之间的距离，然后对k个最近邻进行排序。我可以在for循环中实现这一点，但速度很重要。此外，培训数据的格式要比输入的点长…我将显示：

 xtrain = [[0.5,0.3,0.1232141],...] #for a large number of items.

 xquery = [[0.1,0.2],[0.3,0.4],...] #for a small number of items. 

我需要由查询和训练数据之间的欧几里德距离计算的距离。。。所以：

^{pr2}$

然后我需要对训练数据进行排序，取最接近的k，然后求训练列表中剩余值的平均值。。。在

因此，基本上，我需要一个使用xquery和xtrain生成如下所示的数组的函数：

xdist = [[distance, last_value],... (k-times)], for each value of k]

传统的for循环如下所示：

def distance(p1,p2):
 sum_of_squares = sum([(p1[i] - p2[i])**2.0 for i in range(len(p1))])
 return np.sqrt(sum_of_squares)

qX = data[train_rows:train_rows+5,0:-1]
k = 4

k_nearest_neighbors = [np.array(sorted([ (distance(qX[i],trainX[j]),trainX[j][-1]) for j in range(len(trainX))],key=lambda (x,y): x))[:k] for i in range(len(qX))]
predictions = [ np.average([j[1] for j in i]) for i in k_nearest_neighbors]

我在k峎nearchneighbors步骤中保持了它的紧凑性；我意识到这并不清楚……但是我认为从那里进行矢量化比较容易。在

不管怎样，我知道如何用切片来做这个…看起来应该是可能的。。。在

Answer 1

这是绝对有可能做到这一点通过纽比广播。看起来像这样：

D = np.sum((qX[:, None, :] - trainX[None, :, :2]) ** 2, -1)
ind = np.argpartition(D, k, axis=1)[:, :k]
predictions = trainX[ind, 2].mean(1)

为了确认这一点，我们可以定义实现for loop方法和my broadcasting方法的函数，并比较结果：

^{pr2}$

请记住，随着数据的增长，使用像^{}这样的基于树的方法查找最近的邻居会更加有效：

from scipy.spatial import cKDTree

def with_kd_tree(qX, trainX, k):
    dist, ind = cKDTree(trainX[:, :2]).query(qX, k)
    return trainX[ind, 2].mean(1)

np.allclose(with_broadcasting(qX, trainX, 4),
            with_kd_tree(qX, trainX, 4))
# True

在执行时间上，我们可以看到这些方法在更大的数据集下的性能有了实质性的改进：

np.random.seed(0)
trainX = np.random.rand(1000, 3)
qX = np.random.rand(1000, 2)

%timeit with_for_loop(qX, trainX, 4)
1 loops, best of 3: 7.16 s per loop

%timeit with_broadcasting(qX, trainX, 4)
10 loops, best of 3: 57.7 ms per loop

%timeit with_kd_tree(qX, trainX, 4)
1000 loops, best of 3: 1.61 ms per loop