[PYTHON] Premiers pas avec Sparse Matrix avec scipy.sparse

Cet article est le 22e jour du Calendrier de l'Avent du Furukawa Lab. Je suis OB du Furukawa Lab, mais j'ai été invité par un étudiant à participer. Je vous remercie.

introduction

Cette fois, je voudrais expliquer la matrice éparse et son format d'expression tout en décrivant également l'implémentation par scipy.sparse. Cet article s'adresse aux personnes qui se sont habituées à «numpy» dans une certaine mesure, mais qui n'ont pas encore abordé les choses rares liées aux matrices ... Je veux juste savoir ce que c'est! " Dans cet article, nous nous concentrerons sur les valeurs utilisées par chaque format d'expression pour représenter une matrice éparse, et enfin comparer la taille de la mémoire et la vitesse de calcul dans le cadre d'une expérience simple.

Si vous voulez en savoir plus sur scipy.sparse que cet article, veuillez cliquer ici. https://docs.scipy.org/doc/scipy/reference/sparse.html

Cet article utilise NumPy et SciPy de Python pour l'explication, mais le concept de matrice clairsemée et le format d'expression lui-même ne sont pas limités à ces langages et bibliothèques, mais sont largement utilisés.

À propos de la matrice clairsemée

Une matrice avec de nombreux éléments nuls est appelée une ** matrice creuse **. Des matrices éparses apparaissent souvent dans les données réelles. Par exemple, si vous essayez d'exprimer les données "qui a acheté quel produit et combien" sur le site de la CE de manière simple, le nombre d'achats sera stocké dans une matrice dodéca du nombre total d'utilisateurs x nombre total de produits. Bien entendu, la plupart des éléments de cette matrice seront 0.

Ce qui suit est l'image (à l'origine, le nombre d'utilisateurs et de produits est plus grand et le rapport de zéro élément est beaucoup plus grand). Ces données seront utilisées comme exemples de données pour l'explication suivante.

Les données ci-dessus peuvent être créées avec un tableau Numpy comme suit.

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

Cependant, si l'élément zéro est inclus de cette manière, il y aura beaucoup de gaspillage en termes de mémoire et de calcul.

Il est efficace d'exprimer des informations en se concentrant uniquement sur les éléments non nuls (éléments non nuls / éléments non nuls) dans une matrice creuse. Il existe différentes formes d'expression pour les matrices clairsemées, et il est nécessaire de les utiliser correctement selon le but. Dans cet article, nous nous concentrerons sur le format COO, le format CSR et le format CSC, et présenterons leurs méthodes d'expression d'informations et leurs avantages. (Au fait, je pense que le format le plus utilisé sera le format CSR.)

Si vous souhaitez connaître la méthode d'initialisation et les avantages / inconvénients qui ne sont pas expliqués dans cet article, veuillez vous reporter à ce qui suit. 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

Format COO

Le format le plus intuitif est le format des coordonnées (format COOrdinate: format COO). La matrice clairsemée est représentée par trois tableaux unidimensionnels.

L'un est simplement une liste de valeurs d'éléments non nulles. (Le format COO lui-même peut être organisé dans n'importe quel ordre, mais dans cet article, il est organisé dans l'ordre de la ligne verte dans la figure pour le bien du comportement de scipy.sparse et des explications ultérieures.)

Les deux autres indiquent dans quel index se trouve la valeur de chaque élément différent de zéro. Ces deux tableaux représentent les "coordonnées" de l'élément non nul.

En d'autres termes Le 0e utilisateur achète 2 3e produits Le 0ème utilisateur achète 5 4ème produits L'utilisateur n ° 1 achète 9 produits n ° 0 … C'est une expression d'information comme celle-ci.

Vous pouvez facilement convertir au format COO en utilisant scipy.sparse.coo_matrix ().

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

J'afficherai également les informations indiquées sur la figure.

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]

Les données comme indiqué sur la figure sont stockées.

Vous pouvez revenir à la représentation matricielle normale avec scipy.sparse.coo_matrix.todense ().

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

Avantages du format COO

C'est une expression naturelle de la base de données relationnelle, et de nombreuses données fournies sous forme d'ensembles de données sont dans ce format. Par exemple, les données d'évaluation de films MovieLens 100K Dataset peuvent être facilement lues au format COO comme suit.

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 est les données évaluées par 943 utilisateurs pour 1682 films, et comme il y a 100000 éléments non nuls, il semble qu'il puisse être lu correctement. (Cependant, veuillez noter que ce sera "** une matrice contenant 0 valeurs d'évaluation autres que des éléments non nuls **". "Dans les données MovieLens, la partie 0 de cette matrice est considérée comme une valeur manquante. Il est nécessaire pour l'analyste de gérer la commodité de l'analyse des données, par exemple «la gérer correctement».)

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

De plus, le format COO peut être converti au format CSR et au format CSC à grande vitesse.

Format CSR

Je vais le republier car il est plus facile à comprendre si je procède du format COO.

Si vous regardez row, vous pouvez voir que les mêmes numéros sont alignés successivement. Le format qui compresse davantage ces informations est appelé format Compressed Sparse Row: format CSR. (Format de stockage de lignes compressées: il semble qu'il soit également appelé format CRS. Traduit littéralement, il s'agit d'un format de stockage de lignes compressées.)

Je vais vous expliquer l'image de la façon de compresser. Trouvons une ligne de division au tour de row. Les informations de cette ligne de division sont une représentation compressée de «ligne». La partie délimitée par le délimiteur représente les informations sur la 0ème ligne, la 1ère ligne, la 2ème ligne et la 3ème ligne, respectivement. Utilisez ceci au lieu de «row».

Pour résumer ce qui précède, le format CSR est représenté par les trois tableaux unidimensionnels suivants. Les informations de ligne de séparation sont appelées un pointeur d'index de ligne car il s'agit d'une collection de pointeurs où les indices de ligne changent. Dans scipy.sparse.csr_matrix, le nom de la variable est ʻindptr` pour faire court.

Il peut être facilement créé avec scipy.sparse.csr_matrix () de la même manière que scipy.sparse.coo_matrix ().

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]

Vous pouvez également le créer avec data_csr = data_coo.tocsr (). De cette manière, les fichiers scipy.sparse peuvent être convertis les uns aux autres par la méthode .toxxx ().

Avantages du format CSR

Je suis bon dans le traitement qui est effectué ligne par ligne, comme le tranchage de lignes. Le plus grand avantage réside dans le produit matriciel (pour être clair, le produit de la matrice clairsemée de style CSR et du vecteur). Vérifions le contenu pour voir à quoi ressemble l'implémentation. 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 est un pointeur d'index de ligne, ʻAj est un index de colonne, ʻAx` est une donnée différente de zéro, «Xx» est le vecteur à appliquer à la matrice creuse et «Yx» est le vecteur du résultat du calcul. Comme vous pouvez le voir en l'écrivant lentement sur papier, chaque donnée au format CSR est gérée efficacement. Le pointeur d'index de ligne exprime la plage d'informations dans chaque ligne et les éléments du vecteur multipliés par les indices de colonne peuvent être amenés au point.

Format CSC

Les expressions sont telles que les rôles des lignes et des colonnes au format CSR sont interchangés. Format de colonne clairsemée compressée: C'est le format CSC.

Presque encore une fois, vérifions quel type de valeur est inclus. Lisez la matrice dans l'ordre des lignes vertes et transformez-la en format COO.

Considérez la ligne de division à la transition de «col». Utilisez-le comme un pointeur d'index col et utilisez-le à la place de col. Par conséquent, le format CSC est exprimé comme suit.

Vérifiez avec 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]

Certes, les informations présentées sont stockées.

Avantages du format CSC

Je suis doué pour le tranchage de colonnes. En outre, il semble que le produit vectoriel matriciel soit plus rapide, mais pas autant que le format CSR.

Comparaison de la mémoire et du temps de calcul

Comparons le format d'expression pour la matrice creuse introduit jusqu'à présent avec l'expression de matrice simple d'origine. Tout d'abord, en utilisant le jeu de données MovieLens 100K utilisé dans l'explication des avantages du format COO précédemment, Vérifions la taille de la mémoire de chaque format, en particulier le nombre total d'octets dans le tableau.

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

La taille de la mémoire sera beaucoup plus petite si le format d'expression convient à une matrice creuse. La plus petite mémoire requise pour ces données est le format CSR (bien que par une petite marge).

Ensuite, multipliez le vecteur contenant des valeurs numériques aléatoires à partir de la droite et mesurez le temps de calcul du produit vectoriel matriciel.

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)

Certes, le format CSR semble être le plus rapide!

en conclusion

J'ai expliqué le format d'expression de la matrice clairsemée et fait une comparaison simple. Je suis heureux que vous puissiez l'utiliser comme référence. Ayez une bonne vie clairsemée!

L'environnement utilisé dans cet article est le suivant.

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