Создать матрицу смежности в питоне из CSV набора данных

Question

У меня есть данные, что приходит в формате следующим образом:

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

EventID это событие, элемент присутствовал на данном представлен в виде панели, так как вы можете видеть каждый член участвует в нескольких событиях, и несколько членов могут посещать одно и то же событие. Моя цель - создать матрицу смежности, которая показывает:

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

где есть 1, когда два участника посещают одно и то же событие. Я успешно смог прочитать столбцы файла csv в 2 отдельных массивах 1D numpy. Однако в будущем я не уверен, как действовать дальше. Как лучше всего создать матрицу с использованием столбца 2 и как впоследствии я могу использовать столбец 1 для заполнения значений? Я понимаю, что я не размещал никакого кода и не ожидал каких-либо решений в этом отношении, но был бы очень благодарен за идею о том, как эффективно подойти к проблеме. У меня примерно 3 миллиона наблюдений, поэтому создание слишком большого количества внешних переменных будет проблематичным. Заранее спасибо. Я получил уведомление о том, что мой вопрос является потенциальным дубликатом, однако моя проблема заключалась в анализе данных, а не в создании матрицы смежности.

Answer 1

Вот решение. Он не дает вам напрямую запрошенную матрицу смежности, но дает вам то, что вам нужно, чтобы создать ее самостоятельно.

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

Выполнение этого кода дает следующий результат:

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

Это словарь, где каждый mnbr имеют соответствующий набор смежности mnbrs. Это фактически список смежности, который представляет собой сжатую матрицу смежности. Вы можете развернуть его и создать матрицу, которую вы запрашивали, используя словарные ключи и значения в качестве индексов строк и столбцов.

Надеюсь, что это поможет. Arthur.

EDIT: Я предложил подход с использованием списка смежности, чтобы вы могли реализовать свое собственное построение матрицы смежности. Но вы должны подумать о том, чтобы действительно использовать эту структуру данных, если ваши данные разрежены. См http://en.wikipedia.org/wiki/Adjacency_list

EDIT 2: Добавление кода для преобразования список смежных вершин в небольшой смарт-матрица смежности

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

Этот код даст следующий результат:

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