0x00 Предисловие

Незаменимая вещь от Google! Как рядовой программист, выросший под деревом Google, я по-прежнему высоко ценю различные технологии Google. Тщательно обдумав это, я прочитал много статей Google: Goods, Spanner, F1, GFS, MapReduce, BigTable и Dremel. Впрочем, знаменитый алгоритм Google PageRank не придал этому особого значения, недавно я поиграл с ним по работе и по делам и организовал на память одно-два коротких эссе.

Я всегда считал, что программисты не должны бояться никаких алгоритмов, потому что основная идея и основная структура большинства алгоритмов не так уж неясны. Мы можем сначала разработать и реализовать базовый алгоритм, а затем улучшить его, когда он понадобится для использования в производственной среде.

содержание

Эта статья условно разделена на следующие три части:

1. Фон, созданный PageRank
2. Как работает PageRank
3. Реализуйте простой алгоритм PageRank с помощью Python

Предыстория кратко описана. Эта часть заимствует содержание PPT из внутреннего обмена Марка; принцип будет содержать только основные принципы и не будет слишком подробным (самые основные идеи и конструкции могут быть объяснены, когда другие спросят); окончательный алгоритм Для реализации потребуется только более 20 строк кода, и будет реализован только самый простой алгоритм.

0x01 фон

Говоря об алгоритме PageRank, мы должны в первую очередь говорить о поисковых системах. Это относительно большая тема. Обыватель никогда не занимался поисковой системой и имеет ограниченные возможности. не умею правильно писать.. С трепетом напишу немного разведки ниже.

Мы рассмотрим три проблемы, которые поисковые системы должны решить с технической точки зрения:

1. Создать базу данных
2. Создайте структуру данных, которая может находить ссылки (документы) по ключевому слову.
3. Отсортируйте найденные документы.

1. Создайте базу данных

Чтобы создать базу данных, мы пока будем рассматривать ее как проблему краулера и получать информацию всего Интернета через краулер. (Мне всегда было интересно узнать о технологии поисковых роботов Google и Baidu.)

2. Указатель

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

Реализуется следующими способами: инвертированный индекс, файл сигнатур, суффиксное дерево и др. Мы наиболее знакомы сПеревернутый индекс.

Для этой части содержания вы можете прочитать "Введение в поиск информации". Мне очень стыдно. Я изучил все содержание этой книги, но я не могу написать что-то, когда хочу выразить свой запас знаний.. .

3. Сортировать

Рейтинг является решающим фактором в росте поисковой системы Google.

Существует много способов сортировки веб-страниц, давайте рассмотрим три:

1. не оценивать
2. Взвешивание позиции по частоте слов
3. Алгоритм PageRank

не оценивать

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

Взвешивание позиции по частоте слов

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

Недостатки тоже очевидны.Точки легко стираются.Большое количество ключевых слов во всей статье может улучшить ранжирование.

Алгоритм PageRank

Именно основатели Google Ларри Пейдж и Сергей Брин действительно нашли идеальную математическую модель для расчета качества самой веб-страницы. В следующем разделе объясняется принцип.

0x02 PageRank Принцип

Сначала проясните основную идею PageRank, а затем посмотрите на принципы его построения.

1. Мысль

Мы имитируем неторопливого серфера, серфер сначала случайным образом выбирает веб-страницу для открытия, затем остается на этой веб-странице в течение нескольких минут, а затем переходит по ссылке, на которую указывает веб-страница, так что он переходит на веб-страницу, ничего не делая и бесцельно. Jump, PageRank предназначен для оценки вероятности того, что этот неторопливый посетитель распространяется на различных веб-страницах. Эта вероятность представляет важность этой веб-страницы. Две характеристики:

1. Если на веб-страницу ссылаются многие другие веб-страницы, это означает, что эта веб-страница более важна, то есть значение PageRank будет относительно высоким.

2. Если страница с высоким PageRank ссылается на другую страницу, PageRank связанной страницы соответственно увеличится.

2. Принцип

Обратите внимание, что приведенное ниже умножение матриц является основным принципом алгоритма PageRank, и обычно его понимают после небольшого внимательного прочтения.

Абстракция модели

Узел в графе абстракции веб-страницы, связь между веб-страницами представляет собой направленное ребро, а вся сеть абстрагируется в ориентированный граф. Как показано ниже.

В этом примере есть только четыре веб-страницы. Если вы в данный момент находитесь на веб-странице А, неторопливые пользователи с вероятностью 1/3 перейдут на B, C и D. Здесь 3 означает, что у A есть 3 исходящие ссылки. Если на веб-странице имеется k исходящих ссылок, вероятность перехода по любой исходящей ссылке равна 1/k. Точно так же вероятность D на B и C равна 1/2, а вероятность B на C равна 0.

Когда мы делаем расчет, мы будем представлять график как двумерную матрицу, Если мы сделаем преобразование, он станет матричной формой следующего рисунка.M(i,j)Указывает вероятность того, что узел j указывает на узел i, вообще говоря, сумма каждого столбца равна 1.

Итеративный расчет

Так как же рассчитывается PageRank?

В первом раунде расчета алгоритма мы предполагаем, что вероятность пользователей на каждой веб-странице равна, то есть 1/n, поэтому распределение вероятностей исходного теста представляет собой n-мерный вектор-столбец V0 со всеми значениями 1/n, Умножьте матрицу перехода M на V0 вправо, а затем получите вектор распределения вероятностей MV0 пользователей Интернета после первого шага (nXn)(nX1) по-прежнему получает матрицу V1 из nX1,*Эта V1 представляет собой значение PageRank, рассчитанное за один раунд итераций.. Ниже приведен процесс расчета V1:

Заметим, что в матрице MM[i][j]Если он не равен 0, это означает, что ссылка указывает с j на i, а первая строка M умножается на V0, что означает, что вероятность накопления всех веб-страниц на веб-странице A составляет 9/24. Получив V1, используйте V1, чтобы умножить M вправо, чтобы получить V2, и продолжайте, и, наконец, V сойдется, то естьVn=MV(n-1), приведенный выше пример рисунка, итеративно, в конечном итогеV=[3/9,2/9,2/9,2/9]:

3. Тупиковые вопросы

Когда паутина не сильно связана, то есть есть определенный тип узла, который не указывает на другие, как показано в D на рисунке ниже. На этот раз у нашего алгоритма будет проблема, он не удовлетворяет сходимости.

Ну почему бы не встретить схождение?

Описанное выше поведение серферов является примером реального марковского процесса, для сходимости необходимо выполнение условия: граф сильно связан, то есть на любую веб-страницу можно попасть с любой другой веб-страницы. Как только появляется узел D на приведенном выше рисунке, сходимость не выполняется. (Я до сих пор понимаю это сначала так. Если вам интересно, вы можете взглянуть на марковский процесс. На самом деле, я не присматривался, хе-хе.)

это должнокак решитьШерстяная ткань?

Помимо постоянного нажатия на ссылки на веб-странице для перехода, неторопливые пользователи также имеют определенную вероятность ввести адрес для доступа (не разумнее ли это?).

Таким образом, итерационная формула преобразуется в следующий рисунок:

Если перемножить соответствующую матрицу, получится следующая фигура, чтобы не было проблемы изолированных точек.Среди них a обычно занимает 0,8.

0x03 Реализация

Первоначально это было написано для развлечения и использовало двадцать или тридцать строк кода, чтобы ознакомиться с базовой реализацией алгоритма. Настоящая онлайн-программа по-прежнему пишется с помощью MR. Следующая статья будет посвящена реализации алгоритма PageRank, написанного MR, а также глубокой инженерной оптимизации.

0xFF Сводка

Статья написана с трепетом, PageRank — очень зрелый алгоритм, и я просто прихожу в восторг. Я имею в виду много контента, и многие изображения используются напрямую. Тем не менее, целое по-прежнему организовано в соответствии с их собственным пониманием.

Добро пожаловать в мой публичный аккаунт WeChat! Придерживайтесь оригинального обмена технологиями, ваша поддержка побудит меня продолжать творить! награда

WeChat Pay

• Автор этой статьи:Мастер Мудонг
• Ссылка на эту статью: Город Муданьцзян.info/2017/09/09/…
• Уведомление об авторских правах:Все статьи в этом блоге, если не указано иное, используютCC BY-NC-SA 3.0соглашение. Пожалуйста, укажите источник!