Wikipedia PageRank mit Randomized SVD

Einführung

In diesem Lab werden wir die Verknüpfungsgrafiken innerhalb von Wikipedia-Artikeln analysieren, um die Artikel nach relativer Wichtigkeit gemäß der Eigenvektorzentralität zu klassifizieren. Die traditionelle Methode, um den Haupt-Eigenvektor zu berechnen, ist die Potenziteration. Hier werden wir Martinssons Randomized SVD-Algorithmus verwenden, der in scikit-learn implementiert ist.

Tipps für die VM

Nachdem der VM-Start abgeschlossen ist, klicken Sie in der oberen linken Ecke, um zur Registerkarte Notebook zu wechseln und Jupyter Notebook für die Übung zu nutzen.

Manchmal müssen Sie einige Sekunden warten, bis Jupyter Notebook vollständig geladen ist. Die Validierung von Vorgängen kann aufgrund von Einschränkungen in Jupyter Notebook nicht automatisiert werden.

Wenn Sie bei der Lernphase Probleme haben, können Sie Labby gerne fragen. Geben Sie nach der Sitzung Feedback, und wir werden das Problem für Sie prompt beheben.

Skills Graph

Daten herunterladen, wenn sie nicht bereits auf der Festplatte sind

Wir werden die Daten aus den DBpedia-Dumps herunterladen, die eine Extraktion der latenten strukturierten Daten des Wikipedia-Inhalts sind.

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("Downloading data from '%s', please wait..." % url)
        opener = urlopen(url)
        with open(filename, "wb") as f:
            f.write(opener.read())
        print()

Die Umleitungsdateien laden

Wir werden die Umleitungen analysieren und daraus eine transitiv abgeschlossene Karte erstellen.

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


def short_name(nt_uri):
    """Entfernt die < und > URI-Marker und den üblichen URI-Präfix"""
    return nt_uri[SHORTNAME_SLICE]


def index(redirects, index_map, k):
    """Finds den Index eines Artikelnamens nach der Auflösung der Umleitung"""
    k = redirects.get(k, k)
    return index_map.setdefault(k, len(index_map))


def get_redirects(redirects_filename):
    """Analysiert die Umleitungen und erstellt daraus eine transitiv abgeschlossene Karte"""
    redirects = {}
    print("Analysiere die NT-Umleitungsdatei")
    for l, line in enumerate(BZ2File(redirects_filename)):
        split = line.split()
        if len(split)!= 4:
            print("Ignoriere fehlerhafte Zeile: " + line)
            continue
        redirects[short_name(split[0])] = short_name(split[2])
        if l % 1000000 == 0:
            print("[%s] Zeile: %08d" % (datetime.now().isoformat(), l))

    ## Berechne die transitive Schließung
    print("Berechne die transitive Schließung der Umleitungsrelation")
    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] Zeile: %08d" % (datetime.now().isoformat(), l))

    return redirects


## Laden der Umleitungsdateien
redirects = get_redirects(redirects_filename)

Berechnung der Adjazenzmatrix

Wir werden den Adjazenzgraphen als scipy sparse Matrix extrahieren. Zuerst werden die Umleitungen aufgelöst. Gibt zurück X, die scipy sparse Adjazenzmatrix, Umleitungen als Python-Dictionary von Artikelnamen zu Artikelnamen und index_map ein Python-Dictionary von Artikelnamen zu Python-Int (Artikelindizes).

import numpy as np
from scipy import sparse


def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
    """Extrahiert den Adjazenzgraphen als scipy sparse Matrix"""
    index_map = dict()
    links = list()
    for l, line in enumerate(BZ2File(page_links_filename)):
        split = line.split()
        if len(split)!= 4:
            print("Ignoriere fehlerhafte Zeile: " + 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] Zeile: %08d" % (datetime.now().isoformat(), l))

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

    print("Berechne die Adjazenzmatrix")
    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("Konvertiere in CSR-Repräsentation")
    X = X.tocsr()
    print("CSR-Konvertierung abgeschlossen")
    return X, redirects, index_map


## Stoppe nach 5M Links, um es möglich zu machen, im Arbeitsspeicher zu arbeiten
X, redirects, index_map = get_adjacency_matrix(
    redirects_filename, page_links_filename, limit=5000000
)
names = {i: name for name, i in index_map.items()}

Berechnung des Hauptsingulärvektors mit Randomized SVD

Wir werden die Hauptsingulärvektoren mit der in scikit-learn implementierten randomized_svd-Methode berechnen.

from sklearn.decomposition import randomized_svd

print("Berechne die Hauptsingulärvektoren mit randomized_svd")
U, s, V = randomized_svd(X, 5, n_iter=3)

Berechnung von Zentralitätswerten

Wir werden den Haupt-Eigenvektorwert mit einer Potenziteration-Methode berechnen.

def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
    """Potenziteration zur Berechnung des Haupt-Eigenvektors"""
    n = X.shape[0]
    X = X.copy()
    incoming_counts = np.asarray(X.sum(axis=1)).ravel()

    print("Normalisiere den Graphen")
    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)  ## initial guess
    for i in range(max_iter):
        print("Potenziteration #%d" % i)
        prev_scores = scores
        scores = (
            alpha * (scores * X + np.dot(dangle, prev_scores))
            + (1 - alpha) * prev_scores.sum() / n
        )
        ## Überprüfe die Konvergenz: normalisierte l_inf-Norm
        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("Fehler: %0.6f" % err)
        if err < n * tol:
            return scores

    return scores


print("Berechne den Haupt-Eigenvektorwert mit einer Potenziteration-Methode")
scores = centrality_scores(X, max_iter=100)

Zusammenfassung

In diesem Lab haben wir Martinssons Randomized SVD-Algorithmus, der in scikit-learn implementiert ist, verwendet, um den Graphen der Links innerhalb von Wikipedia-Artikeln zu analysieren und die Artikel nach relativer Wichtigkeit gemäß der Eigenvektorzentralität zu klassifizieren. Wir haben auch den Haupt-Eigenvektorwert mit einer Potenziteration-Methode berechnet.