Понять формат CSR

Question

Я пытаюсь понять, как работает scipy CSR.

https://docs.scipy.org/doc/scipy/reference/sparse.html

Например, следующей матрицы на https://en.wikipedia.org/wiki/Sparse_matrix

( 0 0 0 0 )
( 5 8 0 0 )
( 0 0 3 0 )
( 0 6 0 0 )

он говорит, что представление CSR следующее:

Должен ли V перечислять одну строку за другой с ненулевыми элементами в списке строк слева направо?

Я могу понять COL_INDEX - это индекс столбца (столбец 1 имеет индекс 0), соответствующий элементам в V.

Я не понимаю ROW_INDEX. Может кто-нибудь показать мне, как ROW_INDEX был создан из исходной матрицы? Спасибо.

   V         = [ 5 8 3 6 ]
   COL_INDEX = [ 0 1 2 1 ]
   ROW_INDEX = [ 0 0 2 3 4 ]

Answer 1

coo формат

Я думаю, что лучше начать с определения coo. Это проще для понимания и широко используется:

In [90]: A = np.array([[0,0,0,0],[5,8,0,0],[0,0,3,0],[0,6,0,0]])                                 
In [91]: M = sparse.coo_matrix(A)                                                                

Значения хранятся в 3 атрибутах:

In [92]: M.row                                                                                   
Out[92]: array([1, 1, 2, 3], dtype=int32)
In [93]: M.col                                                                                   
Out[93]: array([0, 1, 2, 1], dtype=int32)
In [94]: M.data                                                                                  
Out[94]: array([5, 8, 3, 6])

Мы можем создать новую матрицу из этих 3 массивов:

In [95]: sparse.coo_matrix((_94, (_92, _93))).A                                                  
Out[95]: 
array([[0, 0, 0],
       [5, 8, 0],
       [0, 0, 3],
       [0, 6, 0]])

упс, мне нужно добавить фигуру, так как все столбцы равны 0:

In [96]: sparse.coo_matrix((_94, (_92, _93)), shape=(4,4)).A                                     
Out[96]: 
array([[0, 0, 0, 0],
       [5, 8, 0, 0],
       [0, 0, 3, 0],
       [0, 6, 0, 0]])

Другой способ отобразить эту матрицу:

In [97]: print(M)                                                                                
  (1, 0)    5
  (1, 1)    8
  (2, 2)    3
  (3, 1)    6

np.where(A) дает те же ненулевые координаты.

In [108]: np.where(A)                                                                            
Out[108]: (array([1, 1, 2, 3]), array([0, 1, 2, 1]))

преобразование в csr

Получив coo, мы можем легко преобразовать его в csr. Фактически sparse часто делает это для нас:

In [98]: Mr = M.tocsr()                                                                          
In [99]: Mr.data                                                                                 
Out[99]: array([5, 8, 3, 6], dtype=int64)
In [100]: Mr.indices                                                                             
Out[100]: array([0, 1, 2, 1], dtype=int32)
In [101]: Mr.indptr                                                                              
Out[101]: array([0, 0, 2, 3, 4], dtype=int32)

Sparse делает несколько вещей - он сортирует индексы, суммирует дубликаты и заменяет row массивом indptr. Здесь он на самом деле длиннее, чем оригинал, но в целом он будет короче, поскольку имеет только одно значение на строку (плюс 1). Но, возможно, более важно, что большинство процедур быстрых вычислений, особенно умножение матриц, были написаны с использованием формата csr.

Я часто использовал этот пакет. MATLAB также, где определение по умолчанию в стиле coo, но внутреннее хранилище - csc (но не так открыто для пользователей, как в scipy). Но я никогда не пытался получить indptr с нуля. Я мог бы, но мне не нужно.

csr_matrix принимает входные данные в формате coo, но также в формате indptr et c. Я бы не советовал, если только вы не рассчитали эти входные данные (скажем, из другой матрицы). Это более подвержено ошибкам и, вероятно, не намного быстрее.

Итерация с indptr

Однако иногда бывает полезно выполнить итерацию на intptr и выполнить вычисления непосредственно на data. Часто это быстрее, чем работа с предоставленными методами.

Например, мы можем перечислить ненулевые значения по строкам:

In [104]: for i in range(Mr.shape[0]): 
     ...:     pt = slice(Mr.indptr[i], Mr.indptr[i+1]) 
     ...:     print(i, Mr.indices[pt], Mr.data[pt]) 
     ...:                                                                                        
0 [] []
1 [0 1] [5 8]
2 [2] [3]
3 [1] [6]

Сохранение начального 0 облегчает эту итерацию. Когда матрица (10000,90000), нет большого стимула уменьшать размер indptr на 1.

lil формат

Формат lil сохраняет матрицу в Аналогично:

In [105]: Ml = M.tolil()                                                                         
In [106]: Ml.data                                                                                
Out[106]: array([list([]), list([5, 8]), list([3]), list([6])], dtype=object)
In [107]: Ml.rows                                                                                
Out[107]: array([list([]), list([0, 1]), list([2]), list([1])], dtype=object)

In [110]: for i,(r,d) in enumerate(zip(Ml.rows, Ml.data)): 
     ...:     print(i, r, d) 
     ...:                                                                                        
0 [] []
1 [0, 1] [5, 8]
2 [2] [3]
3 [1] [6]

Из-за того, как хранятся строки, lil фактически позволяет нам получить view:

In [167]: Ml.getrowview(2)                                                                       
Out[167]: 
<1x4 sparse matrix of type '<class 'numpy.longlong'>'
    with 1 stored elements in List of Lists format>
In [168]: for i in range(Ml.shape[0]): 
     ...:     print(Ml.getrowview(i)) 
     ...:                                                                                        

  (0, 0)    5
  (0, 1)    8
  (0, 2)    3
  (0, 1)    6

Answer 2

Из руководства scipy :

csr_matrix ((данные, индексы, indptr), [shape = (M, N)]) является стандартным представлением CSR, где Индексы столбцов для строки i хранятся в индексах [indptr [i]: indptr [i + 1]], а их соответствующие значения хранятся в данных [indptr [i]: indptr [i + 1]]. Если параметр формы не указан, размеры матрицы выводятся из индексных массивов.

indptr совпадает с ROW_INDEX, а indicies совпадает с COL_INDEX.

Вот пример наивного способа создания массива индексов и значений. По существу, ROW_INDICES [i + 1] - это общее количество ненулевых входов от строки 0 до i включительно, а последняя запись - общее количество ненулевых записей.

ROW_INDICES = [0]
COL_INDICES = []
VALS = []
for i in range(num_rows):
    ROW_INDICES.append(ROW_INDICES[i])
    for j in range(num_cols):
        if m[i, j] > 0:
            ROW_INDICES[i + 1] += 1
            COL_INDICES.append(j)
        VALS.append(m[i, j])