Вопрос по sorting, python, scipy, sparse-matrix – Сортировка в разреженной матрице

8

У меня разреженная матрица. Мне нужно отсортировать эту матрицу построчно и создать другую [разреженную] матрицу. Код может объяснить это лучше:

<code># 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
</code>
Output1
<code>(0, 5) 0.874881629788 
(0, 4) 0.352559852239 
(0, 2) 0.504791645463 
(0, 1) 0.885898140175
</code>

У меня есть этоm матрица. Я хочу создать новую матрицу с отсортированной версией m. Новая матрица содержит 0-ую строку, подобную этой.

<code>new_d = new_m.getrow(0)
print new_d
</code>
Выход2
<code>(0, 1) 0.885898140175
(0, 5) 0.874881629788  
(0, 2) 0.504791645463
(0, 4) 0.352559852239
</code>

Так что я могу узнать, какой столбец больше и т. Д .:

<code>print new_d.indices
</code>
Output3
<code>array([1, 5, 2, 4])
</code>

Конечно, каждая строка должна быть отсортирована, как указано выше, независимо друг от друга.

У меня есть одно решение этой проблемы, но оно не изящно.

Как output2 является отсортированной версией output1? Кажется, вы забыли элемент с индексом 0 ... Fred Foo
@ larsmans Я тебя не понял. Вы спрашиваете (0, 0)? Если да, эта ячейка равна 0, и разреженная матрица не пытается ее сохранить. Baskaya
Так что, вы хотите отсортировать разреженную матрицу построчно? talonmies
@ Thorn: да, это то, что я имел в виду. Поэтому, когда вы сортируете записи, вас не интересуют нули? Fred Foo
Да. Извините, я объясняю эту простую вещь, как атомная бомба. Baskaya

Ваш Ответ

2   ответа
7

приведенный ниже код должен работать. Это также намного быстрее, чем реализации, использующие метод 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)]

В зависимости от ваших потребностей вы можете настроить ключи сортировки в лямбда-выражении или продолжить обработку выходных данных. Если вы хотите, чтобы все в словаре индексировалось подряд, вы можете сделать:

from collections import defaultdict

sorted_rows = defaultdict(list)

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

Мое плохое решение таково:

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]}

Похожие вопросы