Алгоритм поиска Google: реализация на Python
PageRank (PR) - это алгоритм, используемый поиском Google для ранжирования веб-сайтов в результатах поисковых систем в соответствии с их важностью. Но что означает «важность»? В этом случае, согласно Google, это означает количество и качество внутренних ссылок страницы, на самом деле:
«PageRank работает путем подсчета количества и качества ссылок на страницу для определения приблизительной оценки важности веб-сайта. Основное предположение состоит в том, что более важные веб-сайты, вероятно, будут получать больше ссылок с других веб-сайтов ».
Чтобы понять значение этого алгоритма, нам сначала нужно представить, как визуализировать структуру всемирной паутины. По сути, идея состоит в том, что WWW можно представить как (огромную) сеть, где веб-сайты являются узлами, а их связи между собой являются (направленными) ребрами. Итак, давайте упростим настройку нашей WWW, представив, что существует только 4 веб-сайта: A, B, C и D. Для этой цели я использую пакет Python Networkx (вы можете установить его через pip на вашей консоли):
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
DG = nx.DiGraph()
DG.add_nodes_from("ABCD")
nx.draw(DG,with_labels=True)
plt.show()
Алгоритм PageRank выводит распределение вероятностей, используемое для представления вероятности того, что человек, случайно нажимающий на ссылки, попадет на любую конкретную страницу. Следовательно, на выходе будет вектор, сумма компонентов которого равна 1, а количество компонентов равно количеству узлов. Чем выше значение компонента, связанного с одним узлом, тем выше важность этого узла.
Теперь, поскольку между нашими узлами A, B, C, D нет связей, идея состоит в том, что на данный момент все они одинаково важны. Действительно:
pr=nx.pagerank(DG, alpha=0.85)
pr
Output:
{'A': 0.25, 'B': 0.25, 'C': 0.25, 'D': 0.25}
Примечание: параметр alpha - это так называемый коэффициент демпфирования. Это потому, что алгоритм должен учитывать тот факт, что воображаемый пользователь, который случайно нажимает на ссылки, в конечном итоге перестанет нажимать. Вероятность на любом этапе того, что человек продолжит, - это коэффициент демпфирования alpha, и Google установил его равным 0,85, что является значением по умолчанию для нашего алгоритма PageRank networkx.
Как видно из выходных данных, каждый узел имеет важность 1/4. Теперь давайте добавим ссылки между нашими узлами. Допустим, я хочу, чтобы A указывало на точку B, B - на точку C, C - на точку D, а D - на точку A (с одинаково важными связями). Это означает, что каждый узел передает свою важность своему преемнику, получая при этом важность своего предшественника.
DG.add_weighted_edges_from([("A", "B", 1), ("B", "C", 1),("C","D",1),("D","A",1)])
nx.draw(DG,with_labels=True)
plt.show()
Чтобы понять математику, лежащую в основе PageRank, нам нужно ввести еще одно понятие - матрицу ссылок. Последняя представляет собой квадратную матрицу с размерами, равными количеству узлов, и описывает для каждого узла его внутренние и внешние связи. Мы можем читать матрицу в двух направлениях:
- По строкам мы можем прочитать, какие внутренние ссылки для каждого узла. А именно, первая строка показывает внутренние связи первого узла «А»;
- по столбцам мы можем прочитать, какие внешние ссылки для каждого узла. А именно, в первом столбце показаны внешние ссылки первого узла «A»;
В общем, если узел имеет k исходящих ребер, он будет передавать 1 / k своей важности каждому из узлов, с которыми он связан. Следовательно, если у нас есть такая ситуация, когда каждый узел передает всю свою важность своему преемнику и получает всю важность своего предшественника, как наш граф DG, у нас будет следующая матрица:
A=np.matrix([(0,0,0,1),(1,0,0,0),(0,1,0,0),(0,0,1,0)])
A
Output:
matrix([[0, 0, 0, 1],
[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0]])
Идея PageRank заключается в том, что с помощью итеративного процесса мы можем обновить вектор ранжирования (инициализированный равновзвешенными ссылками) матрицей A. А именно, новая вероятность наших веб-сайтов после одной итерации будет вектором v ' = A v. Результирующий вектор после k итераций равен
и он будет сходиться к вектору рангов анализируемой сети. А именно, давайте рассмотрим следующий пример:
DG_test = nx.DiGraph() DG_test.add_nodes_from([1,2,3,4]) DG_test.add_weighted_edges_from([(1,3,1), (1,4, 1),(1,2,1),(2,3,1),(2,4,1),(3,1,1),(4,1,1),(4,3,1)]) nx.draw(DG_test, with_labels=True) plt.show()
Матрица ссылок будет выглядеть так:
B=np.matrix([(0,0,1,0.5),(1/3,0,0,0),(1/3,0.5,0,0.5),(1/3,0.5,0,0)])
B
Output:
matrix([[0. , 0. , 1. , 0.5 ],
[0.33333333, 0. , 0. , 0. ],
[0.33333333, 0.5 , 0. , 0.5 ],
[0.33333333, 0.5 , 0. , 0. ]])
Теперь, если мы применим наш алгоритм PageRank (обратите внимание, что я установил alpha = 1, чтобы мы не рассматривали возможность прекращения нажатия на ссылку):
pr=nx.pagerank(DG_test,alpha=1)
pr
Output:
{1: 0.38709615908859496,
2: 0.12903204605249047,
3: 0.29032302109901886,
4: 0.193548773759895}
Мы получаем тот же результат следующей итерации (с k = 1000) для обновления нашего вектора рангов:
np.array((B**1000)*a.T) Output: array([[0.38709677], [0.12903226], [0.29032258], [0.19354839]])
В заключение давайте посмотрим, как наш алгоритм работает в более сложной сети, скажем, с 10 узлами:
G=nx.fast_gnp_random_graph(10,0.5,directed=True) nx.draw(G,with_labels=True) plt.show()
pr=nx.pagerank(G,alpha=0.85)
rank_vector=np.array([[*pr.values()]])
best_node=np.argmax(rank_vector)
print("The most popular website is {}".format(best_node))
Output:
The most popular website is 4
Сети - один из примеров алгоритмов графов, которые имеют решающее значение в науке о данных. Действительно, в мире, где все объекты связаны друг с другом, мы не можем полагаться только на простые реляционные наборы данных: нам нужны более сложные системы, которые способны хранить данные, сохраняя существующие связи между ними.
