Berechne den euklidischen Abstand in der scipy csr Matrix

Question

Ich muss den Euklidischen Abstand zwischen allen Punkten berechnen, der in CSR Sparse Matrix und einigen Listen von Punkten gespeichert wird. Es wäre einfacher für mich, die CSR in eine dichte zu konvertieren, aber ich konnte wegen des Mangels an Speicher nicht, also muss ich es als CSR behalten.

So zum Beispiel habe ich diese data_csr Sparse Matrix (Blick in beide, csr und dicht):

data_csr 
(0, 2) 4 
(1, 0) 1 
(1, 4) 2 
(2, 0) 2 
(2, 3) 1 
(3, 5) 1 
(4, 0) 4 
(4, 2) 3 
(4, 3) 2 

data_csr.todense() 
[[0, 0, 4, 0, 0, 0] 
[1, 0, 0, 0, 2, 0] 
[2, 0, 0, 1, 0, 0] 
[0, 0, 0, 0, 0, 1] 
[4, 0, 3, 2, 0, 0]] 

und dieses Zentrum Listen Punkte:

center 
array([[0, 1, 2, 2, 4, 1], 
     [3, 4, 1, 2, 4, 0]]) 

die Verwendung von scipy.spatial Paket, das euklidische Distanzfeld zwischen data_csr und Zentrum wird wie th sein e eins unten. Somit wurde jeder Punkt von insgesamt 6 Punkten in jeder Zeile von Mitte für alle Zeilen in data_csr berechnet. Die erste Zeile des Ergebnis-Arrays (2,5) ist die ED zwischen der ersten Zeile von center und allen Zeilen in data_csr.

scipy.spatial.distance.cdist(center, data_csr, 'euclidean') 

array([[ 5.09901951, 3.87298335, 5.19615242, 5.  , 5.91607978], 
     [ 7.34846923, 5.38516481, 5.91607978, 6.8556546 , 6.08276253]]) 

Was ich bisher gelernt, dass ich die Nicht-Null-Werte als auch die Indizes mit bekommen:

data_csr.data 
array([4, 1, 2, 2, 1, 1, 4, 3, 2]) 

data_csr.indices 
array([2, 0, 4, 0, 3, 5, 0, 2, 3]) 

Aber noch kann ich nicht herausfinden, wie der ED berechnen zwischen diese beiden Objekte.

Answer 1

Also lassen Sie uns Ihre Matrix erstellen (zu schlecht Sie nicht Eingaben nicht geben, die ich kopieren-n-Paste könnte)

In [114]: data=[4,1,2,2,1,1,4,3,2] 
In [115]: col=[0,1,1,2,2,3,4,4,4] 
In [116]: row=[2,0,4,0,3,5,0,2,3] 
In [117]: M=sparse.csr_matrix((data,(col,row))) 

In [118]: M 
Out[118]: 
<5x6 sparse matrix of type '<type 'numpy.int32'>' 
    with 9 stored elements in Compressed Sparse Row format> 

In [119]: M.A 
Out[119]: 
array([[0, 0, 4, 0, 0, 0], 
     [1, 0, 0, 0, 2, 0], 
     [2, 0, 0, 1, 0, 0], 
     [0, 0, 0, 0, 0, 1], 
     [4, 0, 3, 2, 0, 0]]) 

In [121]: center=np.array([[0,1,2,2,4,1],[3,4,1,2,4,0]]) 

So, wie Sie die Entfernung zu berechnen haben? M.A ist (5,6), center ist (2,6). Es ist nicht offensichtlich, was Sie mit diesen beiden Arrays tun.

Für den Zugriff auf die 'raw' Sparse-Werte ist das coo Format am einfachsten zu verstehen. Es ist die gleiche Zeile, Spalte, ich Daten Material verwendet, um die Matrix

In [131]: M.tocoo().data 
Out[131]: array([4, 1, 2, 2, 1, 1, 4, 3, 2]) 

In [132]: M.tocoo().col 
Out[132]: array([2, 0, 4, 0, 3, 5, 0, 2, 3]) 

In [133]: M.tocoo().row 
Out[133]: array([0, 1, 1, 2, 2, 3, 4, 4, 4]) 

Die csr speichert diese Informationen in data, indices und indptr Arrays zu erstellen. Aber Sie müssen etwas Mathe tun, um zu den i,j Werten von den letzten 2 zu ziehen. csr Multiplikationsroutinen machen Gebrauch von diesen Reihen gut.

Im Allgemeinen ist es besser, Multiplikation mit csr Matrizen als Addition/Subtraktion zu machen.

Ich erwarte weitere Klärung.

---

spatial.distance.cdist(center,M.A, 'euclidean') 
Out[156]: 
array([[ 5.09901951, 3.87298335, 5.19615242, 5.  , 5.91607978], 
     [ 7.34846923, 5.38516481, 5.91607978, 6.8556546 , 6.08276253]]) 

Was wir tun müssen, ist Studie diese Funktion, und seine Eingänge verstehen. Wir müssen vielleicht über seine Dokumente hinausgehen und den Code anschauen.

Aber mit Blick auf diesen Code sehe ich Schritte, um sicherzustellen, dass xB 2d Array ist, mit der gleichen Anzahl von Spalten wie xA. Dann gilt für euclidian nennt es

_distance_wrap.cdist_euclidean_wrap(_convert_to_double(XA), 
            _convert_to_double(XB), dm) 

, die auf einige C-Code wie ein Wrapper aussieht. Ich kann mir keinen Weg vorstellen, es mit einer spärlichen Matrix zu füllen.

Sie können über Zeilen iterieren; Rufen dist mit M[[0],:].A ist das gleiche wie M.A[[0],:] - außer für die Geschwindigkeit. Das Iterieren über Zeilen einer dünn besetzten Matrix ist etwas langsam, da es bei jeder Iteration eine neue dünne Matrix erstellen muss. csr und lil sind die 2 schnellsten für die Zeileniteration.

Hier ist etwas, das schneller sein könnte - direkt auf den Attributen des lil Format Iterieren:

def foo(a,b,n): 
    # make a dense array from data,row 
    res = np.zeros((1,n)) 
    res[0,b]=a 
    return res 

In [190]: Ml=M.tolil() 

In [191]: Ml.data 
Out[191]: array([[4], [1, 2], [2, 1], [1], [4, 3, 2]], dtype=object) 

In [192]: Ml.rows 
Out[192]: array([[2], [0, 4], [0, 3], [5], [0, 2, 3]], dtype=object) 

In [193]: rowgen=(foo(a,b,6) for a,b in zip(Ml.data,Ml.rows)) 

In [194]: np.concatenate([spatial.distance.cdist(center,row, 'euclidean') for row in rowgen],axis=1) 
Out[194]: 
array([[ 5.09901951, 3.87298335, 5.19615242, 5.  , 5.91607978], 
     [ 7.34846923, 5.38516481, 5.91607978, 6.8556546 , 6.08276253]]) 

Vorerst habe ich die Zeit Tests überspringen werde.

Answer 2

Der paarweise euklidische Abstand auf dünn besetzten Matrizen ist in sklearn implementiert (wie von hpaulj hervorgehoben, funktioniert die scipy-Implementierung nicht auf dünn besetzten Matrizen).

Beispiel auf hpaulj Beispiel:

import scipy.sparse 
import sklearn.metrics.pairwise 
data = [4,1,2,2,1,1,4,3,2] 
col = [0,1,1,2,2,3,4,4,4] 
row = [2,0,4,0,3,5,0,2,3] 
M = scipy.sparse.csr_matrix((data,(col,row))) 
distances = sklearn.metrics.pairwise.pairwise_distances(M,M) 

Dokumentation: http://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.pairwise_distances.html