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.