Wikipedia PageRank con SVD aleatorizado

Introducción

En este laboratorio, analizaremos el gráfico de enlaces dentro de los artículos de Wikipedia para clasificar los artículos por importancia relativa de acuerdo con la centralidad de eigenvector. La forma tradicional de calcular el eigenvector principal es utilizar el método de iteración de potencia. Aquí usaremos el algoritmo de SVD aleatorizado de Martinsson implementado en scikit-learn.

Consejos sobre la VM

Una vez que se haya iniciado la VM, haga clic en la esquina superior izquierda para cambiar a la pestaña Cuaderno y acceder a Jupyter Notebook para practicar.

A veces, es posible que tenga que esperar unos segundos a que Jupyter Notebook termine de cargarse. La validación de las operaciones no se puede automatizar debido a las limitaciones de Jupyter Notebook.

Si tiene problemas durante el aprendizaje, no dude en preguntar a Labby. Deje sus comentarios después de la sesión y lo resolveremos rápidamente para usted.

Descargar datos, si no están ya en el disco

Descargaremos los datos de los dumps de DBpedia, que es una extracción de los datos estructurados latentes del contenido de Wikipedia.

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("Descargando datos de '%s', espere por favor..." % url)
        opener = urlopen(url)
        with open(filename, "wb") as f:
            f.write(opener.read())
        print()

Cargar los archivos de redirección

Analizaremos las redirecciones y construiremos un mapa transitivamente cerrado a partir de ellas.

DBPEDIA_RESOURCE_PREFIX_LEN = len("http://dbpedia.org/resource/")
SHORTNAME_SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)


def short_name(nt_uri):
    """Quitar los marcadores URI < y > y el prefijo URI común"""
    return nt_uri[SHORTNAME_SLICE]


def index(redirects, index_map, k):
    """Encontrar el índice de un nombre de artículo después de la resolución de redirecciones"""
    k = redirects.get(k, k)
    return index_map.setdefault(k, len(index_map))


def get_redirects(redirects_filename):
    """Analizar las redirecciones y construir un mapa transitivamente cerrado a partir de ellas"""
    redirects = {}
    print("Analizando el archivo de redirecciones NT")
    for l, line in enumerate(BZ2File(redirects_filename)):
        split = line.split()
        if len(split)!= 4:
            print("ignorando línea malformada: " + line)
            continue
        redirects[short_name(split[0])] = short_name(split[2])
        if l % 1000000 == 0:
            print("[%s] línea: %08d" % (datetime.now().isoformat(), l))

    ## calcular la clausura transitiva
    print("Calculando la clausura transitiva de la relación de redirección")
    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] línea: %08d" % (datetime.now().isoformat(), l))

    return redirects


## Cargando los archivos de redirección
redirects = get_redirects(redirects_filename)

Calculando la matriz de adyacencia

Extraeremos el gráfico de adyacencia como una matriz dispersa de scipy. Las redirecciones se resuelven primero. Devuelve X, la matriz de adyacencia dispersa de scipy, las redirecciones como un diccionario de Python de nombres de artículo a nombres de artículo, e index_map, un diccionario de Python de nombres de artículo a enteros de Python (índices de artículo).

import numpy as np
from scipy import sparse


def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
    """Extraer el gráfico de adyacencia como una matriz dispersa de scipy"""
    index_map = dict()
    links = list()
    for l, line in enumerate(BZ2File(page_links_filename)):
        split = line.split()
        if len(split)!= 4:
            print("ignorando línea malformada: " + 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] línea: %08d" % (datetime.now().isoformat(), l))

        if limit is not None and l >= limit - 1:
            break

    print("Calculando la matriz de adyacencia")
    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("Convirtiendo a representación CSR")
    X = X.tocsr()
    print("Conversión CSR realizada")
    return X, redirects, index_map


## detener después de 5M enlaces para poder trabajar en RAM
X, redirects, index_map = get_adjacency_matrix(
    redirects_filename, page_links_filename, limit=5000000
)
names = {i: name for name, i in index_map.items()}

Cálculo del vector singular principal utilizando SVD aleatorizado

Calcularemos los vectores singulares principales utilizando el método randomized_svd implementado en scikit-learn.

from sklearn.decomposition import randomized_svd

print("Calculando los vectores singulares principales utilizando randomized_svd")
U, s, V = randomized_svd(X, 5, n_iter=3)

Cálculo de puntuaciones de centralidad

Calcularemos la puntuación del eigenvector principal utilizando un método de iteración de potencia.

def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
    """Cálculo de iteración de potencia del eigenvector principal"""
    n = X.shape[0]
    X = X.copy()
    incoming_counts = np.asarray(X.sum(axis=1)).ravel()

    print("Normalizando el grafo")
    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)  ## suposición inicial
    for i in range(max_iter):
        print("iteración de potencia #%d" % i)
        prev_scores = scores
        scores = (
            alpha * (scores * X + np.dot(dangle, prev_scores))
            + (1 - alpha) * prev_scores.sum() / n
        )
        ## comprobar la convergencia: norma l_inf normalizada
        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("error: %0.6f" % err)
        if err < n * tol:
            return scores

    return scores


print("Calculando la puntuación del eigenvector principal utilizando un método de iteración de potencia")
scores = centrality_scores(X, max_iter=100)

Resumen

En este laboratorio, utilizamos el algoritmo de SVD aleatorizado de Martinsson implementado en scikit-learn para analizar el gráfico de enlaces dentro de los artículos de Wikipedia y clasificar los artículos por importancia relativa de acuerdo con la centralidad del eigenvector. También calculamos la puntuación del eigenvector principal utilizando un método de iteración de potencia.