在 python 中获得大特征向量的最近 10 个欧氏邻居的最快方法

Question

我有一个 numpy 数组，它有 10,000 个向量，每个向量有 3,000 个元素。我想 return 最接近的对的前 10 个索引以及它们之间的距离。因此，如果第 5 行和第 7 行的最近欧氏距离为 0.005，而第 8 行和第 10 行的第二近欧氏距离为 0.0052，那么我想 return [(8,10,.0052),(5 ,7,.005)]。传统的 for 循环方法非常慢。是否有另一种更快的方法来获取大型特征向量（存储为 np 数组）的欧几里德邻居？

我正在执行以下操作：

l = []
for i in range(0,M.shape[0]): 
    for j in range(0,M.shape[0]): 
        if i != j and i > j: 
            l.append( (i,j,euc(M[i],M[j])) 
return l

这里的 euc 是一个函数，使用 scipy 计算矩阵的两个向量之间的欧氏距离。然后我对 l 进行排序并取出前 10 个最接近的距离

Answer 1

我将 post 作为答案，但我承认这不是问题的真正解决方案，因为它只适用于较小的数组。问题是，如果你想非常快并避免循环，你需要一次计算所有成对距离，这意味着内存复杂度与输入的平方成正比......假设 10,000 行 * 10,000行 * 3,000 elems/row * 4 bytes/row（假设我们使用的是 float32）≈ 1TB (!) 所需的内存（实际上可能是两倍，因为您可能需要几个这样大小的数组）。因此，尽管有可能，但这些尺寸并不实用。以下代码显示了如何实现它（大小除以 100）。

import numpy as np

# Row length
n = 30
# Number of rows
m = 100
# Number of top elements
k = 10

# Input data
data = np.random.random((m, n))
# Tile the data in two different dimensions
data1 = np.tile(data[:, :, np.newaxis], (1, 1, m))
data2 = np.tile(data.T[np.newaxis, :, :], (m, 1, 1))
# Compute pairwise squared distances
dist = np.sum(np.square(data1 - data2), axis=1)
# Fill lower half with inf to avoid repeat and self-matching
dist[np.tril_indices(m)] = np.inf
# Find smallest distance for each row
i = np.arange(m)
j = np.argmin(dist, axis=1)
dmin = dist[i, j]
# Pick the top K smallest distances
idx = np.stack((i, j), axis=1)
isort = dmin.argsort()

# Top K indices pairs (K x 2 matrix)
top_idx = idx[isort[:k], :]
# Top K smallest distances
top_dist = np.sqrt(dmin[isort[:k]])

Answer 2

def topTen(M):
    i,j = np.triu_indices(M.shape[0], 1)
    dist_sq = np.einsum('ij,ij->i', M[i]-M[j], M[i]-M[j])
    max_i=np.argpartition(dist_sq, 10)[:10]
    max_o=np.argsort(dist_sq[max_i])
    return np.vstack((i[max_i][max_o], j[max_i][max_o], dist_sq[max_i][max_o]**.5)).T

这应该非常快，因为它只对前 10 个进行排序和平方根，这是很长的步骤（在循环之外）。

在 python 中获得大特征向量的最近 10 个欧氏邻居的最快方法

fastest way to get closest 10 euclidean neighbors of large feature vector in python

python

numpy

distance

euclidean-distance