Introduction
Dans ce laboratoire, nous allons analyser le graphe des liens à l'intérieur des articles Wikipédia pour classer les articles selon leur importance relative en fonction de la centralité propre. La manière traditionnelle de calculer l'autovecteur principal est d'utiliser la méthode d'itération de puissance. Ici, nous utiliserons l'algorithme SVD aléatoire de Martinsson implémenté dans scikit-learn.
Conseils sur la machine virtuelle
Une fois le démarrage de la machine virtuelle terminé, cliquez dans le coin supérieur gauche pour basculer vers l'onglet Notebook pour accéder à Jupyter Notebook pour pratiquer.
Parfois, vous devrez peut-être attendre quelques secondes pour que Jupyter Notebook ait fini de charger. La validation des opérations ne peut pas être automatisée en raison des limitations de Jupyter Notebook.
Si vous rencontrez des problèmes pendant l'apprentissage, n'hésitez pas à demander à Labby. Donnez des commentaires après la session, et nous résoudrons rapidement le problème pour vous.
Télécharger les données, si elles ne sont pas déjà sur le disque
Nous allons télécharger les données à partir des dumps de DBpedia, qui est une extraction des données structurées latentes du contenu Wikipédia.
from bz2 import BZ2File
import os
from datetime import datetime
from urllib.request import urlopen
redirects_url = "http://downloads.dbpedia.org/3.5.1/en/redirects_en.nt.bz2"
redirects_filename = redirects_url.rsplit("/", 1)[1]
page_links_url = "http://downloads.dbpedia.org/3.5.1/en/page_links_en.nt.bz2"
page_links_filename = page_links_url.rsplit("/", 1)[1]
resources = [
(redirects_url, redirects_filename),
(page_links_url, page_links_filename),
]
for url, filename in resources:
if not os.path.exists(filename):
print("Téléchargement des données depuis '%s', veuillez patienter..." % url)
opener = urlopen(url)
with open(filename, "wb") as f:
f.write(opener.read())
print()
Charger les fichiers de redirection
Nous allons analyser les redirections et construire une carte fermée transitive à partir d'elles.
DBPEDIA_RESOURCE_PREFIX_LEN = len("http://dbpedia.org/resource/")
SHORTNAME_SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)
def short_name(nt_uri):
"""Supprime les marqueurs d'URI < et > et le préfixe d'URI commun"""
return nt_uri[SHORTNAME_SLICE]
def index(redirects, index_map, k):
"""Trouve l'index d'un nom d'article après la résolution des redirections"""
k = redirects.get(k, k)
return index_map.setdefault(k, len(index_map))
def get_redirects(redirects_filename):
"""Analyse les redirections et construit une carte fermée transitive à partir d'elles"""
redirects = {}
print("Analyse du fichier de redirection NT")
for l, line in enumerate(BZ2File(redirects_filename)):
split = line.split()
if len(split)!= 4:
print("ignorer la ligne malformée : " + line)
continue
redirects[short_name(split[0])] = short_name(split[2])
if l % 1000000 == 0:
print("[%s] ligne : %08d" % (datetime.now().isoformat(), l))
## calcule la clôture transitive
print("Calcul de la clôture transitive de la relation de redirection")
for l, source in enumerate(redirects.keys()):
transitive_target = None
target = redirects[source]
seen = {source}
while True:
transitive_target = target
target = redirects.get(target)
if target is None or target in seen:
break
seen.add(target)
redirects[source] = transitive_target
if l % 1000000 == 0:
print("[%s] ligne : %08d" % (datetime.now().isoformat(), l))
return redirects
## Chargement des fichiers de redirection
redirects = get_redirects(redirects_filename)
Calcul de la matrice d'adjacence
Nous allons extraire le graphe d'adjacence sous forme d'une matrice creuse scipy. Les redirections sont résolues en premier. Renvoie X, la matrice d'adjacence creuse scipy, les redirections sous forme de dictionnaire python de noms d'articles vers des noms d'articles, et index_map un dictionnaire python de noms d'articles vers des entiers python (index d'articles).
import numpy as np
from scipy import sparse
def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
"""Extraire le graphe d'adjacence sous forme d'une matrice creuse scipy"""
index_map = dict()
links = list()
for l, line in enumerate(BZ2File(page_links_filename)):
split = line.split()
if len(split)!= 4:
print("ignorer la ligne malformée : " + line)
continue
i = index(redirects, index_map, short_name(split[0]))
j = index(redirects, index_map, short_name(split[2]))
links.append((i, j))
if l % 1000000 == 0:
print("[%s] ligne : %08d" % (datetime.now().isoformat(), l))
if limit is not None and l >= limit - 1:
break
print("Calcul de la matrice d'adjacence")
X = sparse.lil_matrix((len(index_map), len(index_map)), dtype=np.float32)
for i, j in links:
X[i, j] = 1.0
del links
print("Conversion en représentation CSR")
X = X.tocsr()
print("Conversion CSR terminée")
return X, redirects, index_map
## s'arrêter après 5M liens pour pouvoir travailler en mémoire vive
X, redirects, index_map = get_adjacency_matrix(
redirects_filename, page_links_filename, limit=5000000
)
names = {i: name for name, i in index_map.items()}
Calcul du vecteur singulier principal à l'aide de la SVD aléatoire
Nous allons calculer les vecteurs singuliers principaux à l'aide de la méthode randomized_svd implémentée dans scikit-learn.
from sklearn.decomposition import randomized_svd
print("Calcul des vecteurs singuliers principaux à l'aide de randomized_svd")
U, s, V = randomized_svd(X, 5, n_iter=3)
Calcul des scores de centralité
Nous allons calculer le score du vecteur propre principal à l'aide d'une méthode d'itération de puissance.
def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
"""Calcul d'itération de puissance du vecteur propre principal"""
n = X.shape[0]
X = X.copy()
incoming_counts = np.asarray(X.sum(axis=1)).ravel()
print("Normalisation du graphe")
for i in incoming_counts.nonzero()[0]:
X.data[X.indptr[i] : X.indptr[i + 1]] *= 1.0 / incoming_counts[i]
dangle = np.asarray(np.where(np.isclose(X.sum(axis=1), 0), 1.0 / n, 0)).ravel()
scores = np.full(n, 1.0 / n, dtype=np.float32) ## estimation initiale
for i in range(max_iter):
print("itération de puissance #%d" % i)
prev_scores = scores
scores = (
alpha * (scores * X + np.dot(dangle, prev_scores))
+ (1 - alpha) * prev_scores.sum() / n
)
## vérification de la convergence : norme l_inf normalisée
scores_max = np.abs(scores).max()
if scores_max == 0.0:
scores_max = 1.0
err = np.abs(scores - prev_scores).max() / scores_max
print("erreur : %0.6f" % err)
if err < n * tol:
return scores
return scores
print("Calcul du score du vecteur propre principal à l'aide d'une méthode d'itération de puissance")
scores = centrality_scores(X, max_iter=100)
Sommaire
Dans ce laboratoire, nous avons utilisé l'algorithme de SVD aléatoire de Martinsson implémenté dans scikit-learn pour analyser le graphe des liens à l'intérieur des articles Wikipédia afin de classer les articles selon leur importance relative en fonction de la centralité du vecteur propre. Nous avons également calculé le score du vecteur propre principal à l'aide d'une méthode d'itération de puissance.