Euclidean Расстояние между Scipy Sparse Matrix и Sparse Vector

Question

Я работаю над алгоритмом KNN для университетского задания, и в настоящий момент я работаю над поиском евклидова расстояния между каждым из векторов обучения, хранящимся как Scipy lil_matrix (из-за разреженность значений в векторах) и вектор тестирования, сохраненный как 1 xn lil_matrix по тем же причинам выше.

Для того, чтобы выработать евклидова расстояния я затем делать следующий код:

for positiveIndex, positivesComparison in enumerate(positives): 
    result.append((spatial.distance.euclidean(positivesComparison.todense(),sentenceVector.todense()), positiveIndex, 1)) 

Где sentenceVector является lil_matrix 1 ряд, и позитивов является lil_matrix размера п х т.

Я хочу попробовать что-то быстрее, чем проходить через положительную матрицу подряд за строкой и каждый раз оценивать эвклидовое расстояние и, возможно, запустить эвклидовое расстояние между матрицей положительных элементов и вектором предложенияVector и вернуть 1 xm матрица с евклидовыми расстояниями. Причина, по которой я хочу сделать это, заключается в том, что текущая система относительно медленна для вычисления, поскольку в основном это временная сложность NM, поскольку мне нужно вычислить более одного теста предложения. Возможно ли это, и если да, как бы я это сделал?

Примечание, задача состоит в том, чтобы оценить эффективность использования различных значений K для алгоритма Knn, а не на фактической реализации KNN (хотя мы не имеем права использовать библиотеки Knn для выполнения задачи)

Answer 1

Вы можете вычислительные партии евклидовы расстояния довольно легко:

In [10]: a = np.random.random(size=(4,5)) 

In [11]: b = np.random.random(size=(1,5)) 

In [12]: from scipy.spatial.distance import euclidean 

In [13]: [euclidean(aa, b) for aa in a] 
Out[13]: [1.1430615949614429, 0.568517046878056, 1.3302284168375587, 1.0581730230363529] 

In [14]: np.sqrt(np.sum((a - b)**2, axis=1)) 
Out[14]: array([ 1.1431, 0.5685, 1.3302, 1.0582]) 

Но мы хотим использовать разреженные матрицы, что делает вещи немного сложнее:

In [22]: import scipy.sparse as ss 

In [23]: sa = ss.lil_matrix(a) 

In [24]: sb = ss.lil_matrix(b) 

In [25]: np.sqrt(np.sum((sa - sb)**2, axis=1)) # <-- ValueError: inconsistent shapes 

Это можно сделать, но вам нужно будет использовать some tricks.

Что еще более важно, вы должны посмотреть, насколько велики (и насколько разрежены) ваши векторы на самом деле. Возможно, вы быстрее оставите все плотным, и это, безусловно, избавит вас от головной боли.

Наконец, я бы избегал использовать матрицы формата LIL, поскольку они являются одним из самых медленных доступных форматов. Для вашего случая загляните в формат CSR.

EDIT: Я забыл простейшее решение: используйте scikit-learn!

In [36]: from sklearn.metrics import pairwise_distances 

In [37]: pairwise_distances(a, b) 
Out[37]: 
array([[ 1.1431], 
     [ 0.5685], 
     [ 1.3302], 
     [ 1.0582]]) 

In [38]: pairwise_distances(sa, sb) 
Out[38]: 
array([[ 1.1431], 
     [ 0.5685], 
     [ 1.3302], 
     [ 1.0582]])