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.
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.