PageRank de Wikipédia avec SVD aléatoire

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.

Skills Graph

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.