使用欧氏距离在 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。

一个小例子是available here。

很多人似乎抱怨性能并在内部推荐sklearn's implementation though (links sklearn.neighbors, which is using this data-structure）！

Answer 2

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

NearestNeighbors 方法还允许您传入一个值列表和 returns 每个值的 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 个。

使用欧氏距离在 numpy 数组列表中查找 numpy 数组的最近邻居

Find nearest neighbors of a numpy array in list of numpy arrays using euclidian distance

python

arrays

algorithm

numpy

nearest-neighbor