Как рассчитать индексы при добавлении csr_matrix? - PullRequest
Новая
       77

Как рассчитать индексы при добавлении csr_matrix?

0 голосов
/ 26 декабря 2018

Я изучаю коды scipy для разреженных операций с матрицами.Тем не менее, я озадачен тем, как вычисляются индексы csr_matrix при выполнении операции сложения.Мой код прост: 

B = A + A.T
A.toarray()
array([[1., 1., 1., 1., 0., 1., 1., 0., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 0., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.]])
A.indices:
array([ 0,  2,  1,  5, 10,  3,  6, 11,  9,  8,  
    1,  2,  9, 10,  5,  8,  6, 11,  3,  7,  
    2, 10,  1,  5,  9,  6, 11,  7,  8,  3,  
    3,  8,  6,  7,  5, 11,  9, 10,  2,  1,  
    4,  9,  1,  7,  8, 11,  3,  6, 10,  5,  
    5,  6, 11, 10,  8,  9,  3,  2,  7,  1,  
    6,  5,  8, 11,  9, 10,  3,  7,  2,  1,  
    7,  9,  3,  6,  8,  5, 11, 10,  2,  1,  
    8,  6, 11,  9,  5,  3, 10,  7,  1,  2,  
    9, 11, 10,  8,  6,  5,  7,  3,  2,  1, 
    10, 11, 5,  9,  6,  8,  2,  3,  1,  7, 
    11, 10,  5,  6,  8,  9,  3,  7,  2, 1], dtype=int32)

Я отладил код для погружения в scipy для получения более подробной информации и обнаружил, что операция .T превращает матрицу A в матрицу формата CSC.И затем, в дополнение к операции перегрузки, AT будет снова преобразован в матрицу формата CSR, но его индексы будут изменены, как показано ниже: 

A.T.toarray():
array([[1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [1., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [0., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
   [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.]])
A.T.indices:
array([ 0,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  0,  1,  2,  3,
    5,  6,  7,  8,  9, 10, 11,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
   10, 11,  4,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  0,  1,
    2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  1,  2,  3,  4,  5,  6,  7,
    8,  9, 10, 11,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  0,
    1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  0,  1,  2,  3,  4,  5,
    6,  7,  8,  9, 10, 11,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
   11], dtype=int32)

, что я не могу понять, это B.indices, показанные ниже: 

B.toarray()
array([[2., 1., 1., 1., 0., 1., 1., 0., 1., 1., 1., 1.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [1., 2., 2., 2., 0., 2., 2., 2., 2., 2., 2., 2.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [0., 1., 0., 1., 2., 1., 1., 1., 1., 1., 1., 1.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [0., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.],
   [1., 2., 2., 2., 1., 2., 2., 2., 2., 2., 2., 2.]])
B.indices
array([ 8,  9, 11,  6,  3, 10,  5,  1,  2,  0,  
    4,  0,  7,  3, 11,  6,  8,  5, 10,  9,  2,  1,  
    0,  3,  8,  7, 11,  6,  9,  5,  1, 10,  2,  
    4,  0,  1,  2, 10,  9, 11,  5,  7,  6,  8,  3,  
    5, 10,  6,  3, 11,  8,  7,  1,  9,  4,
    4,  0,  1,  7,  2,  3,  9,  8, 10, 11,  6,  5,  
    4,  0,  1,  2,  7,  3, 10,  9, 11,  8,  5,  6,  
    4,  1,  2, 10, 11,  5,  8,  6,  3,  9,  7,  
    4,  0,  2,  1,  7, 10,  3,  5,  9, 11,  6,  8,
    4,  0,  1,  2,  3,  7,  5,  6,  8, 10, 11,  9,  
    4,  0,  7,  1,  3,  2,  8,  6,  9,  5, 11, 10,  
    4,  0,  1,  2,  7,  3,  9,  8,  6,  5, 10, 11], dtype=int32)

Результат B вычисляется через C ++, поэтому библиотека _sparsetools.cpython-35m-x86_64-linux-gnu.so в scipy, поэтому я не могу получить ее код.

Эта проблема почти сводит меня с ума.Надеюсь, некоторые из вас могут мне помочь.

1 Ответ

0 голосов
/ 27 декабря 2018

Если я сделаю A с вашего A.todense() дисплея: 

In [156]: A = np.array([[1., 1., 1., 1., 0., 1., 1., 0., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 0., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.],
     ...:    [0., 1., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1.]])

и, что не так: 

In [159]: M = sparse.csr_matrix(A)
In [160]: M
Out[160]: 
<12x12 sparse matrix of type '<class 'numpy.float64'>'
    with 120 stored elements in Compressed Sparse Row format>

In [162]: M.indices
Out[162]: 
array([ 0,  1,  2,  3,  5,  6,  8,  9, 10, 11,  1,  2,  3,  5,  6,  7,  8,
        9, 10, 11,  1,  2,  3,  5,  6,  7,  8,  9, 10, 11,  1,  2,  3,  5,
        6,  7,  8,  9, 10, 11,  1,  3,  4,  5,  6,  7,  8,  9, 10, 11,  1,
        2,  3,  5,  6,  7,  8,  9, 10, 11,  1,  2,  3,  5,  6,  7,  8,  9,
       10, 11,  1,  2,  3,  5,  6,  7,  8,  9, 10, 11,  1,  2,  3,  5,  6,
        7,  8,  9, 10, 11,  1,  2,  3,  5,  6,  7,  8,  9, 10, 11,  1,  2,
        3,  5,  6,  7,  8,  9, 10, 11,  1,  2,  3,  5,  6,  7,  8,  9, 10,
       11], dtype=int32)

Эти индексы не совпадают с вашими - иличто они одинаковы, но отсортированы по строке: 

In [164]: for i in range(12):
     ...:     print(M.indices[M.indptr[i]:M.indptr[i+1]])
     ...:     
[ 0  1  2  3  5  6  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  3  4  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]
[ 1  2  3  5  6  7  8  9 10 11]

И для csr версии его транспонирования: 

In [165]: M1 = M.T.tocsr()
In [166]: for i in range(12):
     ...:     print(M1.indices[M1.indptr[i]:M1.indptr[i+1]])

[0]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[4]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]

Выполнение транспонирования путем переключения в формат csc, с теми же атрибутами, это быстро, но, как вы заметили, чтобы сделать дополнение, оно преобразовало обратно в csr.

, а затем взяло сумму: 

In [167]: B = M+M.T
In [168]: for i in range(12):
     ...:     print(B.indices[B.indptr[i]:B.indptr[i+1]])

[ 0  1  2  3  5  6  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 1  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11]

После M индексы упорядочены по строкам, шаблон довольно очевиден. 

In [172]: M.has_sorted_indices
Out[172]: True

Мои версии также canonical.

Все строки A имеют 10 ненулевых терминов.B имеет 10, 11, 12;транспонирование заполнено 0-2 ненулевыми значениями.

Ваш A имеет несортированные индексы.A.T.indices отсортированы.Я полагаю, что кто-то может сделать вывод о методе оценки, сравнивая неупорядоченный B.indices с A.indices.Но стоит ли это того?

===

Я воссоздал ваши неканонические матрицы следующим образом: 

In [186]: altindices = np.array([ 0,  2,  1,  5, 10,  3,  6, 11,  9,  8,  
     ...:     1,  2,  9, 10,  5,  8,  6, 11,  3,  7,  
     ...:     2, 10,  1,  5,  9,  6, 11,  7,  8,  3,  
     ...:     3,  8,  6,  7,  5, 11,  9, 10,  2,  1,  
     ...:     4,  9,  1,  7,  8, 11,  3,  6, 10,  5,  
     ...:     5,  6, 11, 10,  8,  9,  3,  2,  7,  1,  
     ...:     6,  5,  8, 11,  9, 10,  3,  7,  2,  1,  
     ...:     7,  9,  3,  6,  8,  5, 11, 10,  2,  1,  
     ...:     8,  6, 11,  9,  5,  3, 10,  7,  1,  2,  
     ...:     9, 11, 10,  8,  6,  5,  7,  3,  2,  1, 
     ...:     10, 11, 5,  9,  6,  8,  2,  3,  1,  7, 
     ...:     11, 10,  5,  6,  8,  9,  3,  7,  2, 1], dtype='int32')
    In [188]: M2 = sparse.csr_matrix((M.data, altindices, M.indptr))

M2.T.indices такие же, как M2.indices (csc эквивалент), ноM2.T.tocsr() сортируются при отображении.B2 = M2+M2.T имеет такие же индексы, как и у вас.

Если я вычисляю только одну строку, я получаю те же индексы, подтверждая мое предположение, что он выполняет суммирование строки за строкой (итерация с indptr, как и выше):

In [194]: M2[0,:]+(M2.T)[0,:]
Out[194]: 
<1x12 sparse matrix of type '<class 'numpy.float64'>'
    with 10 stored elements in Compressed Sparse Row format>
In [195]: _.indices
Out[195]: array([ 8,  9, 11,  6,  3, 10,  5,  1,  2,  0], dtype=int32)
...