在稀疏矩阵中排序

Question

我有一个稀疏矩阵.我需要逐行对此矩阵进行排序并创建另一个[稀疏]矩阵.代码可以更好地解释它:

# for `rand` function, you need newer version of scipy.
from scipy.sparse import *
m = rand(6,6, density=0.6)
d = m.getrow(0)
print d

输出1

(0, 5) 0.874881629788 
(0, 4) 0.352559852239 
(0, 2) 0.504791645463 
(0, 1) 0.885898140175

我有这个m矩阵.我想创建一个m的排序版本的新矩阵.新矩阵包含这样的第0行.

new_d = new_m.getrow(0)
print new_d

输出2

(0, 1) 0.885898140175
(0, 5) 0.874881629788  
(0, 2) 0.504791645463
(0, 4) 0.352559852239

所以我可以获得哪个列更大等:

print new_d.indices

OUTPUT3

array([1, 5, 2, 4])

当然,每行应该如上所述独立排序.

我有一个解决这个问题的方法,但它并不优雅.

Answer 1

如果您愿意忽略矩阵的零值元素,则下面的代码应该有效.它也比使用getrow方法的实现快得多,这种方法相当慢.

from itertools import izip

def sort_coo(m):
    tuples = izip(m.row, m.col, m.data)
    return sorted(tuples, key=lambda x: (x[0], x[2]))

例如:

    >>> from numpy.random import rand
    >>> from scipy.sparse import coo_matrix
    >>>
    >>> d = rand(10, 20)
    >>> d[d > .05] = 0
    >>> s = coo_matrix(d)
    >>> sort_coo(s)
    [(0, 2, 0.004775589084940246),
     (3, 12, 0.029941507166614145),
     (5, 19, 0.015030386789436245),
     (7, 0, 0.0075044957259399192),
     (8, 3, 0.047994403933129481),
     (8, 5, 0.049401058471327031),
     (9, 15, 0.040011608000125043),
     (9, 8, 0.048541825332137023)]

根据您的需要,您可能需要调整lambda中的排序键或进一步处理输出.如果你想要连续索引字典中的所有内容,你可以这样做:

from collections import defaultdict

sorted_rows = defaultdict(list)

for i in sort_coo(m):
     sorted_rows[i[0]].append((i[1], i[2]))

Answer 2

我的糟糕解决方案是这样的：

from scipy.sparse import coo_matrix
import numpy as np
a = []
for i in xrange(m.shape[0]): # assume m is square matrix.
   d = m.getrow(i)
   n = len(d.indices)
   s = zip([i]*n, d.indices, d.data)
   sorted_s = sorted(s, key=lambda v: v[2], reverse=True)
   a.extend(sorted_s)
a = np.array(a)
new_m = coo_matrix((a[:,2], (a[:,0], a[:,1])), m.shape)

上面可能有一些简单的错误，因为我还没有检查过。但我想这个想法很直观。有什么好的解决办法吗？

编辑

这个新的矩阵创建可能是无用的，因为如果您调用getrow方法，那么顺序会再次被破坏。只coo_matrix.col保留订单。

另一种解决方案

这不是精确的解决方案，但可能会有所帮助：

def sortSparseMatrix(m, rev=True, only_indices=True):

    """ Sort a sparse matrix and return column index dictionary
    """
    col_dict = dict() 
    for i in xrange(m.shape[0]): # assume m is square matrix.
        d = m.getrow(i)
        s = zip(d.indices, d.data)
        sorted_s = sorted(s, key=lambda v: v[1], reverse=True)
        if only_indices:
            col_dict[i] = [element[0] for element in sorted_s]
        else:
            col_dict[i] = sorted_s
    return col_dict

>>> print sortSparseMatrix(m)
{0: [5, 1, 0],
 1: [1, 3, 5],
 2: [1, 2, 3, 4],
 3: [1, 5, 2, 4],
 4: [0, 3, 5, 1],
 5: [3, 4, 2]}