在Scipy的CSR矩阵中计算欧几里得距离。

Question

我需要计算存储在csr稀疏矩阵和一些点列表中的所有点之间的欧几里得距离。将csr转换为密集矩阵会更容易，但由于内存不足，我无法这样做，因此需要保持其为csr。

例如，我有这个data_csr稀疏矩阵（在csr和dense视图中查看）：

data_csr
(0, 2)  4
(1, 0)  1
(1, 4)  2
(2, 0)  2
(2, 3)  1
(3, 5)  1
(4, 0)  4
(4, 2)  3
(4, 3)  2

data_csr.todense()
[[0, 0, 4, 0, 0, 0]
 [1, 0, 0, 0, 2, 0]
 [2, 0, 0, 1, 0, 0]
 [0, 0, 0, 0, 0, 1]
 [4, 0, 3, 2, 0, 0]]

并且这个中心列出了以下要点：

center
array([[0, 1, 2, 2, 4, 1],
      [3, 4, 1, 2, 4, 0]])

使用 scipy.spatial 包，data_csr 和 center 之间的欧几里得距离数组如下所示。因此，center 的每一行中的总共 6 个点会与 data_csr 的所有行进行计算。结果数组的第一行(2,5)是第一行 center 与 data_csr 的所有行之间的欧氏距离。

scipy.spatial.distance.cdist(center, data_csr, 'euclidean')

array([[ 5.09901951,  3.87298335,  5.19615242,  5.        ,  5.91607978],
      [ 7.34846923,  5.38516481,  5.91607978,  6.8556546 ,  6.08276253]])

到目前为止，我已学会如何通过以下方式获取非零值及其索引：

data_csr.data
array([4, 1, 2, 2, 1, 1, 4, 3, 2])

data_csr.indices
array([2, 0, 4, 0, 3, 5, 0, 2, 3])

但是我仍然无法算出这两个对象之间的编辑距离。

- Rochana Nana

---

假设数据密集，您如何计算数据_csr和center之间的欧几里得距离？ - Alexander

@Alexander 我已经编辑过了，我使用了 scipy.spatial.distance.cdist(center, data_csr, 'euclidean')。 - Rochana Nana

我仍然无法复制您计算距离的结果。请参考此帖子，了解如何从矩阵中提取数据，这是我所能做到的。https://dev59.com/JloV5IYBdhLWcg3wLsT5#36587845 - Alexander

Answer 1

sklearn中实现了对稀疏矩阵的成对欧几里得距离计算（正如hpaulj指出的那样，scipy的实现不适用于稀疏矩阵）。

下面是以hpaulj的示例为例：

import scipy.sparse
import sklearn.metrics.pairwise
data = [4,1,2,2,1,1,4,3,2]  
col = [0,1,1,2,2,3,4,4,4]
row = [2,0,4,0,3,5,0,2,3]
M = scipy.sparse.csr_matrix((data,(col,row)))
distances = sklearn.metrics.pairwise.pairwise_distances(M,M)

文档：http://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.pairwise_distances.html

该文档为sklearn.metrics.pairwise.pairwise_distances函数的API文档，用于计算两个向量之间的距离或相似性。

- mathieu

---

只是为了理解，在稀疏矩阵的背景下。我正在阅读这个问题，似乎sklearn的pairwise_distances非常“低效”，但另一方面，这里似乎有一个很好的替代方案，你认为哪一个是最快的？ - Pablo

Answer 2

那我们来创建你的矩阵吧（可惜你没有提供可以复制粘贴的输入）。

In [114]: data=[4,1,2,2,1,1,4,3,2]   
In [115]: col=[0,1,1,2,2,3,4,4,4]
In [116]: row=[2,0,4,0,3,5,0,2,3]
In [117]: M=sparse.csr_matrix((data,(col,row)))

In [118]: M
Out[118]: 
<5x6 sparse matrix of type '<type 'numpy.int32'>'
    with 9 stored elements in Compressed Sparse Row format>

In [119]: M.A
Out[119]: 
array([[0, 0, 4, 0, 0, 0],
       [1, 0, 0, 0, 2, 0],
       [2, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 1],
       [4, 0, 3, 2, 0, 0]])

In [121]: center=np.array([[0,1,2,2,4,1],[3,4,1,2,4,0]])

那么您是如何计算距离的？M.A是(5,6)，center是(2,6)。这两个数组之间的关系并不明显。

至于访问“原始”的稀疏值，coo格式是最容易理解的。它与我用来创建矩阵的行、列、数据相同。

In [131]: M.tocoo().data
Out[131]: array([4, 1, 2, 2, 1, 1, 4, 3, 2])

In [132]: M.tocoo().col
Out[132]: array([2, 0, 4, 0, 3, 5, 0, 2, 3])

In [133]: M.tocoo().row
Out[133]: array([0, 1, 1, 2, 2, 3, 4, 4, 4])

csr 将相同的信息存储在 data、indices 和 indptr 数组中，但您需要进行一些数学计算才能从后两者中拉取 i,j 值。 csr 乘法例程很好地利用了这些数组。

通常情况下，与加法/减法相比，使用 csr 矩阵进行乘法运算更佳。

我等待进一步澄清。

spatial.distance.cdist(center,M.A, 'euclidean')
Out[156]: 
array([[ 5.09901951,  3.87298335,  5.19615242,  5.        ,  5.91607978],
       [ 7.34846923,  5.38516481,  5.91607978,  6.8556546 ,  6.08276253]])

我们需要做的是研究这个函数，了解它的输入。我们可能需要超越文档并查看代码。

但是，在查看此代码时，我看到了确保xB是二维数组的步骤，并且具有与xA相同数量的列。然后对于euclidian，它调用了。

_distance_wrap.cdist_euclidean_wrap(_convert_to_double(XA),
                                    _convert_to_double(XB), dm)

这段代码看起来像是一些C代码的封装。我无法想象任何一种方法将稀疏矩阵提供给它。

您可以遍历行; 使用 M[[0],:].A 调用 dist 与 M.A[[0],:] 是相同的 - 除了速度不同之外。 遍历稀疏矩阵的行有点慢，因为每次迭代都必须构建一个新的稀疏矩阵。csr 和 lil 是两个最快的行迭代类型。

以下是可能更快的一种方法 - 直接迭代lil格式的属性：

 def foo(a,b,n):
    # make a dense array from data,row
    res = np.zeros((1,n))
    res[0,b]=a
    return res

In [190]: Ml=M.tolil()

In [191]: Ml.data
Out[191]: array([[4], [1, 2], [2, 1], [1], [4, 3, 2]], dtype=object)

In [192]: Ml.rows
Out[192]: array([[2], [0, 4], [0, 3], [5], [0, 2, 3]], dtype=object)

In [193]: rowgen=(foo(a,b,6) for a,b in zip(Ml.data,Ml.rows))

In [194]: np.concatenate([spatial.distance.cdist(center,row, 'euclidean') for row in rowgen],axis=1)
Out[194]: 
array([[ 5.09901951,  3.87298335,  5.19615242,  5.        ,  5.91607978],
       [ 7.34846923,  5.38516481,  5.91607978,  6.8556546 ,  6.08276253]])

目前我将跳过时间测试。

- hpaulj

---

我已经修改了案例并解释了如何计算它，希望足够清晰易懂。使用scipy.spatial.distance.cdist(center, data_csr, 'euclidean')。 - Rochana Nana