Wykresy analizy danych za pomocą Python/NetworkX

Jesteśmy zalewani danymi. Stale rozwijające się bazy danych i arkusze kalkulacyjne są pełne ukrytych informacji biznesowych. Jak możemy analizować dane i wyciągać wnioski, skoro jest ich tak dużo? Wykresy (sieci, a nie wykresy słupkowe) zapewniają eleganckie podejście.

Często używamy tabel do ogólnego przedstawienia informacji. Ale wykresy wykorzystują wyspecjalizowaną strukturę danych: zamiast wiersza tabeli węzeł reprezentuje element. Krawędź łączy dwa węzły, aby wskazać ich związek.

Ta struktura danych grafowych umożliwia nam obserwację danych pod różnymi kątami, dlatego nauka o danych grafowych jest wykorzystywana w każdej dziedzinie, od biologii molekularnej po nauki społeczne:

Jak więc programiści mogą wykorzystać analizę danych na wykresach? Przejdźmy do najczęściej używanego języka programowania data science: Python.

Pierwsze kroki z wykresami „teorii grafów” w Pythonie

Programiści Pythona mają do dyspozycji kilka bibliotek danych wykresów, takich jak NetworkX, igraph, SNAP i graph-tool. Poza zaletami i wadami, mają bardzo podobne interfejsy do obsługi i przetwarzania grafowych struktur danych Pythona.

Wykorzystamy popularną bibliotekę NetworkX. Jest prosty w instalacji i obsłudze oraz obsługuje algorytm wykrywania społeczności, którego będziemy używać.

Tworzenie nowego wykresu za pomocą NetworkX jest proste:

 import networkx as nx G = nx.Graph()

Ale G nie jest jeszcze grafem, ponieważ jest pozbawiony węzłów i krawędzi.

Jak dodać węzły do ​​wykresu

Możemy dodać węzeł do sieci, łącząc wartość zwracaną przez Graph() z .add_node() (lub .add_nodes_from() dla wielu węzłów na liście). Możemy również dodać dowolne cechy lub atrybuty do węzłów, przekazując słownik jako parametr, jak pokazano w przypadku node 4 i node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Spowoduje to:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Ale bez krawędzi między węzłami są odizolowane, a zestaw danych nie jest lepszy niż prosta tabela.

Jak dodać krawędzie do wykresu

Podobnie jak w technice dla węzłów, możemy użyć .add_edge() z nazwami dwóch węzłów jako parametrami (lub .add_edges_from() dla wielu krawędzi na liście) i opcjonalnie dołączyć słownik atrybutów:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

Biblioteka NetworkX obsługuje takie wykresy, w których każda krawędź może mieć wagę. Na przykład na wykresie sieci społecznościowej, gdzie węzły to użytkownicy, a krawędzie to interakcje, waga może oznaczać, ile interakcji zachodzi między daną parą użytkowników — jest to bardzo trafny wskaźnik.

NetworkX wyświetla wszystkie krawędzie podczas korzystania z G.edges , ale nie zawiera ich atrybutów. Jeśli potrzebujemy atrybutów krawędzi, możemy użyć G[node_name] , aby uzyskać wszystko, co jest połączone z węzłem lub G[node_name][connected_node_name] aby uzyskać atrybuty określonej krawędzi:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Spowoduje to:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

Ale czytanie naszego pierwszego wykresu w ten sposób jest niepraktyczne. Na szczęście istnieje znacznie lepsza reprezentacja.

Jak generować obrazy z wykresów (i wykresów ważonych)

Wizualizacja wykresu jest niezbędna: pozwala nam szybko i wyraźnie zobaczyć relacje między węzłami i strukturą sieci.

Wystarczy szybkie wywołanie nx.draw(G) :

Zróbmy odpowiednio grubsze krawędzie za pomocą naszego nx.draw() :

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Podaliśmy domyślną grubość dla nieważkości krawędzi, jak widać w wyniku:

Nasze metody i algorytmy wykresów staną się coraz bardziej złożone, więc następnym krokiem jest użycie lepiej znanego zbioru danych.

Wykres nauki o danych wykorzystujący dane z filmu Gwiezdne wojny: część IV

Aby ułatwić interpretację i zrozumienie naszych wyników, użyjemy tego zbioru danych. Węzły reprezentują ważne postacie, a krawędzie (które nie są tutaj ważone) oznaczają współwystępowanie w scenie.

Uwaga: zbiór danych pochodzi z Gabasova, E. (2016). Sieć społecznościowa Gwiezdnych Wojen. DOI: https://doi.org/10.5281/zenodo.1411479.

Najpierw zwizualizujemy dane za pomocą nx.draw(G_starWars, with_labels = True) :

Postacie, które zwykle pojawiają się razem, takie jak R2-D2 i C-3PO, wydają się być blisko powiązane. W przeciwieństwie do tego widzimy, że Darth Vader nie dzieli się scenami z Owenem.

Układy wizualizacji Python NetworkX

Dlaczego każdy węzeł znajduje się tam, gdzie jest na poprzednim wykresie?

Jest to wynik domyślnego algorytmu spring_layout . Symuluje siłę sprężyny, przyciągając połączone węzły i odpychając rozłączone. Pomaga to wyróżnić dobrze połączone węzły, które kończą się w centrum.

NetworkX ma inne układy, które używają różnych kryteriów do pozycjonowania węzłów, takich jak circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

Wynik:

Układ ten jest neutralny w tym sensie, że lokalizacja węzła nie zależy od jego ważności — wszystkie węzły są reprezentowane jednakowo. (Układ kołowy może również pomóc w wizualizacji oddzielnych połączonych komponentów — podwykresów mających ścieżkę między dowolnymi dwoma węzłami — ale tutaj cały wykres jest jednym dużym połączonym komponentem).

Oba układy, które widzieliśmy, mają pewien wizualny bałagan, ponieważ krawędzie mogą swobodnie przecinać inne krawędzie. Ale Kamada-Kawai, inny algorytm oparty na sile, taki jak spring_layout , pozycjonuje węzły tak, aby zminimalizować energię systemu.

Zmniejsza to przekraczanie krawędzi, ale ma swoją cenę: jest wolniejszy niż inne układy i dlatego nie jest wysoce zalecany w przypadku wykresów z wieloma węzłami.

Ten ma specjalną funkcję rysowania:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Daje to zamiast tego ten kształt:

Algorytm bez specjalnej ingerencji umieścił głównych bohaterów (jak Luke, Leia i C-3PO) w centrum, a mniej widocznych (jak Camie i Generał Dodonna) przy granicy.

Wizualizacja wykresu w określonym układzie może dać nam kilka ciekawych wyników jakościowych. Mimo to wyniki ilościowe są istotną częścią każdej analizy naukowej, więc musimy zdefiniować pewne metryki.

Analiza węzłów: stopień i PageRank

Teraz, gdy możemy wyraźnie zwizualizować naszą sieć, może być dla nas interesujące scharakteryzowanie węzłów. Istnieje wiele metryk opisujących cechy węzłów i, w naszym przykładzie, postaci.

Jedną z podstawowych miar węzła jest jego stopień: ile ma krawędzi. Stopień węzła postaci z Gwiezdnych Wojen mierzy liczbę innych postaci, z którymi dzieli scenę.

Funkcja degree() może obliczyć stopień znaku lub całej sieci:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

Dane wyjściowe obu poleceń:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

Sortowanie węzłów od najwyższego do najniższego według stopnia można wykonać za pomocą jednej linii kodu:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

Wyjście:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

Będąc tylko sumą, stopień nie uwzględnia szczegółów poszczególnych krawędzi. Czy dana krawędź łączy się z izolowanym w inny sposób węzłem lub z węzłem, który jest połączony z całą siecią? Algorytm Google PageRank agreguje te informacje, aby ocenić, jak „ważny” jest węzeł w sieci.

Metryka PageRank może być interpretowana jako agent przemieszczający się losowo z jednego węzła do drugiego. Lepiej połączone węzły mają więcej ścieżek prowadzących przez nie, więc agent będzie je odwiedzał częściej.

Takie węzły będą miały wyższy PageRank, który możemy obliczyć za pomocą biblioteki NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

To drukuje rangę Luke'a i nasze postacie posortowane według rangi:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Owen jest postacią z najwyższym PageRank, przewyższając Luke'a, który miał najwyższy stopień. Analiza: Chociaż Owen nie jest postacią, która dzieli najwięcej scen z innymi postaciami, jest postacią, która dzieli sceny z wieloma ważnymi postaciami, takimi jak sam Luke, R2-D2 i C-3PO.

Natomiast C-3PO, postać z trzecim najwyższym stopniem, ma najniższy PageRank. Pomimo tego, że C-3PO ma wiele powiązań, wiele z nich ma nieistotne postacie.

Wniosek: korzystanie z wielu wskaźników może dać głębszy wgląd w różne cechy węzłów wykresu.

Algorytmy wykrywania społeczności

Podczas analizy sieci ważne może być oddzielenie społeczności : grup węzłów, które są ze sobą silnie połączone, ale w minimalnym stopniu połączone z węzłami spoza ich społeczności.

Istnieje wiele algorytmów na to. Większość z nich znajduje się w nienadzorowanych algorytmach uczenia maszynowego, ponieważ przypisują one węzłom etykiety bez konieczności wcześniejszego oznaczania ich etykietami.

Jedną z najbardziej znanych jest propagacja etykiet . W nim każdy węzeł zaczyna się od unikalnej etykiety, w jednej społeczności. Etykiety węzłów są iteracyjnie aktualizowane zgodnie z większością etykiet sąsiednich węzłów.

Etykiety rozchodzą się po sieci, dopóki wszystkie węzły nie będą współdzielić etykiety z większością swoich sąsiadów. Grupy węzłów blisko ze sobą połączonych mają tę samą etykietę.

W przypadku biblioteki NetworkX uruchomienie tego algorytmu zajmuje zaledwie trzy linijki Pythona:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

Wyjście:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

Na tej liście zestawów każdy zestaw reprezentuje społeczność. Czytelnicy zaznajomieni z filmem zauważą, że algorytm zdołał idealnie oddzielić „dobrych” od „złych”, znacząco różnicując postacie bez użycia prawdziwej (społecznej) etykiety czy metadanych.

Inteligentne wglądy przy użyciu Graph Data Science w Pythonie

Widzieliśmy, że rozpoczęcie pracy z narzędziami do analizy danych w postaci wykresów jest prostsze, niż mogłoby się wydawać. Kiedy już przedstawimy dane jako wykres przy użyciu biblioteki NetworkX w Pythonie, kilka krótkich linijek kodu może być pouczających. Możemy rozsądnie wizualizować nasz zestaw danych, mierzyć i porównywać cechy węzłów oraz węzły klastrowe za pomocą algorytmów wykrywania społeczności.

Umiejętność wyciągania wniosków i spostrzeżeń z sieci za pomocą języka Python umożliwia programistom integrację z narzędziami i metodologią powszechnie spotykaną w potokach usług analizy danych. Od wyszukiwarek, przez planowanie lotów po inżynierię elektryczną, metody te można łatwo zastosować w szerokim zakresie kontekstów.

Zalecana literatura na temat analizy danych grafowych

Algorytmy wykrywania społeczności
Zhao Yang, Rene Algesheimer i Claudio Tessone. „Analiza porównawcza algorytmów wykrywania społeczności w sztucznych sieciach”. Sprawozdania naukowe, 6, no. 30750 (2016).

Głębokie uczenie się wykresów
Thomasa Kipfa. „Wykresuj sieci splotowe”. 30 września 2016 r.

Zastosowania Graph Data Science
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein i Pablo Balenzuela. „Przewidywanie zmieniających się osób za pomocą eksploracji tekstu i uczenia maszynowego wykresów na Twitterze”. (24 sierpnia 2020 r.): arXiv:2008.10749 [cs.SI].

Cohen, Elior. „PyData Spotkanie w Tel Awiwie: Node2vec.” Youtube. 22 listopada 2018 r. Wideo, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.