PageRank Википедии с использованием случайного SVD

Введение

В этом лабе мы будем анализировать граф ссылок внутри статей Википедии, чтобы ранжировать статьи по относительной важности с использованием собственного вектора центральности. Традиционный способ вычисления собственного вектора - это использование метода итерации по степеням. Здесь мы будем использовать алгоритм случайного SVD Мартинссона, реализованный в scikit-learn.

Советы по работе с ВМ

После запуска ВМ нажмите в левом верхнем углу, чтобы переключиться на вкладку Notebook и получить доступ к Jupyter Notebook для практики.

Иногда вам может потребоваться подождать несколько секунд, пока Jupyter Notebook не загрузится полностью. Валидация операций не может быть автоматизирована из-за ограничений Jupyter Notebook.

Если вы сталкиваетесь с проблемами во время обучения, не стесняйтесь обращаться к Labby. Оставьте отзыв после занятия, и мы оперативно решим проблему для вас.

Skills Graph

Загрузка данных, если они отсутствуют на диске

Мы загрузим данные из дампов 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, для анализа графа ссылок внутри статей Википедии, чтобы ранжировать статьи по относительной важности в соответствии с центральностью собственного вектора. Мы также вычислили показатель главного собственного вектора с использованием метода итерации по степеням.