Apprentissage des données relationnelles avec numpy et NetworkX (clustering spectral)
1.Tout d'abord
Cet article est ** un résumé de l'analyse de réseau (extraction de communauté) par python ** et une utilisation simple de NetworkX, qui est une bibliothèque pratique pour l'analyse de réseau **. ** Implémentez le clustering spectral avec numpy ** comme algorithme d'extraction de communauté.
Pour une motivation personnelle, lisez cet article (Derivation of Probabilistic Matrix Factorization and Implemented in Edward). Livre (Apprentissage des données relationnelles) J'ai commencé à le lire parce que je pensais que ce serait intéressant, donc c'est comme un résumé.
2. Construction de l'environnement
2.1. Environnement de mise en œuvre cette fois
- Python 3.6.0 :: Anaconda 4.3.1 (x86_64)
- numpy 1.11.3
2.2. Installation
pip install networkx==1.9.1
Installez networkx 1.9.1. La dernière version est la 1.11 mais quand je l'utilise, j'obtiens NetworkXError: cannot tokenize'graph 'at (2, 1)' '`` lors du chargement des données. Quand je l'ai regardé, il y avait une personne qui a dit: «Je l'ai eu, mais quand je suis passé à la version 1.9.1, je pourrais l'utiliser», alors j'en tirerai des leçons.
3. À propos des données
3.1. Source des données
Ici a publié un certain nombre de données d'essai liées à l'analyse de réseau.
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).
Est utilisé.
3.2. Contenu des données
Ces données semblent être les données de personnes qui sont apparues ensemble dans la même scène dans le roman Remiserable. Le nombre de fois qu'ils apparaissent ensemble devient la valeur de bord et le nœud devient un caractère.
Ce sont des données intéressantes, je me demandais s'il y avait de telles données, mais après avoir fini d'écrire le code, j'ai trouvé cet article de M. TJO, qui est célèbre dans le domaine Twitter.
J'essaie différentes méthodes pour la même tâche d'extraction communautaire. Si vous lisez cet article, vous serez en mesure de comprendre quel type de données sont ces données Remize et ce que vous pouvez comprendre en extrayant la communauté.
Après avoir lu cet article, j'ai pensé que R était plus complet que python dans la bibliothèque d'analyse de réseau. Ou devrais-je utiliser cytoscape? (Ou je ne sais rien d'autre)
3.3. Format des données
.Les données avec l'extension gml se trouvent dans le zip du lien ci-dessus. gml est une abréviation de Graph Modeling Language, qui est un format de stockage pour les données de structure graphique.
Les informations sur les nœuds et les arêtes du graphique sont stockées dans la structure suivante.
```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. Lecture des données
Les données .gml peuvent être lues dans l'objet graphique défini par NetworkX avec la fonction read_gml de NetworkX.
import networkx as nx
data_path = "./data/lesmis/lesmis.gml"
G = nx.read_gml(data_path)
Si vous voulez en faire un tableau de numpy,
X = np.array(nx.to_numpy_matrix(G))
Vous pouvez le faire comme ça. La valeur de retour de to_numpy_matrix``` est numpy matrix, mais comme ndarray est plus facile à utiliser personnellement, je l'ai changé en ndarray comme ci-dessus.
Par ailleurs, dans ce regroupement spectral, on suppose que la matrice du graphe est une matrice symétrique. Comme vous pouvez le voir en regardant les données, dans NetworkX
nx.is_directed(G)
# False
Vous pouvez vérifier si le graphe est un graphe orienté (pas une matrice symétrique) ou un graphe non orienté (matrice symétrique) avec la fonction. C'est un graphe non orienté car il est faux en vérifiant s'il est orienté ou non.
4. Code
4.1. Aperçu
ici,
- Clustering spectral basé sur un graphe laplacien non normalisé
- Clustering spectral basé sur le laplacien de graphe de normalisation de marche ivre Deux sont mis en œuvre.
Dans la méthode basée sur un graphe laplasien non normalisé, lorsque le clustering est exécuté, il y a une tendance à classer un nœud et l'autre, et le clustering est subtil, donc la version améliorée est basée sur le graphe laplasien normalisé. Il existe différents types de laplacien graphique normalisé en fonction de la méthode de normalisation, et le laplacien graphique normalisé ivre est implémenté.
4.2. Définition des classes et des fonctions
Définissez la classe qui effectue réellement le regroupement spectral et les fonctions requises pour tracer les résultats de l'exécution.
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()
Une explication détaillée du code peut être reportée à la classification spectrale et au traçage des résultats comme suit:
4.3. Déplacer le 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)
Je l'utilise comme ça.
graph_clustering(k=15, n_clusters=5, lap_kind="rw")L'argument de estkCombien de vecteurs propresn_clustersCombien de clusters doivent être divisés enlap_kindDonne le type d'algorithme de clustering spectral.
lap_kind=noneDénormalisé aveclap_kind="rw"Effectuer la mise en cluster du laplacien graphique de normalisation de marche en état d'ébriété.
4.4. À propos du code à tracer
La partie intrigue avait besoin d'un peu d'ingéniosité. Je trace avec la fonction nx.draw_networkx``` dans plot_clusters () '', mais je n'avais pas la possibilité de tracer différentes couleurs pour chaque cluster identifié, donc de cette façon Je complote.
nx.draw_networkx(G, node_color=colors[i], labels=labels_dic, nodelist=nodes, pos=pos, font_color="r")
Puisque j'ai pu tracer partiellement à partir du graphique entier avec cet argument de nodelist```, divisez les nœuds en grappes et tracez en changeant les couleurs avec` `node_color = colors [i]` ` Faire. De plus, comme cela écrase de plus en plus le tracé, si vous ne spécifiez pas la position avec l'argument `` pos '', la position changera à chaque fois et elle sera foirée.
5. Résultat de l'exécution
5.1. Laplacien graphique dénormalisé
gclus = graph_clustering(k=15, n_clusters=5, lap_kind=none)Dans le cas de.
Il est vrai qu'un nœud est un cluster, et cela ne ressemble pas du tout à un cluster.
5.2 Graphique de normalisation de la marche en état d'ébriété Laplacien
gclus = graph_clustering(k=15, n_clusters=5, lap_kind="rw")Dans le cas de.
Cela ressemble un peu à un cluster.
5.3. Répartition des clusters
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']
Quel genre de cluster a été divisé est comme ça. Je ne connais Remize que dans les films et je ne me souviens que de Jean Barjan, donc je ne suis pas sûr. Jambarujan est dans le plus grand cluster, je peux seulement dire.
6. À la fin
―― Quant à l'histoire théorique, dans mes connaissances actuelles, je viens de copier et coller Apprentissage des données relationnelles, ce qui est gênant et dénué de sens, alors je l'omets. Alors référez-vous à ce livre. C'est un bon livre. Au fait, un autre clustering par normalisation symétrique laplacienne apparaît également dans ce livre. Il n'y a pas de clustering, mais le calcul laplacien de normalisation symétrique a une fonction définie dans NetworkX, [ici](https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.linalg. laplacianmatrix.normalized_laplacian_matrix.html # networkx.linalg.laplacianmatrix.normalized_laplacian_matrix) pour plus de détails. ――Lors de la mise en cluster, nous nous concentrons sur celui avec la plus petite valeur propre, ce qui est frais et intéressant. Concentrez-vous sur le plus grand, comme le PCA.
Recommended Posts