1
votes

Obtenez un voisin différent de zéro à gauche, à droite, en haut et en bas de SciPy Sparse Matrix

Dites que j'ai une matrice 2D SciPy Sparse:

left = np.array([[0, 0, 4,  0, 2],
                 [3, 0, 0, -1, 0],
                 [0, 2, 1,  0, 0],
                 [3, 0, 0, -1, 0],
                 [0, 1, 0,  0, 0],
                ])

down = np.array([[0, 0,  2, 0, -1],
                 [3, 0,  0, 3,  0],
                 [0, 4, -1, 0,  0],
                 [1, 0,  0, 1,  0],
                 [0, 2,  0, 0,  0],
                ])

Pour chaque élément différent de zéro dans la matrice, j'aimerais créer quatre nouvelles matrices éparses contenant l'index correspondant au suivant le plus proche voisin différent de zéro à gauche, à droite, en haut et en bas. Les éléments aux extrémités peuvent avoir des voisins qui sont enroulés (pensez à une liste circulaire à double liaison dans les directions horizontale et verticale ou toroïdale). Dans le cas où un élément est le seul élément différent de zéro dans sa ligne / colonne, l'index correspondant pointera vers lui-même. De plus, étant donné que les indices peuvent avoir une valeur nulle (lors du référencement de la première ligne ou colonne) et être indiscernables des éléments naturellement nuls, nous définissons ces indices zéro à -1 afin de lever l'ambiguïté entre un index réel et les éléments nuls. p>

Pour la matrice ci-dessus, les matrices denses Left et Down ressembleraient à:

import numpy as np
from scipy.sparse import csc_matrix

arr = np.array([[0, 0, 1, 0, 1],
                [1, 0, 0, 1, 0],
                [0, 1, 1, 0, 0],
                [1, 0, 0, 1, 0],
                [0, 1, 0, 0, 0],
               ])

csc = csc_matrix(arr)

N'oubliez pas que les éléments avec une valeur d'index de -1 sont en fait des références à l'index zéro. Bien sûr, j'ai besoin d'avoir ces matrices sous forme de matrice clairsemée car mes vraies matrices sont trop grandes et rares pour tenir dans la mémoire.

python numpy matrix scipy sparse-matrix

0 commentaires

4 Réponses :

1
votes

Voici une manière possible de faire le voisin de gauche. Ce n'est pas particulièrement efficace, mais fonctionne probablement bien s'il n'y a pas beaucoup d'entrées différentes de zéro dans toute la matrice. Vous pouvez l'optimiser légèrement en obtenant les entrées différentes de zéro de chaque ligne au fur et à mesure et en ne calculant j [i == row] qu'une fois.

Notez que je décale simplement les index de un plutôt que définir 0 sur -1 .

i,j = csc.nonzero()
ind = sp.sparse.csc_matrix(csc.shape,dtype='int')
for row in range(csc.shape[0]):
    ind[row,j[i==row]] = np.roll(j[i==row]+1,1)

ind.A = array([[0, 0, 5, 0, 3],
   [4, 0, 0, 1, 0],
   [0, 3, 2, 0, 0],
   [4, 0, 0, 1, 0],
   [0, 2, 0, 0, 0]])

4 commentaires

Je pensais que np.roll produit une matrice dense?

np.roll est appliqué à un tableau d'index d'entrées différentes de zéro.

Ahhhh, intéressant. Cela pourrait bien fonctionner! Je me demande si nous devons même en ajouter un aux index tant que nous n'appelons pas remove_zeros sur le tableau épars. Bien sûr, cela devient déroutant lorsque nous le convertissons en dense ...

L'initialisation de ind avec sparse.lil_matrix peut être plus rapide et éviter l'avertissement d'efficacité.

0
votes

Une réponse possible (forme dense):

ix, iy = csc.nonzero()
w = np.where(np.insert(np.diff(ix), 0,1) != 0)[0]
iy2 = np.concatenate([np.roll(_, 1) for _ in np.split(iy,w)])
iy2[iy2==0] = -1

left = csc_matrix(arr.shape)
left[ix, iy] = iy2

ix, iy = csc.transpose().nonzero()
w = np.where(np.insert(np.diff(ix), 0,1) != 0)[0]
iy2 = np.concatenate([np.roll(_, 1) for _ in np.split(iy,w)])
iy2[iy2==0] = -1

down = csc_matrix(arr.T.shape)
down[ix, iy] = iy2
down = down.transpose()
print(left.todense(), '\n', down.todense())


 >> [[ 0  0  4  0  2]
 [ 3  0  0 -1  0]
 [ 0  2  1  0  0]
 [ 3  0  0 -1  0]
 [ 0  1  0  0  0]]

[[ 0  0  2  0 -1]
 [ 3  0  0  3  0]
 [ 0  4 -1  0  0]
 [ 1  0  0  1  0]
 [ 0  2  0  0  0]]

2 commentaires

Je pensais que np.roll produit une matrice dense? J'ai besoin que les données intermédiaires soient dans un format clairsemé ainsi que la matrice finale doit également être clairsemée.

J'ai édité la réponse. Essentiellement, ce que je propose, c'est de ne travailler que sur les indices non nuls sous forme dense, de les rouler, puis de les placer dans une matrice plus grande sous une forme éparse. Les indices non nuls (IMO) peuvent être travaillés sous forme dense car ils ne représentent qu'une petite partie de votre matrice d'origine

1
votes

ind = Mr.copy()
for i in range(Mr.shape[0]):
    slc = slice(Mr.indptr[i],Mr.indptr[i+1])
    k = Mr.indices[slc]
    ind.data[slc] = np.roll(k+1,1)

0 commentaires

0
votes

Une approche plus vectorielle:

>>> down.A 
array([[0, 0, 2, 0, 0],
       [3, 0, 0, 3, 0],
       [0, 4, 0, 0, 0],
       [1, 0, 0, 1, 0],
       [0, 2, 0, 0, 0]], dtype=int32)

Vérifier:

csc = csc_matrix(arr)
inds = (csc.indices,csc.indptr)
irows = np.split(*inds)[1:-1]

down = csc_matrix((np.hstack([np.roll(row,-1) for row in irows]),*inds))
up = csc_matrix((np.hstack([np.roll(row,1) for row in irows]),*inds))

La gauche et la droite peuvent être obtenues avec la représentation CSR. p >

Je ne pense pas que coder 0 par -1 soit une bonne idée, car cela brisera toute amélioration de calcul parcimonieuse. seuls les lieux conçus par csc.nonzeros () doivent être visités.

0 commentaires