Pythonで大規模な特徴ベクトルに最も近い10個のユークリッド近似を得る最速の方法

Question

私はそれぞれが3000個の要素を持つ10,000個のベクトルを持つnumpy配列を持っています。私はそれらの間の距離で最も近いペアの上位10のインデックスを返したいと思います。行5と行7が最も近いユークリッド距離0.005を持ち、行8と行10が0.0052の2番目に近いユークリッド距離を持っていれば、私は[（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のダウンロードを使用して、マトリックスの2つのベクトル間のユークリッド距離を計算するための機能です。 次に、私は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

これを回答として投稿しますが、それは小さな配列に対してのみ機能するため、実際の解決策ではありません。問題は、あなたが本当に速くループを避けたいのであれば、すべての対の距離を一度に計算する必要があり、それは入力の2乗のオーダーのメモリの複雑さを意味します... 10,000行* 10,000行×3,000エレム/行×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]])