Самый быстрый способ получить самые близкие 10 эвклидовых соседей большого вектор-функции в python

Question

У меня есть массив numpy, который имеет 10000 векторов с 3000 элементов в каждом. Я хочу вернуть 10 лучших индексов ближайших пар с расстоянием между ними. Так что, если строки 5 и ряд 7 имеют самое близкое эвклидовое расстояние 0,005, а ряд 8 и ряд 10 имеют второе ближайшее эвклидовое расстояние 0,0052, то я хочу вернуться [(8,10, .0052), (5,7. 005)]. Традиционный метод цикла очень медленный. Существует ли альтернативный более быстрый подход к способу получения евклидовых соседей векторов больших объектов (хранимых в виде массива 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

Я отправлю это как ответ, но я признаю, что это не настоящее решение вопроса, потому что оно будет работать только для небольших массивов. Проблема в том, что если вы хотите быть очень быстрым и избегать циклов, вам нужно будет вычислить все попарные расстояния одновременно, а это означает сложность памяти в порядке квадрата ввода ... Скажем, 10 000 строк * 10 000 строки * 3000 э/строк * 4 байта/строка (скажем, мы используем float32) ≈ 1 ТБ (!) требуемой памяти (на самом деле, возможно, дважды, потому что вам, вероятно, потребуется несколько массивов такого размера). Поэтому, хотя это возможно, это не практично с такими размерами. Следующий код показывает, как вы могли бы реализовать это (с размерами, деленными на 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]])