[PYTHON] Erste Schritte mit Sparse Matrix mit scipy.sparse

Dieser Artikel ist der 22. Tag des Furukawa Lab Adventskalenders. Ich bin ein OB des Furukawa Lab, wurde aber von einem Studenten zur Teilnahme eingeladen. Vielen Dank.

Einführung

Dieses Mal möchte ich die Sparse-Matrix und ihr Ausdrucksformat erläutern und gleichzeitig die Implementierung durch scipy.sparse beschreiben. Dieser Artikel richtet sich an Personen, die sich bis zu einem gewissen Grad an "Numpy" gewöhnt haben, aber noch keine spärlichen Matrix-Themen angesprochen haben ... Ich möchte ein wenig darüber wissen, wie es ist! " In diesem Artikel konzentrieren wir uns darauf, welche Werte jedes Darstellungsformat zur Darstellung einer dünnen Matrix verwendet, und vergleichen schließlich die Speichergröße und die Berechnungsgeschwindigkeit als einfaches Experiment.

Wenn Sie mehr über scipy.sparse als diesen Artikel erfahren möchten, klicken Sie bitte hier. https://docs.scipy.org/doc/scipy/reference/sparse.html

In diesem Artikel werden NumPy und SciPy von Python zur Erklärung verwendet. Das Konzept der Sparse-Matrix und das Ausdrucksformat selbst sind jedoch nicht auf diese Sprachen und Bibliotheken beschränkt, sondern werden häufig verwendet.

Über spärliche Matrix

Eine Matrix mit vielen Nullelementen wird als ** spärliche Matrix ** bezeichnet. In realen Daten erscheinen häufig spärliche Matrizen. Wenn Sie beispielsweise versuchen, die Daten "Wer hat welches Produkt gekauft und wie viele?" Auf einfache Weise auf der EC-Website auszudrücken, wird die Anzahl der Käufe in einer Dodeca-Matrix aus der Gesamtzahl der Benutzer x der Gesamtzahl der Produkte gespeichert. Natürlich sind die meisten Elemente dieser Matrix 0.

Das Folgende ist das Bild (ursprünglich ist die Anzahl der Benutzer und Produkte größer und das Verhältnis der Nullelemente ist viel größer). Diese Daten werden als Beispieldaten für die folgende Erläuterung verwendet.

Die obigen Daten können mit einem Numpy-Array wie folgt erstellt werden.

import numpy as np
data_np = np.array([[0, 0, 0, 2, 5],
                    [9, 0, 1, 8, 0],
                    [0, 0, 6, 0, 0],
                    [0, 4, 7, 0, 3]])

Wenn das Nullelement jedoch auf diese Weise einbezogen wird, entsteht viel Verschwendung in Bezug auf Speicher und Berechnung.

Es ist effizient, Informationen auszudrücken, indem man sich nur auf Nicht-Null-Elemente (Nicht-Null-Elemente / Nicht-Null-Elemente) in einer dünnen Matrix konzentriert. Es gibt verschiedene Ausdrucksformen für spärliche Matrizen, und es ist notwendig, sie je nach Zweck richtig zu verwenden. In diesem Artikel konzentrieren wir uns auf das COO-Format, das CSR-Format und das CSC-Format und stellen deren Methoden und Vorteile für den Ausdruck von Informationen vor. (Ich denke übrigens, das am häufigsten verwendete Format wird das CSR-Format sein.)

Wenn Sie die Initialisierungsmethode und die Vor- und Nachteile kennen möchten, die in diesem Artikel nicht erläutert werden, lesen Sie bitte die folgenden Informationen. https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html

COO-Format

Das intuitivste Format ist das Koordinatenformat (COOrdinate-Format: COO-Format). Die dünn besetzte Matrix wird durch drei eindimensionale Arrays dargestellt.

Eine ist einfach eine Liste von Nicht-Null-Elementwerten. (Das COO-Format selbst kann in beliebiger Reihenfolge angeordnet werden. Aus Gründen des Verhaltens von "scipy.sparse" und späterer Erläuterungen ist es jedoch in der Reihenfolge der grünen Linie in der Abbildung angeordnet.)

Die anderen beiden zeigen, in welchem Index sich der Wert jedes Nicht-Null-Elements befindet. Diese beiden Arrays repräsentieren die "Koordinaten" des Nicht-Null-Elements.

Mit anderen Worten Der 0. Benutzer kauft 2 3. Produkte Der 0. Benutzer kauft 5 4. Produkte Benutzer Nr. 1 kauft 9 Produkte Nr. 0 … Es ist ein Informationsausdruck wie dieser.

Sie können einfach mit scipy.sparse.coo_matrix () in das COO-Format konvertieren.

from scipy import sparse
data_coo = sparse.coo_matrix(data_np)
print(data_coo)

output

  (0, 3)	2
  (0, 4)	5
  (1, 0)	9
  (1, 2)	1
  (1, 3)	8
  (2, 2)	6
  (3, 1)	4
  (3, 2)	7
  (3, 4)	3

Ich werde auch die in der Abbildung gezeigten Informationen anzeigen.

print(f"row: {data_coo.row}")
print(f"col: {data_coo.col}")
print(f"data: {data_coo.data}")

output

row: [0 0 1 1 1 2 3 3 3]
col: [3 4 0 2 3 2 1 2 4]
data: [2 5 9 1 8 6 4 7 3]

Die in der Abbildung gezeigten Daten werden gespeichert.

Sie können mit scipy.sparse.coo_matrix.todense () zur normalen Matrixdarstellung zurückkehren.

print(data_coo.todense())

output

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

Vorteile des COO-Formats

Es ist ein natürlicher Ausdruck für die relationale Datenbank, und viele der als Datensätze bereitgestellten Daten haben dieses Format. Beispielsweise können Filmevaluierungsdaten MovieLens 100K Dataset wie folgt einfach im COO-Format gelesen werden.

import pandas as pd
df = pd.read_table('ml-100k/u.data', names=['user_id', 'movie_id', 'rating', 'timestamp'])
ml100k_coo = sparse.coo_matrix((df.rating, (df.user_id-1, df.movie_id-1)))

print(f'number of nonzero: {ml100k_coo.nnz}')
print(f'shape: {ml100k_coo.shape}')

output

number of nonzero: 100000
shape: (943, 1682)

MovieLens 100K Dataset sind die Daten, die von 943 Benutzern für 1682 Filme ausgewertet wurden. Da es 100.000 Nicht-Null-Elemente gibt, scheint es, dass sie richtig gelesen werden können. (Beachten Sie jedoch, dass es sich um "** eine Matrix mit 0 anderen Auswertungswerten als Nicht-Null-Elementen **" handelt. In den MovieLens-Daten wird der 0-Teil dieser Matrix als fehlender Wert angesehen. Der Analyst muss mit der Bequemlichkeit der Datenanalyse umgehen, z. B. "ordnungsgemäß damit umgehen".)

import pandas as pd
df = pd.read_table('ml-100k/u.data', names=['user_id', 'movie_id', 'rating', 'timestamp'])
user_id_categorical = pd.api.types.CategoricalDtype(categories=sorted(df.user_id.unique()), ordered=True)
user_index = df.user_id.astype(user_id_categorical).cat.codes
movie_id_categorical = pd.api.types.CategoricalDtype(categories=sorted(df.movie_id.unique()), ordered=True)
movie_index = df.movie_id.astype(movie_id_categorical).cat.codes
ml100k_coo = sparse.coo_matrix((df.rating, (user_index, movie_index)))

Darüber hinaus kann das COO-Format mit hoher Geschwindigkeit in das CSR-Format und das CSC-Format konvertiert werden.

CSR-Format

Ich werde es erneut veröffentlichen, da es einfacher zu verstehen ist, wenn ich vom COO-Format ausgehe.

Wenn Sie sich "Zeile" ansehen, können Sie sehen, dass die gleichen Zahlen nacheinander aufgereiht sind. Das Format, das diese Informationen weiter komprimiert, heißt Compressed Sparse Row-Format: CSR-Format. (Komprimiertes Zeilenspeicherformat: Es scheint, dass es auch als CRS-Format bezeichnet wird. Wörtlich übersetzt handelt es sich um ein komprimiertes Zeilenspeicherformat.)

Ich werde das Bild erklären, wie man komprimiert. Zeichnen wir eine Trennlinie am Ende der Reihe. Die Information dieser Trennlinie ist eine komprimierte Darstellung von "Zeile". Der vom Trennzeichen eingeschlossene Teil repräsentiert die Informationen in der 0. Zeile, 1. Zeile, 2. Zeile bzw. 3. Zeile. Verwenden Sie dies anstelle von "Zeile".

Um das Obige zusammenzufassen, wird das CSR-Format durch die folgenden drei eindimensionalen Arrays dargestellt. Die Trennlinieninformationen werden als Zeilenindexzeiger bezeichnet, da es sich um eine Sammlung von Zeigern handelt, bei denen sich die Zeilenindizes ändern. In scipy.sparse.csr_matrix wird der Variablenname als "indptr" abgekürzt.

Es kann einfach mit "scipy.sparse.csr_matrix ()" auf die gleiche Weise wie "scipy.sparse.coo_matrix ()" erstellt werden.

data_csr = sparse.csr_matrix(data_np)
print(f"index pointer: {data_csr.indptr}")
print(f"indices: {data_csr.indices}")
print(f"data: {data_csr.data}")

output

index pointer: [0 2 5 6 9]
indices: [3 4 0 2 3 2 1 2 4]
data: [2 5 9 1 8 6 4 7 3]

Alternativ können Sie es mit data_csr = data_coo.tocsr () erstellen. Auf diese Weise können scipy.sparses mit der Methode .toxxx () ineinander konvertiert werden.

Vorteile des CSR-Formats

Ich bin gut darin, zeilenweise zu verarbeiten, z. B. Linien zu schneiden. Der größte Vorteil liegt im Matrixprodukt (um klar zu sein, dem Produkt der CSR-spärlichen Matrix und des Vektors). Lassen Sie uns den Inhalt überprüfen, um zu sehen, wie die Implementierung aussieht. https://github.com/scipy/scipy/blob/41800a2fc6f86446c7fe0248748bfb371e37cd04/scipy/sparse/sparsetools/csr.h#L1100-L1137

csr.h

template <class I, class T>
void csr_matvec(const I n_row,
                const I n_col,
                const I Ap[],
                const I Aj[],
                const T Ax[],
                const T Xx[],
                      T Yx[])
{
    for(I i = 0; i < n_row; i++){
        T sum = Yx[i];
        for(I jj = Ap[i]; jj < Ap[i+1]; jj++){
            sum += Ax[jj] * Xx[Aj[jj]];
        }
        Yx[i] = sum;
    }
}

"Ap" ist ein Zeilenindexzeiger, "Aj" sind Spaltenindizes, "Ax" sind Daten ungleich Null, "Xx" ist der Vektor, der auf die dünn besetzte Matrix angewendet werden soll, und "Yx" ist der Vektor des Berechnungsergebnisses. Wie Sie sehen können, indem Sie es langsam auf Papier schreiben, werden alle Daten im CSR-Format effizient verarbeitet. Der Zeilenindexzeiger drückt den Informationsbereich in jeder Zeilenvertiefung aus, und die Elemente des Vektors multipliziert mit den Spaltenindizes können auf den Punkt gebracht werden.

CSC-Format

Die Ausdrücke sind so, dass die Rollen von Zeilen und Spalten im CSR-Format vertauscht werden. Komprimiertes Sparse Column-Format: Es ist das CSC-Format.

Lassen Sie uns noch einmal überprüfen, welche Art von Wert enthalten ist. Lesen Sie die Matrix in der Reihenfolge der grünen Linien und machen Sie sie zum COO-Format.

Betrachten Sie die Trennlinie am Übergang von col. Verwenden Sie dies als Spaltenindexzeiger und verwenden Sie es anstelle von "Spalten". Daher wird das CSC-Format wie folgt ausgedrückt.

Überprüfen Sie mit scipy.sparse.csc_matrix ().

data_csc = sparse.csc_matrix(data_np)
print(f"index pointer: {data_csc.indptr}")
print(f"indices: {data_csc.indices}")
print(f"data: {data_csc.data}")

output

index pointer: [0 1 2 5 7 9]
indices: [1 3 1 2 3 0 1 0 3]
data: [9 4 1 6 7 2 8 5 3]

Natürlich werden die gezeigten Informationen gespeichert.

Vorteile des CSC-Formats

Ich bin gut im Spaltenschneiden. Es scheint auch, dass das Matrixvektorprodukt schneller ist, wenn auch nicht so viel wie das CSR-Format.

Vergleich von Speicher und Rechenzeit

Vergleichen wir das bisher eingeführte Ausdrucksformat für die Sparse-Matrix mit dem ursprünglichen einfachen Matrix-Ausdruck. Verwenden Sie zunächst den MovieLens 100K-Datensatz, der zuvor zur Erläuterung der Vorteile des COO-Formats verwendet wurde. Lassen Sie uns die Speichergröße jedes Formats überprüfen, insbesondere die Gesamtzahl der Bytes im Array.

ml100k_csr = ml100k_coo.tocsr()
ml100k_csc = ml100k_coo.tocsc()
ml100k_np = ml100k_coo.todense()

print(f'np: {ml100k_np.nbytes}')
print(f'coo: {ml100k_coo.data.nbytes + ml100k_coo.col.nbytes + ml100k_coo.row.nbytes}')
print(f'csr: {ml100k_csr.data.nbytes + ml100k_csr.indices.nbytes + ml100k_csr.indptr.nbytes}')
print(f'csc: {ml100k_csc.data.nbytes + ml100k_csc.indices.nbytes + ml100k_csc.indptr.nbytes}')

output

np: 12689008
coo: 1600000
csr: 1203776
csc: 1206732

Die Speichergröße ist viel kleiner, wenn das Ausdrucksformat für eine dünne Matrix geeignet ist. Der kleinste für diese Daten erforderliche Speicher ist das CSR-Format (allerdings mit geringem Abstand).

Als nächstes multiplizieren Sie den Vektor mit zufälligen numerischen Werten von rechts und messen die Berechnungszeit des Matrixvektorprodukts.

x = np.random.randint(1, 10, 1682)

%timeit ml100k_np @ x
%timeit ml100k_coo @ x
%timeit ml100k_csr @ x
%timeit ml100k_csc @ x

output

3.2 ms ± 20.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
159 µs ± 995 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
92.6 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
140 µs ± 1.41 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Sicherlich scheint das CSR-Format das schnellste zu sein!

abschließend

Ich erklärte das Ausdrucksformat der spärlichen Matrix und machte einen einfachen Vergleich. Ich bin froh, wenn Sie es als Referenz verwenden können. Hab ein gutes, spärliches Leben!

Die in diesem Artikel verwendete Umgebung ist wie folgt.

python = '3.7.0'
scipy = '1.3.3'
numpy = '1.17.3'
pandas = '0.25.3'