Clusterizarea spectrală a unui grafic în python (Programare, Python, Grafic, Scikit Learn, Analiza Clusterului, Spectral)

Alex Lenail a intrebat.
a intrebat.

Aș dori să grupez un graf în python folosind spectral clustering.

Clusterizarea spectrală este o tehnică mai generală care poate fi aplicată nu doar la grafice, ci și la imagini sau la orice fel de date, însă este considerată o excepție graf excepțională tehnică de clusterizare a grafurilor. Din păcate, nu pot găsi online exemple de grafice spectral clustering în python.

Mi-ar plăcea să primesc indicații despre cum să procedez. Dacă cineva mă poate ajuta să înțeleg, pot adăuga documentația la scikit learn.

Note:

  • O întrebare foarte asemănătoare cu aceasta a fost deja pusă pe acest site.

Comentarii

  • Dacă ne uităm la codul sursă, , SpectralClustering este un înveliș orientat obiect care apelează spectral_clustering (printre altele) stackoverflow.com/a/55720891/6509615 –  > Por rlchqrd.
  • există vreo modalitate de a face acest lucru pe grafuri ponderate? –  > Por Daniel Pop.
2 răspunsuri
sascha

Fără prea multă experiență cu Spectral-clustering și doar mergând după documente (treceți la sfârșit pentru rezultate!):

Cod:

import numpy as np
import networkx as nx
from sklearn.cluster import SpectralClustering
from sklearn import metrics
np.random.seed(1)

# Get your mentioned graph
G = nx.karate_club_graph()

# Get ground-truth: club-labels -> transform to 0/1 np-array
#     (possible overcomplicated networkx usage here)
gt_dict = nx.get_node_attributes(G, 'club')
gt = [gt_dict[i] for i in G.nodes()]
gt = np.array([0 if i == 'Mr. Hi' else 1 for i in gt])

# Get adjacency-matrix as numpy-array
adj_mat = nx.to_numpy_matrix(G)

print('ground truth')
print(gt)

# Cluster
sc = SpectralClustering(2, affinity='precomputed', n_init=100)
sc.fit(adj_mat)

# Compare ground-truth and clustering-results
print('spectral clustering')
print(sc.labels_)
print('just for better-visualization: invert clusters (permutation)')
print(np.abs(sc.labels_ - 1))

# Calculate some clustering metrics
print(metrics.adjusted_rand_score(gt, sc.labels_))
print(metrics.adjusted_mutual_info_score(gt, sc.labels_))

Ieșire:

ground truth
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
spectral clustering
[1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
just for better-visualization: invert clusters (permutation)
[0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
0.204094758281
0.271689477828

Ideea generală:

Introducere pe datele și sarcina de la aici:

Nodurile din grafic reprezintă cei 34 de membri ai unui club de karate din cadrul unei facultăți. (Zachary este sociolog și a fost unul dintre membri.) O muchie între două noduri indică faptul că cei doi membri au petrecut mult timp împreună în afara ședințelor normale ale clubului. Setul de date este interesant deoarece, în timp ce Zachary își colecta datele, a avut loc o dispută în cadrul clubului de karate, care s-a împărțit în două facțiuni: una condusă de „domnul Hi” și una condusă de „John A”. Se pare că, folosind doar informațiile de conectivitate (marginile), este posibilă recuperarea celor două facțiuni.

Folosind sklearn & spectral-clustering pentru a aborda acest lucru:

Dacă afinitatea este matricea de adiacență a unui graf, această metodă poate fi utilizată pentru a găsi tăieturi de graf normalizate.

Această descrie tăieturile de grafuri normalizate astfel:

Găsiți două partiții disjuncte A și B ale vârfurilor V ale unui graf, astfel încât A ∪ B = V și A ∩ B = ∅

Având în vedere o măsură de similaritate w(i,j) între două vârfuri (de exemplu, identitatea atunci când acestea sunt conectate), o valoare de tăiere (și versiunea sa normalizată) se definește astfel: cut(A, B) = SUM u în A, v în B: w(u, v)

se urmărește minimizarea disocierii între grupurile A și B și maximizarea asocierii în cadrul fiecărui grup.

Sună bine. Deci creăm matricea de adiacență (nx.to_numpy_matrix(G)) și stabilim parametrul affinity la precalculată (deoarece matricea noastră de adiacență este măsura de similaritate precalculată).

Alternativ, folosind precomputed, se poate utiliza o matrice de afinitate furnizată de utilizator.

Editați: Deși nu sunt familiarizat cu acest lucru, am căutat parametrii de reglat și am găsit assign_labels:

Strategia care trebuie utilizată pentru a atribui etichete în spațiul de încorporare. Există două modalități de atribuire a etichetelor după încorporarea laplaciană. k-means poate fi aplicat și este o alegere populară. Dar poate fi, de asemenea, sensibilă la inițializare. Discretizarea este o altă abordare care este mai puțin sensibilă la inițializarea aleatorie.

Așadar, încercați abordarea mai puțin sensibilă:

sc = SpectralClustering(2, affinity='precomputed', n_init=100, assign_labels='discretize')

Ieșire:

ground truth
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
spectral clustering
[0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
just for better-visualization: invert clusters (permutation)
[1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
0.771725032425
0.722546051351

Aceasta este o potrivire aproape perfectă cu adevărul de bază!

Comentarii

  • Mulțumesc! Văzând rezultatul final mi-a dat ceva încredere, că această cale urmată ar putea fi ceva. –  > Por sascha.
  • ai putea face și un print al adj_mat? Apoi, îl pot replica fără a fi nevoie să instalez networkx. –  > Por sinapan.
sinapan

Iată un exemplu fictiv, doar pentru a vedea ce face cu o matrice de similaritate simplă — inspirat de răspunsul lui sascha.

Cod

import numpy as np
from sklearn.cluster import SpectralClustering
from sklearn import metrics
np.random.seed(0)

adj_mat = [[3,2,2,0,0,0,0,0,0],
           [2,3,2,0,0,0,0,0,0],
           [2,2,3,1,0,0,0,0,0],
           [0,0,1,3,3,3,0,0,0],
           [0,0,0,3,3,3,0,0,0],
           [0,0,0,3,3,3,1,0,0],
           [0,0,0,0,0,1,3,1,1],
           [0,0,0,0,0,0,1,3,1],
           [0,0,0,0,0,0,1,1,3]]

adj_mat = np.array(adj_mat)

sc = SpectralClustering(3, affinity='precomputed', n_init=100)
sc.fit(adj_mat)

print('spectral clustering')
print(sc.labels_)

Ieșire

spectral clustering
[0 0 0 1 1 1 2 2 2]