Creare matrice di adiacenza in python da CSV dataset

Question

Ho dati che viene nel formato come segue:

eventid mnbr 
20   1 
26   1 
12   2 
14   2 
15   3 
14   3 
10   3 

eventid è un evento che il membro ha assistito il dato è rappresentato come un pannello così come si può vedere ogni un membro partecipa a più eventi e più membri possono partecipare allo stesso evento. Il mio obiettivo è quello di creare una matrice di adiacenza che mostra:

mnbr 1 2 3 
1  1 0 0 
2  0 1 1 
3  0 1 1 

dove c'è un 1 ogni volta che due membri frequentano lo stesso evento. Sono riuscito a leggere le colonne del file csv in 2 array numpy 1D separati. Comunque qui andando avanti non sono sicuro di come procedere. Quanto è meglio creare una matrice utilizzando la colonna 2 e come utilizzare successivamente la colonna 1 per inserire i valori? Capisco che non ho pubblicato alcun codice e non mi aspetto alcuna soluzione in merito, ma apprezzerei molto l'idea di come affrontare il problema in modo efficiente. Ho circa 3 milioni di osservazioni, quindi creare troppe variabili esterne sarebbe problematico. Grazie in anticipo. Ho ricevuto una notifica che la mia domanda è un potenziale duplicato, tuttavia il mio problema era quello di analizzare i dati piuttosto che creare la matrice di adiacenza.

Answer 1

Ecco una soluzione. Non ti dà direttamente la matrice di adiacenza richiesta, ma ti fornisce ciò che ti serve per crearlo da solo.

#assume you stored every line of your input as a tuples (eventid, mnbr). 
observations = [(20, 1), (26, 1), (12, 2), (14, 2), (15,3), (14, 3), (10, 3)] 

#then creates an event link dictionary. i.e something that link every event to all its mnbrs 
eventLinks = {} 

for (eventid, mnbr) in observations : 
    #If this event have never been encoutered then create a new entry in links 
    if not eventid in eventLinks.keys(): 
     eventLinks[eventid] = [] 

    eventLinks[eventid].append(mnbr) 

#collect the mnbrs 
mnbrs = set([mnbr for (eventid, mnbr) in observations]) 

#create a member link dictionary. This one link a mnbr to other mnbr linked to it. 
mnbrLinks = { mnbr : set() for mnbr in mnbrs } 

for mnbrList in eventLinks.values() : 
    #add for each mnbr all the mnbr implied in the same event. 
    for mnbr in mnbrList: 
     mnbrLinks[mnbr] = mnbrLinks[mnbr].union(set(mnbrList)) 

print(mnbrLinks) 

L'esecuzione di questo codice il seguente risultato:

{1: {1}, 2: {2, 3}, 3: {2, 3}} 

Questo è un dizionario in cui ogni mnbr hanno associato un insieme di adiacenza mnbrs. Questa è in realtà una lista di adiacenze, cioè una matrice di adiacenza compressa. È possibile espanderlo e creare la matrice che si stava richiedendo utilizzando le chiavi e i valori del dizionario come indici di righe e colonne.

Spero che sia d'aiuto. Arthur.

MODIFICA: ho fornito un approccio utilizzando l'elenco di adiacenze per consentire di implementare il proprio edificio della matrice di adiacenza. Ma dovresti considerare di usare davvero questa struttura dati nel caso in cui i tuoi dati siano sparsi. Vedere http://en.wikipedia.org/wiki/Adjacency_list

EDIT 2: Aggiungere un codice per convertire lista di adiacenza ad un po 'di matrice delle adiacenze intelligente

adjacencyList = {1: {1}, 2: {2, 3}, 3: {2, 3}} 

class AdjacencyMatrix(): 

    def __init__(self, adjacencyList, label = ""): 
     """ 
     Instanciation method of the class. 
     Create an adjacency matrix from an adjacencyList. 
     It is supposed that graph vertices are labeled with numbers from 1 to n. 
     """ 

     self.matrix = [] 
     self.label = label 

     #create an empty matrix 
     for i in range(len(adjacencyList.keys())): 
      self.matrix.append([0]*(len(adjacencyList.keys()))) 

     for key in adjacencyList.keys(): 
      for value in adjacencyList[key]: 
       self[key-1][value-1] = 1 

    def __str__(self): 
     # return self.__repr__() is another possibility that just print the list of list 
     # see python doc about difference between __str__ and __repr__ 

     #label first line 
     string = self.label + "\t" 
     for i in range(len(self.matrix)): 
      string += str(i+1) + "\t" 
     string += "\n" 

     #for each matrix line : 
     for row in range(len(self.matrix)): 
      string += str(row+1) + "\t" 
      for column in range(len(self.matrix)): 
       string += str(self[row][column]) + "\t" 
      string += "\n" 


     return string 

    def __repr__(self): 
     return str(self.matrix) 

    def __getitem__(self, index): 
     """ Allow to access matrix element using matrix[index][index] syntax """ 
     return self.matrix.__getitem__(index) 

    def __setitem__(self, index, item): 
     """ Allow to set matrix element using matrix[index][index] = value syntax """ 
     return self.matrix.__setitem__(index, item) 

    def areAdjacent(self, i, j): 
     return self[i-1][j-1] == 1 

m = AdjacencyMatrix(adjacencyList, label="mbr") 
print(m) 
print("m.areAdjacent(1,2) :",m.areAdjacent(1,2)) 
print("m.areAdjacent(2,3) :",m.areAdjacent(2,3)) 

Questo codice dà il seguente risultato:

mbr 1 2 3 
1 1 0 0 
2 0 1 1 
3 0 1 1 

m.areAdjacent(1,2) : False 
m.areAdjacent(2,3) : True