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

Question

我有一个 n 维向量，我想使用欧几里得距离在 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。

这里有一个小例子。

许多人似乎抱怨性能并推荐 sklearn 的实现(链接 sklearn.neighbors，它在内部使用此数据结构(！

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)

Answer 3

我会尝试使用 scipy 的 pdist 函数通过蛮力找到成对距离： https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html

它应该非常快，因为 pdist 是高度优化的。然后为每个元素选择最近的 k。