Classificação de Páginas da Wikipédia com SVD Aleatorizado

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.