减少从非连续坐标列表创建的 python 中的稀疏矩阵

Question

我正在尝试构建一个双邻接矩阵并找到它的特征值。由于数据集的构建方式，列号和行号是不连续的。这使得矩阵大小爆炸。如何从稀疏矩阵中清除完全空的行和列？其余的行和列应该以连续的方式重新列举。

主题域是买家和卖家以及他们的购买。买卖双方用随机整数 ID 表示。这些 ID 是不连续的。数据集是CSV格式的buyer_ID,seller_ID列表形式的所有购买列表。

这是我的代码

from sympy import *
import scipy
import csv
rows=[]
cols=[]
data=[]
with open('dataset.txt', 'rt') as csvfile:
    reader = csv.reader(csvfile, delimiter=',')              
    next(reader, None)  # skip the headers
    for row in reader:    
        rows.append(int(row[0]))
        cols.append(int(row[1]))
        data.append(1.0) # values were absent in the list of edges
print(len(rows))
print(len(set(rows)))
print(len(cols))
print(len(set(cols)))
edges_matrix = coo_matrix((data,(rows,cols)))
print(edges_matrix.get_shape())
biajacency_matrix=bmat([[None,edges_matrix],[edges_matrix.transpose(),None]])
print(biajacency_matrix.get_shape())
scipy.sparse.linalg.eigen.eigsh(biajacency_matrix,3,which='LM')

我的数据集中有 303987 行，50385 位买家和 125854 位卖家。但是因为 ID 的范围更大，所以创建的 edges_matrix 的大小为 (215115110, 215117581)。

我的双邻接（非常稀疏的正方形）矩阵变成了 430232691 的大小并且特征值函数 eigsh 因内存错误而失败。事实上，它的大部分列和行都是空的。

我怎样才能轻松地重新枚举买家和卖家以将双邻接矩阵的大小减小到 50385+125854=176249？换句话说，只保留至少有一个值的行。

我可以在构建字典 table 并加入原始数据集以替换 ID 的数据库上做同样的事情。但在 Python?

中这可能更容易完成吗？

解决方案：

baj_m=biajacency_matrix.tocsr()[list(set(rows)),:][:,list(set(cols))] # drop all zero rows and columns

Answer 1

下面是一个从稀疏矩阵中删除空行和空列的简单示例。

A=sparse.rand(100,100,format='csr')
I=np.nonzero(A.sum(0))[1].A.flatten()
J=np.nonzero(A.sum(1))[0].A.flatten()

I 和 J 是具有至少一个值的列和行的索引（或者技术上 sum !=0，这对于浮点数是一样的）。

A 
<100x100 sparse matrix of type '<class 'numpy.float64'>'
    with 100 stored elements in Compressed Sparse Row format>

A[J,:][:,I] 
<64x62 sparse matrix of type '<class 'numpy.float64'>'
    with 100 stored elements in Compressed Sparse Row format>

缩减矩阵具有相同数量的非零元素，但形状有所缩减。

这不是您的案例的完整解决方案，但我认为它为您提供了一个可以调整的工具。

请注意，只有少数稀疏格式允许像这样建立索引。幸运的是，那些有利于特征值计算的也实现了索引。

减少从非连续坐标列表创建的 python 中的稀疏矩阵

Reduce a sparse matrix in python created from a noncontiguous coordinates lists

python

algebra

matrix

scipy

sparse-matrix