So lesen Sie eine Kantenliste ein, um eine spärliche Matrix zu erstellen

Question

Ich habe eine große Datei, in der jede Zeile ein Paar von 8 Zeichenfolgen hat. Etwas wie:

ab1234gh iu9240gh 

auf jeder Zeile.

Diese Datei stellt wirklich ein Diagramm dar und jede Zeichenfolge ist eine Knoten-ID. Ich würde gerne die Datei einlesen und direkt eine spärliche Adjazenzmatrix erstellen. Ich werde dann PCA auf dieser Matrix mit einem der vielen Werkzeuge in Python

laufen lassen Gibt es eine gute Möglichkeit, dies zu tun, oder muss ich zuerst ein Diagramm im RAM machen und dann das in eine dünne Matrix konvertieren? Da die Datei groß ist, möchte ich, wenn möglich, Zwischenschritte vermeiden.

Letztendlich werde ich die spärliche Adjazenzmatrix in http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html#sklearn.decomposition.TruncatedSVD einspeisen.

Answer 1

Ich denke, das ist eine regelmäßige Aufgabe in sklearn, so muss es ein Tool in dem Paket, das dies tut, oder eine Antwort in anderen Fragen SO. Wir müssen das richtige Tag hinzufügen.

Aber die Arbeit gerade von meinem Wissen über numpy und sparse, wo das, was ich tun würde:

eine Probe 2d Array Stellen - N Zeilen, 2 Spalten mit Zeichenwerten:

In [638]: A=np.array([('a','b'),('b','d'),('a','d'),('b','c'),('d','e')]) 
In [639]: A 
Out[639]: 
array([['a', 'b'], 
     ['b', 'd'], 
     ['a', 'd'], 
     ['b', 'c'], 
     ['d', 'e']], 
     dtype='<U1') 

Verwenden np.unique um die einzigartigen Strings zu identifizieren, und als Bonus eine Karte von diesen Strings zum ursprünglichen Array. Dies ist das Arbeitspferd der Aufgabe.

In [640]: k1,k2,k3=np.unique(A,return_inverse=True,return_index=True) 
In [641]: k1 
Out[641]: 
array(['a', 'b', 'c', 'd', 'e'], 
     dtype='<U1') 
In [642]: k2 
Out[642]: array([0, 1, 7, 3, 9], dtype=int32) 
In [643]: k3 
Out[643]: array([0, 1, 1, 3, 0, 3, 1, 2, 3, 4], dtype=int32) 

kann ich das Array inverse umformen die Zeile und Spalte für jeden Eintrag in A zu identifizieren.

In [644]: rows,cols=k3.reshape(A.shape).T 
In [645]: rows 
Out[645]: array([0, 1, 0, 1, 3], dtype=int32) 
In [646]: cols 
Out[646]: array([1, 3, 3, 2, 4], dtype=int32) 

mit denen, ist es trivial, eine Sparse-Matrix zu konstruieren, die an jedem 1 ‚intersection` hat.

In [648]: M=sparse.coo_matrix((np.ones(rows.shape,int),(rows,cols))) 
In [649]: M 
Out[649]: 
<4x5 sparse matrix of type '<class 'numpy.int32'>' 
    with 5 stored elements in COOrdinate format> 
In [650]: M.A 
Out[650]: 
array([[0, 1, 0, 1, 0], 
     [0, 0, 1, 1, 0], 
     [0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 1]]) 

die erste Reihe, hat a Werte in der 2. und 4. col, b und d. und so weiter.

============================

Ursprünglich hatte ich:

In [648]: M=sparse.coo_matrix((np.ones(k1.shape,int),(rows,cols))) 

Das ist falsch . Das data Array sollte rows und cols in Form entsprechen. Hier hat es keinen Fehler ausgelöst, weil k1 zufälligerweise die gleiche Größe hat. Aber mit einer anderen Mischung könnten einzigartige Werte einen Fehler verursachen.

====================

Dieser Ansatz geht davon aus, die gesamte Datenbank kann A in den Speicher geladen werden. unique erfordert wahrscheinlich eine ähnliche Speichernutzung. Anfänglich erhöht eine coo Matrix die Speichernutzung möglicherweise nicht, da sie die als Parameter bereitgestellten Arrays verwendet.Aber jede Berechnungen und/oder Umwandlung in csr oder ein anderes Format wird weitere Kopien machen.

Ich kann mir vorstellen, Speicherprobleme zu umgehen, indem ich die Datenbank in Chunks lade und eine andere Struktur verwende, um die eindeutigen Werte und das Mapping zu erhalten. Sie könnten sogar in der Lage sein, eine coo Matrix aus Chunks zu konstruieren. Aber früher oder später werden Sie auf Speicherprobleme stoßen. Der Scikit-Code erstellt eine oder mehrere Kopien dieser Sparse-Matrix.