Scipy稀疏矩阵和稀疏矢量之间的欧几里德距离

Question

我正在研究大学任务的KNN算法，此刻我正在寻找作为Scipy lil_matrix存储的每个训练矢量之间的欧几里得距离（由于由于上述相同的原因，向量中的值的稀疏性）以及作为1×nil_matrix存储的测试向量。

制定出欧氏距离，然后我做了下面的代码：

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

哪里sentenceVector是1行的lil_matrix和阳性是大小为n×m的一个lil_matrix。

我想试着找出一些东西，比逐行检查正向矩阵和每次评估欧氏距离，并且可能运行正向量矩阵和sentenceVector向量之间的欧氏距离，并返回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格式。

编辑：我忘了最简单的解决方案：使用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]])