Google в значительной степени обязан своим успехом алгоритму, который изначально использовался для ранжирования веб-страниц. Этот алгоритм, PageRank, сортирует все страницы сети по их популярности. Чем больше веб-страниц ссылается на какую-либо страницу A, тем выше ее оценка и с наибольшей вероятностью она появится среди лучших результатов поиска. Пример PageRank обычно приводится в курсах линейной алгебры, так как это хорошая иллюстрация применения собственных значений и собственных векторов. Эта статья направлена на создание интуитивного понимания PageRank и покажет математические вычисления и код, лежащий в основе этого.
Он предполагает базовые знания линейной алгебры, включая управление матрицами и векторами. Предварительное знание собственных значений и собственных векторов будет полезно, хотя и не обязательно. Мы проиллюстрируем алгоритм чистой реализацией на Python и Numpy, а также с библиотекой NetworkX.
Начнем с настройки крошечного Интернета. Он состоит из шести веб-страниц, содержащих ссылки на другие страницы или на самих себя. Мы можем представить эту сеть в виде ориентированного графа, как на беспорядочном рисунке ниже.
Мы представим этот график с помощью матрицы смежности, где значение в строке r и столбце c - это вероятность попадания на веб-страницу r при условии, что вы только что перешли по ссылке с веб-страницы c. Например, страница A ссылается на страницы B, D и F. Поскольку существует три пункта назначения, мы нормализуем наш вектор с коэффициентом 1/3, что дает нам:
Мы назвали этот вектор L[A], что означает Ссылка со страницы A.
Применяя тот же процесс ко всем нашим страницам, мы получаем матрицу ссылок, показанную ниже.
Хотя вы можете найти реализации, которые ведут себя по-другому, наша матрица ссылок игнорирует ссылки, ссылающиеся на себя. Мы также не рассматриваем несколько ссылок на одну и ту же цель.
Прежде чем перейти к более абстрактному описанию PageRank, этот отрывок из оригинальной статьи, опубликованной в 1998 году (ссылка в сносках), может дать вам хорошее представление о том, что делает алгоритм:
Интуитивно это можно представить как моделирование поведения «случайного пользователя». «Случайный пользователь» просто продолжает случайным образом переходить по последовательным ссылкам.
Идея PageRank состоит в том, чтобы присвоить каждой странице рейтинг популярности, который мы называем рейтингом. Если пользователи часто попадают на какую-либо веб-страницу, это означает, что многие другие страницы рекомендуют ее, и, следовательно, это может быть хорошо. Цель алгоритма - определить вероятность того, что случайные пользователи окажутся на каждой странице, пока они бродят по Интернету.
n-я строка матрицы указывает все страницы, которые содержат ссылку на n-ю страницу и вероятность ее достижения. Суммируя все значения в каждой строке, мы можем определить первую оценку популярности. Но мы также должны учитывать популярность страницы, на которой есть ссылка, так как вас лучше упомянула бы популярная страница, чем та, которую редко посещают. Мы можем перевести это описание в итеративную формулу, в которой популярность страницы A зависит от каждой ссылки, которая ведет на нее, и взвешена по популярности страницы, содержащей ссылку:
Мы можем обобщить и упростить приведенное выше выражение, записав его как произведение матрицы ссылок L на матрицу столбцов R, которая содержит оценку популярности каждой веб-страницы:
Мы оцениваем это выражение до тех пор, пока оно не сойдется, то есть пока популярность всех веб-страниц не изменится при умножении на матрицу ссылок.
Другими словами, эта операция сводится к нахождению собственных векторов собственного значения 1 матрицы связей. Учитывая размер матрицы, которая может быстро стать чрезвычайно большой, использование этой рекурсивной формулы, известной как степенной метод, является одним из наиболее эффективных способов решения проблемы.
Давайте посмотрим на простую реализацию на Python:
def rank_websites(links: np.ndarray, threshold: float = 1e-4):
size = links.shape[0]
initial = np.ones(size) * 1/size
previous_ranking: np.ndarray = initial
iterations = 1
popularity = links @ initial
while np.linalg.norm(previous_ranking - popularity) > threshold:
previous_ranking = popularity
popularity = links @ popularity
iterations += 1
return popularity, iterations
Функция принимает два параметра: матрицу ссылок в виде массива Numpy и порог, установленный по умолчанию на 1 × 10 ^ {- 4}. Порог соответствует толерантности при проверке сходимости популярности.
Мы начинаем с создания нашего исходного вектора популярности, в котором популярность каждой страницы распределяется равномерно.
Нам также нужно сохранить предыдущий вектор популярности, который мы будем использовать, чтобы проверить, сходится ли он.
Теперь мы можем выполнять итерацию, пока норма разницы между предыдущим и текущим вектором ранжирования больше порогового значения.
Если мы оценим эту функцию с помощью нашей матрицы ссылок L, мы получим следующий результат (я умножил его на 100, чтобы сделать его более разборчивым) после 35 итераций:
[29.12342755 22.33189164 11.64928625 9.71001964 13.98001348 13.20536144]
Имейте в виду, что наш метод дает только приближение собственных векторов собственного значения 1 матрицы связей. Поскольку сеть достаточно мала, мы можем сравнить наши результаты с результатами, возвращаемыми калькулятором собственных векторов Numpy:
eigenvalues, eigenvectors = np.linalg.eig(L)
order = np.absolute(eigenvalues).argsort()[::-1]
eigenvectors = eigenvectors[:, order]
r = eigenvectors[:, 0]
normalised_r = r / np.sum(r)
print("using numpy eig function, r =", 100 * normalised_r)
Этот код начинается с выборки собственных значений и собственных векторов матрицы ссылок. Затем мы вычисляем порядок индексов на основе их собственных значений в строке 2), который мы используем для сортировки собственных векторов путем увеличения собственного значения (в строке 3). Мы извлекаем собственный вектор с наивысшим собственным значением в строке 4, который нормализуем, чтобы сделать его стохастическим. Это дает нам следующий результат:
[29.12621359-0.j 22.33009709-0.j 11.65048544-0.j 9.70873786-0.j 13.98058252-0.j 13.2038835 -0.j]
Фактор демпфирования
Предыдущая реализация отлично работала на простом примере. Но мы не ожидаем, что все сети будут вести себя так хорошо: если мы рассмотрим больше примеров и некоторые частные случаи, мы можем натолкнуться на некоторые неожиданные результаты. Возьмем для примера следующий график Дельта:
Сеть разделена на две подсети, которые мы назвали (i) и (ii). (i) и (ii) связаны односторонней ссылкой. Следовательно, если случайные серферы начинают свой квест в (i), вероятность того, что они попадут в (ii), не равна нулю.
Однако, как только они достигнут этого, они не могут вернуться к (i). Если мы построим матрицу связей и вычислим ее главный собственный вектор, мы получим следующие результаты:
[-3.58205484e-01, 0.00000000e+00, 7.61186653e-01, 2.23878427e-02, 4.06650495e+14, -8.13300990e+14, 1.21995149e+15, -8.13300990e+14]
Как и следовало ожидать, страницы в (ii) имеют гораздо более высокий рейтинг, чем страницы в (i). Распространенным примером таких подсетей является Википедия: многие страницы содержат ссылки на нее, но страницы Википедии содержат только внутренние ссылки (внешние ссылки являются «ссылками без подписки» и, следовательно, не регистрируются поисковыми системами).
Проблема этой реализации PageRank заключается в том, что она предполагает, что, попав на любую страницу Википедии, вы просматриваете все другие страницы, даже не возвращаясь или не телепортируясь на другой веб-сайт, набрав его URL. Очевидно, что этот подход не отображает реальное поведение веб-пользователя, и результаты, которые он дает, не имеют отношения к делу.
Более наглядный пример этой проблемы - когда сеть состоит из нескольких полностью отключенных графов, как в примере ниже.
Поскольку между обеими подсетями, составляющими Epsilon, нет взаимосвязей, будет невозможно получить общий рейтинг популярности.
Если мы попытаемся использовать наш алгоритм для вычисления PageRank этой сети, вот вектор r после каждой из 10 первых итераций:
Initial [0.2 0.2 0.2 0.2 0.2] 1 [0. 0.2 0.4 0.2 0.2] 2 [0. 0.4 0.2 0.2 0.2] 3 [0. 0.2 0.4 0.2 0.2] 4 [0. 0.4 0.2 0.2 0.2] 5 [0. 0.2 0.4 0.2 0.2] 6 [0. 0.4 0.2 0.2 0.2] 7 [0. 0.2 0.4 0.2 0.2] 8 [0. 0.4 0.2 0.2 0.2] 9 [0. 0.2 0.4 0.2 0.2] 10 [0. 0.4 0.2 0.2 0.2]
Рейтинг страниц B и C колеблется между 0.2 и 0.4, не меняясь. Если дать ему поработать немного дольше, он продолжит повторяться более 1 миллиона раз, не перегружая.
Мы воспользуемся калькулятором собственных векторов Numpy, чтобы попытаться понять причину такого поведения.
eigenvalues: [ 1. -1. 1. -1. 0.] first eigenvector of eigenvalue 1: [0. 0. 0. 0.70710678 0.70710678] second eigenvector of eigenvalue 1: [0. 0.70710678 0.70710678 0. 0. ]
Проблема этой сети в том, что она содержит несколько собственных векторов с собственным значением 1: первый вектор дает ранг сети {DE} без учета другого, а второй вектор дает ранг сети {ABC}.
Эти два примера объясняют, почему нам нужно включить в нашу формулу дополнительный параметр: коэффициент демпфирования. В исходной статье он описан следующим образом:
[…] Если настоящий веб-серфер когда-либо попадет в небольшой цикл веб-страниц, маловероятно, что он будет продолжать оставаться в этом цикле вечно. Вместо этого пользователь перейдет на другую страницу. Дополнительный фактор E можно рассматривать как способ моделирования этого поведения: серфер периодически «скучает» и переходит на случайную страницу, выбранную на основе распределения в E.
Коэффициент демпфирования (который мы назовем d) соответствует вероятности того, что случайный пользователь перейдет по ссылке на странице, которую он в данный момент посещает. Следовательно, мы можем рассматривать вероятность 1 — d как вероятность того, что они введут URL-адрес в строку поиска и попадут на случайный веб-сайт.
При использовании коэффициента затухания мы пытаемся вычислить собственный вектор собственного значения 1 новой матрицы - мы назовем его L_hat (не удалось найти способ поставить циркумфлекс на согласный звук на моей клавиатуре ...) - что является «улучшенным »Версия матрицы ссылок L. Он задается в виде d и L по формуле ниже:
Этот метод помогает решить проблемы, с которыми мы столкнулись, удаляя все ссылки со значением 0.
Чтобы обновить нашу реализацию Python, все, что нам нужно, это добавить новый параметр d и написать следующую строку после инициализации переменной size:
links = (d * links + (1 - d) * 1/size)
Обратите внимание, что матрица, содержащая 1 'везде, необходима в математическом утверждении, потому что вычитание скаляра из матрицы не определено, но эта операция неявна при использовании массивов Numpy (она заберет значение из каждой записи матрицы).
Давайте теперь протестируем нашу улучшенную реализацию с помощью графика Delta. Вместо того, чтобы получать огромные ранги величиной 10^{14} для страниц во второй подсети и крохотные ранги, вращающиеся вокруг 10^{-1} для страниц в первой сети, мы получаем гораздо более реалистичные результаты при использовании коэффициента демпфирования 0.85:
[0.1011186, 0.10702601, 0.07014488, 0.07014488, 0.10941522, 0.15981798, 0.22251445, 0.15981798]
В целом подсеть (ii) остается более популярной, чем (i). Но все ранги имеют одинаковую величину, что подтверждает нашу интуицию и не позволяет страницам, не содержащим исходящих ссылок, поглощать весь трафик.
Коэффициент демпфирования также позволяет нашим случайным пользователям телепортироваться через Эпсилон. Таким образом, PageRank теперь равномерно распределяется по сети:
[0.03 0.2918891 0.2781109 0.2 0.2 ]
Страница A имеет ненулевой рейтинг, даже если никто этого не рекомендует; и все записи в сумме составляют 1. Это означает, что они соответствуют вероятности попадания на каждую страницу по отношению ко всей сети, а не к локальным подграфам.
Использование NetworkX
Теперь, когда мы знаем, как работает PageRank, мы можем просто использовать его реализацию в NetworkX. NetworkX - это библиотека Python, которая позволяет управлять графиками. Вот как это сделать.
- Установка
networkx.
$pip install networkx
2. Построение графика. Есть несколько способов сделать это, один из самых полезных - функция from_numpy_matrix. Он принимает матрицу смежности Numpy (матрицу ссылок) и возвращает график:
import networkx as nx internet = nx.from_numpy_matrix(L)
3. Вычисление рейтинга страницы. Здесь опять же существует несколько функций, которые выполняют свою работу по-разному. Двумя основными являются pagerank, который повторяется заданное количество раз и вызывает исключение, если сеть не сходится; и pagerank_numpy, который использует Numpy для вычисления собственного вектора матрицы смежности графа.
nx.pagerank(graph, alpha=0.85, max_iter=100)
nx.pagerank_numpy(graph, alpha=0.85)В приведенном выше примере показано базовое использование этих двух функций. Параметр alpha - коэффициент демпфирования. Для получения дополнительной информации, вот ссылки на документацию по обеим функциям.
networkx.algorithms.link_analysis.pagerank_alg.pagerank_numpy - документация NetworkX 2.5
dangling (dict, необязательно) - выходы, которые будут назначены любым« висячим узлам, т. Е. Узлам без выступов. … networkx.github.io »
Ресурсы:
Оригинал статьи: http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf
Википедия: https://en.wikipedia.org/wiki/PageRank
Видео с курса Линейная алгебра для машинного обучения ICL на Coursera: M4ML - Линейная алгебра - 5.7 Введение в PageRank… www.youtube.com› смотреть
Плейлист Youtube от Global Software Support: Глобальная поддержка программного обеспечения алгоритма PageRank Google. Глобальная поддержка программного обеспечения •
