python中获取大特征向量最近10个欧几里德邻域的最快方法

Question

我有一个numpy数组，有10000个向量，每个向量有3000个元素。我想返回最近对的前10个指数，以及它们之间的距离。因此，如果第5行和第7行的最近欧几里德距离为0.005，第8行和第10行的第二个最近欧几里德距离为0.0052，那么我想返回[（8,10，.0052），（5,7，.005）]。传统的for-loop方法速度很慢。有没有另一种更快的方法来获取大特征向量的欧几里德邻域（存储为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

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的平方根，这是很长的步骤（在循环之外）。在

Answer 2

我将把这个作为答案，但我承认这并不是这个问题的真正解决方案，因为它只适用于较小的阵列。问题是，如果你想快速避免循环，你就需要一次计算所有成对的距离，这意味着内存复杂度是按输入平方的顺序排列的。。。假设10000行*10000行*3000个元素/行*4个字节/行（假设我们使用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]])