python - Scipy 稀疏矩阵和稀疏向量之间的欧氏距离

Question

我正在为一项大学作业研究 KNN 算法，目前我正在寻找存储为 Scipy lil_matrix 的每个训练向量之间的欧几里德距离(由于向量中值的稀疏性) ，以及出于上述相同原因存储为 1 x n lil_matrix 的测试向量。

为了计算出欧氏距离，我正在执行以下代码:

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

其中 sentenceVector 是 1 行的 lil_matrix，positives 是大小为 n x m 的 lil_matrix。

我想尝试比逐行遍历正矩阵并每次评估欧几里得距离更快地计算出一些东西，并且可能运行正矩阵和 sentenceVector 向量之间的欧几里得距离，并返回一个 1 x m 矩阵与欧氏距离。我想这样做的原因是当前系统计算速度相对较慢，因为它基本上是 NM 时间复杂度，因为我需要计算多个句子测试。这可能吗？如果可能，我该怎么做？

请注意，任务是使用 KNN 算法的不同 K 值评估性能，而不是 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]])