Euclidean distance (python3, sklearn): эффективно вычислять ближайшие пары и их соответствующие расстояния

Question

Мне дана двухмерная матрица X, состоящая из плавающих значений и должна вычислять евклидовы расстояния между всеми парами строк, а затем вычислять верхние индексы k строк с наименьшими расстояниями и возвращаем их (где k> 0). Я тестирую с небольшой массив, и это то, что я до сих пор ...

import numpy as np 
from sklearn.metrics.pairwise import euclidean_distances 

X_testing = np.asarray([[1,2,3.5],[4,1,2],[0,0,2],[3.4,1,5.6]]) 
test = euclidean_distances(X_testing, X_testing) 
print(test) 

В результате распечатке:

[[ 0.   3.5   2.6925824 3.34215499] 
[ 3.5   0.   4.12310563 3.64965752] 
[ 2.6925824 4.12310563 0.   5.05173238] 
[ 3.34215499 3.64965752 5.05173238 0.  ]] 

Далее необходимо эффективно вычислить верхний K наименьшие расстояния между всеми парами строк и возвращать соответствующие k кортежей (row1, row2, distance_value) в порядке в виде списка.

Таким образом, в приведенном выше тестовом случае, если к = 2, то я должен был бы возвратить следующее:

[(0, 2, 2,6925824), (0, 3, 3,34215499)]

Есть ли встроенный способ (как в scipy, sklearn, numpy и т. Д.), Так и в любом другом способе эффективного вычисления этого? Хотя приведенный выше тестовый пример невелик, на самом деле двухмерный массив очень велик, поэтому память и время являются проблемой. Спасибо

Answer 1

Это пример, но включает в себя понимание списка, чтобы вы могли видеть нарезку. Очевидно, это не демон скорости, а больше для понимания.

>>> import numpy as np 
>>> a = np.random.randint(0,10, size=(5,5)) 
>>> a 
array([[8, 3, 3, 8, 9], 
     [0, 8, 6, 6, 5], 
     [6, 7, 6, 5, 0], 
     [4, 2, 4, 0, 3], 
     [4, 1, 3, 2, 2]]) 
>>> idx = np.argsort(a, axis=1) 
>>> idx 
array([[1, 2, 0, 3, 4], 
     [0, 4, 2, 3, 1], 
     [4, 3, 0, 2, 1], 
     [3, 1, 4, 0, 2], 
     [1, 3, 4, 2, 0]]) 
>>> v = np.vstack([ a[i][idx[i]] for i in range(len(idx))]) 
>>> v 
array([[3, 3, 8, 8, 9], 
     [0, 5, 6, 6, 8], 
     [0, 5, 6, 6, 7], 
     [0, 2, 3, 4, 4], 
     [1, 2, 2, 3, 4]]) 
>>> 
>>> v3 = np.vstack([ a[i][idx[i]][:3] for i in range(len(idx))]) 
>>> v3 
array([[3, 3, 8], 
     [0, 5, 6], 
     [0, 5, 6], 
     [0, 2, 3], 
     [1, 2, 2]]) 
>>> 

Вы можете возиться с разрезанием и поместить его в полный np, если хотите.

Answer 2

scipy.spatial Использование вместо sklearn (который я до сих пор не установлен) я могу получить такую ​​же матрицу расстояний:

In [623]: from scipy import spatial 
In [624]: pdist=spatial.distance.pdist(X_testing) 
In [625]: pdist 
Out[625]: 
array([ 3.5  , 2.6925824 , 3.34215499, 4.12310563, 3.64965752, 
     5.05173238]) 
In [626]: D=spatial.distance.squareform(pdist) 
In [627]: D 
Out[627]: 
array([[ 0.  , 3.5  , 2.6925824 , 3.34215499], 
     [ 3.5  , 0.  , 4.12310563, 3.64965752], 
     [ 2.6925824 , 4.12310563, 0.  , 5.05173238], 
     [ 3.34215499, 3.64965752, 5.05173238, 0.  ]]) 

pdist находится в сжатой форме, которой indicies в squareform можно найти с

In [629]: np.triu_indices(4,1) 
Out[629]: 
(array([0, 0, 0, 1, 1, 2], dtype=int32), 
array([1, 2, 3, 2, 3, 3], dtype=int32)) 

2 маленьких расстояниях 1-й 2 значения

In [630]: idx=np.argsort(pdist) 
In [631]: idx 
Out[631]: array([1, 2, 0, 4, 3, 5], dtype=int32) 

Так что мы хотим [1,2] от pdist и соответствующие элементы triu:

In [633]: pdist[idx[:2]] 
Out[633]: array([ 2.6925824 , 3.34215499]) 
In [634]: np.transpose(np.triu_indices(4,1))[idx[:2],:] 
Out[634]: 
array([[0, 2], 
     [0, 3]], dtype=int32) 

и собрать эти значения в виде списка кортежей:

In [636]: I,J = np.triu_indices(4,1) 
In [637]: kbig = idx[:2] 
In [638]: [(i,j,d) for i,j,d in zip(I[kbig], J[kbig], pdist[kbig])] 
Out[638]: [(0, 2, 2.6925824035672519), (0, 3, 3.3421549934136805)] 

Numpy array of distances to list of (row,col,distance)