[PYTHON] Lernen von Beziehungsdaten mit Numpy und NetworkX (Spektralclustering)
1. Zuallererst
Dieser Artikel ist ** eine Zusammenfassung der Netzwerkanalyse (Community-Extraktion) durch Python ** und eine einfache Verwendung von NetworkX, einer praktischen Bibliothek für die Netzwerkanalyse **. ** Implementieren Sie spektrales Clustering mit numpy ** als Community-Extraktionsalgorithmus.
Lesen Sie diesen Artikel zur persönlichen Motivation (Ableitung der probabilistischen Matrixfaktorisierung und implementiert in Edward). Buch (Lernen von Beziehungsdaten) Ich habe angefangen, es zu lesen, weil ich dachte, es wäre interessant, also ist es wie eine Zusammenfassung.
2. Umweltbau
2.1. Implementierungsumgebung dieses Mal
- Python 3.6.0 :: Anaconda 4.3.1 (x86_64)
- numpy 1.11.3
2.2 Installation
pip install networkx==1.9.1
Installieren Sie networkx 1.9.1. Die neueste Version ist 1.11, aber wenn ich sie benutze, erhalte ich NetworkXError: Beim Laden von Daten kann kein Graph bei (2, 1) tokenisiert werden. Als ich es nachgeschlagen habe, gab es eine Person, die sagte: "Ich habe es bekommen, aber als ich auf 1.9.1 herabgestuft habe, konnte ich es verwenden", also werde ich daraus lernen.
3. Über Daten
3.1. Datenquelle
Here hat eine Reihe von Testdaten zur Netzwerkanalyse veröffentlicht.
Les Miserables: coappearance network of characters in the novel Les Miserables. Please cite D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, Reading, MA (1993).
Wird genutzt.
3.2. Dateninhalt
Diese Daten scheinen die Daten von Personen zu sein, die im Remiserable-Roman zusammen in derselben Szene aufgetreten sind. Die Häufigkeit, mit der sie zusammen auftreten, wird zum Kantenwert, und der Knoten wird zum Zeichen.
Es sind interessante Daten, ich habe mich gefragt, ob es solche Daten gibt, aber nachdem ich den Code fertig geschrieben habe, habe ich diesen Artikel von Herrn TJO gefunden, der im Twitter-Bereich berühmt ist.
Ich probiere verschiedene Methoden für dieselbe Community-Extraktionsaufgabe aus. Wenn Sie diesen Artikel lesen, können Sie verstehen, um welche Art von Daten es sich bei diesen Remize-Daten handelt und was Sie durch Extrahieren der Community verstehen können.
Nachdem ich diesen Artikel gelesen hatte, dachte ich, dass R in der Netzwerkanalysebibliothek vollständiger als Python ist. Oder sollte ich cytoscape verwenden? (Oder ich weiß einfach nichts anderes)
3.3. Datenformat
.Die Daten mit der Erweiterung gml befinden sich in der Zip-Datei des obigen Links. gml ist eine Abkürzung für Graph Modeling Language, ein Speicherformat für Diagrammstrukturdaten.
Informationen zu den Knoten und Kanten des Diagramms werden in der folgenden Struktur gespeichert.
```sh
$ cat lesmis.gml
Creator "Mark Newman on Fri Jul 21 12:44:53 2006"
graph
[
node
[
id 0
label "Myriel"
]
node
[
id 1
label "Napoleon"
]
...
edge
[
source 14
target 11
value 1
]
edge
[
source 15
target 11
value 1
3.4 Daten lesen
Die .gml-Daten können mit der Funktion read_gml von NetworkX in das von NetworkX definierte Diagrammobjekt eingelesen werden.
import networkx as nx
data_path = "./data/lesmis/lesmis.gml"
G = nx.read_gml(data_path)
Wenn Sie dies zu einem Array von Numpy machen möchten,
X = np.array(nx.to_numpy_matrix(G))
Sie können es so machen. Der Rückgabewert von `` `to_numpy_matrix``` ist eine Numpy-Matrix, aber da ndarray persönlich einfacher zu verwenden ist, habe ich ihn wie oben in ndarray geändert.
Übrigens wird bei dieser spektralen Clusterbildung angenommen, dass die Matrix des Graphen eine symmetrische Matrix ist. Wie Sie anhand der Daten in NetworkX sehen können
nx.is_directed(G)
# False
Mit der Funktion können Sie überprüfen, ob der Graph ein gerichteter Graph (keine symmetrische Matrix) oder ein ungerichteter Graph (symmetrische Matrix) ist. Es ist ein ungerichteter Graph, weil er falsch ist, indem überprüft wird, ob er gerichtet ist oder nicht.
4. Code
4.1 Übersicht
Hier,
- Spektrale Clusterbildung basierend auf nicht normalisiertem Laplace-Diagramm
- Spektrales Clustering basierend auf dem Laplace-Diagramm für die Normalisierung des betrunkenen Spaziergangs Zwei sind implementiert.
Bei der Methode, die auf nicht normalisiertem Graph-Laplasian basiert, besteht bei der Ausführung von Clustering die Tendenz, einen Knoten und den anderen zu klassifizieren, und die Clusterbildung ist subtil, sodass die verbesserte Version auf normalisiertem Graph-Laplasian basiert. Abhängig von der Normalisierungsmethode gibt es verschiedene Arten von normalisierten Graphlaplace, und der betrunkene normalisierte Graphlaplace ist implementiert.
4.2. Definition von Klassen und Funktionen
Definieren Sie die Klasse, die tatsächlich Spektralclustering ausführt, und die Funktionen, die zum Zeichnen der Ausführungsergebnisse erforderlich sind.
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from sklearn.cluster import KMeans
class graph_clustering():
def __init__(self, K, n_clusters, lap_kind):
"""
K : int
n_clusters : int
lap_kind : None or str
Ex. "rw"
"""
self.lap_kind = lap_kind
self.K = K
self.n_clusters = n_clusters
def _calc_g_laplacian(self, X):
D = np.diag(np.sum(X, axis=0))
L = D - X
self.L = L
self.D = D
return L
def _calc_rw_g_laplacian(self, X):
L = self._calc_g_laplacian(X)
Lrw = np.dot(np.linalg.inv(self.D), L)
self.L = Lrw
return Lrw
def _get_K_eigen_vec(self, Lam, V):
sorted_index = np.argsort(Lam.real)
Lam_K = Lam[sorted_index][0:self.K]
V_K = V[sorted_index][0:self.K]
self.Lam_K = Lam_K
self.V_K = V_K
return Lam_K, V_K
def _Kmeans_V_K(self, V_K):
kmeans = KMeans(n_clusters=self.n_clusters, random_state=0).fit(V_K.T.real)
clusters = kmeans.labels_
self.clusters = clusters
return clusters
def laplacian_clustering(self, X):
"""
X : ndarray
a matrix representation of undirected graph
"""
if self.lap_kind is None:
L = self._calc_g_laplacian(X)
elif self.lap_kind == "rw":
L = self._calc_rw_g_laplacian(X)
else:
raise NotImplementedError
Lam, V = np.linalg.eig(L)
Lam_K, V_K = self._get_K_eigen_vec(Lam, V)
clusters = self._Kmeans_V_K(V_K)
return clusters
# for plot
def get_labels_dic(G):
"""
G : networkx.classes.graph.Graph
"""
labels_dic = { key:G.node[key]['label'] for key in G.node.keys() }
return labels_dic
def get_labels_list(G):
labels_list = np.array([ G.node[key]['label'] for key in G.node.keys() ])
return labels_list
def split_labels(labels_list, clusters):
"""
labels_list : list
return value of get_labels_list function.
clusters : ndarray
return value of graph_clustering.laplacian_clustering
"""
class_uniq = np.unique(clusters)
node_index_split= []
labels_split = []
index = np.arange(clusters.shape[0])
for class_elem in class_uniq:
node_index_split.append(list(index[clusters == class_elem]))
labels_split.append(list(labels_list[clusters == class_elem]))
return node_index_split, labels_split
def plot_clusters(G, node_index_split):
"""
G : networkx.classes.graph.Graph
node_index_split : list (2-dim list)
return value of split_labels function.
"""
labels_dic = get_labels_dic(G)
pos = nx.spring_layout(G)
colors = [ cm.jet(x) for x in np.arange(0, 1, 1/len(node_index_split)) ]
for i, nodes in enumerate(node_index_split):
nx.draw_networkx(G, node_color=colors[i], labels=labels_dic, nodelist=nodes, pos=pos, font_color="r")
plt.show()
Eine detaillierte Erläuterung des Codes kann wie folgt auf die spektrale Clusterbildung und Darstellung der Ergebnisse verschoben werden:
4.3 Verschieben Sie den Code
data_path = "./data/lesmis/lesmis.gml"
G = nx.read_gml(data_path)
X = np.array(nx.to_numpy_matrix(G))
GClus = graph_clustering(K=15, n_clusters=5, lap_kind="rw")
clusters = GClus.laplacian_clustering(X)
labels_list = get_labels_list(G)
node_index_split, labels_split = split_labels(labels_list, clusters)
plot_clusters(G, node_index_split)
Ich benutze es so.
graph_clustering(k=15, n_clusters=5, lap_kind="rw")Das Argument von istkWie viele Eigenvektorenn_clustersIn wie viele Cluster sollte unterteilt werden?lap_kindGibt den Typ des Spektralclustering-Algorithmus an.
lap_kind=noneDenormalisiert mitlap_kind="rw"Führen Sie das Clustering des Laplace-Diagramms für die Normalisierung des betrunkenen Spaziergangs durch.
4.4 Über den zu zeichnenden Code
Der Handlungsteil brauchte etwas Einfallsreichtum. Ich zeichne mit der Funktion `nx.draw_networkx``` in` plot_clusters () ``, aber ich hatte nicht die Möglichkeit, für jeden identifizierten Cluster unterschiedliche Farben zu zeichnen, also auf diese Weise Ich plane.
nx.draw_networkx(G, node_color=colors[i], labels=labels_dic, nodelist=nodes, pos=pos, font_color="r")
Da ich mit diesem Argument von nodelist``` einen Teil des gesamten Graphen zeichnen konnte, teilen Sie den Knoten in Cluster und zeichnen Sie, während Sie die Farbe mit node_color = colours [i] ändern. tun. Da dies den Plot immer mehr überschreibt, ändert sich die Position jedes Mal, wenn Sie die Position nicht mit dem Argument `pos``` angeben, und sie wird durcheinander gebracht.
5. Ausführungsergebnis
5.1 Denormalisierter Graph Laplace
gclus = graph_clustering(k=15, n_clusters=5, lap_kind=none)Im Falle von.
Es ist wahr, dass ein Knoten ein Cluster ist und sich überhaupt nicht wie ein Cluster anfühlt.
5.2. Drunk Walk Normalization Graph Laplace
gclus = graph_clustering(k=15, n_clusters=5, lap_kind="rw")Im Falle von.
Es sieht ein wenig clusterartig aus.
5.3 Aufteilung der Cluster
labels_split[0]
['MmeMagloire', 'CountessDeLo', 'Geborand']
labels_split[1]
['Myriel',
'Napoleon',
'MlleBaptistine',
'Champtercier',
'Cravatte',
'Count',
'OldMan',
'Labarre',
'Valjean',
'MmeDeR',
'Isabeau',
'Gervais',
'Tholomyes',
'Blacheville',
'Favourite',
'Dahlia',
'Zephine',
'MmeThenardier',
'Cosette',
'Javert',
'Fauchelevent',
'Bamatabois',
'Perpetue',
'Woman1',
'Judge',
'Champmathieu',
'Brevet',
'Chenildieu',
'Cochepaille',
'Pontmercy',
'Boulatruelle',
'Eponine',
'Anzelma',
'Woman2',
'MotherInnocent',
'Gribier',
'Jondrette',
'Gavroche',
'Gillenormand',
'Magnon',
'MlleGillenormand',
'MmePontmercy',
'MlleVaubois',
'LtGillenormand',
'Marius',
'BaronessT',
'Mabeuf',
'Enjolras',
'Courfeyrac',
'Bahorel',
'Bossuet',
'MotherPlutarch',
'Gueulemer',
'Babet',
'Montparnasse',
'Toussaint',
'Child2',
'MmeHucheloup']
labels_split[2]
['Combeferre', 'Prouvaire', 'Joly', 'Grantaire', 'Claquesous', 'Brujon']
labels_split[3]
['Marguerite',
'Listolier',
'Fameuil',
'Fantine',
'Thenardier',
'Simplice',
'MmeBurgon',
'Feuilly',
'Child1']
labels_split[4]
['Scaufflaire']
Welche Art von Cluster geteilt wurde, ist wie folgt. Ich kenne Remize nur in Filmen und ich erinnere mich nur an Jean Barjan, also bin ich mir nicht sicher. Jambarujan ist im größten Cluster, kann ich nur sagen.
6. Am Ende
―― Was die theoretische Geschichte betrifft, kopiere ich nach meinem derzeitigen Kenntnisstand einfach Lernen von Beziehungsdaten, die mühsam und bedeutungslos ist, und lasse sie daher weg. Dann beziehen Sie sich auf dieses Buch. Es ist ein gutes Buch. ―― Übrigens erscheint in diesem Buch auch eine weitere Clusterbildung durch symmetrische Normalisierung Laplace. Es gibt kein Clustering, aber die Laplace-Berechnung für die symmetrische Normalisierung hat eine in NetworkX definierte Funktion hier. laplacianmatrix.normalized_laplacian_matrix.html # networkx.linalg.laplacianmatrix.normalized_laplacian_matrix) für Details. ――Wenn wir Clustering durchführen, konzentrieren wir uns auf den mit dem kleinsten Eigenwert, der frisch und interessant ist. Konzentrieren Sie sich auf die größere wie PCA.
Recommended Posts