Разреженные массивы (scipy.sparse)#

Введение#

scipy.sparse и его подмодули предоставляют инструменты для работы с разреженные массивы. Разреженные массивы — это массивы, в которых только несколько позиций содержат данные, большинство позиций считаются «пустыми». Разреженные массивы полезны, потому что они позволяют использовать более простые, быстрые и/или менее требовательные к памяти алгоритмы для линейной алгебры (scipy.sparse.linalg) или вычисления на графах (scipy.sparse.csgraph), но они обычно менее гибки для операций, таких как срезы, изменение формы или присваивание. Это руководство познакомит с основами разреженных массивов в scipy.sparse, объясните уникальные аспекты структур разреженных данных и отсылайте к другим разделам руководства пользователя, где объясняется разреженная линейная алгебра и методы графов.

Начало работы с разреженными массивами#

Разреженные массивы — это особый вид массивов, где данные находятся только в нескольких позициях. Это позволяет сжатый представления данных для использования, где записываются только местоположения, где данные существуют. Существует множество различных форматов разреженных массивов, каждый из которых делает различный компромисс между сжатием и функциональностью. Для начала создадим очень простой разреженный массив, координатный (COO) массив (coo_array) и сравнить его с плотным массивом:

>>> import scipy as sp
>>> import numpy as np
>>> dense = np.array([[1, 0, 0, 2], [0, 4, 1, 0], [0, 0, 5, 0]])
>>> sparse = sp.sparse.coo_array(dense)
>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])
>>> sparse

     with 5 stored elements and shape (3, 4)>

Обратите внимание, что в нашем плотном массиве у нас есть пять ненулевых значений. Например, 2 находится в местоположении 0,3, и 4 находится в местоположении 1,1. Все остальные значения равны нулю. Разреженный массив записывает эти пять значений явно (см. 5 stored elements and shape (3, 4)), а затем представляет все оставшиеся нули как неявный значения.

Большинство методов разреженных массивов работают аналогично методам плотных массивов:

>>> sparse.max()
5
>>> dense.max()
5
>>> sparse.argmax()
10
>>> dense.argmax()
10
>>> sparse.mean()
1.0833333333333333
>>> dense.mean()
1.0833333333333333

Несколько "дополнительных" свойств, таких как .nnz который возвращает количество хранимых значений, также присутствуют в разреженных массивах:

>>> sparse.nnz
5

Большинство операций редукции, таких как .mean(), .sum(), или .max() будет возвращать массив numpy при применении по оси разреженного массива:

>>> sparse.mean(axis=1)
array([0.75, 1.25, 1.25])

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

Понимание форматов разреженных массивов#

Различные типы разреженных массивов имеют разные возможности. Например, массивы COO не могут быть индексированы или нарезаны:

>>> dense[2, 2]
5
>>> sparse[2, 2]
Traceback (most recent call last):
  File "", line 1, in 
TypeError: 'coo_array' object is not subscriptable

Но другие форматы, такие как Compressed Sparse Row (CSR) csr_array поддерживают срезы и индексацию элементов:

>>> sparse.tocsr()[2, 2]
5

Иногда, scipy.sparse вернет другой формат разреженной матрицы, чем формат входной разреженной матрицы. Например, скалярное произведение двух разреженных массивов в формате COO будет массивом в формате CSR:

>>> sparse @ sparse.T

     with 5 stored elements and shape (3, 3)>

Это изменение происходит из-за scipy.sparse изменит формат входных разреженных массивов, чтобы использовать наиболее эффективный вычислительный метод.

The scipy.sparse модуль содержит следующие форматы, каждый со своими преимуществами и недостатками:

  • Массивы блочной разреженной строки (BSR) scipy.sparse.bsr_array, которые наиболее подходят, когда части массива с данными находятся в смежных блоках.

  • Массивы координат (COO) scipy.sparse.coo_array, которые предоставляют простой способ создания разреженных массивов и их модификации на месте. COO также может быть быстро преобразован в другие форматы, такие как CSR, CSC или BSR.

  • Массивы сжатых разреженных строк (CSR) scipy.sparse.csr_array, которые наиболее полезны для быстрой арифметики, векторных произведений и срезов по строкам.

  • Сжатые разреженные столбцовые (CSC) массивы scipy.sparse.csc_array, которые наиболее полезны для быстрой арифметики, векторных произведений и срезов по столбцам.

  • Диагональные (DIA) массивы scipy.sparse.dia_array, которые полезны для эффективного хранения и быстрой арифметики, пока данные в основном расположены вдоль диагоналей массива.

  • Массивы типа Dictionary of Keys (DOK) scipy.sparse.dok_array, которые полезны для быстрого построения и доступа к отдельным элементам.

  • Массивы List of Lists (LIL) scipy.sparse.lil_array, которые полезны для быстрого создания и изменения разреженных массивов.

Дополнительная информация о сильных и слабых сторонах каждого формата разреженных массивов доступна в их документация.

Все форматы scipy.sparse массивы могут быть построены непосредственно из numpy.ndarray. Однако некоторые разреженные форматы также могут быть построены разными способами. Каждый формат разреженного массива имеет разные преимущества, и эти преимущества задокументированы в каждом классе. Например, один из наиболее распространённых методов построения разреженных массивов — создание разреженного массива из отдельных row, column, и data значения. Для нашего массива из предыдущего примера:

>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])

The row, column, и data массивы описывают строки, столбцы и значения, где наш разреженный массив имеет записи:

>>> row = [0,0,1,1,2]
>>> col = [0,3,1,2,2]
>>> data = [1,2,4,1,5]

Используя это, мы можем теперь определить разреженный массив без предварительного построения плотного массива:

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr

     with 5 stored elements and shape (3, 4)>

Разные классы имеют разные конструкторы, но scipy.sparse.csr_array, scipy.sparse.csc_array, и scipy.sparse.coo_array позволяют такой стиль построения.

Разреженные массивы, неявные нули и дубликаты#

Разреженные массивы полезны, потому что они представляют большую часть своих значений неявно, без хранения фактического значения-заполнителя. В scipy.sparse, значение, используемое для представления "отсутствующих данных", является неявный ноль. Это может сбивать с толку, когда явные нули требуются. Например, в методы графов из scipy.sparse.csgraph, нам часто нужно уметь различать (A) связь, соединяющую узлы i и j с нулевым весом и (B) без связи между i и j. Разреженные матрицы могут это делать, если мы сохраняем явный и неявный с учётом нулей.

Например, в нашем предыдущем csr массив, мы могли бы включить явный ноль, добавив его в data список. Рассмотрим последний элемент массива в нижней строке и последнем столбце как явный ноль:

>>> row = [0,0,1,1,2,2]
>>> col = [0,3,1,2,2,3]
>>> data = [1,2,4,1,5,0]

Тогда наш разреженный массив будет иметь six хранимых элементов, а не пять:

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr

     with 6 stored elements and shape (3, 4)>

«Дополнительный» элемент — это наш явный ноль. При преобразовании обратно в плотный массив они всё ещё идентичны, поскольку плотные массивы представляют всё явно:

>>> csr.todense()
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])
>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])

Но для разреженной арифметики, линейной алгебры и графовых методов значение в 2,3 будет считаться явный ноль. Чтобы удалить этот явный ноль, можно использовать csr.eliminate_zeros() метод. Это работает с разреженным массивом на месте, и удаляет любые хранимые элементы с нулевым значением:

>>> csr

     with 6 stored elements and shape (3, 4)>
>>> csr.eliminate_zeros()
>>> csr

     with 5 stored elements and shape (3, 4)>

До csr.eliminate_zeros(), было шесть сохраненных элементов. После осталось только пять сохраненных элементов.

Другая точка сложности возникает из-за того, как дубликаты обрабатываются при построении разреженного массива. A дублировать может возникать, когда у нас есть две или более записи в row,col при построении разреженного массива. Это часто происходит при создании разреженных массивов с использованием data, row, и col векторы. Например, мы можем представить наш предыдущий массив с дублирующимся значением в 1,1:

>>> row = [0,0,1,1,1,2]
>>> col = [0,3,1,1,2,2]
>>> data = [1,2,1,3,1,5]

В этом случае мы видим, что есть два data значения, соответствующие 1,1 позиция в нашем конечном массиве. scipy.sparse будет хранить эти значения отдельно:

>>> dupes = sp.sparse.coo_array((data, (row, col)))
>>> dupes

     with 6 stored elements and shape (3, 4)>

Обратите внимание, что в этом разреженном массиве хранится шесть элементов, несмотря на наличие только пяти уникальных позиций с данными. При преобразовании этих массивов обратно в плотные массивы повторяющиеся значения суммируются. Таким образом, в позиции 1,1, плотный массив будет содержать сумму дублирующихся хранимых записей, 1 + 3:

>>> dupes.todense()
array([[1, 0, 0, 2],
      [0, 4, 1, 0],
      [0, 0, 5, 0]])

Чтобы удалить дублирующиеся значения внутри самого разреженного массива и таким образом уменьшить количество хранимых элементов, мы можем использовать .sum_duplicates() method:

>>> dupes.sum_duplicates()
>>> dupes

     with 5 stored elements and shape (3, 4)>

Теперь в нашем разреженном массиве хранится только пять элементов, и он идентичен массиву, с которым мы работали в этом руководстве:

>>> dupes.todense()
array([[1, 0, 0, 2],
       [0, 4, 1, 0],
       [0, 0, 5, 0]])

Канонические форматы#

Несколько форматов разреженных массивов имеют "канонические форматы" для повышения эффективности операций. Обычно они включают дополнительные ограничения, такие как:

  • Нет повторяющихся записей для любого значения

  • Отсортированные индексы

Классы с канонической формой включают: coo_array, csr_array, csc_array, и bsr_array. Подробности о каждом каноническом представлении см. в документации этих классов.

Чтобы проверить, находится ли экземпляр этих классов в канонической форме, используйте .has_canonical_format attribute:

>>> coo = sp.sparse.coo_array(([1, 1, 1], ([0, 2, 1], [0, 1, 2])))
>>> coo.has_canonical_format
False

Чтобы преобразовать экземпляр в каноническую форму, используйте .sum_duplicates() method:

>>> coo.sum_duplicates()
>>> coo.has_canonical_format
True

Следующие шаги с разреженными массивами#

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