Sparse Arrays (scipy.sparse)#

Einleitung#

scipy.sparse und seine Untermodule bieten Werkzeuge für die Arbeit mit Sparse Arrays. Sparse Arrays sind Arrays, bei denen nur an wenigen Stellen im Array Daten vorhanden sind, die meisten Stellen gelten als „leer“. Sparse Arrays sind nützlich, da sie einfachere, schnellere und/oder speichereffizientere Algorithmen für lineare Algebra (scipy.sparse.linalg) oder graphenbasierte Berechnungen (scipy.sparse.csgraph) ermöglichen, aber sie sind im Allgemeinen weniger flexibel für Operationen wie Slicing, Reshaping oder Zuweisung. Diese Anleitung führt in die Grundlagen von Sparse Arrays in scipy.sparse ein, erklärt die Besonderheiten von Sparse-Datenstrukturen und verweist auf andere Abschnitte des Benutzerhandbuchs, die sparse lineare Algebra und Graphenmethoden erklären.

Erste Schritte mit Sparse Arrays#

Sparse Arrays sind eine spezielle Art von Array, bei der nur wenige Positionen im Array Daten enthalten. Dies ermöglicht die Verwendung von komprimierten Darstellungen der Daten, bei denen nur die Positionen aufgezeichnet werden, an denen Daten vorhanden sind. Es gibt viele verschiedene Sparse Array-Formate, die jeweils einen anderen Kompromiss zwischen Komprimierung und Funktionalität eingehen. Beginnen wir damit, ein sehr einfaches Sparse Array zu erstellen, das Coordinate (COO) Array (coo_array) und es mit einem dichten Array zu vergleichen.

>>> 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
<COOrdinate sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

Beachten Sie, dass wir in unserem dichten Array fünf Nicht-Null-Werte haben. Zum Beispiel ist 2 an Position 0,3 und 4 an Position 1,1. Alle anderen Werte sind Null. Das Sparse Array zeichnet diese fünf Werte explizit auf (siehe die 5 gespeicherten Elemente und die Form (3, 4)) und stellt dann alle verbleibenden Nullen als implizite Werte dar.

Die meisten Methoden für Sparse Arrays funktionieren ähnlich wie Methoden für dichte Arrays.

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

Einige „zusätzliche“ Eigenschaften, wie z.B. .nnz, die die Anzahl der gespeicherten Werte zurückgibt, sind ebenfalls für Sparse Arrays vorhanden.

>>> sparse.nnz
5

Die meisten Reduktionsoperationen wie .mean(), .sum() oder .max() geben ein NumPy-Array zurück, wenn sie über eine Achse des Sparse Arrays angewendet werden.

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

Dies liegt daran, dass Reduktionen über Sparse Arrays oft dicht sind.

Verständnis von Sparse Array-Formaten#

Verschiedene Arten von Sparse Arrays haben unterschiedliche Fähigkeiten. Zum Beispiel können COO-Arrays nicht indiziert oder geslicet werden.

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

Andere Formate, wie z.B. das Compressed Sparse Row (CSR) csr_array unterstützen Slicing und Elementindizierung.

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

Manchmal gibt scipy.sparse ein anderes Sparse Matrix-Format als das Eingabeformat zurück. Zum Beispiel ist das Punktprodukt zweier Sparse Arrays im COO-Format ein Array im CSR-Format.

>>> sparse @ sparse.T
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 3)>

Diese Änderung tritt auf, weil scipy.sparse das Format der Eingabe-Sparse-Arrays ändert, um die effizienteste Berechnungsmethode zu verwenden.

Das Modul scipy.sparse enthält die folgenden Formate, jedes mit seinen eigenen spezifischen Vor- und Nachteilen.

  • Block Sparse Row (BSR) Arrays scipy.sparse.bsr_array, die am besten geeignet sind, wenn die Teile des Arrays mit Daten in zusammenhängenden Blöcken auftreten.

  • Coordinate (COO) Arrays scipy.sparse.coo_array, die eine einfache Möglichkeit bieten, Sparse Arrays zu erstellen und sie direkt zu modifizieren. COO kann auch schnell in andere Formate wie CSR, CSC oder BSR konvertiert werden.

  • Compressed Sparse Row (CSR) Arrays scipy.sparse.csr_array, die am nützlichsten für schnelle Arithmetik, Vektorprodukte und zeilenweises Slicing sind.

  • Compressed Sparse Column (CSC) Arrays scipy.sparse.csc_array, die am nützlichsten für schnelle Arithmetik, Vektorprodukte und spaltenweises Slicing sind.

  • Diagonal (DIA) Arrays scipy.sparse.dia_array, die für effiziente Speicherung und schnelle Arithmetik nützlich sind, solange die Daten hauptsächlich entlang der Diagonalen des Arrays auftreten.

  • Dictionary of Keys (DOK) Arrays scipy.sparse.dok_array, die für schnelle Erstellung und Einzelwertezugriff nützlich sind.

  • List of Lists (LIL) Arrays scipy.sparse.lil_array, die für schnelle Erstellung und Modifikation von Sparse Arrays nützlich sind.

Weitere Informationen zu den Stärken und Schwächen jedes Sparse Array-Formats finden Sie in ihrer Dokumentation.

Alle Formate von scipy.sparse Arrays können direkt aus einem numpy.ndarray erstellt werden. Einige Sparse-Formate können jedoch auch auf andere Weise erstellt werden. Jedes Sparse Array-Format hat unterschiedliche Stärken, und diese Stärken sind in jeder Klasse dokumentiert. Eine der häufigsten Methoden zur Erstellung von Sparse Arrays ist beispielsweise der Aufbau eines Sparse Arrays aus den einzelnen Zeilen-, Spalten- und Daten-Werten. Für unser Array von zuvor.

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

Die Arrays row, column und data beschreiben die Zeilen, Spalten und Werte, an denen unser Sparse Array Einträge hat.

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

Mithilfe dieser können wir nun ein Sparse Array definieren, ohne zuerst ein dichtes Array zu erstellen.

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

Verschiedene Klassen haben unterschiedliche Konstruktoren, aber scipy.sparse.csr_array, scipy.sparse.csc_array und scipy.sparse.coo_array ermöglichen diese Art der Konstruktion.

Sparse Arrays, implizite Nullen und Duplikate#

Sparse Arrays sind nützlich, da sie viele ihrer Werte implizit darstellen, ohne einen tatsächlichen Platzhalterwert zu speichern. In scipy.sparse ist der Wert, der verwendet wird, um „keine Daten“ darzustellen, eine implizite Null. Dies kann verwirrend sein, wenn explizite Nullen erforderlich sind. Zum Beispiel müssen wir in Graphenmethoden von scipy.sparse.csgraph oft zwischen (A) einer Verbindung, die die Knoten i und j mit Gewicht Null verbindet, und (B) keiner Verbindung zwischen i und j unterscheiden können. Sparse Matrizen können dies leisten, solange wir die expliziten und impliziten Nullen im Auge behalten.

Zum Beispiel könnten wir in unserem vorherigen csr Array eine explizite Null aufnehmen, indem wir sie in die data Liste aufnehmen. Betrachten wir den letzten Eintrag im Array in der untersten Zeile und letzten Spalte als explizite Null.

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

Dann hat unser Sparse Array sechs gespeicherte Elemente, nicht fünf.

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>

Die beiden sind immer noch identisch, wenn sie wieder in ein dichtes Array umgewandelt werden, da dichte Arrays alles explizit darstellen.

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

Aber für Sparse Arithmetik, lineare Algebra und Graphenmethoden wird der Wert an 2,3 als explizite Null betrachtet. Um diese explizite Null zu entfernen, können wir die Methode csr.eliminate_zeros() verwenden. Diese operiert direkt auf dem Sparse Array und entfernt alle gespeicherten Elemente mit dem Wert Null.

>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>
>>> csr.eliminate_zeros()
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

Vor csr.eliminate_zeros() gab es sechs gespeicherte Elemente. Danach gibt es nur noch fünf gespeicherte Elemente.

Ein weiterer Komplikationspunkt ergibt sich aus der Art und Weise, wie Duplikate bei der Erstellung eines Sparse Arrays verarbeitet werden. Ein Duplikat kann auftreten, wenn wir zwei oder mehr Einträge an Zeile,Spalte haben, während ein Sparse Array erstellt wird. Dies geschieht oft beim Erstellen von Sparse Arrays mit den Vektoren data, row und col. Zum Beispiel könnten wir unser vorheriges Array mit einem doppelten Wert an 1,1 darstellen.

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

In diesem Fall sehen wir, dass es zwei data-Werte gibt, die der Position 1,1 in unserem endgültigen Array entsprechen. scipy.sparse speichert diese Werte separat.

>>> dupes = sp.sparse.coo_array((data, (row, col)))
>>> dupes
<COOrdinate sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>

Beachten Sie, dass dieses Sparse Array sechs gespeicherte Elemente hat, obwohl es nur fünf eindeutige Positionen gibt, an denen Daten vorkommen. Wenn diese Arrays wieder in dichte Arrays umgewandelt werden, werden die doppelten Werte summiert. An Position 1,1 enthält das dichte Array also die Summe der doppelten gespeicherten Einträge, 1 + 3.

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

Um doppelte Werte innerhalb des Sparse Arrays selbst zu entfernen und somit die Anzahl der gespeicherten Elemente zu reduzieren, können wir die Methode .sum_duplicates() verwenden.

>>> dupes.sum_duplicates()
>>> dupes
<COOrdinate sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

Jetzt gibt es nur noch fünf gespeicherte Elemente in unserem Sparse Array, und es ist identisch mit dem Array, mit dem wir in dieser Anleitung gearbeitet haben.

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

Kanonische Formate#

Mehrere Sparse Array-Formate haben „kanonische Formate“, um effizientere Operationen zu ermöglichen. Im Allgemeinen bestehen diese aus zusätzlichen Einschränkungen wie:

  • Keine doppelten Einträge für irgendeinen Wert.

  • Sortierte Indizes.

Klassen mit kanonischer Form umfassen: coo_array, csr_array, csc_array und bsr_array. Details zu jeder kanonischen Darstellung finden Sie in den Docstrings dieser Klassen.

Um zu überprüfen, ob eine Instanz dieser Klassen im kanonischen Format vorliegt, verwenden Sie das Attribut .has_canonical_format.

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

Um eine Instanz in kanonisches Format zu konvertieren, verwenden Sie die Methode .sum_duplicates().

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

Nächste Schritte mit Sparse Arrays#

Sparse Array-Typen sind am hilfreichsten, wenn mit großen, fast leeren Arrays gearbeitet wird. Insbesondere sparse lineare Algebra und sparse Graphenmethoden erfahren unter diesen Umständen die größten Effizienzsteigerungen.