Введение
В этом лабе мы будем анализировать граф ссылок внутри статей Википедии, чтобы ранжировать статьи по относительной важности с использованием собственного вектора центральности. Традиционный способ вычисления собственного вектора - это использование метода итерации по степеням. Здесь мы будем использовать алгоритм случайного SVD Мартинссона, реализованный в scikit-learn.
Советы по работе с ВМ
После запуска ВМ нажмите в левом верхнем углу, чтобы переключиться на вкладку Notebook и получить доступ к Jupyter Notebook для практики.
Иногда вам может потребоваться подождать несколько секунд, пока Jupyter Notebook не загрузится полностью. Валидация операций не может быть автоматизирована из-за ограничений Jupyter Notebook.
Если вы сталкиваетесь с проблемами во время обучения, не стесняйтесь обращаться к Labby. Оставьте отзыв после занятия, и мы оперативно решим проблему для вас.
Загрузка данных, если они отсутствуют на диске
Мы загрузим данные из дампов DBpedia, которые представляют собой извлечение скрытой структурированной информации из содержания Википедии.
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()
Загрузка файлов с переадресациями
Мы будем разбирать переадресации и создавать из них транзитивно замкнутую карту.
DBPEDIA_RESOURCE_PREFIX_LEN = len("http://dbpedia.org/resource/")
SHORTNAME_SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)
def short_name(nt_uri):
"""Удалить маркеры URI < и > и общий префикс URI"""
return nt_uri[SHORTNAME_SLICE]
def index(redirects, index_map, k):
"""Найти индекс имени статьи после разрешения переадресации"""
k = redirects.get(k, k)
return index_map.setdefault(k, len(index_map))
def get_redirects(redirects_filename):
"""Разобрать переадресации и создать из них транзитивно замкнутую карту"""
redirects = {}
print("Разбор NT файла с переадресациями")
for l, line in enumerate(BZ2File(redirects_filename)):
split = line.split()
if len(split)!= 4:
print("игнорируем неправильную строку: " + line)
continue
redirects[short_name(split[0])] = short_name(split[2])
if l % 1000000 == 0:
print("[%s] строка: %08d" % (datetime.now().isoformat(), l))
## вычислить транзитивное замыкание
print("Вычисление транзитивного замыкания отношения переадресации")
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] строка: %08d" % (datetime.now().isoformat(), l))
return redirects
## Загрузка файлов с переадресациями
redirects = get_redirects(redirects_filename)
Вычисление матрицы смежности
Мы извлечем граф смежности в виде разреженной матрицы в scipy. Переадресации разрешаются сначала. Возвращает X - разреженную матрицу смежности в scipy, redirects - словарь на Python от имен статей к именам статей, и index_map - словарь на Python от имен статей к целым числам Python (индексам статей).
import numpy as np
from scipy import sparse
def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
"""Извлечь граф смежности в виде разреженной матрицы в scipy"""
index_map = dict()
links = list()
for l, line in enumerate(BZ2File(page_links_filename)):
split = line.split()
if len(split)!= 4:
print("игнорируем неправильную строку: " + 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] строка: %08d" % (datetime.now().isoformat(), l))
if limit is not None and l >= limit - 1:
break
print("Вычисление матрицы смежности")
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("Преобразование в CSR представление")
X = X.tocsr()
print("Преобразование CSR завершено")
return X, redirects, index_map
## остановиться после 5M ссылок, чтобы можно было работать в 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()}
Вычисление главного сингулярного вектора с использованием случайного SVD
Мы вычислим главные сингулярные векторы с использованием метода randomized_svd, реализованного в scikit-learn.
from sklearn.decomposition import randomized_svd
print("Вычисление главных сингулярных векторов с использованием randomized_svd")
U, s, V = randomized_svd(X, 5, n_iter=3)
Вычисление показателей центральности
Мы вычислим показатель главного собственного вектора с использованием метода итерации по степеням.
def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
"""Вычисление главного собственного вектора методом итерации по степеням"""
n = X.shape[0]
X = X.copy()
incoming_counts = np.asarray(X.sum(axis=1)).ravel()
print("Нормализация графа")
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) ## начальное приближение
for i in range(max_iter):
print("итерация по степеням #%d" % i)
prev_scores = scores
scores = (
alpha * (scores * X + np.dot(dangle, prev_scores))
+ (1 - alpha) * prev_scores.sum() / n
)
## проверка сходимости: нормализованная l_inf норма
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("ошибка: %0.6f" % err)
if err < n * tol:
return scores
return scores
print("Вычисление показателя главного собственного вектора методом итерации по степеням")
scores = centrality_scores(X, max_iter=100)
Резюме
В этом практическом занятии мы использовали алгоритм случайного SVD Мартинссона, реализованный в scikit-learn, для анализа графа ссылок внутри статей Википедии, чтобы ранжировать статьи по относительной важности в соответствии с центральностью собственного вектора. Мы также вычислили показатель главного собственного вектора с использованием метода итерации по степеням.