使用欧几里得距离在numpy数组列表中找到numpy数组的最近邻居

Question

我有一个n维向量，并且我想使用euclidian距离在n维向量列表中找到它的k个最近邻居。

我写了下面的代码（k = 10），它运行得很慢，但我想知道是否有更优化的解决方案。

def nearest_neighbors(value, array, nbr_neighbors=1): 
    return np.argsort(np.array([np.linalg.norm(value-x) for x in array]))[:nbr_neighbors] 

Answer 1

使用scipy的kd-tree。

一个小例子是available here。

许多人似乎抱怨的性能，并建议sklearn's implementation虽然（链接sklearn.neighbors，这是使用data-structure内部）！

Answer 2

正如sascha所说，我最终使用了scipy库（但方法为NearestNeighbors），将计算时间从50小时减少到36分钟。这是我不应该尝试重新实现自己的计算，因为专用库对此更加优化。

NearestNeighbors方法还允许您传入值列表并返回每个值的k个最近邻居。

最后的代码是：

def nearest_neighbors(values, all_values, nbr_neighbors=10): 
    nn = NearestNeighbors(nbr_neighbors, metric='cosine', algorithm='brute').fit(all_values) 
    dists, idxs = nn.kneighbors(values)