稀疏矩阵与稀疏V的欧氏距离

Question

我正在研究一个大学作业的KNN算法，目前我正在寻找存储为Scipy lil_矩阵的每个训练向量之间的欧几里德距离（由于向量中值的稀疏性），以及存储为1 x n lil_矩阵的测试向量之间的欧几里得距离。在

为了计算出欧几里得距离，我执行以下代码：

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

其中sentenceVector是一个1行的lil峎u矩阵，正数是一个大小为n x m的lil峎矩阵

我想尝试计算出比逐行遍历正数矩阵和每次计算欧几里德距离更快的方法，或者运行正数矩阵和句子向量向量之间的欧几里德距离，然后返回一个带有欧几里得距离的1×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])

但我们希望使用稀疏矩阵，这会使事情变得更加困难：

^{pr2}$

这是可能的，但您需要使用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]])