Introdução
Neste laboratório, analisaremos o gráfico de links dentro dos artigos da Wikipédia para classificar os artigos por importância relativa de acordo com a centralidade do autovetor. A forma tradicional de calcular o autovetor principal é usar o método da iteração de potências. Aqui, usaremos o algoritmo SVD Aleatorizado de Martinsson, implementado no scikit-learn.
Dicas da Máquina Virtual
Após o arranque da VM, clique no canto superior esquerdo para mudar para a aba Notebook para aceder ao Jupyter Notebook para a prática.
Por vezes, pode ser necessário esperar alguns segundos para o Jupyter Notebook terminar de carregar. A validação das operações não pode ser automatizada devido a limitações no Jupyter Notebook.
Se tiver problemas durante o aprendizado, não hesite em contactar o Labby. Forneça feedback após a sessão e resolveremos o problema rapidamente para si.
Descarregar dados, se ainda não estiverem no disco
Descarregaremos os dados dos dumps do DBpedia, que é uma extração dos dados estruturados latentes do conteúdo da 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("A descarregar dados de '%s', aguarde..." % url)
opener = urlopen(url)
with open(filename, "wb") as f:
f.write(opener.read())
print()
Carregar os ficheiros de redirecionamento
Vamos analisar os redirecionamentos e construir um mapa transitivamente fechado a partir deles.
DBPEDIA_RESOURCE_PREFIX_LEN = len("http://dbpedia.org/resource/")
SHORTNAME_SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)
def short_name(nt_uri):
"""Remover os marcadores de URI < e > e o prefixo URI comum"""
return nt_uri[SHORTNAME_SLICE]
def index(redirects, index_map, k):
"""Encontrar o índice de um nome de artigo após a resolução de redirecionamentos"""
k = redirects.get(k, k)
return index_map.setdefault(k, len(index_map))
def get_redirects(redirects_filename):
"""Analisar os redirecionamentos e construir um mapa transitivamente fechado a partir deles"""
redirects = {}
print("A analisar o ficheiro de redirecionamento NT")
for l, line in enumerate(BZ2File(redirects_filename)):
split = line.split()
if len(split) != 4:
print("Ignorar linha malformada: " + line)
continue
redirects[short_name(split[0])] = short_name(split[2])
if l % 1000000 == 0:
print("[%s] linha: %08d" % (datetime.now().isoformat(), l))
## calcular o fecho transitivo
print("A calcular o fecho transitivo da relação de redirecionamento")
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] linha: %08d" % (datetime.now().isoformat(), l))
return redirects
## Carregando os ficheiros de redirecionamento
redirects = get_redirects(redirects_filename)
Cálculo da matriz de adjacência
Extrairemos o grafo de adjacência como uma matriz esparsa scipy. Primeiro, os redirecionamentos são resolvidos. Retorna X, a matriz de adjacência esparsa scipy, redirecionamentos como um dicionário Python de nomes de artigos para nomes de artigos e index_map, um dicionário Python de nomes de artigos para inteiros Python (índices de artigos).
import numpy as np
from scipy import sparse
def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
"""Extrair o grafo de adjacência como uma matriz esparsa scipy"""
index_map = dict()
links = list()
for l, line in enumerate(BZ2File(page_links_filename)):
split = line.split()
if len(split) != 4:
print("ignorando linha 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] linha: %08d" % (datetime.now().isoformat(), l))
if limit is not None and l >= limit - 1:
break
print("Calculando a matriz de adjacência")
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("Convertendo para representação CSR")
X = X.tocsr()
print("Conversão CSR concluída")
return X, redirects, index_map
## parar após 5M links para tornar possível o trabalho na 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 do Vetor Singular Principal usando SVD Aleatorizado
Calcularemos os vetores singulares principais usando o método randomized_svd implementado no scikit-learn.
from sklearn.decomposition import randomized_svd
print("Calculando os vetores singulares principais usando randomized_svd")
U, s, V = randomized_svd(X, 5, n_iter=3)
Cálculo de pontuações de centralidade
Calcularemos a pontuação do autovetor principal usando um método de iteração de potência.
def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
"""Cálculo do autovetor principal por iteração de potência"""
n = X.shape[0]
X = X.copy()
incoming_counts = np.asarray(X.sum(axis=1)).ravel()
print("Normalizando o 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) ## estimativa inicial
for i in range(max_iter):
print("iteração de potência #%d" % i)
prev_scores = scores
scores = (
alpha * (scores * X + np.dot(dangle, prev_scores))
+ (1 - alpha) * prev_scores.sum() / n
)
## verificar convergência: 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("erro: %0.6f" % err)
if err < n * tol:
return scores
return scores
print("Calculando a pontuação do autovetor principal usando um método de iteração de potência")
scores = centrality_scores(X, max_iter=100)
Resumo
Neste laboratório, utilizamos o algoritmo SVD Aleatorizado de Martinsson, implementado no scikit-learn, para analisar o grafo de ligações entre artigos da Wikipédia e classificar os artigos por importância relativa, de acordo com a centralidade do autovetor. Também calculamos a pontuação do autovetor principal usando um método de iteração de potência.